Pour illustrer ça, voici deux codes qui calculent exactement la même chose (un crible d'Eratosthene, un des plus anciens algorithmes s'il en est :-) D'un point de vue algorithmique tout se passe de la même façon, d'un point de vue calculs ils sont très différents.
Sur un intel atom N270 (1.6GHz), la différence est flagrante pour les tailles les plus grosses : (tous deux sont compilés avec gcc 4.3.4 -O3 ; avec gcc-4.4.2 on gagne à peu près 5 à 8 % dans les deux cas)
time ./cache_sieve > result
1234567890
real 0m53.146s
user 0m48.663s
sys 0m0.164
time ././basic_sieve > result
1234567890
real 2m43.930s
user 2m29.473s
sys 0m3.760s
(je vous recommande de rediriger la sortie vers un fichier pour bien mesurer le temps de calcul, sinon tout sera pollué par le temps d'affichage dans la console).
Notons que les accès mémoire du crible d'Eratosthene basique sont relativement simples, et sans doutes faciles à prédire et donc à optimiser par le compilateur et les mécanismes de prefetch du processeur. Dans des applications plus complexes, le gain d'une implémentation optimisée serait certainement encore plus important.
[^] # Re: dbench
Posté par khivapia . En réponse au journal Linux, Gentoo, et gcc dans un bateau.... Évalué à 7.
Pour illustrer ça, voici deux codes qui calculent exactement la même chose (un crible d'Eratosthene, un des plus anciens algorithmes s'il en est :-) D'un point de vue algorithmique tout se passe de la même façon, d'un point de vue calculs ils sont très différents.
crible basique :
http://www.joux.biz/algcrypt/PROGRAMS/Sieve_4-1.html
crible par petits morceaux de 16ko tenant largement dans le cache L1
http://www.joux.biz/algcrypt/PROGRAMS/Sieve_4-2.html
Sur un intel atom N270 (1.6GHz), la différence est flagrante pour les tailles les plus grosses : (tous deux sont compilés avec gcc 4.3.4 -O3 ; avec gcc-4.4.2 on gagne à peu près 5 à 8 % dans les deux cas)
time ./cache_sieve > result
1234567890
real 0m53.146s
user 0m48.663s
sys 0m0.164
time ././basic_sieve > result
1234567890
real 2m43.930s
user 2m29.473s
sys 0m3.760s
(je vous recommande de rediriger la sortie vers un fichier pour bien mesurer le temps de calcul, sinon tout sera pollué par le temps d'affichage dans la console).
Notons que les accès mémoire du crible d'Eratosthene basique sont relativement simples, et sans doutes faciles à prédire et donc à optimiser par le compilateur et les mécanismes de prefetch du processeur. Dans des applications plus complexes, le gain d'une implémentation optimisée serait certainement encore plus important.