我如何编码的Java允许使用SSE和边界检查消除(或其他高级优化)?

情况:

我正在优化LZF压缩algorithm的纯Java实现,它涉及到大量的byte []访问和基本的intmath,用于哈希和比较。 性能真的很重要,因为压缩的目标是减lessI / O需求。 我不张贴代码,因为它尚未清理,并可能会重组。

问题:

  • 我怎样才能编写我的代码,以允许它使用更快的SSE操作JIT编译为表单?
  • 我怎样才能构造它,使编译器可以轻松消除数组边界检查?
  • 是否有关于特定math运算相对速度的广泛参考(需要多less增量/减量才能达到正常的加/减,移位速度有多快?还是与数组访问有多快?
  • 我怎样才能优化分支 – 有更多的条件陈述短身体,或一些长期的,或短嵌套条件?
  • 使用当前的1.6 JVM,在System.arraycopy击败复制循环之前必须复制多less个元素?

我已经做了什么:

在我受到过早优化攻击之前:基本algorithm已经非常优秀,但是Java的实现速度还不到C的速度的2/3。我已经用System.arraycopyreplace了复制循环,并且优化了循环,并且删除了un需要的操作。

我大量地使用bit来转换和填充字节来performance性能,以及转换和屏蔽。

出于法律方面的原因,我不能看类似库中的实现,而现有的库有太多限制的许可条款可供使用。

良好(接受)答案的要求:

  • 不可接受的答案: “这是更快”没有解释多less和为什么,OR还没有用JIT编译器testing过。
  • 边界线答案:在Hotspot 1.4之前没有经过任何testing
  • 基本的答案:将提供一个通用的规则和解释,为什么它在编译器级别更快,并且大概快了多less
  • 很好的答案:包括几个代码示例来演示
  • 优秀的答案:有JRE 1.5和1.6的基准
  • 完美的答案:是由HotSpot编译器工作的人员,可以完全解释或引用要使用的优化的条件,以及它通常的速度。 可能包括由HotSpot生成的Java代码和样例汇编代码。

另外:如果有人有详细的热点优化和分支性能的内涵的链接,欢迎。 我对字节码有足够的了解,即一个分析字节码而不是源代码级别的性能的站点会有所帮助。

(编辑)部分答案:Bounds-Check Ellimination:

这是从提供的链接到HotSpot内部维基: https : //wikis.oracle.com/display/HotSpotInternals/RangeCheckElimination

在以下情况下,HotSpot将消除所有for循环中的边界检查:

  • 数组是循环不变的(不在循环内重新分配)
  • 索引variables有一个不断的步幅(按照常量增加/减less,如果可能的话,只有一个点)
  • 数组由variables的线性函数索引。

例如: int val = array[index*2 + 5]

OR: int val = array[index+9

NOT: int val = array[Math.min(var,index)+7]


代码的早期版本:

这是一个示例版本。 不要偷,因为它是H2数据库项目的未发布版本。 最终版本将是开源的。 这里是代码优化: H2 CompressLZF代码

从逻辑上讲,这与开发版本相同,但是使用for(…)循环来逐步执行input,并且在文字和反向引用模式之间使用不同逻辑的if / else循环。 它减less了数组访问和模式之间的检查。

 public int compressNewer(final byte[] in, final int inLen, final byte[] out, int outPos){ int inPos = 0; // initialize the hash table if (cachedHashTable == null) { cachedHashTable = new int[HASH_SIZE]; } else { System.arraycopy(EMPTY, 0, cachedHashTable, 0, HASH_SIZE); } int[] hashTab = cachedHashTable; // number of literals in current run int literals = 0; int future = first(in, inPos); final int endPos = inLen-4; // Loop through data until all of it has been compressed while (inPos < endPos) { future = (future << 8) | in[inPos+2] & 255; // hash = next(hash,in,inPos); int off = hash(future); // ref = possible index of matching group in data int ref = hashTab[off]; hashTab[off] = inPos; off = inPos - ref - 1; //dropped for speed // has match if bytes at ref match bytes in future, etc // note: using ref++ rather than ref+1, ref+2, etc is about 15% faster boolean hasMatch = (ref > 0 && off <= MAX_OFF && (in[ref++] == (byte) (future >> 16) && in[ref++] == (byte)(future >> 8) && in[ref] == (byte)future)); ref -=2; // ...EVEN when I have to recover it // write out literals, if max literals reached, OR has a match if ((hasMatch && literals != 0) || (literals == MAX_LITERAL)) { out[outPos++] = (byte) (literals - 1); System.arraycopy(in, inPos - literals, out, outPos, literals); outPos += literals; literals = 0; } //literal copying split because this improved performance by 5% if (hasMatch) { // grow match as much as possible int maxLen = inLen - inPos - 2; maxLen = maxLen > MAX_REF ? MAX_REF : maxLen; int len = 3; // grow match length as possible... while (len < maxLen && in[ref + len] == in[inPos + len]) { len++; } len -= 2; // short matches write length to first byte, longer write to 2nd too if (len < 7) { out[outPos++] = (byte) ((off >> 8) + (len << 5)); } else { out[outPos++] = (byte) ((off >> 8) + (7 << 5)); out[outPos++] = (byte) (len - 7); } out[outPos++] = (byte) off; inPos += len; //OPTIMIZATION: don't store hashtable entry for last byte of match and next byte // rebuild neighborhood for hashing, but don't store location for this 3-byte group // improves compress performance by ~10% or more, sacrificing ~2% compression... future = ((in[inPos+1] & 255) << 16) | ((in[inPos + 2] & 255) << 8) | (in[inPos + 3] & 255); inPos += 2; } else { //grow literals literals++; inPos++; } } // write out remaining literals literals += inLen-inPos; inPos = inLen-literals; if(literals >= MAX_LITERAL){ out[outPos++] = (byte)(MAX_LITERAL-1); System.arraycopy(in, inPos, out, outPos, MAX_LITERAL); outPos += MAX_LITERAL; inPos += MAX_LITERAL; literals -= MAX_LITERAL; } if (literals != 0) { out[outPos++] = (byte) (literals - 1); System.arraycopy(in, inPos, out, outPos, literals); outPos += literals; } return outPos; } 

最终编辑:

截至目前,我已经标出了最好的答案,因为截止date已经接近尾声。 由于我花了很长时间才决定发布代码,所以我会继续在可能的情况下积极回应评论。 道歉,如果代码是凌乱的:这代表在开发中的代码,没有打磨提交。

没有一个完整的答案,我根本没有时间来做你的问题所需的详细基准,但希望有用。

了解你的敌人

您的目标是JVM(本质上是JIT)和底层CPU /内存子系统的组合。 因此,当您进入更积极的优化时,“JVM X上的速度更快”在所有情况下都不可能有效。

如果您的目标市场/应用程序将主要运行在特定架构上,则应考虑投资特定的工具。 *如果你在x86平台上的performance是关键因素,那么intel的VTune非常适合你深入描述的那种jit输出分析 。 * 64位和32位JIT之间的差异可能是相当大的,特别是在x86平台上,调用约定可以改变,并且注销机会是非常不同的。

获得正确的工具

你可能会想要一个采样分析器。 仪器的开销(以及与内联,caching污染和代码大小膨胀等相关联的事情)会对您的具体需求产生太大的影响。 intel VTune分析器实际上可以用于Java,尽pipe集成并不像其他的那样严格。
如果你正在使用Sun的JVM,并且很高兴只知道最新版本或者最好的版本正在做什么,那么如果你知道一些汇编,那么可以用来调查JIT输出的选项是相当可观的。 本文详细介绍了一些使用此function的有趣分析

从其他实现中学习

更改历史logging更改历史logging表明,以前的内联汇编实际上是反生产的,允许编译器对输出进行全面控制(在代码中进行调整而不是在汇编中的指令)可以产生更好的结果。

一些细节

由于LZF在现代桌面CPUS上的一个高效的非托pipe实现中,大部分的内存带宽受到限制(因此它被认为是未优化的memcpy的速度),因此您将需要代码才能完全保留在1级caching中。
由于这样的任何静态字段,你不能把常量放在同一个类中,因为这些值通常放在专用于vtable和相关类的元数据的相同区域内。

对象分配不能被Escape Analysis(仅在1.6以上)所困住。

C代码大量使用循环展开。 然而,在较旧的(1.4时代)VM上的这种性能在很大程度上取决于JVM所处的模式 。 显然,后来的sun jvm版本在内联和展开时更加积极,特别是在服务器模式下。

由JIT生成的预取instrctions可以使像这样的代码在内存边界附近的所有差异。

“这是直接为我们”

你的目标正在移动,并将继续。 Marc Lehmann先前的经历:

默认的HLOG大小现在是15(cpucaching已经增加)

即使对jvm进行较小的更新也会涉及到重大的编译器更改

6544668不要在运行时无法alignment的数组操作。 6536652实现一些超级字(SIMD)优化6531696不使用立即的16位值存储到英特尔CPU 6468290上的内存划分和分配出eden基于每个CPU

上尉明显

测量,测量,测量。 如果你可以让你的库包括(在一个单独的DLL)一个简单和易于执行的基准,logging相关信息(VM版本,CPU,操作系统,命令行开关等),使这个简单的发送给你,你会增加你的覆盖面,最重要的是你会覆盖那些使用它的人。

边界检查消除而言,我相信新的JDK已经包含了一个改进的algorithm,在任何可能的时候消除它。 这是关于这个问题的两个主要论文:

  • V. Mikheev,S. Fedoseev,V. Sukharev,N. Lipsky。 2002年在Java中有效增强循环版本 。 链接 。 本文来自Excelsior的人,他们在Jet JVM中实现了这项技术。
  • 维林杰,托马斯,克里斯蒂安·温默和汉斯彼得·莫森伯克。 Java HotSpot客户端编译器的数组边界检查消除 。 PPPJ。 链接 。 稍微基于上面的文章,这是我相信将包含在下一个JDK中的实现 。 也提出了实现的加速

还有这个博客文章,它从表面上讨论了其中的一篇文章,并且还提供了一些基准testing结果,不仅是针对数组,而且还针对新的JDK中的算术。 博客文章的评论也非常有趣,因为上述文章的作者提出了一些非常有趣的评论和讨论论点。 此外,还有一些关于这个主题的其他类似博客文章的指针。

希望能帮助到你。

您不太需要通过优化简单的数字运算algorithm(如LZW)来帮助JIT编译器。 ShuggyCoUk提到了这一点,但我认为它值得额外的关注:

你的代码的caching友好将是一个很大的因素。

你必须尽可能减less你的woking集的大小,并提高数据访问的本地化。 您提到“将字节打包成性能”。 这听起来像使用整数来保存字节值,以使它们字alignment。 不要这样做! 增加的数据集大小将超过任何收益(我曾经将一些ECC数字处理代码从int []转换为byte [],并获得了2倍加速)。

如果你不知道这一点:如果你需要把一些数据作为字节和整数来处理,你不需要移动和屏蔽它 – 使用ByteBuffer.asIntBuffer()和相关的方法。

使用当前的1.6 JVM,在System.arraycopy击败复制循环之前必须复制多less个元素?

更好地自己做基准。 当我回到Java的时候1.3倍,这是在2000左右的元素。

到目前为止有很多答案,但还有一些额外的东西:

  • 衡量,衡量,衡量。 与大多数Java开发人员一样,要警告微型基准testing,请确保比较更改之间的性能。 不会导致可衡量的改进的优化通常是不值得保留的(当然,有时它是事物的组合,并且变得更复杂)
  • 对于Java而言,紧密循环与C一样重要(同样也要考虑variables分配 – 尽pipe不直接控制它,HotSpot最终还是要这样做)。 我把UTF-8解码的速度提高了一倍,通过重新安排紧密的循环来处理单字节的情况(7位ASCII)作为紧密(er)的内部循环,而将其他情况排除在外。
  • 不要低估分配和/或清除大型数组的成本 – 如果你希望lzf编码/解码对于中小型数据块来说也更快(不仅仅是兆字节大小),请记住所有的byte [] / int [ ]有点昂贵; 不是因为GC,而是因为JVM必须清除空间。

H2的实现也被优化了很多(例如:它不再清除哈希数组,这通常是有道理的); 我实际上帮助修改它在另一个Java项目中使用。 我的贡献大部分只是改变它对于非stream式传输而言更为优化,但是这并没有触及紧密的编码/解码循环。