std::queue très rapide !?
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:
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:
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.
