Discussion :

[henrygoland]

Bonjour,

Je m'occupe actuellement en créant une liste C++ ressemblant aux listes de type vector des libs std. (utilisant des template pour le type, et en utilisant le principe des listes chaînées à double sens pour le stockage).

J'en viens à quelques tests de vitesse, et je remarque que l'insertion des valeurs est plus rapide du côté de la std (pas très surprenant..) :

Pour insérer 5 000 000 de int*, ma liste prend ~ 1.94 secondes, alors que std::vector ne prend que 1.08 secondes.
J'utilise push_back avec la std::vector, est une fonction qui insère à la fin pour ma liste.
Je ne parcours pas toute la liste pour connaître la dernière adresse, j'ai toujours un pointeur vers celle-ci histoire de gagner du temps.


J'avoue qu'aller voir comment std::vector est programmé ne me tente pas énormément (peur de ne pas comprendre du tout ), alors j'en viens à vous pour savoir si quelqu'un connaîtrait le fonctionnement d'allocation de std::vector.
Sachant que pour le moment, j'alloue un espace mémoire à chaque insertion, est-ce que créer des espaces mémoires avant d'en avoir besoin, et donc par plus gros 'paquet' plutôt qu'à l'unité, serait plus rapide ? Ou est-ce que l'insertion dans std::vector utilise un procédé spécial, etc... Si quelqu'un à la moindre idée/doc là dessus, je suis preneur !

Si je ne suis pas assez clair ou qu'il manque des informations, svp excusez-moi et je tenterais de résoudre ce problème.

Merci d'avance
r'm

[Jean-Marc.Bourguet]

std::vector n'est pas une liste chainée, c'est beaucoup plus proche d'un tableau.
std::list est une liste chainée.

[henrygoland]

Ok merci pour l'information. (effectivement ! Ma liste insère plus vite que std::list).

[nikko34]

après faut aussi ne pas essayer en debug

[screetch]

a part prouver qu'un vecteur/tableau est plus adapté qu'une liste, ton benchmark ne montre pas grand chose...

[loufoque]

Ça m'étonnerait que tu puisses vraiment faire plus rapide que std::list...
Tu testes probablement pas des choses équivalentes, et pas avec les bonnes options.

[henrygoland]

Uniquement à l'insertion de 5 000 000 de int* dans ma liste, j'ai bien un temps plus court d'exécution avec ma liste que std::list (j'utilise time (sous linux), pour "benchmarker")

Après je suis conscient que à l'utilisation elle doit bien evidemment être plus lente, genre pour accéder aux valeurs. Mais je ne vois pas en quoi l'insertion pourrait ne pas être plus rapide, surtout que ma liste lors de l'insertion ne fait rien d'autre que d'allouer & stocker les valeurs à la suite. La std::list doit bien avoir quelques choses faites en plus comme par exemple gérer le nombre d'accès à la liste comme certaines listes java, ou d'autres choses dans ce genre ?

screetch: on est d'accord. Je ne connaissais pas le fonctionnement interne sous forme de tableaux de vector. Mais maintenant que je compare ma liste chainées à double sens, et la std::list, le "benchmark" est un peu plus représentatif pour moi.
Je cherchais juste à comprendre pourquoi je perdais autant de temps à l'exécution, pour l'insertion.

[loufoque]

À vue de nez (boule de cristal magique), je dirais que contrairement à std::list qui traite des valeurs qu'elle copie pour insérer, ta liste manipule des pointeurs.

[screetch]

insérer a la fin d'une liste est un cas particulier, une liste est faite pour etre manipulée par le milieu (sinon un tableau convient mieux)

comme dit plus haut, ton benchmark ne teste rien de bon, il faut voir les opérations réelles.

D'ailleurs, un benchmark c'est toujours le mal.

[Arzar]

Serait il possible que tu nous montre le code que tu utilises pour ton benchmark ?

J'avoue être un peu sceptique. J'ai regardé le code de std::list (et c'est vrai que c'est pas évident) mais il me semble qu'une insertion ne fait rien de plus "qu'allouer & stocker les valeurs à la suite". Il ne devrait pas y avoir de différence significative avec une liste codée à la main.

[henrygoland]

loufoque: tout juste, ma liste manipule des pointeurs

Le test que j'ai fait pour std::list:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
// list_stl.cpp
#include <list>
 
int main(void)
{
	std::list<int *> list;
	int * i;
	for (int jj = 0; jj < 5000000; jj++)
	{
		i = new int;
		*i = jj;
		list.push_back(i);
	}
	list.clear();
	return 0;
}

Et maintenant le code de test de ma liste

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
// list_ukw.cpp
#include "ukwlist.h"
 
int main(void)
{
	ukw::list<int> list;
	int * i;
	for (int jj = 0; jj < 5000000; jj++)
	{
		i = new int;
		*i = jj;
		list.insertLast(i); // insère à la fin de la liste
	}
	list.eraseAll(); // desalloue toute la mémoire allouée
	return 0;
}

La seule différence est donc à la création de la liste. Ma liste ne gérant que des pointeurs, même si il est écrit 'int', c'est bien des 'int *' qui sont utilisés, c'est implicite. C'est pourquoi j'utilise bien std::list<int *>.

Ok et en fait les résultats avec 'time' :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
remy@cqfd bench 17:35 : g++ list_ukw.cpp -o ukw
remy@cqfd bench 17:35 : g++ list_stl.cpp -o stl
remy@cqfd bench 17:35 : time ./ukw
 
real	0m1.281s
user	0m1.117s
sys	0m0.107s
remy@cqfd bench 17:35 : time ./stl
 
real	0m1.576s
user	0m1.463s
sys	0m0.097s

screetch: bien d'accord pour les benchmark, c'est assez souvent le mal, surtout dans ce cas où je ne test rien d'autre que l'allocation, et uniquement de int*, ça ne représente pas la qualité de ma liste à l'utilisation en conditions normales, j'en suis bien conscient.

[screetch]

g++ -O3 ?

[henrygoland]

Effectivement avec le flag d'optimisation, la stl reprend le dessus !

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
remy@cqfd bench 17:59 : g++ -O3 list_ukw.cpp -o ukw
remy@cqfd bench 18:00 : g++ -O3 list_stl.cpp -o stl
remy@cqfd bench 18:00 : time ./stl
 
real	0m0.959s
user	0m0.833s
sys	0m0.127s
remy@cqfd bench 18:00 : time ./ukw
 
real	0m1.062s
user	0m0.960s
sys	0m0.103s

total stl: 1.919s
total ukw: 2.125s

Est-ce que ça signifie que le code de la stl est fait pour que lors d'une optimisation de GCC, le code asm généré soit plus rapide ?
Ou bien en fait le -O3 permet de retirer des sortes de trucs de debug dans la stl ?
Merci de l'indication !

[screetch]

la STL contient beaucoup de code dans des fonctions d'une ligne ou des tests "if" que le compilateur arrive a optimiser.
sache aussi que real = user+sys, ca ne sert a rien de les additionner.

[henrygoland]

Merci pour le 'time' je n'avais jamais vu
et merci aussi pour les infos !


r'm

[koala01]

Salut,

Es tu au courent qu'il y a une belle fuite mémoire avec le test effectué sur la liste STL (et, selon le code de eraseAll, il n'est pas impossible qu'il y en ait une sur ta liste perso)

En effet, la fonction clear ne va pas prendre en charge la libération de la mémoire dynamiquement allouée, et, comme tu va - fatalement - perdre les pointeurs placés dans la liste, il te sera impossible de demander la libération de cette mémoire par la suite

[henrygoland]

Yep je suis au courant merci
J'ai mis clear pour le test STL pour tester juste l'insertion, sachant que les deletes prennent plus de temps que de remplacer 3 pointeurs.
Et d'ailleurs pour avoir un code de test vraiment équivalent pour le bout de code avec ma liste, je n'aurais pas du mettre eraseAll() qui désalloue vraiment la mémoire, mais clear() aussi.
Merci

[loufoque]

Si tu veux vraiment les meilleures performances, il suffit de mettre les pointeurs suivant/précédent dans tes objets eux-mêmes.
C'est ce que permet Boost.Intrusive.

Enfin de toutes façons, je vois vraiment pas l'intérêt d'une liste de pointeurs personnellement... Si c'est pour permettre le polymorphisme, tu peux faire ça sans pointeurs. Si c'est pour mettre dans plusieurs conteneurs à la fois, tu ferais mieux d'utiliser un système intrusif, sinon bonjour la fragmentation...

[henrygoland]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
struct s
{
	T * data;
	struct s * prev;
	struct s * next;
};

J'utilise déjà des pointeurs vers le précédent & le suivant dans l'objet lui-même.
Par contre pourquoi j'ai fait T * data, je t'avoue que j'y ai fais automatiquement sans vraiment penser aux avantages/désavantages de ce côté là. Mais aurais-je une vrai différence à ne pas utiliser un pointeur ? Rien qui me vient

[henrygoland]

Et est-ce ce que si je mets de l'allocation automatique (donc sans utiliser un pointeur), la mémoire sera allouée correctement sans fragmentation ? Sachant que la taille de la liste est inconnue au lancement du programme, le compilateur peut optimiser bcp de choses, mais est-ce qu'il est capable de gérer ça ?!

à+,
r'm