Comment puis-je coder Java pour permettre l'utilisation de SSE et l'élimination de la vérification des limites (ou d'autres optimisations avancées) ?

https://stackoverflow.com/questions/1352422

20-09-2019
|

Question

La situation:

J'optimise une implémentation purement Java de l'algorithme de compression LZF, qui implique beaucoup d'accès byte[] et des mathématiques int de base pour le hachage et la comparaison.Les performances sont vraiment importantes, car l'objectif de la compression est de réduire les besoins en E/S.Je ne publie pas de code car il n'est pas encore nettoyé et peut être fortement restructuré.

Questions:

Comment puis-je écrire mon code pour lui permettre de se compiler JIT sous un formulaire en utilisant des opérations SSE plus rapides ?
Comment puis-je le structurer pour que le compilateur puisse facilement éliminer les vérifications des limites du tableau ?
Existe-t-il des références générales sur la vitesse relative d'opérations mathématiques spécifiques (combien d'incréments/décréments faut-il pour égaler une addition/soustraction normale, quelle est la vitesse de décalage ou de vs.un accès au tableau) ?
Comment puis-je travailler sur l'optimisation des branchements : est-il préférable d'avoir de nombreuses instructions conditionnelles avec des corps courts, ou quelques longues, ou des courtes avec des conditions imbriquées ?
Avec la JVM 1.6 actuelle, combien d'éléments doivent être copiés avant que System.arraycopy ne batte une boucle de copie ?

Ce que j'ai déjà fait :

Avant de me faire attaquer pour optimisation prématurée :l'algorithme de base est déjà excellent, mais l'implémentation Java est inférieure aux 2/3 de la vitesse de l'équivalent C.J'ai déjà remplacé les boucles de copie par System.arraycopy, travaillé sur l'optimisation des boucles et éliminé les opérations inutiles.

J'utilise beaucoup la manipulation de bits et le regroupement d'octets dans des entiers pour les performances, ainsi que le décalage et le masquage.

Pour des raisons juridiques, je ne peux pas examiner les implémentations dans des bibliothèques similaires, et les bibliothèques existantes ont des conditions de licence trop restrictives pour être utilisées.

Conditions requises pour une BONNE réponse (acceptée) :

Réponses inacceptables : "c'est plus rapide" sans explication de combien ET pourquoi, OU n'a pas été testé avec un compilateur JIT.
Réponses limites : n'ont pas été testés avec quoi que ce soit avant Hotspot 1.4
Réponses de base : fournira une règle générale et une explication de la raison pour laquelle il est plus rapide au niveau du compilateur, et à peu près à quel point
Bonnes réponses : inclure quelques exemples de code pour démontrer
Excellentes réponses : avoir des benchmarks avec JRE 1.5 et 1.6
Réponse PARFAITE : Il s'agit d'une personne qui a travaillé sur le compilateur HotSpot et qui peut expliquer ou référencer en détail les conditions d'utilisation d'une optimisation et à quel point elle est généralement plus rapide.Peut inclure du code Java et un exemple de code assembleur généré par HotSpot.

Aussi:si quelqu'un a des liens détaillant les entrailles de l'optimisation des points d'accès et des performances de branchement, ils sont les bienvenus.J'en sais suffisamment sur le bytecode pour qu'un site analysant les performances au niveau du bytecode plutôt que du code source serait utile.

(Modifier) Réponse partielle :Élimination des limites-vérification :

Ceci est extrait du lien fourni vers le wiki interne de HotSpot à l'adresse : https://wikis.oracle.com/display/HotSpotInternals/RangeCheckElimination

HotSpot éliminera les vérifications de limites dans toutes les boucles for avec les conditions suivantes :

Le tableau est invariant en boucle (non réaffecté dans la boucle)
La variable d'index a une foulée constante (augmente/diminue d'un montant constant, à un seul endroit si possible)
Le tableau est indexé par une fonction linéaire de la variable.

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

OU: int val = array[index+9]

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

Première version du code :

Ceci est un exemple de version.Ne le volez pas, car il s'agit d'une version inédite du code du projet de base de données H2.La version finale sera open source.Il s'agit d'une optimisation du code ici : Code H2 CompressLZF

Logiquement, ceci est identique à la version de développement, mais celle-ci utilise une boucle for(...) pour parcourir les entrées, et une boucle if/else pour une logique différente entre les modes littéral et de référence arrière.Il réduit l'accès au tableau et vérifie entre les modes.

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

Modification finale :

J'ai marqué la meilleure réponse jusqu'à présent comme acceptée, car le délai est presque écoulé.Comme j'ai mis si longtemps avant de décider de publier du code, je continuerai à voter positivement et à répondre aux commentaires dans la mesure du possible. Toutes mes excuses si le code est compliqué :cela représentait du code en développement, non peaufiné pour la validation.

La solution

Ce n'est pas une réponse complète, je n'ai tout simplement pas le temps de faire les références détaillées dont votre question a besoin, mais j'espère qu'elles seront utiles.

Connais ton ennemi

Vous ciblez une combinaison de la JVM (essentiellement le JIT) et du sous-système CPU/Mémoire sous-jacent.Ainsi, "C'est plus rapide sur JVM X" ne sera probablement pas valable dans tous les cas à mesure que vous passez à des optimisations plus agressives.

Si votre marché/application cible fonctionnera en grande partie sur une architecture particulière, vous devriez envisager d'investir dans des outils qui lui sont spécifiques.* Si vos performances sur x86 sont le facteur critique, alors Intel VTune est excellent pour approfondir le genre de analyse de sortie jit tu décris.* Les différences entre les JIT 64 bits et 32 bits peuvent être considérables, en particulier sur les plateformes x86 où les conventions d'appel peuvent changer et inscription les opportunités sont très différentes.

Obtenez les bons outils

Vous souhaiterez probablement vous procurer un profileur d’échantillonnage.Les frais généraux liés à l'instrumentation (et les conséquences associées sur des éléments tels que l'inlining, la pollution du cache et l'inflation de la taille du code) pour vos besoins spécifiques seraient bien trop importants.L'analyseur Intel VTune peut en fait être utilisé pour Java bien que l'intégration ne soit pas aussi étroite que d'autres.
Si vous utilisez la JVM Sun et que vous êtes satisfait de savoir uniquement ce que fait la dernière/la meilleure version, les options disponibles pour étudier la sortie du JIT sont considérables si l'on connaît un peu le montage.Ce l'article détaille quelques analyses intéressantes utilisant cette fonctionnalité

Apprendre des autres implémentations

L'historique des modifications l'historique des modifications indique que l'assemblage en ligne précédent était en fait contre-productif et que cela permettait au compilateur de prendre le contrôle total de la sortie (avec des ajustements dans code plutôt que des directives en assemblée) ont donné de meilleurs résultats.

Quelques détails

Étant donné que LZF est, dans une implémentation non gérée efficace sur les processeurs de bureau modernes, largement limitée en bande passante mémoire (elle est donc comparée à la vitesse d'une mémoire non optimisée), vous aurez besoin que votre code reste entièrement dans le cache de niveau 1.
En tant que tels, tous les champs statiques que vous ne pouvez pas transformer en constantes doivent être placés dans la même classe, car ces valeurs seront souvent placées dans la même zone de mémoire consacrée aux tables virtuelles et aux métadonnées associées aux classes.

Les allocations d'objets qui ne peuvent pas être piégées par Escape Analysis (uniquement à partir de la version 1.6) devront être évitées.

Le codec fait un usage agressif du déroulement de la boucle.Cependant, les performances de ceci sur les machines virtuelles plus anciennes (ère 1.4) sont fortement dépendant du mode dans lequel se trouve la JVM.Apparemment, les dernières versions de Sun JVM sont plus agressives en termes d'intégration et de déroulement, en particulier en mode serveur.

Les instructions de prélecture générées par le JIT peuvent faire toute la différence sur un code comme celui-ci qui est proche de la mémoire.

"Ça arrive tout droit pour nous"

Votre cible bouge et continuera de le faire.Encore une fois l'expérience précédente de Marc Lehmann :

la taille par défaut du HLOG est désormais de 15 (les caches du processeur ont augmenté)

Même des mises à jour mineures de la JVM peuvent impliquer changements importants dans le compilateur

6544668 Ne vécorisez pas les opérations sur les tableaux qui ne peuvent pas être alignées au moment de l'exécution.6536652 Implémentez des optimisations de superword (SIMD) 6531696 N'utilisez pas la mémoire immédiate de la valeur de 16 bits sur la mémoire sur les processeurs Intel 6468290 divisez et allouez à Eden sur une base CPU par CPU 6468290

Capitaine évident

Mesurer, mesurer, mesurer.SI vous pouvez demander à votre bibliothèque d'inclure (dans une DLL séparée) un benchmark simple et facile à exécuter qui enregistre les informations pertinentes (version de la machine virtuelle, processeur, système d'exploitation, commutateurs de ligne de commande, etc.) et rend cela simple à vous renvoyer, vous le ferez augmentez votre couverture, mieux encore, vous couvrirez les personnes qui utilisent ces soins.

Autres conseils

En ce qui concerne limites vérifier l'élimination est concerné, je crois que le nouveau JDK comprendra déjà un algorithme amélioré qui l'élimine, chaque fois qu'il est possible. Ce sont les deux principaux documents à ce sujet:

V. Mikheev, S. Fedoseev, V. Sukharev, N. Lipsky. 2002 Amélioration efficace de la boucle Versioning en Java . lien. Ce document est des gars de Excelsior, qui mis en œuvre la technique dans leur Jet JVM.
Würthinger, Thomas, Christian Wimmer et Hanspeter Mössenböck. 2007. array Bounds Check élimination pour le compilateur Java HotSpot client . PPPJ. Lien . Un peu basé sur le papier ci-dessus, c'est la mise en œuvre que je crois sera inclus dans la prochaine JDK . Les obtenus speedups sont également présentés.

Il y a aussi

Il est assez peu probable que vous devez aider le compilateur JIT beaucoup avec l'optimisation d'un nombre simple algorithme LZW comme crissement. ShuggyCoUk mentionné, mais je pense qu'il mérite une attention particulière:

Le cache-convivialité de votre code sera un facteur important.

Vous devez réduire la taille de votre ensemble de Woking et d'améliorer la localité d'accès aux données, autant que possible. Vous mentionnez « emballage octets dans ints pour la performance ». Cela ressemble à l'aide ints pour contenir des valeurs d'octets afin de les avoir mot alignés. Ne fais pas ça! La taille de l'ensemble de données a augmenté l'emportent sur les gains (I fois converti un code ECC à partir crissement nombre int [] à l'octet [] et a obtenu une vitesse jusqu'à 2x).

Au hasard que vous ne savez pas: si vous avez besoin pour traiter certaines données comme les deux octets et ints, vous ne devez pas changer et | -mask il - utiliser ByteBuffer.asIntBuffer() et des procédés associés.

Avec 1,6 actuelle machine virtuelle Java, combien éléments doivent être copiés avant System.arraycopy bat une boucle de copie?

Mieux faire la référence vous-même. Quand je l'ai fait le chemin du retour quand en Java 1.3 fois, il était quelque part autour de 2000 éléments.

Beaucoup de réponses à ce jour, mais deux choses supplémentaires:

Mesure, mesure, mesure. Autant que la plupart des développeurs Java mettent en garde contre des micro-analyses comparatives, assurez-vous de comparer les performances entre les changements. Optimisations qui ne donnent pas lieu à des améliorations mesurables ne sont généralement pas utile de garder (bien sûr, il est parfois combinaison de choses, et qui devient plus délicat)
boucles serrées comptent autant avec Java avec C (et idem avec les allocations variables - même si vous ne HotSpot aura finalement pas directement contrôler, de le faire). J'arrive à pratiquement doubler la vitesse de décodage UTF-8 en réarrangeant boucle serrée pour le traitement des cas un seul octet (ASCII 7 bits) en tant que boucle interne étanche (ER), en laissant les autres cas out.
Ne pas sous-estimer le coût de l'allocation et / ou de compensation de grands tableaux - si vous voulez lzf encodage / décodage pour être plus rapide pour des morceaux de petites / moyennes trop (et pas seulement méga-octet de taille), gardez à l'esprit que toutes les allocations de l'octet [] / int [] sont peu coûteux; non pas à cause de GC, mais parce que JVM DOIT effacer l'espace.

mise en œuvre de H2 a également été optimisé un peu (par exemple: il ne voit pas clairement le tableau de hachage plus, ce qui rend souvent le sens); et je réellement aidé à modifier pour l'utiliser dans un autre projet Java. Ma contribution a été la plupart du temps juste le changer ne sera plus optimale pour le cas non-streaming, mais qui ne touche pas les boucles encode / decode serrés.

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow