Au sujet du Code Bloat

Version imprimable

11/07/2009, 20h41
Invité

Au sujet du Code Bloat

Bonjour,

Je récris actuellement un gros programme, en modifiant du code existant. J'utilise le même environnement et le même compilateur, mais je constate un accroissement rapide de la taille de mon exe. En gros, un programme qui faisait hier 3 Mo en fait aujourd'hui 9, alors que le nombre total de ligne de codes n'a pas changé (il a en fait baissé).

Actuellement, je soupconne fortement la STL. J'utilise pas mal de vector<> sur des types utilisateurs. Comme toute la STL est template, cela signifie beaucoup d'instanciation, mais quand même un triplement du code à fonctionnalités égales?

Avez vous rencontré ce genre de problème? la STL est elle réellement coupable? Comment peut on le résoudre (je n'ai pas du tout envie de finir avec un exe de 20Mo, 5 c'est déjà bien trop...)

Merci d'avance,
Francois
11/07/2009, 23h03
JolyLoic

Y a-t-il beaucoup de vecteurs sur des types vraiment différents(1) ? En théorie, ça pourrait expliquer, même si j'avoue avoir du mal à croire que ça pourrait être aussi impactant... Tu as essayé d'ajouter pour le plaisir un bout de code qui ne fait rien d'autre que d'instancier un vector sur une dizaine de types crées pour la circonstance, histoire de mesurer un delta ?

Un gros accroissement peut apparaître la première fois que l'on utilise les flux dans un programme, mais ce devrait être one shot.

Tu utilises quel compilateur ? Quelles options d'optimisation ?

(1) : Par vraiment différent, je veux dire qu'une bonne implémentation n'aura pas de code bloat supplémentaire pour un vector<B*> si le programme contient déjà un vector<A*>, et on peut espérer que dans le futur, ce soit aussi vrai avec les vector<shared_ptr<A>> et vector<unique_ptr<A>>.
11/07/2009, 23h34
Invité

Citation:

Envoyé par JolyLoic

Y a-t-il beaucoup de vecteurs sur des types vraiment différents(1) ?

Tout à fait... Il doit y avoir une petite centaine de structures distinctes, au total, et des vecteur sur presque chacune. Avec des structures arborescentes de vecteurs de vecteurs...

Citation:

Envoyé par JolyLoic

En théorie, ça pourrait expliquer, même si j'avoue avoir du mal à croire que ça pourrait être aussi impactant... Tu as essayé d'ajouter pour le plaisir un bout de code qui ne fait rien d'autre que d'instancier un vector sur une dizaine de types crées pour la circonstance, histoire de mesurer un delta ?

Je vais effectivement essayer, et poster mes trouvailles sur ce fil, je pense que c'est utile... Pour l'instant, j'ai fait un essai sur un tout petit module (150 lignes de code). Le code était du calcul très proche du C, mais à la fin, pour je ne sais quelle raison, j'avais mis un fill_n (donc un algorithme de la stl)... un seul...

Avec fill_n : code généré ds l'obj: 7k
Sans fill_n : code généré 2k

(cependant, enlever un fill_n par ci par la dans les autres modules représente un petit gain, mais pas aussi spectaculaire, ce serait trop facile!)

Morale provisoire, il y a clairement un coût d'entrée de la STL au niveau du module. Je soupconne que l'un des effets indirects des templates est que le compilateur reinstancie tout ce dont il a besoin pour chaque module, et ca peut être un peu lourd...

Citation:

Envoyé par JolyLoic

Un gros accroissement peut apparaître la première fois que l'on utilise les flux dans un programme, mais ce devrait être one shot.

Des flux j'en avais avant, donc ca ne peut être cela.

Citation:

Envoyé par JolyLoic

Tu utilises quel compilateur ? Quelles options d'optimisation ?

Borland C++ Builder 6.0, options vitesse maxi (mais j'ai aussi teste l'option "debug", sans différence notable), et une STLPort fournie avec le compilateur (donc optimisé, pourrait on croire)

Francois
12/07/2009, 04h42
koala01

Salut,

Fais attention au fait que BCB 6 revendiquait ne pas respecter le standard (et pas uniquement pour la VCL)...

Il n'est donc absolument pas impossible que la version STL port ne soit pas aussi bien optimisé que ce que tu ne semble croire :aie:

Il *semblerait* que les nouvelles versions de BCB tentent de mieux respecter la norme (mais je ne peux absolument pas donner de certitudes sur le sujet) ;)

Ceci dit, il serait intéressant de vérifier sur plusieurs modules (inter) dépendants du premier module sur lequel tu as testé les changements...

*Peut-être* auras tu la chance que seul le module testé ne présente un tel accroissement de poids :question:

Enfin, es-tu sur d'avoir utilisé les mêmes options de compilation :question:

Généralement, on observe effectivement un accroissement (parfois considérable) du poids de l'exécutable en mode débug, du fait de la présence de toutes les informations nécessaires au débuggage, par rapport à la version release...

Mais certaines options de compilations ou certaines habitudes de programmation (comme l'inlining implicite ou explicite de fonction qui ne devraient pas l'être) peuvent également avoir un impact fort malsain sur le poids de l'exécutable ;) ([EDIT]et force est d'avouer que l'utilisation de template de facto l'inlining des fonctions template [/EDIT])
12/07/2009, 11h36
Invité

Citation:

Envoyé par koala01

Fais attention au fait que BCB 6 revendiquait ne pas respecter le standard (et pas uniquement pour la VCL)...

Est ce un problème de standard? Il me semble que celui ci ne parle pas beaucoup de la taille des executables, laissé au compilateur... Ce qui me travaille, c'est que BCB, que j'utilise depuis longtemps, produit en général des exes pas trop gros, sauf dans certains cas précis (appels OLE typiquement).

Citation:

Envoyé par koala01

Ceci dit, il serait intéressant de vérifier sur plusieurs modules (inter) dépendants du premier module sur lequel tu as testé les changements...

En fait, c'est après avoir modifié pas mal de choses que j'ai constaté ce triplement de taille. On avait un code de 3-4Mo environ (pour environ 35 000 lignes de code utilisateur, ie sans les librairies externes), répartis dans 75 modules environ. Pour l'instant seuls les principaux modules ont été touchés par la réorganisation, mais le code approche les 9Mo.

Je vais essayer de rajouter des modifs similaires à celles faites récemment, et voir l'augmentation...

Citation:

Envoyé par koala01

Enfin, es-tu sur d'avoir utilisé les mêmes options de compilation :question:

Oui, en fait, j'ai fait les calculs de comparaison en mode debug et en mode release, sur l'ancien et le nouveau source... Il peut bien sur y avoir une subtilité qui m'échappe, mais j'en doute un peu... (j'observe en fait la hausse lors de modification successives de mon code, sans changement des options)

Citation:

Envoyé par koala01

Généralement, on observe effectivement un accroissement (parfois considérable) du poids de l'exécutable en mode débug, du fait de la présence de toutes les informations nécessaires au débuggage, par rapport à la version release...

Oui, mais chez borland, j'ai repéré que l'augmentation se traduisait au niveau des .obj (modules compilés avant reliure), mais que le relieur avait le bon gout de supprimer ces éléments de l'exe pour les mettre dans un fichiers "annexe" (le tds) utilisé par le debuguer. Du coup, l'exe en mode débug n'est pas vraiment plus gros, voire légèrement plus petit que celui en mode release.

Je comprends que Microsoft suit une voie très différente.

Citation:

Envoyé par koala01

Mais certaines options de compilations ou certaines habitudes de programmation (comme l'inlining implicite ou explicite de fonction qui ne devraient pas l'être) peuvent également avoir un impact fort malsain sur le poids de l'exécutable ;)

C'est mon hypothèse de travail. Je vais continuer à regarder, et essayer de raconter cela sur ce fil. Je soupconne que la situation est assez générique pour n'être pas qu'un pb borland...

En attendant, merci beaucoup pour ces réponses, ça m'aide pas mal.

Francois
12/07/2009, 18h03
JolyLoic

Citation:

Envoyé par fcharton

Oui, mais chez borland, j'ai repéré que l'augmentation se traduisait au niveau des .obj (modules compilés avant reliure), mais que le relieur avait le bon gout de supprimer ces éléments de l'exe pour les mettre dans un fichiers "annexe" (le tds) utilisé par le debuguer. Du coup, l'exe en mode débug n'est pas vraiment plus gros, voire légèrement plus petit que celui en mode release.

Ce ne sont pas tant les informations de debug que le fait que l'inlining ne soit pas possible qui modifie le plus la taille des exécutable debug, surtout avec un style de programmation où plein d'appels de fonctions s'imbriquent comme le template metaprogramming pousse à le faire. J'ai déjà eu des explosions de stack en debug, alors qu'en release, j'en était très loin, avec boost.serialization, par exemple.
12/07/2009, 18h12
Silverstone

Peut-être as-tu un léger problème de conception dans ton programme...

Moi j'utilise Visual c++ et j'ai toujours eu l'impression que les exécutables étaient particulièrement optimisés en taille (même avec l'option "vitesse maximale").
17/07/2009, 19h03
deadalnix

Non mais il y a forcément un truc qui débloque.

Pour générer 6Mo de rab au niveau de l'exécutable, ou bien du fait dans la métaprogramation très massive (template récursives, ce genre de trucs), ou bien tu as soucis dans le compilo.

A mon avis tu as une option de compilation qui fait exploser la taille de ton exe. C'est ce qui me parait le plus probable.
17/07/2009, 22h03
Invité

Je ne crois pas que ce soit une option de compilation: j'ai fait l'essai avec les mêmes options (sur les deux versions du code, avant et après), et pour plusieurs jeux d'options (de debug à optimisé...)

Maintenant, et après un peu d'analyse je commence à mieux comprendre.

Effectivement, toute l'augmentation ne venait pas du code. Une partie venait apparemment de ressources (images en fait) stockées de façon différentes dans les deux programmes (l'une inefficace...).

En ce qui concerne le code, j'ai commencé à faire la chasse à la STL inutile, dans les headers d'abord, puis les algorithmes qui n'apportent rien (typiquement fill et copy sur types natifs), puis les types utilisateurs redondants (structures identiques définis comme classes différentes, et STL dessus), et enfin les conteneurs inutiles (vecteur de taille fixe et connue à la compilation, ce genre de choses).

Sur les seules parties de codes modifiées cette semaines (quelques centaines de lignes réécrites, je pense), j'arrive à une baisse de 10% de la taille de l'exe... Voire, sur des fonctions appelées souvent, l'élimination de la STL se traduit souvent par un gain de performance...

Je commence à douter de l'efficacité (au moins dans l'environnement que j'utilise) de la STL, en terme de vitesse et de taille de code produit. C'est bien évidemment un excellent outil de prototypage, mais sur du vrai code qui tourne vite?

Francois
17/07/2009, 22h23
Luc Hermitte

Même si elles pourraient en être capables, je ne connais pas de SL qui remplace copy/fill sur les types natifs par les appels à memcpy/memset qui vont bien.
17/07/2009, 22h33
Invité

Je viens de regarder, celle que j'utilise (STL Port 4.5, distribuée avec Borland Builder 6) a en fait une spécialisation des template fill et fill_n pour les types mono-octet (signed char, unsigned char et char), qui utilise memset.

Francois
17/07/2009, 22h50
Luc Hermitte

Au temps pour moi alors.
Et tu te retrouves quand même avec un truc plus gros ? Tu fais du fill sur des int, des choses comme ça ?
18/07/2009, 09h53
Invité

Oui, en fait, à un moment j'avais pris l'habitude d'écrire des

Code:

fill_n(tab,tab+taille,0)

ou des choses du genre pour initialiser des tableaux (généralement d'int, parfois d'unsigned short)

L'exemple que je cite plus haut est extrème (mais bien réel malheureusement). Il s'agit d'un module de 150 lignes de C qui implémente un décodeur arithmétique (c'est à dire une série de fonctions qui lisent des données compactées par codage arithmétique).

L'interface du module ressemblait donc à cela :

Code:

void decode_var(int nind,int *res,unsigned char *ptr)

nind étant le nombre de données à décoder, res un tableau destiné à recevoir les données (pré-alloué), et ptr un pointeur du le début des données codées.

Or, il y avait à la fin un gestionnaire de cas particulier qui, soit en cas d'erreur de lecture, soit pour une certaine valeur de l'entête des données d'entrée, renvoyait un tableau initialisé par une constante. Implémenté comme

Code:

else fill_n(res,nind,vdef);

C'était le seul appel à la STL, avec donc un #include <algorithm> en haut du fichier...

Cet appel (remplacé maintenant par un bête for(int i=0;i<nind;i++) res[i]=vdef;) se traduisait par un triplement de la taille de l'obj compilé (qui passait en mode optimisé, de 2 à 7k), rien de dramatique à l'échelle du programme, mais tout à fait exemplaire, je crois...

Francois
18/07/2009, 14h30
Goten

Ca serait très intéressant d'essayer sur un voir plusieurs autres compilo, car il est vrai que la STL fourni avec borland est assez exotique je crois.
18/07/2009, 14h56
Luc Hermitte

Autant je comprends que l'on ait du code bloat à utiliser std::fill au lieu de memset, en revanche je ne comprends pas que l'on en ait à utiliser std::fill au lieu d'une boucle for sur indices codée à la main.
Cela sens le mauvais compilo -- maintenant BCB est un ancien ...

Citation:

Envoyé par Luc Hermitte

Cela sens le mauvais compilo -- maintenant BCB est un ancien ...

A mon avis, l'importance de l'augmentation constatée semble indiquer que BCB, quand il utilise la STL, inclut dans le code tout un tas de choses qui ne lui servent pas... (même mal optimisé un unique appel à fill_n ne peut générer plusieurs kilo-octets de code machine).

Ceci est à rapprocher de l'"overhead iostream" dont on a parlé précédemment...

En terme de vitesse, BCB fonctionne correctement. J'ai plusieurs fois essayé de le remplacer, en le comparant sur des programmes "calcul pur" avec GCC et Visual, et honnêtement, je n'ai jamais vu de différence spectaculaire. Il semblerait donc qu'ils ne soient pas aussi bien sur la taille...

Si d'autres ont le temps de tester d'autres compilateurs sur des cas simples comme celui ci, je suis preneur...

Sur le même thème, j'ai repéré une autre curiosité (que j'enjoins les utilisateurs d'autres compilateurs à tester...). J'ai quelque part un code qui ressemble à cela
Code:

1 2 3 4 5 6 7 8 9 int *Src=new int[nind]; int *Res=new int[nind]; vector<int> Val(nb); ... for(int i=0;i<nind;i++) { Res[i]=0; for(int j=0;j<nb;j++) if(Src[i]==Val[j]) {Res[i]=1;break;} }
En gros, cela prend un tableau Src, et cela renvoie un tableau qui indique, pour chaque élément de Src, s'il appartient aux éléments du vecteur Val

(je mets des tableaux pour isoler le comportement que je veux mettre en évidence...)

J'observe, toujours sous Borland, que si j'utilise
Code:

1 2 3 4 5 6 7 8 9 10 int *Src=new int[nind]; int *Res=new int[nind]; vector<int> Val(nb); ... int *ptr=&Val[0]; for(int i=0;i<nind;i++) { Res[i]=0; for(int j=0;j<nb;j++) if(Src[i]==ptr[j]) {Res[i]=1;break;} }
Mon code tourne un peu (environ 15% en fait) plus vite...

Je suis donc assez d'accord avec Luc, BCB 6 a presque 10 ans, il est donc assez vraisemblable que les optimisations nécessaires à l'utilisation intensive de la STL, des templates, et autres nouveautés relatives, y soit mal gérée...

(maintenant, c'est aussi un outil très puissant quand on veut faire de l'interface... alors...)

Goten, la STL est une STLPort, donc un truc assez mainstream, en fait... Je doute qu'elle soit en cause (surtout pour fill et fill_n qui sont peut être les trucs les plus bateaux qui soient...)

Francois

Citation:

Envoyé par fcharton

Sur le même thème, j'ai repéré une autre curiosité (que j'enjoins les utilisateurs d'autres compilateurs à tester...).

J'en suis. :ccool:
On peux tester très précisément la pénalité imposée par les itérateurs par rapport aux pointeurs nus grâce au benchmark d'adobe.

Il suffit de dézipper l'archive et de lancer le test contenu dans stepanov_vector.cpp. C'est une extension au fameux benchmarck de "pénalité d'abstraction" crée par Stepanov, le concepteur de la STL.

Citation:

Envoyé par stepanov_vector.cpp

Goal: examine any change in performance when moving from pointers to vector iterators

Assumptions:
1) Vector iterators should not perform worse than raw pointers.

Programmers should never be tempted to write
std::sort( &*vec.begin(), &*( vec.begin() + vec.size() ) )
instead of
std::sort( vec.begin(), vec.end() )

HIstory:
This is an extension to Alex Stepanov's original abstraction penalty benchmark
to test the compiler vendor implementation of vector iterators.

Mes résultats avec Visual Studio 10 beta 1 :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
 
C
 
test                            description   absolute   operations   ratio with
number                                        time       per second   test0
 
 0                 "double pointer verify2"   3.77 sec   796.60 M     1.00
 1                 "double vector iterator"   3.81 sec   786.99 M     1.01
 2                 "double pointer reverse"   3.81 sec   786.78 M     1.01
 3         "double vector reverse_iterator"   3.83 sec   783.70 M     1.02
 4         "double vector iterator reverse"   3.81 sec   786.99 M     1.01
 5         "double pointer reverse reverse"   3.81 sec   786.78 M     1.01
 6 "double vector reverse_iterator reverse"   3.81 sec   786.99 M     1.01
 7 "double vector iterator reverse reverse"   3.81 sec   786.78 M     1.01
 
Total absolute time for Vector accumulate: 30.47 sec
 
Vector accumulate Penalty: 1.01
 
 
test                                           description   absolute   operations   ratio with
number                                                       time       per second   test0
 
 0                 "insertion_sort double pointer verify2"   1.44 sec    2.09 M     1.00
 1                 "insertion_sort double vector iterator"   1.44 sec    2.09 M     1.00
 2                 "insertion_sort double pointer reverse"   1.41 sec    2.13 M     0.98
 3         "insertion_sort double vector reverse_iterator"   1.41 sec    2.13 M     0.98
 4         "insertion_sort double vector iterator reverse"   1.42 sec    2.11 M     0.99
 5         "insertion_sort double pointer reverse reverse"   1.44 sec    2.09 M     1.00
 6 "insertion_sort double vector reverse_iterator reverse"   1.50 sec    2.00 M     1.04
 7 "insertion_sort double vector iterator reverse reverse"   1.49 sec    2.02 M     1.03
 
Total absolute time for Vector Insertion Sort: 11.53 sec
 
Vector Insertion Sort Penalty: 1.00
 
 
test                                      description   absolute   operations   ratio with
number                                                  time       per second   test0
 
 0                 "quicksort double pointer verify2"   2.16 sec   11.13 M     1.00
 1                 "quicksort double vector iterator"   2.23 sec   10.74 M     1.04
 2                 "quicksort double pointer reverse"   2.17 sec   11.05 M     1.01
 3         "quicksort double vector reverse_iterator"   2.16 sec   11.13 M     1.00
 4         "quicksort double vector iterator reverse"   2.17 sec   11.05 M     1.01
 5         "quicksort double pointer reverse reverse"   2.23 sec   10.74 M     1.04
 6 "quicksort double vector reverse_iterator reverse"   2.23 sec   10.74 M     1.04
 7 "quicksort double vector iterator reverse reverse"   2.23 sec   10.74 M     1.04
 
Total absolute time for Vector Quicksort: 17.59 sec
 
Vector Quicksort Penalty: 1.02
 
 
test                                      description   absolute   operations   ratio with
number                                                  time       per second   test0
 
 0                 "heap_sort double pointer verify2"   2.05 sec   11.72 M     1.00
 1                 "heap_sort double vector iterator"   2.20 sec   10.89 M     1.08
 2                 "heap_sort double pointer reverse"   2.73 sec    8.78 M     1.34
 3         "heap_sort double vector reverse_iterator"   2.81 sec    8.53 M     1.37
 4         "heap_sort double vector iterator reverse"   2.72 sec    8.83 M     1.33
 5         "heap_sort double pointer reverse reverse"   2.22 sec   10.82 M     1.08
 6 "heap_sort double vector reverse_iterator reverse"   2.22 sec   10.82 M     1.08
 7 "heap_sort double vector iterator reverse reverse"   2.22 sec   10.82 M     1.08
 
Total absolute time for Vector Heap Sort: 19.17 sec
 
Vector Heap Sort Penalty: 1.19

Résutats:
L'implémentation de Visual Studio est plutôt bonne sur ce point et réussi à supprimer quasiment toute trace d'overhead dans le passage pointeur nu/itérateur.

Reste à examiner les résultats avec d'autres compilateurs, en particulier, avec BCB.

18/07/2009, 23h23
Invité

Merci beaucoup Arzar!

Je viens de faire le test sur borland 6, et c'est effectivement assez violent...

Juste pour la comparaison pointeurs nus itérateurs (sans les reverse et tout le reste), je trouve (en optimisé) un écart de

21% pour accumulate
55% pour insertion_sort
14% pour quick_sort
21% pour heapsort

Et quand on va vers des combinaisons plus complexes, ca tourne vite au massacre...

J'ai également fait le test avec GCC+MingW32, et je trouve des performances correctes, mais pas aussi bonnes que la version de Visual que tu as postée...

En gros, sous gcc il n'y a pas de penalité pour un itérateur normal, sauf sur quicksort (pénalité de 26% !), et on a des pénalités importantes (30 à 60%) pour des itérateurs inverses.

J'essaierai de tester Borland 2007 et une version plus ancienne de Visual lundi... Ce qui me travaille, c'est que l'on peut apparemment avoir des problèmes même avec des compilateurs assez récents.

Francois

Quelle version de gcc? Faudra que je teste avec la 4.4
Btw j'ai testé avec visual studio 2008 j'obtiens des résultats assez bizarre rien que pour l'accumulate sur un simple iterator :
pointer : 3,58 secondes
iterator : 40 secondes ...

Et pareil pour tout les autres j'ai arrêter à accumulate d'ailleurs parce que bon... ça prenais trop de temps XD. Bon j'utilise pas du tout visual au quotidien alors je fais peut être quelque chose mal.... toujours est-il que je suis en release et l'optimisation en /02 ...
Trop fatigué ce soir je verrais demain à tête reposé, mais il semble que j'obtienne les mêmes résultats sous VS2010 ...

EDIT: ça me tracasse trop pour dormir donc voilà mes résultats sous VS2008 et en baissant int iterations à 150000 afin d'avoir des temps proche d'une seconde. (parce que 40 secondes c'est pas possible m ais je comprends quand même pas.) Les ratios reste les mêmes qu'avec 10 fois plus d'itérations :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
 
c:\Documents and Settings\Goten\Mes documents\Visual Studio 2008\Projects\bench\
Release\bench.exe
 
test                            description   absolute   operations   ratio with
 
number                                        time       per second   test0
 
 0                 "double pointer verify2"   0.34 sec   872.09 M     1.00
 1                 "double vector iterator"   4.23 sec   70.85 M     12.31
 2                 "double pointer reverse"   0.36 sec   833.33 M     1.05
 3         "double vector reverse_iterator"   4.88 sec   61.54 M     14.17
 4         "double vector iterator reverse"   4.89 sec   61.35 M     14.22
 5         "double pointer reverse reverse"   0.36 sec   833.33 M     1.05
 6 "double vector reverse_iterator reverse"   5.17 sec   58.02 M     15.03
 7 "double vector iterator reverse reverse"   5.09 sec   58.89 M     14.81
 
Total absolute time for Vector accumulate: 25.33 sec
 
Vector accumulate Penalty: 6.70
 
 
test                                           description   absolute   operations   ratio
 with
number                                                       time       per second   test0
 
 
 0                 "insertion_sort double pointer verify2"   0.19 sec    1.60 M     1.00
 1                 "insertion_sort double vector iterator"   2.34 sec    0.13 M     12.46
 2                 "insertion_sort double pointer reverse"   0.19 sec    1.60 M     1.00
 3         "insertion_sort double vector reverse_iterator"   3.61 sec    0.08 M     19.20
 4         "insertion_sort double vector iterator reverse"   3.59 sec    0.08 M     19.12
 5         "insertion_sort double pointer reverse reverse"   0.20 sec    1.48 M     1.08
 6 "insertion_sort double vector reverse_iterator reverse"   4.70 sec    0.06 M     25.02
 7 "insertion_sort double vector iterator reverse reverse"   4.72 sec    0.06 M     25.10
 
Total absolute time for Vector Insertion Sort: 19.55 sec
 
Vector Insertion Sort Penalty: 8.46
 
 
test                                      description   absolute   operations   ratio with
 
number                                                  time       per second   test0
 
 0                 "quicksort double pointer verify2"   0.20 sec   11.82 M     1.00
 1                 "quicksort double vector iterator"   0.63 sec    3.84 M     3.08
 2                 "quicksort double pointer reverse"   0.22 sec   10.96 M     1.08
 3         "quicksort double vector reverse_iterator"   0.83 sec    2.90 M     4.08
 4         "quicksort double vector iterator reverse"   0.83 sec    2.90 M     4.08
 5         "quicksort double pointer reverse reverse"   0.22 sec   10.96 M     1.08
 6 "quicksort double vector reverse_iterator reverse"   1.05 sec    2.29 M     5.16
 7 "quicksort double vector iterator reverse reverse"   1.06 sec    2.26 M     5.23
 
Total absolute time for Vector Quicksort: 5.03 sec
 
Vector Quicksort Penalty: 2.87
 
 
test                                      description   absolute   operations   ratio with
 
number                                                  time       per second   test0
 
 0                 "heap_sort double pointer verify2"   0.20 sec   11.82 M     1.00
 1                 "heap_sort double vector iterator"   0.89 sec    2.69 M     4.39
 2                 "heap_sort double pointer reverse"   0.25 sec    9.60 M     1.23
 3         "heap_sort double vector reverse_iterator"   1.28 sec    1.87 M     6.31
 4         "heap_sort double vector iterator reverse"   1.25 sec    1.92 M     6.16
 5         "heap_sort double pointer reverse reverse"   0.22 sec   10.96 M     1.08
 6 "heap_sort double vector reverse_iterator reverse"   1.56 sec    1.54 M     7.70
 7 "heap_sort double vector iterator reverse reverse"   1.55 sec    1.55 M     7.62
 
Total absolute time for Vector Heap Sort: 7.20 sec
 
Vector Heap Sort Penalty: 3.88

19/07/2009, 00h19
Invité

gcc 3.4.5, je crois.

Pour Visual, il doit y avoir un paramètre de compilation qui pose pb (t'es sur que tu es en release? ou que tu n'utilises pas une version "debug" de la stl?) Parce qu'un rapport de 1 à 12 pour une opération comme accumulate (qui se contente d'incrémenter et de déréférencer), ca parait gros, quand même...

Francois

Bas écoute j'ai pourtant bien générer la solution release. Après pour la STL normalement ça link avec une version release non? J'ai MSVC installé, je me demande encore pourquoi.. x)

Sinon voilà mes résultats sous mingw (gcc 3.4.5):

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
 
 
test                            description   absolute   operations   ratio with
number                                        time       per second   test0
 
 0                 "double pointer verify2"   3.72 sec   806.67 M     1.00
 1                 "double vector iterator"   3.56 sec   842.22 M     0.96
 2                 "double pointer reverse"   3.59 sec   834.72 M     0.97
 3         "double vector reverse_iterator"   8.03 sec   373.55 M     2.16
 4         "double vector iterator reverse"   8.05 sec   372.81 M     2.16
 5         "double pointer reverse reverse"   3.63 sec   827.59 M     0.97
 6 "double vector reverse_iterator reverse"   7.44 sec   403.39 M     2.00
 7 "double vector iterator reverse reverse"   7.45 sec   402.47 M     2.00
 
Total absolute time for Vector accumulate: 45.47 sec
 
Vector accumulate Penalty: 1.50
 
 
test                                           description   absolute   operations   ratio
 with
number                                                       time       per second   test0
 
 
 0                 "insertion_sort double pointer verify2"   1.95 sec    1.54 M     1.00
 1                 "insertion_sort double vector iterator"   1.97 sec    1.52 M     1.01
 2                 "insertion_sort double pointer reverse"   3.00 sec    1.00 M     1.54
 3         "insertion_sort double vector reverse_iterator"   2.56 sec    1.17 M     1.31
 4         "insertion_sort double vector iterator reverse"   2.56 sec    1.17 M     1.31
 5         "insertion_sort double pointer reverse reverse"   3.09 sec    0.97 M     1.58
 6 "insertion_sort double vector reverse_iterator reverse"   2.84 sec    1.05 M     1.46
 7 "insertion_sort double vector iterator reverse reverse"   2.83 sec    1.06 M     1.45
 
Total absolute time for Vector Insertion Sort: 20.81 sec
 
Vector Insertion Sort Penalty: 1.37
 
 
test                                      description   absolute   operations   ratio with
 
number                                                  time       per second   test0
 
 0                 "quicksort double pointer verify2"   2.33 sec   10.31 M     1.00
 1                 "quicksort double vector iterator"   2.84 sec    8.44 M     1.22
 2                 "quicksort double pointer reverse"   2.69 sec    8.93 M     1.15
 3         "quicksort double vector reverse_iterator"   2.69 sec    8.93 M     1.15
 4         "quicksort double vector iterator reverse"   2.69 sec    8.93 M     1.15
 5         "quicksort double pointer reverse reverse"   2.89 sec    8.30 M     1.24
 6 "quicksort double vector reverse_iterator reverse"   2.88 sec    8.35 M     1.23
 7 "quicksort double vector iterator reverse reverse"   2.84 sec    8.44 M     1.22
 
Total absolute time for Vector Quicksort: 21.84 sec
 
Vector Quicksort Penalty: 1.20
 
 
test                                      description   absolute   operations   ratio with
 
number                                                  time       per second   test0
 
 0                 "heap_sort double pointer verify2"   2.23 sec   10.74 M     1.00
 1                 "heap_sort double vector iterator"   2.22 sec   10.82 M     0.99
 2                 "heap_sort double pointer reverse"   3.11 sec    7.72 M     1.39
 3         "heap_sort double vector reverse_iterator"   3.27 sec    7.35 M     1.46
 4         "heap_sort double vector iterator reverse"   3.27 sec    7.35 M     1.46
 5         "heap_sort double pointer reverse reverse"   2.52 sec    9.54 M     1.13
 6 "heap_sort double vector reverse_iterator reverse"   2.75 sec    8.73 M     1.23
 7 "heap_sort double vector iterator reverse reverse"   2.67 sec    8.98 M     1.20
 
Total absolute time for Vector Heap Sort: 22.03 sec
 
Vector Heap Sort Penalty: 1.25

Voilà enfin des résultats cohérents. Sachant que c'est obtenu avec le nombre d'itérations par défaut soit 10 fois plus que ce que j'ai utilisé sous VS, ça confirme bien que y'a un problème avec ma compilation sous VS.

Demain je ferais sur gcc 4.4.x sous nux.

19/07/2009, 00h26
Invité

Tes résultats sous mingw sont les mêmes que les miens.

Pour Visual, je me souviens d'un problème rencontré par un collègue, qui avait essayé de remplacer la version STL livrée avec son compilateur par une autre, et avait constaté ce genre de ralentissement. Faudrait que je lui demande...

Francois
19/07/2009, 00h51
Arzar

Citation:

Envoyé par Goten

Quelle version de gcc? Faudra que je teste avec la 4.4
Btw j'ai testé avec visual studio 2008 j'obtiens des résultats assez bizarre rien que pour l'accumulate sur un simple iterator :
pointer : 3,58 secondes
iterator : 40 secondes ...

_HAS_ITERATOR_DEBUGGING=0 et _SECURE_SCL=0 :mrgreen:
Sinon, dans un bench qui teste en profondeur la différence pointeur/itérateur ça fait des dégâts....

Ah bas oui de suite... Enfin dans ma tête ce genre de chose (de ce que j'ai lu ça check que les itérateurs soient pas hors limite du container) en release ça devrait être passez automatiquement à zéro non?

Voilà donc les résultats sous VS2008 fchartron :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
 
c:\Documents and Settings\Goten\Mes documents\Visual Studio 2008\Projects\bench\
Release\bench.exe
 
test                            description   absolute   operations   ratio with
number                                        time       per second   test0
 
 0                 "double pointer verify2"   3.52 sec   853.24 M     1.00
 1                 "double vector iterator"   3.56 sec   842.22 M     1.01
 2                 "double pointer reverse"   3.56 sec   841.99 M     1.01
 3         "double vector reverse_iterator"   3.59 sec   834.96 M     1.02
 4         "double vector iterator reverse"   3.56 sec   841.99 M     1.01
 5         "double pointer reverse reverse"   3.58 sec   838.46 M     1.02
 6 "double vector reverse_iterator reverse"   3.56 sec   841.99 M     1.01
 7 "double vector iterator reverse reverse"   3.53 sec   849.62 M     1.00
 
Total absolute time for Vector accumulate: 28.47 sec
 
Vector accumulate Penalty: 1.01
 
 
test                                           description   absolute   operations   ratio
 with
number                                                       time       per second   test0
 
 
 0                 "insertion_sort double pointer verify2"   1.94 sec    1.55 M     1.00
 1                 "insertion_sort double vector iterator"   1.91 sec    1.57 M     0.98
 2                 "insertion_sort double pointer reverse"   1.86 sec    1.61 M     0.96
 3         "insertion_sort double vector reverse_iterator"   1.86 sec    1.61 M     0.96
 4         "insertion_sort double vector iterator reverse"   1.91 sec    1.57 M     0.98
 5         "insertion_sort double pointer reverse reverse"   1.91 sec    1.57 M     0.98
 6 "insertion_sort double vector reverse_iterator reverse"   1.89 sec    1.59 M     0.98
 7 "insertion_sort double vector iterator reverse reverse"   1.91 sec    1.57 M     0.98
 
Total absolute time for Vector Insertion Sort: 15.17 sec
 
Vector Insertion Sort Penalty: 0.98
 
 
test                                      description   absolute   operations   ratio with
 
number                                                  time       per second   test0
 
 0                 "quicksort double pointer verify2"   2.08 sec   11.55 M     1.00
 1                 "quicksort double vector iterator"   2.16 sec   11.13 M     1.04
 2                 "quicksort double pointer reverse"   2.16 sec   11.13 M     1.04
 3         "quicksort double vector reverse_iterator"   2.16 sec   11.13 M     1.04
 4         "quicksort double vector iterator reverse"   2.14 sec   11.21 M     1.03
 5         "quicksort double pointer reverse reverse"   2.14 sec   11.21 M     1.03
 6 "quicksort double vector reverse_iterator reverse"   2.16 sec   11.13 M     1.04
 7 "quicksort double vector iterator reverse reverse"   2.14 sec   11.21 M     1.03
 
Total absolute time for Vector Quicksort: 17.13 sec
 
Vector Quicksort Penalty: 1.03
 
 
test                                      description   absolute   operations   ratio with
 
number                                                  time       per second   test0
 
 0                 "heap_sort double pointer verify2"   1.97 sec   12.20 M     1.00
 1                 "heap_sort double vector iterator"   2.13 sec   11.29 M     1.08
 2                 "heap_sort double pointer reverse"   2.61 sec    9.20 M     1.33
 3         "heap_sort double vector reverse_iterator"   2.77 sec    8.68 M     1.40
 4         "heap_sort double vector iterator reverse"   2.75 sec    8.73 M     1.40
 5         "heap_sort double pointer reverse reverse"   2.13 sec   11.29 M     1.08
 6 "heap_sort double vector reverse_iterator reverse"   2.16 sec   11.13 M     1.10
 7 "heap_sort double vector iterator reverse reverse"   2.13 sec   11.29 M     1.08
 
Total absolute time for Vector Heap Sort: 18.63 sec
 
Vector Heap Sort Penalty: 1.20

Tout aussi bon :).

21/07/2009, 21h14
Silverstone

Visual c++ est de loin le meilleur compilateur pour Windows (d'après ce que j'ai pu constater).

Citation:

Envoyé par Luc Hermitte

Cela sens le mauvais compilo -- maintenant BCB est un ancien ...

Je pense qu'il a fait son temps, qu'il repose en paix à présent...
21/07/2009, 22h08
Invité

D'après tous les benchmarks que j'ai pu lire, le meilleur compilateur pour Windows, en termes de vitesse du code produit, c'est celui d'Intel (qui utilise, il est vrai, Visual comme front end).

Pour le reste, la notion de "meilleur" est très subjective. En ce qui me concerne, il sera nettement plus facile de lâcher la STL (que j'utilise plus souvent pour "faire moderne" que parce que j'en ai réellement besoin) que BCB (autour duquel s'organise mon interface...) Et BCB6, tout vieillot qu'il soit reste "mon meilleur" compilateur, parce que c'est celui sous lequel je développe le plus efficacement (NB j'ai également Visual et GCC, et je les utilise de temps en temps)

Francois
21/07/2009, 22h17
Invité

Je me rends compte que je n'ai pas remercié les testeurs bénévoles... Merci beaucoup à vous. A charge de revanche !

Francois
21/07/2009, 22h26
Silverstone

Citation:

Envoyé par fcharton

D'après tous les benchmarks que j'ai pu lire, le meilleur compilateur pour Windows, en termes de vitesse du code produit, c'est celui d'Intel (qui utilise, il est vrai, Visual comme front end).

Oui mais je suppose qu'il ne marche que pour les processeurs Intel, ce qui rend la chose plus facile ;) .
21/07/2009, 22h53
Goten

Citation:

Envoyé par Silverstone

Oui mais je suppose qu'il ne marche que pour les processeurs Intel, ce qui rend la chose plus facile ;) .

Non non.. le code produit marche aussi sur amd. Après pour autre chose que le x86 je sais pas du tout.

Citation:

Envoyé par Silverstone

Oui mais je suppose qu'il ne marche que pour les processeurs Intel, ce qui rend la chose plus facile .

?
Le code compilé par ICC tourne sur n'importe quel processeur x86. Ça serait un peu bête d'obtenir des programmes qui se limiteraient à la moitié des pc du marché, non ? Par contre, bien sur, ICC produit du code particulièrement optimisé pour les processeurs intels.

Citation:

Envoyé par fcharton

D'après tous les benchmarks que j'ai pu lire, le meilleur compilateur pour Windows, en termes de vitesse du code produit, c'est celui d'Intel (qui utilise, il est vrai, Visual comme front end).

Je viens justement de tester la démo de la dernière version d'ICC 11.1.
Il est en effet tout aussi bon.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
 
C:\Documents and Settings\Thomas Petit\My Documents\Visual Studio 2008\Projects\Benchmark\Release\Benchmark.exe
 
test                            description   absolute   operations   ratio with
number                                        time       per second   test0
 
 0                 "double pointer verify2"   0.95 sec   3147.95 M     1.00
 1                 "double vector iterator"   0.95 sec   3147.95 M     1.00
 2                 "double pointer reverse"   1.55 sec   1939.24 M     1.62
 3         "double vector reverse_iterator"   1.58 sec   1901.14 M     1.66
 4         "double vector iterator reverse"   1.63 sec   1846.15 M     1.71
 5         "double pointer reverse reverse"   0.95 sec   3147.95 M     1.00
 6 "double vector reverse_iterator reverse"   0.95 sec   3147.95 M     1.00
 7 "double vector iterator reverse reverse"   0.97 sec   3095.98 M     1.02
 
Total absolute time for Vector accumulate: 9.53 sec
 
Vector accumulate Penalty: 1.25
 
 
test                                           description   absolute   operations   ratio with
number                                                       time       per second   test0
 
 0                 "insertion_sort double pointer verify2"   1.51 sec    1.98 M     1.00
 1                 "insertion_sort double vector iterator"   1.33 sec    2.26 M     0.88
 2                 "insertion_sort double pointer reverse"   1.91 sec    1.57 M     1.26
 3         "insertion_sort double vector reverse_iterator"   1.30 sec    2.31 M     0.86
 4         "insertion_sort double vector iterator reverse"   1.30 sec    2.31 M     0.86
 5         "insertion_sort double pointer reverse reverse"   1.31 sec    2.29 M     0.87
 6 "insertion_sort double vector reverse_iterator reverse"   1.30 sec    2.31 M     0.86
 7 "insertion_sort double vector iterator reverse reverse"   1.31 sec    2.29 M     0.87
 
Total absolute time for Vector Insertion Sort: 11.27 sec
 
Vector Insertion Sort Penalty: 0.91
 
 
test                                      description   absolute   operations   ratio with
number                                                  time       per second   test0
 
 0                 "quicksort double pointer verify2"   1.95 sec   12.28 M     1.00
 1                 "quicksort double vector iterator"   2.16 sec   11.13 M     1.10
 2                 "quicksort double pointer reverse"   2.20 sec   10.89 M     1.13
 3         "quicksort double vector reverse_iterator"   2.13 sec   11.29 M     1.09
 4         "quicksort double vector iterator reverse"   2.13 sec   11.29 M     1.09
 5         "quicksort double pointer reverse reverse"   2.09 sec   11.46 M     1.07
 6 "quicksort double vector reverse_iterator reverse"   2.16 sec   11.13 M     1.10
 7 "quicksort double vector iterator reverse reverse"   2.14 sec   11.21 M     1.10
 
Total absolute time for Vector Quicksort: 16.95 sec
 
Vector Quicksort Penalty: 1.10
 
 
test                                      description   absolute   operations   ratio with
number                                                  time       per second   test0
 
 0                 "heap_sort double pointer verify2"   1.97 sec   12.20 M     1.00
 1                 "heap_sort double vector iterator"   2.20 sec   10.89 M     1.12
 2                 "heap_sort double pointer reverse"   2.23 sec   10.74 M     1.14
 3         "heap_sort double vector reverse_iterator"   2.00 sec   12.00 M     1.02
 4         "heap_sort double vector iterator reverse"   2.00 sec   12.00 M     1.02
 5         "heap_sort double pointer reverse reverse"   2.25 sec   10.67 M     1.14
 6 "heap_sort double vector reverse_iterator reverse"   2.28 sec   10.52 M     1.16
 7 "heap_sort double vector iterator reverse reverse"   2.30 sec   10.45 M     1.17
 
Total absolute time for Vector Heap Sort: 17.23 sec
 
Vector Heap Sort Penalty: 1.11

Il est quand même un peu moins "stable" que MSVC sur la pénalité d'abstraction. Alors que MSVC aligne les 1.0 imperturbablement, ICC dérape de temps en temps.

Deux petites particularités intéressantes :
1) Il éclate complètement MSVC 10 sur le premier test "Vector accumulate". Sur mon pc, on passe de 30 secondes à 10 secondes et de 796.60 M à 3147.95 M d'opérations par secondes ! Le timing des autres tests est par contre à peu près identique... Bizarre...

2) Pour le deuxième test, ICC donne des "pénalités" d'abstraction de 1.00, 0.88, 1.26, 0.86, 0.86, 0.87, 0.86, 0.87 pour un total de .... 0.91 ! :fou:
C'est un mystère complet pour moi. Je ne comprends pas du tout comment un compilateur peut faire une meilleure optimisation avec un itérateur qu'avec un pointeur, même dans les cas les plus tordus, car sous Visual Studio ICC utilise la STL de microsoft, qui définit un itérateur de vecteur peu ou prou comme ceci :

Code:

1
2
3
4
5
6
7
8
9
10
 
template <typename T>
class Vector_Iterator
{
public:
// plein de fonction.... operator *, operator ++, operator --,  etc
 
private:
   T* _Ptr;
}

:koi:

21/07/2009, 23h03
Silverstone

Citation:

Envoyé par Arzar

Par contre, bien sur, ICC produit du code particulièrement optimisé pour les processeurs intels.

Oui donc ça n'est valable que pour les processeurs Intel ;) . En tout cas en ce qui concerne les optimisations (ce qui rend la chose plus facile)...

Citation:

Envoyé par Arzar

Alors que MSVC aligne les 1.0 imperturbablement, ICC dérape de temps en temps.

Il était sur une patinoire ? Ca pourrait expliquer ;) .
22/07/2009, 01h56
Invité

Citation:

Envoyé par Arzar

?
1) Il éclate complètement MSVC 10 sur le premier test "Vector accumulate". Sur mon pc, on passe de 30 secondes à 10 secondes et de 796.60 M à 3147.95 M d'opérations par secondes ! Le timing des autres tests est par contre à peu près identique... Bizarre...

Accumulate est une fonction assez particulière, dans le sens où (à la difference des autres tests, fondés sur des tris) elle parcourt le tableau de proche en proche, et l'ordre de parcours est connu à l'avance. Donc, ni saut ni indirection. Je soupçonne que c'est typiquement ce qu'un compilateur "dédié" comme ICC sait parfaitement exploiter. Je suis juste un peu surpris que cela ne se retrouve pas dans quicksort, parce que la boucle internet de quicksort (recherche de pivot) ca repose exactement sur le même principe. Sans doute à cause des tests...

Citation:

Envoyé par Arzar

2) Pour le deuxième test, ICC donne des "pénalités" d'abstraction de 1.00, 0.88, 1.26, 0.86, 0.86, 0.87, 0.86, 0.87 pour un total de .... 0.91 ! :fou:
C'est un mystère complet pour moi. Je ne comprends pas du tout comment un compilateur peut faire une meilleure optimisation avec un itérateur qu'avec un pointeur, même dans les cas les plus tordus,

Ma théorie personnelle, là dessus, c'est que dans le cas où il travaille sur des itérateurs, ICC n'effectue pas les optimisations de code dans le même sens que pour des types natifs. En gros, sur des types natifs, il va privilégier des optimisations "bas niveau" alors que pour des types utilisateur il commence par simplifier le code "haut niveau".

Pour insert sort, dont la boucle de plus haut niveau est assez simple, je pense qu'il arrive à appliquer (pour les itérateurs) la même ruse que celle qui fait des merveilles avec accumulate. En revanche, quand il a des pointeurs, il commence par une optimisation malencontreuse de bas niveau...

Ceci dit, hors STL, la différence de vitesse entre Visual et ICC est assez documentée. Au fil des années Visual se rapproche, mais ICC a encore pas mal d'avance.

Francois