如何编写 Java 代码以允许 SSE 使用和边界检查消除（或其他高级优化）？
2022-09-01 02:42:46
情况：
我正在优化LZF压缩算法的纯java实现，它涉及大量的byte[]访问和基本的int数学，用于散列和比较。性能确实很重要，因为压缩的目标是降低 I/O 要求。我没有发布代码，因为它尚未清理，并且可能会进行大量重组。
问题：
- 如何编写代码以允许它使用更快的 SSE 操作进行 JIT 编译为窗体？
- 如何构建它，以便编译器可以轻松消除数组边界检查？
- 有没有关于特定数学运算的相对速度的广泛参考（需要多少增量/递减才能等于正常的加减，shift-or与数组访问的速度有多快）？
- 我该如何优化分支 - 是使用大量具有短主体的条件语句，还是具有嵌套条件的短语句更好？
- 使用当前的 1.6 JVM，在 System.arraycopy 击败复制循环之前，必须复制多少个元素？
我已经做了什么：
在我被攻击过早优化之前：基本算法已经非常出色，但Java实现的速度不到等效C的2/3。我已经用System.arraycopy取代了复制循环，致力于优化循环并消除不需要的操作。
我大量使用位微调并将字节打包成整数以提高性能，以及移位和屏蔽。
出于法律原因，我无法查看类似库中的实现，并且现有库的许可条款限制太多而无法使用。
良好（接受）答案的要求：
- 不可接受的答案：“这更快”没有解释多少和为什么，或者还没有用JIT编译器测试过。
- 边缘答案：在Hotspot 1.4之前没有经过任何测试
- 基本答案：将提供一般规则和解释为什么它在编译器级别更快，以及大致快多少
- 好的答案：包括几个代码示例来演示
- 出色的答案：同时具有JRE 1.5和1.6的基准测试
- 完美的答案：是由在 HotSpot 编译器上工作过的人编写的，可以完全解释或引用使用优化的条件，以及它通常快得多。可能包括由 HotSpot 生成的 Java 代码和示例汇编代码。
另外：如果有人有链接详细说明了Hotspot优化和分支性能的胆量，那么这些都是受欢迎的。我对字节码有足够的了解，一个在字节码而不是源代码级别分析性能的网站会很有帮助。
（编辑）部分答案：边界检查省略：
这是从提供的指向HotSpot内部wiki的链接中获取的：https://wikis.oracle.com/display/HotSpotInternals/RangeCheckElimination
HotSpot 将在以下条件下消除所有循环中的边界检查：
- 数组是循环不变的（不在循环中重新分配）
- 指数变量具有恒定的步幅（以恒定的量增加/减少，如果可能，仅在一个点上）
- 数组由变量的线性函数索引。
例： 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;
}
最终编辑：
我已经标记了迄今为止接受的最佳答案，因为截止日期即将到来。由于我花了很长时间才决定发布代码，因此我将继续投票并在可能的情况下回复评论。如果代码凌乱，请道歉：这表示开发中的代码，而不是为提交而完善。
