Assembleur PPC besoin d’un bout de code…

[Tcheko]

Tcheko

#4330

Bonjour,

Je m’acharne en ce moment sur un petit programme réseau et je fais face à un problème de vitesse d’exécution… Mon programme est ‘CPU bound’ et le bout de code critique est (je pense) déjà optimisé en C. L’étape suivante éventuelle est donc de passer le bout de code en pur assembleur PPC histoire de voir si l’on peut grapiller quelques cycles.

Voici le bout de code C en question :

long Lookup(const Cache *cache, const unsigned char *hash)

{

register long j;

register unsigned long *ts;

register unsigned long *td;

ts = (unsigned long*)hash;

td = (unsigned long*)cache->Lookup + (MAX_CACHE_ENTRY – 1) * 16;

j = MAX_CACHE_ENTRY – 1;

do

{

if(td[0] != ts[0]) goto next;

if(td[1] != ts[1]) goto next;

if(td[2] != ts[2]) goto next;

if(td[3] != ts[3]) goto next;

if(td[4] != ts[4]) goto next;

if(td[5] != ts[5]) goto next;

if(td[6] != ts[6]) goto next;

if(td[7] != ts[7]) goto next;

if(td[8] != ts[8]) goto next;

if(td[9] != ts[9]) goto next;

if(td[10] != ts[10]) goto next;

if(td[11] != ts[11]) goto next;

if(td[12] != ts[12]) goto next;

if(td[13] != ts[13]) goto next;

if(td[14] != ts[14]) goto next;

if(td[15] == ts[15]) return j;

next:

td -= 16;

} while(j–);

return -1;

}

Ce code permet de retrouver une clé de hashage (variable hash / ts) de 64 octets de long dans une table (cache->Lookup / td) qui est d’une longueur fixe (MAX_CACHE_ENTRY). Le temps d’exécution est lineaire puisque le parcours se fait de la fin de la table en remontant vers le début du tableau (td -=16). La fonction retourne l’indice du tableau qui contient la clé demandée.

D’autres structures de données qu’un simple adressage linéaire pourraient offrir des performances plus intéressantes lors d’une recherche notamment ranger les clés dans un arbre. N’ayant pas l’envie (pour l’instant) d’explorer ces solutions, est ce que quelqu’un a une idée pour optimiser le temps d’exécution de ce bout de code ? (que ce soit en C… ou mieux, révons un peu! en assembleur…). Actuellement, c’est cette partie qui limite la bande passante… Quelques chiffres : pour un tableau de 10240 éléments, j’obtiens environ 3Mo/s. Avec un tableau de 65536 éléments, je tombe à 1,1Mo/s… Ce qui est mou du genou.

Des idées ?

PS : il y a de jolis goto dans le code. Je sais. Alors pour les acharnés de l’axiome débile ‘le goto c’est pas bien’ merci de garder vos trolls. Le goto est intéressant dans certaine situation et j’ai estimé que dans celle ci, c’était le cas. L’usage est concis et clair et ne nuit pas à la compréhension du code ou à sa maintenance.

[Gilloo]

Gilloo

#75347

Bin là c’est déjà très optimisé vu que tu as:

– utilisé 16 ULONG au lieu de 64 octets.

– utilisé une boucle avec un compteur qui se décrémente et qui finit à 0.

– figé une boucle sur la comparaison (td != ts)

Je n’aurais pas mis de goto, vu que le compilo C qui se respecte fait le boulot pour toi sans rien dire (optimisation sur la première condition qui est fausse et fait en sorte de ne pas évaluer le reste à droite).

Bof j’essaierais ça:

long Lookup(const Cache *cache, const unsigned char *hash)

{

register long j;

register unsigned long *ts;

register unsigned long *td;

ts = (unsigned long*)hash;

td = (unsigned long*)cache->Lookup + (MAX_CACHE_ENTRY – 1) * 16;

j = MAX_CACHE_ENTRY – 1;

do

{

if ((td[0] == ts[0]) &&

(td[1] == ts[1]) &&

(td[2] == ts[2]) &&

(td[3] == ts[3]) &&

(td[4] == ts[4]) &&

(td[5] == ts[5]) &&

(td[6] == ts[6]) &&

(td[7] == ts[7]) &&

(td[8] == ts[8]) &&

(td[9] == ts[9]) &&

(td[10] == ts[10]) &&

(td[11] == ts[11]) &&

(td[12] == ts[12]) &&

(td[13] == ts[13]) &&

(td[14] == ts[14]) &&

(td[15] == ts[15])) return j;

td -= 16;

} while(j–);

return -1;

}

[Fab1]

Fab1

#75348

Puisque finalement, ton truc s’apparente énormément à une recherche de string dans une table (à la différence près que c’est pt être cyclique), tu pourrais déjà grandement améliorer les perfs en changeant l’algorithme, en utilisant la méthode Boyer-Moore par exemple, qui permet, en regardant la fin du motif recherché, d’éviter beaucoup de vérifications inutiles.

Sinon, ça doit sûrement s’optimiser en altivec, mais là je connais pas trop.

Mais quoiqu’il en soit, il vaut mieux passer du temps à penser à l’algo, qu’à la façon de l’optimiser. Un tri bulle 100% asm sera toujours plus lent qu’un quicksort en C pas trop optimisé.

[Tcheko]

Tcheko

#75349

Gilloo a écrit :

Bin là c’est déjà très optimisé vu que tu as:

– utilisé 16 ULONG au lieu de 64 octets.

– utilisé une boucle avec un compteur qui se décrémente et qui finit à 0.

– figé une boucle sur la comparaison (td != ts)

Je n’aurais pas mis de goto, vu que le compilo C qui se respecte fait le boulot pour toi sans rien dire (optimisation sur la première condition qui est fausse et fait en sorte de ne pas évaluer le reste à droite).

Bof j’essaierais ça:

long Lookup(const Cache *cache, const unsigned char *hash)

{

register long j;

register unsigned long *ts;

register unsigned long *td;

ts = (unsigned long*)hash;

td = (unsigned long*)cache->Lookup + (MAX_CACHE_ENTRY – 1) * 16;

j = MAX_CACHE_ENTRY – 1;

do

{

if ((td[0] == ts[0]) &&

(td[1] == ts[1]) &&

(td[2] == ts[2]) &&

(td[3] == ts[3]) &&

(td[4] == ts[4]) &&

(td[5] == ts[5]) &&

(td[6] == ts[6]) &&

(td[7] == ts[7]) &&

(td[8] == ts[8]) &&

(td[9] == ts[9]) &&

(td[10] == ts[10]) &&

(td[11] == ts[11]) &&

(td[12] == ts[12]) &&

(td[13] == ts[13]) &&

(td[14] == ts[14]) &&

(td[15] == ts[15])) return j;

td -= 16;

} while(j–);

return -1;

}

Ok. Je vais tenter cette façon de faire puisque effectivement, au premier échec, la suite de la comparaison ne sera pas traitée.

J’ai transformé les long ts[x] en long ix (ix = ts[x]). Ca n’a apparement pas amélioré les perfs mais en tout cas, ça ne leur à pas fait de mal…

Je viens de faire le test de perf, j’obtiens environ 1200Ko/s pour un cache de 65536 entrées. Bref. Je dois être pas loin du maximum théorique possible en bande passante mémoire… sans utiliser des instructions altivec. Sans rentrer dans les détails, je fais appel environ 550 fois à cette fonction de lookup pour récupérer des index de positions dans un fichier. La taille du tableau étant de 64 octets x 65536, ca fait 4Mo. Je balaye donc dans le pire des cas 550 fois 4Mo ce qui est un peu lourdingue et doit passablement malmener les caches du CPU…

C’est clairement cette fonction qui rend l’exécution mou du genou. La réduction de la taille du tableau à 10240 éléments multiplie les performances par 2,5… Je vais peut être changer de Mac… Ca rame.

Concernant l’algo de Booyer-Moore, la taille des éléments du tableau est égale à la taille de la clé de hash. Je doute qu’une implémentation de cet algorithme apporte une amélioration des performances. La distribution des bits dans la clé de hash est normalement homogène, les probabilités de trouver deux clés ayant les 4 premiers octets identiques me semble faible en comparaison du nombre d’éléments du tableau. En tout cas, merci pour l’info concernant cet algo…

Si un acharné à quelques connaissances concernant la programmation de l’altivec…

++

[bigdan]

bigdan

#75350

Tcheko a écrit :

Si un acharné à quelques connaissances concernant la programmation de l’altivec…

Kakace par exemple mais il traine plutôt sur des sites Mac.

[henes]

henes

#75351

As tu vérifié que memcmp() n’était pas plus rapide que ta routine ? Apple est assez bon pour optimiser ce genre de choses (en plus leur version est sans doute opensource).

[Tcheko]

Tcheko

#75352

Yop Henes,

Je viens d’essayer la fonction memcmp. Résultat sans appel : 630Ko/s soit deux fois moins que ma fonction handmade…

C’est bien… mais moins rapide.

Merci pour l’idée toutefois!

++

[corto]

corto

#75353

Aaargh ! J’aimerais beaucoup y regarder mais … je déménage aujourd’hui, dans une heure !!! Hop, ça aura fait remonter le thread pour pouvoir y regarder plus tard.

Tu as essayé de voir l’assembleur généré ? Il y a plein de conditions, il faudrait limiter le nombre de branchements.

Peux-tu nous mettre un jeu de test à disposition stp ?

[Tcheko]

Tcheko

#75354

Yop Corto,

Je n’ai pas regardé le code asm généré par gcc. N’y connaissant pas grand chose en code PowerPC, je suis resté collé à l’asm 68k… Et puis surtout, il y a quelques pointures de l’assembler PPC ici… donc je sollicite

Hmmm, un jeu de test?

Pour la table de lookup

unsigned long cache[16 * 65536];

for(j=0; j<65536; j++) for(i=0;i<16;i++) cache = j;

Pour le hash à chercher

unsigned long hash[16];

for(i=0;i<16;i++) hash = 4290;

Voila pour le jeu de test.

[corto]

corto

#75355

Je suis encore dans les cartons mais j’ai quand même pu jeter un oeil à ton algo hier soir après avoir mis en forme le jeu de test (déformation professionnelle, c’est mon job de faire du test) que tu m’as indiqué

Ici, gcc génère quasiment le même code en -O2 et -O3. Et je pense qu’il y a moyen d’améliorer les choses. En effet dans ta boucle principale, tu effectues au pire 16 comparaisons, soit pour chacune dans le code assembleur :

– lecture en mémoire d’un mot de 32 bits appartenant la clé de ta table

– lecture en mémoire d’un mot de 32 bits de la clé recherchée

– comparaison des 2

– saut conditionnel (les branchements coûtent cher !)

Ce qui me frappe c’est que très peu de registres sont utilisés. Les données lues devraient être entrelacées en utilisant plus de registres et en faisant intervenir plusieurs registres de condition. Le PowerPC a un registre de condition (CR) de 32 bits qui contient en quelque sorte 8 registres de condition de 4 bits où tu peux enregistrer le résultat de 8 comparaisons ! Par exemple, tu peux dire que le résultat d’une comparaison va dans cr0 puis plus loin que le résultat d’une autre va dans cr2. Puis tu peux les tester séparément ou … ensemble ! Tu peux ainsi sortir de ta boucle si cr0 OU cr2 n’a pas rencontré d’égalité entre les mots de ton entrée de table et ceux de ta clé. Avec ce principe, tu dois pouvoir diviser par 2 ton nombre de branchements.

Là, il y a un branchement conditionnel toutes les 4 instructions et ça me paraît énorme. Si le compilo ne peut pas bien optimiser, c’est parce qu’il doit s’attendre à sortir de la boucle à chaque fois. A mon avis, même en C, j’essaierais de charger plusieurs valeurs des tableaux td et ts, le compilo devrait utiliser plusieurs registres et hop, après tu compares et sautes.

Mon hypothèse serait d’anticiper le chargement de quelques valeurs quitte à les lire pour rien (en plus elles sont dans le cache) afin de repousser les comparaisons / branchements.

Et au lieu de charger mot par mot, je me demande ce que donnerait un chargement de plusieurs registres en même temps …

Je crois qu’il y a des pistes à creuser ! Je vais essayer de faire des mesures de temps avec plusieurs versions modifiées.

PS : Je ne sais pas du tout si ce que j’ai dit est clair … ou complètement juste.

[Tcheko]

Tcheko

#75356

Yop Corto,

Mon cas est pourri jusqu’à la moëlle. L’algo que j’utilise jusqu’à présent bouffe toute la (maigre) bande passante mémoire du G4… Essayer de retrouver une chaine de 64 caractères dans un tableau de 4Mo avec une recherche linéaire, c’est comme chercher son nom au hasard dans l’annuaire…

Pour ce qui est de l’exécution des instructions ppc… j’en ai foutrement aucune idée. Je n’ai que mes connaissances en 68k… ce qui avec les cpu modernes ne sert presque à rien… Bref.

J’ai fait quelques tests avec un algo modifée (il vaut mieux parfois changer son fusil d’épaule… un algo plus adapté vaut mieux qu’une optimisation forcenée…).

Avec une table de hash de 512Mo histoire de bourriner un peu sur le [email protected]

Grosso modo :

Deux tables :

Une table de hash original de 64 octets.

Une table de hash réduit à base long qui reprend les 4 premiers octets de la table de hash original. Cette table est 16x plus petite.

Avec une table de 512Mo

Temps d’exécution avec algo original : 3000

Temps d’exécution avec algo modifé : 30

Avec une table de 256Mo

Temps d’exécution avec algo original : 80

Temps d’exécution avec algo modifé : 17

Fold : x4 à x100 en fonction de la taille de la table…

La seule différence avec le code original est l’ajout d’une condition sur la table de hash réduite :

if(shash[j] == ts[0])

if ((td[0] == ts[0]) &&

(td[1] == ts[1]) &&

(td[2] == ts[2]) &&

(td[3] == ts[3]) &&

(td[4] == ts[4]) &&

(td[5] == ts[5]) &&

(td[6] == ts[6]) &&

(td[7] == ts[7]) &&

(td[8] == ts[8]) &&

(td[9] == ts[9]) &&

(td[10] == ts[10]) &&

(td[11] == ts[11]) &&

(td[12] == ts[12]) &&

(td[13] == ts[13]) &&

(td[14] == ts[14]) &&

(td[15] == ts[15])) return j;

J’attends un coup de main du créateur de freeveclib pour un bout de code altivec…

Si tu as une version à me proposer en asm pur… Ca m’intéresse quand même!

++

[Tcheko]

Tcheko

#75357

Youpla BOOM.

J’ai fait la modif du lookup dans le code réseau et j’ai un gain x3 en vitesse pour le DL des fichiers depuis le cache local soit 3,5Mo/s environ. Ca commence à être raisonnable : ça pourra saturer une ligne DSL2+ 24Mbits depuis une machine qui n’est plus uptodate… J’ai surement déplacé la congestion ailleurs avec cette modification du code. Shark est mon ami, ils ont de bon outils napple pour l’optimisation!