消除边界检查的 foreach/for 循环的特殊情况是什么？还有哪个边界检查？

情况：

我正在优化 LZF 压缩算法的纯 java 实现，它涉及大量 byte[] 访问和基本的 int 数学，用于散列和比较。性能确实很重要，因为压缩的目标是减少 I/O 需求。我没有发布代码，因为它还没有被清理，并且可能会被大量重组。

问题：

• 如何编写代码以使用更快的 SSE 操作将其 JIT 编译为表单？
• 如何构造它以便编译器可以轻松消除数组边界检查？
• 是否有关于特定数学运算的相对速度的广泛参考（等于正常加/减需要多少增量/减量，移位或与数组访问相比有多快）？
• 我该如何优化分支——拥有大量带有短主体的条件语句，或者一些长的，还是带有嵌套条件的短的条件语句更好？
• 使用当前的 1.6 JVM，在 System.arraycopy 击败复制循环之前必须复制多少元素？

我已经做了什么：

在我因过早优化而受到攻击之前：基本算法已经很出色了，但 Java 实现的速度不到等效 C 的 2/3。我已经用 System.arraycopy 替换了复制循环，致力于优化循环并消除了 un - 需要的操作。

我大量使用位旋转并将字节打包到整数中以提高性能，以及移位和屏蔽。

出于法律原因，我无法查看类似库中的实现，并且现有库的使用许可条款过于严格。

良好（已接受）答案的要求：

• 不可接受的答案： “这更快”没有解释多少和为什么，或者没有用 JIT 编译器测试。
• 边界答案：在 Hotspot 1.4 之前没有经过任何测试
• 基本答案：将提供一般规则和解释，说明为什么它在编译器级别更快，以及大概快多少
• 好的答案：包括几个代码示例来演示
• 很好的答案：有 JRE 1.5 和 1.6 的基准
• 完美答案：由从事 HotSpot 编译器工作的人提供，并且可以完全解释或参考要使用的优化的条件，以及它通常的速度有多快。可能包括由 HotSpot 生成的 java 代码和示例汇编代码。

另外：如果有人有详细说明热点优化和分支性能的链接，欢迎提供。我对字节码有足够的了解，因此在字节码而不是源代码级别分析性能的网站会有所帮助。

（编辑）部分答案：边界检查消除：

这取自提供的 HotSpot 内部 wiki 链接：https ://wikis.oracle.com/display/HotSpotInternals/RangeCheckElimination

HotSpot 将在以下条件下消除所有 for 循环中的边界检查：

• 数组是循环不变的（不在循环内重新分配）
• 索引变量有一个恒定的步幅（以恒定的量增加/减少，如果可能的话，只在一个点上）
• 数组由变量的线性函数索引。

例子： int val = array[index*2 + 5]

或者： int val = array[index+9]

不是： int val = array[Math.min(var,index)+7]

早期版本的代码：

这是一个示例版本。不要盗用它，因为它是 H2 数据库项目的未发布版本代码。最终版本将是开源的。这是对此处代码的优化：H2 CompressLZF 代码

从逻辑上讲，这与开发版本相同，但它使用 for(...) 循环来单步执行输入，并使用 if/else 循环来处理文字和反向引用模式之间的不同逻辑。它减少了阵列访问和模式之间的检查。

最终编辑：

到目前为止，我已将最佳答案标记为已接受，因为截止日期快到了。由于我在决定发布代码之前花了很长时间，因此我将继续投票并在可能的情况下回复评论。 如果代码混乱，请道歉：这代表开发中的代码，没有为提交而完善。

“Hotspot 可以删除 Java 中的边界检查。” 任何人都可以解释一下吗？实际上我正在分析 C++ 和 Java 之间的差异。这不是家庭作业，我根据自己的兴趣进行分析。

我读过一些 JVM 可以通过删除边界检查来优化代码执行。我想弄清楚的是哪种编码技术会更好。

在下面的方法example1中，JVM 是否会弄清楚并消除对source[index]引用的边界检查？

example2是更好的代码实践吗？看起来是这样，但在循环内的某些算法中，索引超出范围是正常情况。因此，您不想在该循环内生成大量 Exception 对象。

这些代码片段仅具有代表性。我知道在这些示例中，边界检查对性能几乎没有影响。但是，我正在开发一个嵌入式协议应用程序，其中冗余边界检查将加起来。

我最近阅读了 Dave Detlefs 的这篇文章，他在其中介绍了 CLR 执行数组边界检查消除的几个案例。我决定自己测试一下，所以我做了以下事情：

• 打开 Visual Studio 2010 Ultimate SP1
• 创建了一个控制台应用程序类型的新 C# 项目（默认针对 .NET 4 客户端配置文件）

• 添加以下代码（所有子方法均直接取自文章）：

  /li>

• 切换到释放模式；验证在构建选项中选中了“优化代码”

• 为每个数组访问添加断点，开始调试（F5）并打开反汇编窗口

所以这里是 a[i] = i; 的反汇编。在 Test_SimpleAscend 中：

cmp/jb/call 是边界检查，实际上强制执行调用会引发 IndexOutOfRangeException。

所有数组访问都一样，包括 Test_SimpleRedundant 中的冗余访问。那么我的测试方法是否有问题，或者 CLR 实际上并没有消除边界检查？我希望我错了，如果是这样，我想知道如何才能真正获得数组边界检查消除。

我正在制作很多数组，其索引类型为Bounded，其索引范围为(minBound, maxBound). 对于这样的数组，边界检查应该是不必要的。如何说服 GHC 取消边界检查？

我的特定应用程序同时使用装箱和未装箱的不可变数组，但我对所有类型的 Haskell 数组都感兴趣。

sw.ElapsedMilliseconds：~2930ms

sw.ElapsedMilliseconds: ~3520ms

Win8x64, VS12, .NET4.5, Release build, "Optimize code" on.

据我所知，由于数组边界检查优化，第二种方法应该更快。我错过了什么吗？

我有简单的 for 循环和使用 ILGenerator 编写的数组访问。当使用这个确切的代码创建方法时，我打开反汇编，没关系，没有数组边界检查。

但是当我首先将其他类的实例放在评估堆栈上，然后运行 ​​for 循环时，它会检查数组边界。我正在发布。

知道为什么吗？我已经阅读了有关数组绑定检查的博客文章：http: //blogs.msdn.com/b/clrcodegeneration/archive/2009/08/13/array-bounds-check-elimination-in-the-clr.aspx

当我生成 IL 代码时，最好将类的实例保存在评估堆栈或局部变量中？

例如，我得到实例，遍历字段，为每个字段做任何事情然后返回。在读取下一个字段之前，我刚刚将实例保存在堆栈上并调用了 Emit(OpCodes.Dup)。但这似乎是错误的（至少对于上述情况）。

任何关于生成（高效/格式良好）IL 代码的文章/博客文章都值得赞赏。

我对.net 中低级算法的效率感兴趣。我希望让我们能够选择在未来使用 C# 而不是 C++ 编写更多代码，但一个绊脚石是在循环和随机访问数组时发生的 .net 中的边界检查。

一个有启发性的例子是一个函数，它计算两个数组中对应元素的乘积之和（这是两个向量的点积）。

据我所知，并且不知道足够的 IL 或 x86 来检查，编译器不会优化X and Y的边界检查。我错了和/或有没有办法编写我的代码以允许编译器帮助我？

更多详细信息

有许多支持和反对使用特定语言的效率论据，尤其是最好专注于“大 O”算法成本而不是比例常数，更高级别的语言可以帮助您做到这一点。关于 .net 中的边界检查，我发现的最好的文章是MSDN上 CLR 中的 Array Bounds Check Elimination（也在关于启用优化重要性的堆栈溢出答案中引用）。

这可以追溯到 2009 年，所以我想知道从那时起情况是否发生了显着变化。此外，这篇文章揭示了一些真正的微妙之处，这些细节会引起我的注意，因此仅出于这个原因，我就欢迎一些专家的建议。

例如，在我上面的代码中，我最好写i< X.Length而不是i < length. 此外，我还天真地假设对于具有单个数组的算法，编写一个foreach循环会更好地向编译器声明您的意图，并给它优化边界检查的最佳机会。

根据SumForBAD下面的 MSDN 文章，我认为肯定会优化，但不会。而SumFor将被直接优化，并且SumForEach也会被优化，但不是微不足道的（如果数组被传递给函数 as ，可能根本不会被优化IEnumerable<int>）？

我根据 doug65536 的回答做了一些调查。在 C++ 中，我比较了进行边界检查的 SumProduct 的时间

针对执行两次边界检查的另一个版本

我发现第二个版本速度较慢，但​​只有 3.5% 左右（Visual Studio 2010，优化构建，默认选项）。但是我突然想到，在 C# 中，可能有三个边界检查。一个显式（在此问题开头i < length的函数中）和两个隐式（和）。所以我测试了第三个 C++ 函数，带有三个边界检查static void SumProduct(double[] X, double[] Y)X[i]Y[i]

这比第一个慢了 35%，值得关注。我在这个问题上做了更多调查，为什么在某些机器上添加额外的检查循环会产生很大的不同，而在其他机器上会产生很小的差异？. 有趣的是，边界检查的成本似乎在不同的机器上差异很大。

我编写了一个简单的基准测试，以确定在通过按位与计算数组时是否可以消除边界检查。这基本上是几乎所有哈希表所做的：它们计算

作为 的索引table，其中或h是hashCode派生值。结果表明边界检查没有被消除。

我的基准测试的想法非常简单：计算两个值i和j，保证两者都是有效的数组索引。

• i是循环计数器。当它被用作数组索引时，边界检查就被消除了。
• j计算为x & (table.length - 1)，其中x每次迭代都有一些值变化。当它被用作数组索引时，边界检查不会被消除。

相关部分如下：

另一个实验使用

反而。时间上的差异可能是 15%（在我尝试过的不同变体中非常一致）。我的问题：

• 除了约束检查消除之外，还有其他可能的原因吗？
• 是否有一些复杂的原因我看不出为什么没有约束检查消除j？

答案摘要

MarkoTopolnik 的回答表明这一切都更加复杂，并且不能保证消除边界检查是胜利，尤其是在他的计算机上，“正常”代码比“屏蔽”代码慢。我想这是因为它允许进行一些额外的优化，这在这种情况下实际上是有害的（鉴于当前 CPU 的复杂性，编译器甚至几乎无法确定）。

leventov 的回答清楚地表明，数组边界检查是在“屏蔽”中完成的，并且它的消除使代码与“正常”一样快。

Donal Fellows 指出了这样一个事实，即屏蔽不适用于零长度表，x & (0-1)如x. 所以编译器能做的最好的事情就是用零长度检查代替边界检查。但恕我直言，这仍然值得，因为零长度检查可以轻松移出循环。

建议的优化

由于a[x & (a.length - 1)]当且仅当 等价抛出a.length == 0，编译器可以执行以下操作：

• 对于每个数组访问，检查索引是否已通过按位与计算。
• 如果是这样，请检查是否有任何一个操作数被计算为长度减一。
• 如果是这样，请将边界检查替换为零长度检查。
• 让现有的优化来处理它。

这样的优化应该非常简单且便宜，因为它只查看SSA图中的父节点。与许多复杂的优化不同，它永远不会有害，因为它只是用稍微简单的检查代替了一项检查；所以没有问题，即使它不能移出循环。

我会将其发布到热点开发邮件列表。

消息

约翰·罗斯提交了一份RFE，并且已经有一个“快速而肮脏”的补丁。