Bob*_*Gee 40 java optimization performance jvm-hotspot bounds-check-elimination
我正在优化LZF压缩算法的纯java实现,它涉及大量的byte []访问和基本的int数学,用于散列和比较.性能确实很重要,因为压缩的目标是降低I/O要求.我没有发布代码,因为它尚未清理,并且可能会进行大量重组.
在我因为过早优化而受到攻击之前:基本算法已经非常出色,但Java实现的速度不到等效C的2/3.我已经用System.arraycopy替换了复制循环,致力于优化循环并消除了un - 需要的操作.
我大量使用bit twiddling并将字节打包为整数,以实现性能,以及移位和屏蔽.
出于法律原因,我无法查看类似库中的实现,并且现有库具有过于严格的许可条款.
另外:如果有人有详细说明Hotspot优化和分支性能的内容的链接,那么欢迎这些.我对字节码有足够的了解,网站分析字节码而不是源代码级别的性能会有所帮助.
这是从提供的HotSpot内部维基链接获取的: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循环来实现文字和反向引用模式之间的不同逻辑.它减少了阵列访问和模式之间的检查.
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;
}
到目前为止,我已经标记了最佳答案,因为截止日期已接近尾声.由于我在决定发布代码之前花了这么长时间,因此我将继续提升并尽可能回复评论. 如果代码混乱,请道歉:这代表了开发中的代码,而不是用于提交.
Shu*_*oUk 18
不是一个完整的答案,我根本没有时间做你的问题需要的详细基准测试,但希望有用.
您的目标是JVM(实质上是JIT)和底层CPU /内存子系统的组合.因此,"在JVM X上运行速度更快"在所有情况下都不太可能有效,因为您会进行更积极的优化.
如果您的目标市场/应用程序将主要在特定架构上运行,您应该考虑投资特定于它的工具.*如果你在x86上的表现是关键因素,那么英特尔的VTune非常适合深入研究你描述的那种jit输出分析.*64位和32位JIT之间的差异可能相当大,尤其是在x86平台上,其中调用约定可以更改并且注册机会非常不同.
您可能希望获得一个采样分析器.根据您的特定需求,仪器的开销(以及与内联,缓存污染和代码大小膨胀相关的相关因素)将会非常大.英特尔VTune分析器实际上可以用于Java,尽管集成并不像其他人那么紧密.
如果您正在使用sun JVM并且很高兴只知道最新/最好的版本正在做什么,那么如果您知道一些程序集,那么可用于调查JIT输出的选项是相当可观的.该文章描述了使用此功能的一些有趣的分析
更改历史记录更改历史记录表明,先前的内联汇编实际上是反效果的,并且允许编译器完全控制输出(在代码中调整而不是在汇编中指令)产生更好的结果.
由于LZF在现代桌面CPUS上的高效非托管实现中,主要是内存带宽有限(因此它被编程为未经优化的memcpy的速度),因此您需要将代码完全保留在1级缓存中.
因此,您不能将任何静态字段放入同一个类中,因为这些值通常会放在专用于与类关联的vtable和元数据的内存区域中.
需要避免Escape Analysis无法捕获的对象分配(仅在1.6以后).
在C代码,使积极利用循环展开的.然而,在较旧的(1.4时代)VM上的性能很大程度上取决于JVM所处的模式.显然,后来的sun jvm版本在内联和展开方面更具攻击性,尤其是在服务器模式下.
由JIT生成的预取指令可以在像这样接近内存绑定的代码上产生所有差异.
你的目标正在移动,并将继续.Marc Lehmann先前的经历:
默认的HLOG大小现在是15(cpu缓存增加了)
即使是对jvm的微小更新也可能涉及重大的编译器更改
6544668不执行无法在运行时对齐的数组操作.6536652实现一些超级字(SIMD)优化6531696不要立即将16位值存储到Intel cpus上的内存中6468290基于每个cpu划分和分配eden
测量,测量,测量.如果您可以让您的库包含(在一个单独的DLL中)一个简单易于执行的基准测试,记录相关信息(虚拟机版本,CPU,操作系统,命令行开关等),并使这个简单的发回给你,你将增加你的覆盖面,最重要的是你会覆盖那些使用它的人.
就边界检查消除而言,我相信新的JDK已经包含一个改进的算法,只要有可能就消除它.这是关于这个主题的两篇主要论文:
还有这篇博客文章,它在表面上讨论了其中一篇论文,并且还提供了一些基准测试结果,不仅用于数组,还用于新JDK中的算术.博客条目的评论也非常有趣,因为上述论文的作者提出了一些非常有趣的评论和讨论论点.此外,还有一些关于此主题的其他类似博客文章的指示.
希望能帮助到你.