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

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

• 如何编写代码以允许它使用更快的SSE操作JIT编译成表单?
• 如何构造它,以便编译器可以轻松地消除数组边界检查?
• 关于特定数学运算的相对速度,是否有广泛的参考资料(需要多少增量/减量才能等于正常的加法/减法,移位或数组访问的速度有多快)?
• 我怎样才能优化分支呢?最好是有许多短体的条件语句,还是有几个长体,还是有嵌套条件的短体?
• 对于当前的1.6 JVM,在System.arraycopy击败复制循环之前,必须复制多少个元素?

我已经做了:

为了提高性能,我大量使用位旋转和将字节打包到int中,以及移位&掩蔽。

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

• 不可接受的答案: “这是更快的”,没有解释多少和为什么,或者没有用JIT编译器进行测试。
• 基本答案:
• 好答案: 包括两个代码示例以演示
• 有JRE 1.5和1.6的基准测试
• 完美答案: 是由在HotSpot编译器上工作的人编写的,他可以完全解释或引用要使用的优化的条件,以及它通常有多快。可能包括由HotSpot生成的java代码和示例汇编代码。

(编辑)部分答案:边界检查省略:

这是从热点内部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 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; 
    }

最终编辑:

如果代码凌乱,则表示歉意:这表示代码正在开发中,而不是在提交时经过润色。