在 Java 中检查 int l,r 的条件 l+1<r 的最快方法

当前位置：文江博客话题详情

performance integer Java

在 Java 中检查 int l,r 的条件 l+1

发布于 2024-07-24 22:34:53 字数 284 浏览 1 评论 0 原文

条件的最快方法是什么

l + 1 < r

在 Java 中检查 int l,r

？ l 和 r 不是常数，我知道 l <= r。比较是二分搜索实现中 while 循环的停止条件。当然，我在单独的测试（搜索大数组）和使用它的代码中对我的代码进行基准测试。

我想，我正在寻找的是某种比目前情况更快的位操作。但我不知道。

原文

What is the fastest way of checking the condition

l + 1 < r

for int l,r in Java?

l and r are not constant and I know that l <= r. The comparison is a stopping condition for a while loop in a binary search implementation. I am of course benchmarking my code, both in a separate test (searching a large array) and in the code which uses it.

What I am looking for, I imagine, is some sort of a bit operation which would be faster than the present condition. But I don't know.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

快乐很简单 2024-07-31 22:34:53

这种微观优化几乎总是一个坏主意。这么小的一点的性能将完全取决于热点编译器如何优化您的代码，以及与周围代码有关的微妙缓存效果。

回复收藏 0 原文

虫児飞 2024-07-31 22:34:53

我认为这可能是最快的。这将简化为非常简单的字节码，而 JIT（即时编译器）可能会将其简化为非常简单的本机实现。

（无关：顺便说一句，看到“定量开发”使用 Java 很有趣。这种情况并不经常发生）

回复收藏 0 原文

≈。彩虹 2024-07-31 22:34:53

那么底层比较必须是：

将 l 加 1，将结果与 r 进行比较

，或者

从 r 中减去 1，并将结果与 l 进行比较

所有现代硬件对于任一操作都将具有相同的原始性能（其中任何本机数据类型的加法和减法）在完成周期和管道副作用方面具有相同的性能）。

唯一产生效果的方法是：

l 或 r 之一在编译时是已知常量。例如。

l + 1 < 5
5 + 1 < r

在这种情况下，一个糟糕的优化编译器可能没有意识到它可以将第一个转换为 l <; 4

但所有 java 编译器都需要发现第二种情况是6 < r

另一种情况是l和r的数据类型不同。

操作：

浮点加/减然后与 int 比较
与
整数加法/减法相比，与双精度数的比较可能会有所不同。

可以公平地说，这在您的应用程序中成为严重问题的可能性可以忽略不计，因为与与决策相关的任何分支错误预测的管道命中相比，其中任何一个的周期成本都很小。

此外，一个像样的 JIT 可以对周围的代码进行各种优化，这些优化比执行的微优化更重要。

Well the underlying comparison must either:

add 1 to l, compare the result to r

subtract 1 from r and compare the result to l

All modern hardware will have the same raw performance for either operation (where addition and subtraction of any native data type has identical performance in terms of cycles to complete and pipeline side effects).

The only way this will have any effect is if:

one of l or r are known constants at compile time. eg.

l + 1 < 5
5 + 1 < r

in this case a poor optimizing compiler may not realise it can convert the first into l < 4

but all java compilers are required to spot that the second case is 6 < r

The other is if the data types of l and r are different.

The operation of :

floating point addition/subtraction then comparison to an int
verses
integral addition/subtraction then comparison with a double may be different.

It is fair to say that the chances of this being a serious issue in your application are negligible since the cycle cost of any of these is tiny compared to the pipeline hit of any branch mispredictions associated with the decision.

Also a decent JIT may do all sorts of optimizations in relation to the surrounding code that outweigh the micro optimization performed.

回复收藏 0 原文

婴鹅 2024-07-31 22:34:53

有一个变量lr1，它始终等于(l - r + 1)。每当您递增或递减 l 时，请对 lr1 执行相同的操作。对于r 也是如此。

然后，您的测试将变为 (lr1 < 0)，并且修改 lr1 的指令的执行次数不会超过必要的次数。

我觉得给你一个微观优化有点愚蠢，在大多数情况下这是小聪明，大笨蛋。就像如果您正在比较字符串一样，它将完全淹没该测试。

添加：既然你正在进行二分搜索，我会提到乔恩·本特利（Jon Bentley）对二分搜索的精彩展开。首先，将表 A 填充到 2 的幂，例如 1024。然后编写如下内容：

i = 0;
if (X >= A[i+512]) i += 512;
if (X >= A[i+256]) i += 256;
   . . .
if (X >= A[i+  1]) i +=   1;

最后测试 if (X == A[i]) 。或者，如果您不想填充它，请让 if 语句类似于
if (i+512 < N && X >= A[ i+512]) i += 512;

Have a variable lr1 which always equals (l - r + 1). Whenever you increment or decrement l, do the same to lr1. Similarly for r.

Then your test becomes (lr1 < 0), and the instructions to modify lr1 are executed no more often than necessary.

I feel a little silly giving you a micro-optimization, which in most cases is penny-wise, pound-foolish. Like if you're comparing strings, it will totally swamp that test.

ADDED: Since you're doing binary search, I would mention Jon Bentley's cool unrolling of binary search. First you pad the table A up to a power of 2, like 1024. Then you write something like this:

i = 0;
if (X >= A[i+512]) i += 512;
if (X >= A[i+256]) i += 256;
   . . .
if (X >= A[i+  1]) i +=   1;

and finally test if (X == A[i]). Or, if you don't want to pad it, let the if statements be something like
if (i+512 < N && X >= A[i+512]) i += 512;