Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

SL & STL C++ Discussion :

std::deque adapté à mon besoin?


Sujet :

SL & STL C++

  1. #1
    Expert éminent sénior
    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" ?
    "Parce que le diable est dans les détails, une vision sans nuance ne peut prétendre à la compréhension du monde."

    Mon ancienne page perso : https://neckara.developpez.com/

  2. #2
    Expert éminent sénior
    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

    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

    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é
    A méditer: La solution la plus simple est toujours la moins compliquée
    Ce qui se conçoit bien s'énonce clairement, et les mots pour le dire vous viennent aisément. Nicolas Boileau
    Compiler Gcc sous windows avec MinGW
    Coder efficacement en C++ : dans les bacs le 17 février 2014
    mon tout nouveau blog

  3. #3
    Inactif  
    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

    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 :Sélectionner tout -Visualiser dans une fenêtre à part
    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)

    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")

  4. #4
    Expert éminent sénior
    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à ).


    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.
    "Parce que le diable est dans les détails, une vision sans nuance ne peut prétendre à la compréhension du monde."

    Mon ancienne page perso : https://neckara.developpez.com/

  5. #5
    Inactif  
    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

  6. #6
    Expert éminent
    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.
    Les MP ne sont pas là pour les questions techniques, les forums sont là pour ça.

  7. #7
    Expert éminent sénior
    Citation Envoyé par Jean-Marc.Bourguet Voir le message
    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.
    "Parce que le diable est dans les détails, une vision sans nuance ne peut prétendre à la compréhension du monde."

    Mon ancienne page perso : https://neckara.developpez.com/

  8. #8
    Expert éminent
    Citation Envoyé par Neckara Voir le message
    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.
    Les MP ne sont pas là pour les questions techniques, les forums sont là pour ça.

  9. #9
    Expert éminent sénior
    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^^
    "Parce que le diable est dans les détails, une vision sans nuance ne peut prétendre à la compréhension du monde."

    Mon ancienne page perso : https://neckara.developpez.com/

  10. #10
    Membre expert
    Tu as jetté un oeil a boost::circular_buffer?

  11. #11
    Expert éminent sénior
    Citation Envoyé par Klaim Voir le message
    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^^
    "Parce que le diable est dans les détails, une vision sans nuance ne peut prétendre à la compréhension du monde."

    Mon ancienne page perso : https://neckara.developpez.com/

  12. #12
    Membre expert
    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.