La Situation:
Je suis de l'optimisation d'un pur-java mise en œuvre de la LZF algorithme de compression, ce qui implique beaucoup de byte[] d'accès et de base int mathématiques pour le hachage et la comparaison. La Performance est vraiment important, parce que le but de la compression est de réduire les exigences d'e/S. Je ne suis pas poster du code, car il n'est pas nettoyé encore, et peut-être restructuré fortement.
Les Questions:
- Comment puis-je écrire mon code afin de permettre à JIT compiler un formulaire à l'aide de vite SSE opérations?
- Comment puis-je de la structure de sorte que le compilateur peut facilement éliminer les limites du tableau des contrôles?
- Existe-il des grandes références au sujet de la vitesse relative de certaines opérations mathématiques (combien de incrémente/décrémente faut-il pour l'égalité normale ajouter/soustraire, quelle est la vitesse de changement-ou contre un tableau)?
- Comment puis-je travailler sur l'optimisation de la ramification -- est-il préférable d'avoir de nombreuses instructions conditionnelles avec de courtes corps, ou un peu longs, ou courts, avec des conditions nichées?
- Avec 1,6 JVM, combien d'éléments doivent être copiés à l'avant du Système.arraycopy bat une copie de la boucle?
Ce que j'ai déjà fait:
Avant de me faire attaquer pour l'optimisation prématurée: l'algorithme de base est déjà excellente, mais l'implémentation de Java est inférieure à 2/3 de la vitesse de l'équivalent de C. j'ai déjà remplacé la copie des boucles avec le Système.arraycopy, a travaillé sur l'optimisation de boucles et éliminé de l'onu nécessaire des opérations.
Je fais un usage intensif de peu tourner et d'emballage octets dans ints de performances, ainsi que de changer & de masquage.
Pour des raisons juridiques, je ne peux pas regarder mises en œuvre dans les bibliothèques similaires, et les bibliothèques ont trop restrictive les conditions de licence pour l'utiliser.
Exigences pour une BONNE (accepté) réponse:
- Inacceptable répond: "c'est plus rapide", sans une explication de combien ET pourquoi, OU n'a pas été testé avec un compilateur JIT.
- Limite des réponses: n'ont pas été testés avec quoi que ce soit avant Hotspot 1.4
- Des réponses simples: fournira une règle générale et que l'explication de pourquoi il est plus rapide au niveau du compilateur, et à peu près combien plus rapide
- Bonnes réponses: inclure un couple d'échantillons de code pour illustrer
- Excellentes réponses: avoir des repères à la fois avec le JRE 1.5 et 1.6
- PARFAIT réponse: Est par quelqu'un qui a travaillé sur le HotSpot compilateur, et peut expliquer ou de référence, les conditions d'une optimisation à être utilisé, et comment beaucoup plus rapide, il est généralement. Peut inclure du code java et exemples de code assembleur généré par HotSpot.
Aussi: si quelqu'un a des liens détaillant les entrailles de Hotspot de l'optimisation et de la ramification de la performance, ceux sont les bienvenus. J'en sais assez sur le bytecode qu'un site d'analyse de la performance à un bytecode plutôt que le code source serait utile.
(Edit) Réponse Partielle: Limites-Vérifier Ellimination:
Ceci est pris à partir fournis lien vers le HotSpot internes au wiki à: https://wikis.oracle.com/display/HotSpotInternals/RangeCheckElimination
HotSpot permettra d'éliminer les limites des contrôles dans tous les cas pour les boucles avec les conditions suivantes:
- Tableau est invariant de boucle (pas réaffecter à l'intérieur de la boucle)
- L'indice de la variable est une constante de la foulée (augmente/diminue en quantité constante, en un seul endroit, si possible)
- 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]
La première version du code:
Ceci est un exemple de version. Ne pas voler, parce que c'est une version éditée de code pour le H2 projet de base de données. La version finale sera open source. C'est une optimisation sur le code ici: H2 CompressLZF code
Logiquement, c'est identique à la version de développement, mais que l'on utilise un pour(...) de la boucle à l'étape d'entrée, et d'un si/d'autre de la boucle pour des logiques différentes entre littéral et backreference modes. 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;
}
Montage Final:
J'ai marqué la meilleure réponse jusqu'à présent comme acceptée, car la date limite est presque à la fin. Depuis que j'ai pris autant de temps avant de décider de poster le code, je vais continuer à upvote et répondre à des commentaires si possible. Toutes mes excuses si le code est illisible, c'està-code en développement, n'est pas poli de s'engager.
