Discussion :

[rulianf]

Bonjour à tous,

J'essaie depuis un moment de comprendre comment certains containers de la STL sont optimisés et j'avoue que je suis bluffé par les performances de certains d'entre eux et notamment de la classe std::queue. J'ai réimplémenté rapidement une file (FIFO) basique :

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
18
19
20
21
22
23
 
template<class T>
class myqueue
{
protected:
	struct node
	{
	public:
		T Value;
		node *Next;
	public:
		inline node(const T& value): Value(value) { Next = NULL; };
		inline ~node(void) { delete Next; };
	};
	node *Root, *Last;
public:
	myqueue(void): Root(NULL), Last(NULL) {};
	~myqueue(void) { delete Root; };
	inline bool empty(void) const { return !Root ; };
	T &front(void) { return Root->Value; };
	inline void push(const T& t) { if(!Root) { Last = (Root = new node(t)); } else { Last = (Last->Next = new node(t)); } };
	inline void pop(void) { node *ptr = Root; Root = ptr->Next ; ptr->Next = NULL; delete ptr; };
};

J'ai lancé un code également simple du style :

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
18
 
int main(int argc, char **argv)
{
	uint i, N = 10000000;
	myqueue<uint> mq;
 
	for(i=0;i<N;i++)
	{
 		mq.push(i);
	}
 
 	while(!pq.empty())
	{
 		mq.pop();
	}
 
	return 0;
}

puis j'ai relancé ce code avec un objet de la classe std::queue<uint> en lieu et place de ma classe. Le code avec la classe de la STL est près de 10 fois plus rapide que le code avec la file que j'ai implémentée (et ceci que l'on considère les push ou les pop). Certes l'implémentation de la classe myqueue est basique mais je ne vois pourtant pas les améliorations que je pourrais ajouter à ce code pour le rendre 10 fois plus rapide. Je précise que j'ai compilé ce code avec g++ -03 . Quelqu'un saurait-il d'où proviennent les améliorations manifestement présentes dans la STL ? Gestion de la mémoire optimisée ? Options de compilation particulières ??

Merci par avance pour vos commentaires.

[Arzar]

Bonjour,
Ton code utilise une liste chainée, alors que l'implémentation sous-jacente à std::queue est presque toujours une std::deque.

[rulianf]

D'accord, j'avais bien remarqué la présence sous-jacente d'une deque mais je reconnais que je n'avais pas bien perçu à quoi correspondait réellement cet objet. Merci pour ton lien, je vais approfondir tout ça.