To optimize or not to optimize, that is the question.....
Par Vanhu le mardi, octobre 30 2007, 15:43 - Vieux con de hacker old school..... - Lien permanent
Rahlala, ces petits jeunes qui ne connaissent même pas ZE codeur, plus casse couilles que théo, plus intégriste que richard, et qui code de façon plus illisible que richie !!!!
J'ai nommé bien évidemment le fameux, l'unique (heureusement), l'incontournable (quoique): Daniel J. B. (rien à voir avec une marque de bouteille carrée a ma connaissance), auteur entre autres de plein de logiciels essentiellement interopérables avec eux même, sous une licence qui pourrait vous faire croire qu'elle est Opensource si vous n'y prêtez pas trop attention, et qui ont parfois du code source curieux.....
Entre autres exemples de code curieux, on avait trouvé à une époque un truc dans ce genre:
for (;;) {
if (!n) return; *to++ = *from++; --n;
if (!n) return; *to++ = *from++; --n;
if (!n) return; *to++ = *from++; --n;
if (!n) return; *to++ = *from++; --n;
}
L'idée de base de ce truc la, au delà du fait d’être moins lisible, c'est de faire moins d'itérations de boucle (un peu comme un -funroll-loops de gcc, quoi).
En des temps reculés, c'était sûrement pertinent (enfin, à part le fait de le rendre moins lisible, bien sur). Bien sur, je vous parle d'un temps que les moins de 20 ans ne peuvent pas connaître: les CPUs en ce temps la disposaient (parfois) de quelques kilooctets de mémoire cache, effectuaient sagement une instruction CPU à la fois, et le moindre JMP (lire "Jump", soit un saut à une autre adresse mémoire pour exécuter la prochaine instruction) ralentissait à mort le déroulement du programme.
Mais qu'en est-il aujourd'hui ?
Nos CPUs modernes disposent de plus de mémoire cache que mon Amiga 500 n'avait de Chip RAM (mémoire principale), ont des pipes (lire "tuyaux") d'instructions monstrueux, font de la prédiction de saut de branche, etc....
Encore une fois, il faut des professionnels au service des hommes, des gens volontaires, dévoués corps et âme à la cause, prêts à prendre tous les risques pour la science, fût-ce au péril de leur vie. Et en plus ca tombe bien, on est le 30 du mois et j'avais pas fait mon billet.....
ATTENTION: comme d'habitude, les tests sont effectués par des vieux cons de hackers old school, des gars qui ont survécu à des trucs terribles (installation d'une Gentoo sur un Octane, mise à jour en FreeBSD7, passage à Xorg 7.3, plus de papier dans les toilettes, réunions "OuaneToOuane", repas de famille avec la belle mère, etc....), des gars chevelus, avec des t shirt de geek, des gars qui comprennent celle de l'admin sys qui édite ses variables d'environnement, et PATH le chemin, des gars qui sont même morts de rire en se re-racontant cette blague, c'est pour vous dire !
Et bien sur, tout ça est fait dans un labo haute sécurité, on a les pompiers, le gros bouton rouge pour tout arrêter en cas de problèmes, l'infirmière aux gros seins au cas ou on aurait besoin d’être réanimés, un système d'exploitation robuste et fiable, des câbles antivol, une bouteille d'huile d'arachide, une superbe baie de brassage et deux gros airbags (ah, on me signale que non, apparemment il s'agirait toujours de l'infirmière sus-nommée.....).
Donc déconnez pas, ne FAITES PAS CA CHEZ VOUS, c'est dangereux, ou en tout cas venez pas chialer ici si vous vous êtes loutrés, que ca a formaté votre PC, fait mourir votre hamster, fait fuir votre copine, fait venir votre belle mère, vous a fait perdre au loto, ou toute autre catastrophe du genre.
Bon, donc, comment qu'on fait si on veut copier de la donnée rapidement:
- La façon "classique", c'est de copier caractère par caractère.
- La façon "classique et moderne", c'est de copier int par int.
- La façon "a la D.J.", c'est de copier "classique", mais 4 affectations par boucle.
- On peut faire quelques mélanges de ces techniques.
- En en discutant un peu, on m'a fait découvrir la façon Duff's device.
- Et bien sur, la façon "on se fait pas chier": on appelle bcopy(), tout simplement.....
Pour tester tout ça, on va utiliser un petit programme automatique, forcément, puisqu'un vieux dicton d'informaticien dit "ne fais jamais toi même ce que tu peux faire faire par un programme":
On va commencer par un beau tableau qui contient tous nos algos:
struct copy_alg_t {
char *name;
void (*func)(const void*, void*, size_t);
}copyalgs[] = {
{"bcopy", bcopy},
{"loop_char", loop_char},
{"loop_int", loop_int},
{"loop_4char", loop_4char},
{"loop_16char", loop_16char},
{"loop_256char", loop_256char},
{"loop_4int", loop_4int},
{"duff_char8", duff_char8},
{"byte_copy", byte_copy},
{"bcopy", bcopy},
{"NULL", NULL},
};
bcopy() est présent au début et en fin de la table, juste pour vérifier qu'on n'a pas particulièrement d'effet de cache sur le premier algo de la liste.
loop_xxxx() sont des algos de loop, le xxxxx indique le type de valeur manipulée et la quantité de valeurs manipulées par itération de boucle.
Quelques exemples:
#define LOOP_CHAR_INLINE(src, dst, size){\
char *_s, *_d;\
_s=(char*)src;\
_d=(char*)dst;\
while(size--)\
*_d++=*_s++;\
}
Ca, c'est la version "octet par octet", je l'ai fait en define parce que j'ai bien senti le coup venir: toutes les autres versions vont avoir besoin de ça pour "finir" la copie si la taille n'est pas un multiple de la taille de bloc traitée, et comme j'avais ni envie de faire de copier-coller massif, et que je voulais pas prendre le "risque" de polluer les tests par des appels de fonctions supplémentaires, c'est passé en macro.
Du coup, loop_char(), c'est ça:
void loop_char(const void *src, void *dst, size_t size){
LOOP_CHAR_INLINE(src, dst, size);
}
Et, pour vous donner 2 exemples un peu plus complexes:
void loop_4char(const void *src, void *dst, size_t size){
char *s, *d;
s=(char*)src;
d=(char*)dst;
while(size>4){
*d++=*s++;
*d++=*s++;
*d++=*s++;
*d++=*s++;
size-=4;
}
LOOP_CHAR_INLINE(s, d, size);
}
void loop_4int(const void *src, void *dst, size_t size){
int *s, *d;
s=(int*)src;
d=(int*)dst;
while(size > 4*sizeof(int) ){
*d++=*s++;
*d++=*s++;
*d++=*s++;
*d++=*s++;
size-=4*sizeof(int);
}
LOOP_CHAR_INLINE(s, d, size);
}
duff_char8(), c'est ca:
void duff_char8(const void *src, void *dst, size_t size){
char *s, *d;
s=(char *)src;
d=(char *)dst;
switch (size % 8) /* size > 0 assumed */
{
case 0: do { *d++ = *s++;
case 7: *d++ = *s++;
case 6: *d++ = *s++;
case 5: *d++ = *s++;
case 4: *d++ = *s++;
case 3: *d++ = *s++;
case 2: *d++ = *s++;
case 1: *d++ = *s++;
} while ((size -= 8) > 0);
}
}
Ouais, ça compile. Ca vous la coupe, hein ?
Et, pour reprendre le code exact de notre cher ami D.J., à peine adapté pour pouvoir s'intégrer dans notre procédure de test, on a aussi ça:
void byte_copy(const void *src, void *dst, size_t size)
{
register char *from;
register char *to;
register size_t n;
from=(char *)src;
to=(char *)dst;
n=size;
for (;;) {
if (!n) return; *to++ = *from++; --n;
if (!n) return; *to++ = *from++; --n;
if (!n) return; *to++ = *from++; --n;
if (!n) return; *to++ = *from++; --n;
}
}
Il ne nous manque plus qu'une fonction qui remplit un tableau avec des valeurs "aléatoires":
void init_refbuff(char *buff, size_t size){
while(size--)
*buff++= (size&0xFF) ^((size&0xFF00)>>8);
}
(ok, mon aléa est plus que discutable, c’était surtout pour ne pas avoir un tableau avec que des zéros).
Et bien sur, un programme principal, qui remplit le tableau de référence, et qui teste chaque algo en le chronométrant:
int main(int argc, char **argv){
struct copy_alg_t *alg;
struct timeval starttime, endtime;
int i;
char ref_buff[BUFSIZE];
char dst_buff[BUFSIZE];
init_refbuff(ref_buff, BUFSIZE);
for(alg=copyalgs; alg->func != NULL; alg++){
bzero(dst_buff, BUFSIZE);
printf("Alg %s...", alg->name);
for(i=strlen(alg->name); i<15;i++)
putchar(' ');
gettimeofday(&starttime, NULL);
alg->func(ref_buff, dst_buff, BUFSIZE);
gettimeofday(&endtime, NULL);
if(starttime.tv_usec > endtime.tv_usec){
endtime.tv_usec+=1000000;
endtime.tv_sec--;
}
printf("%10d micros",
(endtime.tv_sec-starttime.tv_sec)*1000000+
endtime.tv_usec-starttime.tv_usec
);
if(memcmp(ref_buff, dst_buff, BUFSIZE))
printf("*** Mismatch !!! ***");
else
printf(" Ok");
}
return 0;
}
Notez quelques points quand même:
- On donne uniquement un résultat en microsecondes.
- On fait un bzero du buffer de destination a chaque fois, "au cas ou".
- On vérifie bien que la copie est conforme à l'original, ça permet de vérifier qu'on s'est pas loutrés dans les implémentations, et qu'elles font toutes ce qu'elles sont censées faire.
Après 2-3 tests rapides, BUFSIZE sera fixé à 16*1024*1024, soit 16 mégaoctets, qui permet d'avoir des tests relativement rapides, mais tout de même facilement mesurables.
Pour ceux qui se diraient "feignasse, le Vanhu, il aurait quand même pu coder vite fait un truc qui les trie et qui les affiche du plus rapide au plus lent", je répondrai juste: "bande de noobs....":
vanhu@darkstar ~/work/c$ make copy vanhu@darkstar ~/work/c$ ./copy |sort -k3 -n Alg bcopy... 15807 micros Ok Alg bcopy... 16139 micros Ok Alg loop_64int... 30093 micros Ok Alg loop_int... 37409 micros Ok Alg loop_4int... 38564 micros Ok Alg loop_256char... 175909 micros Ok Alg duff_char8... 178660 micros Ok Alg loop_4char... 202243 micros Ok Alg loop_16char... 230192 micros Ok Alg byte_copy... 234586 micros Ok Alg loop_char... 245383 micros Ok vanhu@darkstar ~/work/c$
Bien sur, il faut exécuter ca plusieurs fois et faire une moyenne, on constate que certains algos très proches dans le classement ne sont pas toujours classés dans le meme ordre, mais ca donne une bonne idée.
On constate donc:
- Que tous les algos font bien ce qu'on leur demande, c'est déjà ca ! :-)
- loop_char() est bien nettement le plus lent, et se retrouve systématiquement en dernière position.
- byte_copy() fait a peine mieux, alors qu'il utilise pourtant des register, qu'il divise par 4 le nombre de boucles, tout ca..... C'etait bien la peine de réécrire la moitié de la libc...
- loop_xchar() font pas vraiment mieux non plus, sauf peut etre loop_256char(), et encore, pas toujours.
- Meme combat pour duff_char8(), qui arrive quand meme a etre vaguement devant ses potes qui travaillent aussi 8 bits par 8 bits (voire 16 par 16) quand meme.
- On a une grosse accélération dès qu'on passe en int, tout simplement, et la encore, ca change pas des masses qu'on travaille par 1 ou par 64 int (bon, par 64 ints, c'est toujours un poil plus rapide que par 1 ou par 4, qui se valent en moyenne).
- bcopy() met une valise à tout le monde, tout le temps....
Conclusions:
- Vous faites pas chier à recoder la libc, les gars....
- Vaut mieux travailler par mots machine et faire de grosses boucles, que faire du unroll octet par octet.
- Faut vraiment faire un unroll massif pour que ca commence à se sentir sur de grosses données.
- bcopy() met une valise à tout le monde, je sais plus si je l'avais déjà dit....
Forcément, la question que vous vous posez surement, c'est "comment qu'y fait bzero() pour mettre une valise à tout le monde"
Bah simple: il est op-ti-mi-zé, et il sait que, dans son contexte précis, il peut exploiter les possibilités du processeur:
[des trucs qui vont bien pour avoir un programme avec les symboles de déboguage, tout ca chargé dans un gdb]
(gdb) disass bcopy Dump of assembler code for function bcopy:
[des trucs pour gérer les arguments, pour voir si la taille fait pas zero, s'il fait pas trop froid dehors, si on a bien éteint le gaz, tout ca]
0x2812fa97 <bcopy+23>: mov %ecx,%edx 0x2812fa99 <bcopy+25>: shr $0x2,%ecx 0x2812fa9c <bcopy+28>: repz movsl %ds:(%esi),%es:(%edi) 0x2812fa9e <bcopy+30>: mov %edx,%ecx 0x2812faa0 <bcopy+32>: and $0x3,%ecx 0x2812faa3 <bcopy+35>: repz movsb %ds:(%esi),%es:(%edi)
Donc voila, il fait faire sa boucle par le CPU, tout simplement, et ca dépote sa maman.....
Le mois prochain, on causera d'un truc ou il y a pas besoin de foutre des copies de code partout, parceque c'est super galère à faire dans un truc de blog, y'a la moitié du code qui est interprété par le bazar a bidule.