std::deque adapté à mon besoin?

Bonjour,

Je développe actuellement un serveur pour un TP de C++ que je compte reprendre pour un de mes projets perso.

De celui-ci, j'ai un thread qui lit des données sur un port, enregistre les données dans une liste tandis que plusieurs threads se chargent de lire cette liste.

J'aurais donc des insertions en queue et en tête (pour certains messages prioritaires) et des suppressions/lectures en tête.
D'après ce que j'ai lu, les std::deque seraient plus adapté que des std::list à mon besoin.

Malheureusement, je ne comprend pas trop comment les std::deque sont implémentés (tableau circulaires ? maillons contenant plusieurs éléments ?), or j'aimerais bien me faire une idée des performances dû à son utilisation.

S'il faut allouer à chaque insertion, mon thread de lecture va être extrêmement lourd or je veux l'éviter à tout prix.

La solution optimale à laquelle je penserais serait d'allouer un tableau de X éléments et d'avoir un pointeur pour la lecture et un pointeur pour l'écriture.
Une fois arrivé au bout du tableaux, ils reviendrait au début de celui-ci. Ce qui me permet de ne bloquer que lors du déplacement du pointeur d'écriture, la remise au début du tableau du pointeur de lecture et non pas lors de la lecture/écriture des éléments.

Est-ce que le deque pourrait m'offrir des performances relativement aussi intéressante que ma solution "maison" ?

Salut,

Le problème majeur, c'est, justement, de déterminer le fameux X dont tu parles...

Si tu pouvais avoir la certitude que chaque thread effectue l'ensemble de ce qu'il doit faire en un laps de temps tout à fait identique, (pour faire simple: que ce qui doit être fait au moment du traitement ne prend, en toute état de cause, jamais plus longtemps que de qui doit être fait au moment de l'insertion), tu pourrais, effectivement arriver, sur base de la bande passante, de la taille des requetes, et d'autres facteurs arriver à déterminer qu'il n'y aura jamais plus que X instructions "dans le pipe"...

Le problème, c'est que je mettrais bien ma main à couper quant au fait que c'est tout le contraire...

Je suis en effet prêt à parier ma chemise sur le fait que le traiement global de ce qui se trouve "dans le pipe" prend très régulièrement plus de temps que la procédure d'ajout :aie:

Dés lors, on peut craindre très fortement que, quel que puisse être la valeur de X, on en arrive, tôt ou tard, à insérer, dans une période de temps T, plus d'éléments que ce que l'on est capable d'en traiter dans la même période, avec tous les risques liés au fait que l'on risque donc d'écraser des données en cours ou en attente de traitement :aie:

Très honnêtement, c'est un risque que je ne voudrais pas prendre ;)

Alors, en effet, le problème des listes (quelle qu'elles soient) est qu'il y a une allocation dynamique à chaque insertion ( ou peu s'en faut)...

Je ne crois cependant pas que cela puisse représenter un "bottleneck" majeur, simplement parce qu'il y a d'autres restrictions bien plus embêtantes, comme la bande passante, le temps qu'il faut pour analyser les requètes et / ou pour créer l'élément que tu vas rajouter à ta liste.

D'un avis personnel, une dequeue ou une liste me semblent, dans ce cas de figure, bien plus intéressant que le fait d'avoir, effectivement, la possibilité d'avoir un accès aléatoire en temps constant, et ce, d'autant plus que tu n'auras jamais besoin d'un accès aléatoire, chaque instruction devant être effectuée dans l'ordre où elle est arrivée, modulo son système de priorité ;)

Pour la question : aucune idée !

Mais j'ai l'impression que tu prends la problème à l'envers. deque et list n'ont la même sémantique. Et tu sais exactement la sémantique que tu veux.
L'approche que je prendrais, c'est de créer une container adaptator, prenant un container en paramètre template

Citation:

---

J'aurais donc des insertions en queue et en tête (pour certains messages prioritaires) et des suppressions/lectures en tête.

---

Ça donne directement ça :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

template <class T, class Container = std::list<T>> class MyContainer { // pour ajouter : void insert(T msg, Priority p = low); // ou tu peux faire 2 fonctions puhs_back et push_front ou utiliser // un enum ou un unsigned pour Priority   // pour lire : T& front(); T const& front(); void pop_front(); };

---

En gros, ça revient à réécrire un priority_queue, autant l'utiliser (en plus, le type de conteneur utilisé en interne est paramétrable... que demander de plus)

Citation:

---

Malheureusement, je ne comprend pas trop comment les std::deque sont implémentés (tableau circulaires ? maillons contenant plusieurs éléments ?), or j'aimerais bien me faire une idée des performances dû à son utilisation.

---

Si tu te poses la question de l'implémentation, tu ne résonnes plus en terme d'abstraction. Bof...
Pour les performances, toujours la même chose : fais des benchmarks. C'est plus simple que de se prendre la tête 10 ans pour connaître l'implémentation (une petite option de compilation dans l'implémentation de la classe dessus et tu auras ta réponse, adapté à ton cas d'utilisation)

(et tu risques d'avoir encore des réponses du genre "si tu veux des performances, il faut pas utiliser la stl et tout coder avec des malloc, voir avec du code asm")

Bonjour, merci pour vos réponses.

Pour le contenair adaptator, je suis déjà en train d'en créer un pour stocker des objets de façon safe thread (lecteur/rédacteur) donc je l'utiliserais ici (par contre je ne savais pas que ça existait déjà :aie:).


Je veux connaitre un peu l'implémentation pour me faire une idée de comment il fonctionne.
Avec deque, j'ai un reserve ce qui est très intéressant.

Par contre :
- à force de faire des lectures en têtes et écritures en queues, est-ce qu'il ne va arriver "à la fin de sa zone mémoire" et va devoir réallouer une zone et copier tout le contenu ? (1)
- lors du redimensionnement est-ce qu'il va réallouer toute une zone mémoire et copier le résultat ? (2)

La liste peut contenir pas mal d'éléments et le temps de réallouer et de tous les copier....
Si (2) est vrai, ça ne fait rien, il faudra juste réserver la taille maximal à l'initialisation.
Si (1) est vrai, autant utiliser les std::list.

Sinon se faire deux std::list, l'une contenant les éléments de la liste et l'autre les éléments alloués fini de traité qui pourront être réécrit pour être remis dans la liste.

Avec des fonctions resize() et reserve() et un opérateur [] en temps constant pour deque, je serais pas étonné qu'il soit implémenté comme un vecteur (bloc de mémoire contigu). Du coup, a priori, mauvais pour les performances (réallocation lors de l'insertion et resize)

A priori, je partirais sur une liste (mais je serais pas choqué de tu partes sur un vector ou un deque dans un premier temps et de changer après tests de charge réels, vu que le changement est facile)

Mais très clairement, mon conseil est de créer ta propre structure (pour ajouter le thread safe + avoir la sémantique recherchée) et utiliser un list en interne (ou une priority_queue) dans un premier temps et d'avoir un programme fonctionnel. Ce choix de conteneur est une optimisation, donc à faire dans un second temps

Une deque est normalement un tableau de (pointeurs vers) tableaux. Et on ne copie jamais les elements, i.e. une reference n'est invalidee que quand on sort l'element de la deque. Si tu n'as rien a faire au milieu, c'est normalement mieux qu'une liste. Si tu inseres en tete, c'est normalement mieux qu'un vector. En fait, c'est relativement souvent mieux qu'un vector des que tu n'as pas la contrainte de la continuite.

Citation:

---

Envoyé par Jean-Marc.Bourguet

Une deque est normalement un tableau de (pointeurs vers) tableaux. Et on ne copie jamais les elements, i.e. une reference n'est invalidee que quand on sort l'element de la deque. Si tu n'as rien a faire au milieu, c'est normalement mieux qu'une liste. Si tu inseres en tete, c'est normalement mieux qu'un vector. En fait, c'est relativement souvent mieux qu'un vector des que tu n'as pas la contrainte de la continuite.

---

Donc si je veux agrandir mon deque je n'aurais jamais de réallocation et de copie du contenu du deque?
De même si je fais énormément d'insertions en queues et de lectures en têtes ?
Si c'est le cas c'est tout à fait ce qu'il me faut.

Citation:

---

Envoyé par Neckara

Donc si je veux agrandir mon deque je n'aurais jamais de réallocation et de copie du contenu du deque?
De même si je fais énormément d'insertions en queues et de lectures en têtes ?
Si c'est le cas c'est tout à fait ce qu'il me faut.

---

Non. Tu peux avoir une allocation d'un nouveau tableau ou meme une reallocation du tableau de pointeurs, mais pas de deplacement de tes objets.

Mais naturellement, mesure si tu es sensible aux perfs. Tu peux tomber sur une implementation "optimisee" pour un cas principal different du tien et qui considere le tien comme un cas degenere dont il ne faut pas tenir compte.

Merci pour vos réponses.

Au final, je pense que je vais me faire des petites listes simplement chaînées

Une première liste pour les objets alloués non-utilisé et une seconde liste pour les paquets reçus.

C'est théoriquement la méthode la plus rapide qu'on puisse avoir et elle ne sera pas longue à mettre en place^^

Tu as jetté un oeil a boost::circular_buffer?

Citation:

---

Envoyé par Klaim

Tu as jetté un oeil a boost::circular_buffer?

---

A la base c'est un TP de C++ (que je reprendrais ensuite à mon compte) donc j'ai quelques restrictions.
Par exemple on ne peut pas utiliser la SFML pour les sockets, on est obligé d'utiliser socket.h (POSIX)
Pour boost, comme on ne l'a pas vu, je ne suis pas sûr que le prof accepte, mais j'irais quand même voir ce lien^^

Oui mieux vaut lui demander.

Si le sujet porte sur comment implémenter ce container a partir de la STL, alors mieu vaut ne pas l'utiliser.