情况:
我正在优化 LZF 压缩算法的纯 Java 实现,其中涉及大量的 byte[] 访问和基本的 int 数学运算用于哈希和比较。性能非常重要,因为压缩的目标是减少 I/O 要求。我没有发布代码,因为它还没有整理好,可能会被大幅重构。
问题:
- 如何编写代码以允许 JIT 编译成使用更快速的 SSE 操作的形式?
- 如何构建代码,以便编译器可以轻松消除数组边界检查?
- 有关特定数学运算的相对速度(多少次递增/递减等于正常加/减,移位或与数组访问相比有多快)是否有任何广泛的参考资料?
- 如何在优化分支方面工作——有许多具有短体的条件语句更好,还是有几个具有长体的条件语句,或者具有嵌套条件的短体?
- 在当前的 1.6 JVM 中,在 System.arraycopy 打败复制循环之前必须复制多少个元素?
我已经做了什么:
在我被攻击为过早优化之前:基本算法已经非常好,但是 Java 实现的速度不到等效 C 的 2/3。我已经用 System.arraycopy 替换了复制循环,努力优化循环并消除不需要的操作。
我大量使用位运算和将字节打包到 int 中以提高性能,以及移位和掩码。
出于法律原因,我无法查看类似库中的实现,并且现有库的许可条款过于限制。
对一个良好(接受)答案的要求:
- 不可接受的答案:没有解释多少和为什么,或者没有使用 JIT 编译器进行测试的“这更快”。
- 边缘答案:尚未在 Hotspot 1.4 之前进行任何测试
- 基本答案:将提供一般规则和解释,说明它在编译器级别上更快,以及大约更快多少
- 好的答案:包括几个代码示例以演示
- 优秀答案:具有 JRE 1.5 和 1.6 的基准测试
- 完美答案:是 HotSpot 编译器的工作人员,可以完全解释或引用使用优化的条件以及它通常更快多少。可能包括 HotSpot 生成的 Java 代码和示例汇编代码。
另外:如果有任何详细介绍 Hotspot 优化和分支性能的链接,那将是受欢迎的。我了解足够的字节码,一个分析字节码而不是源代码级别的性能站点将是有帮助的。
(编辑)部分答案:消除边界检查:
这里是从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 code 在逻辑上,它与开发版本相同,但该版本使用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;
}
最终编辑:
由于时间紧迫,我已经将目前最佳答案标记为接受。由于在发布代码之前我花费了很长时间,因此我将继续在可能的情况下点赞和回复评论。如果代码看起来很混乱,请见谅:这是开发中的代码,不是为提交而精心打磨的。