Wie kann ich code in Java zu ermöglichen, SSE verwenden und bounds-check-elimination (oder andere erweiterte Optimierungen)?

Die Situation:

Ich bin die Optimierung einer pure-java-Implementierung des LZF-Kompressions-Algorithmus, die beinhaltet eine Menge von byte[] zugreifen und grundlegende int Mathematik für das hashing und Vergleich. Leistung wirklich zählt, denn das Ziel der Kompression ist die Verringerung der I/O-Anforderungen. Ich bin nicht posting-code, weil es nicht aufgeräumt ist noch nicht, und kann umstrukturiert werden, stark.

Die Fragen:

• Wie kann Schreibe ich meinen code, um es zu ermöglichen, JIT-kompilieren, um eine form mit schnelleren SSE-Operationen?
• Wie kann ich die Struktur es so, dass der compiler kann Sie leicht beseitigen, die array-Grenzen überprüft?
• Gibt es umfassende Referenzen über die relative Geschwindigkeit der bestimmte mathematische Operationen (wie viele inkrementiert/dekrementiert dauert es, gleich eine normal addieren/subtrahieren, wie schnell ist der shift-oder im Vergleich zu einem array-Zugriff)?
• Wie kann ich arbeiten auf die Optimierung der Verzweigung -- ist es besser mehrere bedingte Anweisungen mit kurzen Körper, oder ein paar lange oder kurze mit verschachtelten Bedingungen?
• Mit aktuellen 1.6 JVM, wie viele Elemente kopiert werden müssen, bevor das System.arraycopy beats eine Kopier-Schleife?

Was ich bereits getan habe:

Bevor ich angegriffen für die vorzeitige Optimierung: der grundlegende Algorithmus ist schon Prima, aber die Java-Implementierung ist weniger als 2/3 der Geschwindigkeit entspricht C. habe ich bereits ausgetauscht und kopieren von loops und System.arraycopy, arbeitete an der Optimierung von Schleifen und beseitigt un-Operationen benötigt.

Ich machen starken Gebrauch von bit twiddling und Verpackung bytes in int-Werte für die Leistung, sowie die Verlagerung & maskieren.

Aus rechtlichen Gründen, kann ich nicht anschauen-Implementierungen in ähnlichen Bibliotheken, und Bibliotheken haben eine zu restriktive Lizenzbedingungen zu verwenden.

Anforderungen für eine GUTE (angenommen) Antwort:

• Inakzeptable Antworten: "das ist schneller" ohne eine Erklärung, wie viel UND warum, ODER ist nicht getestet worden mit einem JIT-compiler.
• Borderline Antworten: nicht getestet haben, mit etwas vor-Hotspot 1.4
• Grundlegenden Antworten: wird eine Allgemeine Regel und die Erklärung, warum es schneller in die compiler-Ebene, und ungefähr wie viel schneller
• Gute Antworten: ein paar Beispiele von code, um zu demonstrieren,
• Ausgezeichnete Antworten: haben benchmarks mit den beiden JRE 1.5 und 1.6
• PERFEKTE Antwort: Ist von jemandem, der arbeitete auf der HotSpot-compiler, und kann vollständig erklären oder einen Verweis auf die Bedingungen für eine Optimierung verwendet werden, und wie viel schneller es in der Regel. Vielleicht gehören java-code und Beispiel-Assembler-code generiert HotSpot.

Außerdem: wenn jemand die links mit den Details der Eingeweide der Hotspot-Optimierung und-Verzweigung Leistung, sind willkommen. Ich weiß genug über bytecode, die eine Website Analyse der Leistung bei bytecode eher als sourcecode-Ebene wäre hilfreich.

(Edit) Teilweise Antwort: Bounds-Check-Ellimination:

Dies ist genommen aus gelieferten link zur HotSpot internals wiki unter: https://wikis.oracle.com/display/HotSpotInternals/RangeCheckElimination

HotSpot beseitigen bounds-checks in allen for-Schleifen mit den folgenden Bedingungen:

• Array loop-invariant (nicht umgeschichtet innerhalb der Schleife)
• Index-variable eine Konstante Schrittlänge (erhöht/verringert durch die Konstante Menge an nur einem Ort, wenn möglich)
• Array wird indiziert durch eine lineare Funktion der variable.

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

ODER: int val = array[index+9]

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

---

Frühe version von code:

Dies ist eine Probe-version. Nicht stehlen, denn es ist eine unveröffentlichte version des Codes für die H2-Datenbank-Projekt. Die Finale version wird open source sein. Dies ist eine Optimierung auf dem code hier: H2 CompressLZF code

Logisch, diese ist identisch mit der development-version, aber das nutzt man eine for (...) - Schleife zum Schritt durch den Eingang, und eine if/else-Schleife für unterschiedliche Logik zwischen wörtlichen und Rückverweis Modi. Es reduziert array-Zugriff und Kontrollen zwischen den Modi.

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; 
    }

---

Letzte änderung:

Ich ' ve markiert die beste Antwort, die so weit akzeptiert, da die Frist fast bis. Da ich so lange dauerte, bevor Sie sich entscheiden zu post code, werde ich weiter upvote und reagieren auf Kommentare, wo möglich. Entschuldigt, wenn der code unordentlich ist: diese vertreten-code in Entwicklung, nicht Poliert zu Begehen.

InformationsquelleAutor der Frage BobMcGee | 2009-08-29