Critique ma file d'attente concurrente

Question

Il s'agit d'une file d'attente simultanée que j'ai écrite et que je prévois d'utiliser dans un pool de threads que j'écris. Je me demande s'il y a des améliorations de performance que je pourrais apporter. atomic_counter est collé ci-dessous si vous êtes curieux!

#ifndef NS_CONCURRENT_QUEUE_HPP_INCLUDED 
#define NS_CONCURRENT_QUEUE_HPP_INCLUDED 

#include <ns/atomic_counter.hpp> 
#include <boost/noncopyable.hpp> 
#include <boost/smart_ptr/detail/spinlock.hpp> 
#include <cassert> 
#include <cstddef> 

namespace ns { 
    template<typename T, 
      typename mutex_type = boost::detail::spinlock, 
      typename scoped_lock_type = typename mutex_type::scoped_lock> 
    class concurrent_queue : boost::noncopyable { 
     struct node { 
      node * link; 
      T const value; 
      explicit node(T const & source) : link(0), value(source) { } 
     }; 
     node * m_front; 
     node * m_back; 
     atomic_counter m_counter; 
     mutex_type m_mutex; 
    public: 
     // types 
     typedef T value_type; 

     // construction 
     concurrent_queue() : m_front(0), m_mutex() { } 
     ~concurrent_queue() { clear(); } 

     // capacity 
     std::size_t size() const { return m_counter; } 
     bool empty() const { return (m_counter == 0); } 

     // modifiers 
     void push(T const & source); 
     bool try_pop(T & destination); 
     void clear(); 
    }; 

    template<typename T, typename mutex_type, typename scoped_lock_type> 
    void concurrent_queue<T, mutex_type, scoped_lock_type>::push(T const & source) { 
     node * hold = new node(source); 
     scoped_lock_type lock(m_mutex); 
     if (empty()) 
      m_front = hold; 
     else 
      m_back->link = hold; 
     m_back = hold; 
     ++m_counter; 
    } 

    template<typename T, typename mutex_type, typename scoped_lock_type> 
    bool concurrent_queue<T, mutex_type, scoped_lock_type>::try_pop(T & destination) { 
     node const * hold; 
     { 
      scoped_lock_type lock(m_mutex); 
      if (empty()) 
       return false; 
      hold = m_front; 
      if (m_front == m_back) 
       m_front = m_back = 0; 
      else 
       m_front = m_front->link; 
      --m_counter; 
     } 
     destination = hold->value; 
     delete hold; 
     return true; 
    } 

    template<typename T, typename mutex_type, typename scoped_lock_type> 
    void concurrent_queue<T, mutex_type, scoped_lock_type>::clear() { 
     node * hold; 
     { 
      scoped_lock_type lock(m_mutex); 
      hold = m_front; 
      m_front = 0; 
      m_back = 0; 
      m_counter = 0; 
     } 
     if (hold == 0) 
      return; 
     node * it; 
     while (hold != 0) { 
      it = hold; 
      hold = hold->link; 
      delete it; 
     } 
    } 
} 

#endif 

atomic_counter.hpp

#ifndef NS_ATOMIC_COUNTER_HPP_INCLUDED 
#define NS_ATOMIC_COUNTER_HPP_INCLUDED 

#include <boost/interprocess/detail/atomic.hpp> 
#include <boost/noncopyable.hpp> 

namespace ns { 
    class atomic_counter : boost::noncopyable { 
     volatile boost::uint32_t m_count; 
    public: 
     explicit atomic_counter(boost::uint32_t value = 0) : m_count(value) { } 

     operator boost::uint32_t() const { 
      return boost::interprocess::detail::atomic_read32(const_cast<volatile boost::uint32_t *>(&m_count)); 
     } 

     void operator=(boost::uint32_t value) { 
      boost::interprocess::detail::atomic_write32(&m_count, value); 
     } 

     void operator++() { 
      boost::interprocess::detail::atomic_inc32(&m_count); 
     } 

     void operator--() { 
      boost::interprocess::detail::atomic_dec32(&m_count); 
     } 
    }; 
} 

#endif 

Answer 1

Je pense que vous aurez des problèmes de performance avec une liste chaînée dans ce cas en raison de l'appel new pour chaque nouveau nœud. Et ce n'est pas seulement parce que l'appel de l'allocateur de mémoire dynamique est lent. C'est parce que l'appeler fréquemment introduit beaucoup de surcharges de concurrence, car le magasin gratuit doit être maintenu cohérent dans un environnement multithread.

J'utiliserais un vecteur que vous redimensionnez pour être plus grand lorsqu'il est trop petit pour contenir la file d'attente. Je ne le redimensionnerais jamais plus petit.

Je voudrais organiser les valeurs avant et arrière afin que le vecteur est un tampon en anneau. Cela nécessitera que vous déplaciez des éléments lorsque vous redimensionnez bien. Mais cela devrait être un événement assez rare et peut être atténué dans une certaine mesure en donnant une taille de vecteur suggérée lors de la construction.

Vous pouvez également conserver la structure de liste liée, mais ne jamais détruire un nœud. Continuez simplement à l'ajouter à une file de noeuds gratuits. Malheureusement, la file d'attente des nœuds libres va nécessiter un verrouillage pour pouvoir fonctionner correctement, et je ne suis pas sûr que vous soyez vraiment dans un meilleur endroit que si vous appeliez supprimer et tout le temps.

Vous obtiendrez également une meilleure localisation de référence avec un vecteur. Mais je ne suis pas sûr de savoir comment cela va interagir avec les lignes de cache qui doivent faire la navette entre les CPUs.

Certains autres suggèrent un ::std::deque et je ne pense pas que ce soit une mauvaise idée, mais je soupçonne que le vecteur de tampon en anneau est une meilleure idée.

Answer 2

Herb Sutter a proposé une mise en œuvre d'une file d'attente sans verrou qui serait sûrement le vôtre surperformer :)

L'idée principale est d'utiliser un anneau tampon, renoncer à l'allocation dynamique de la mémoire tout à fait pendant la course de la file d'attente. Cela signifie que la file d'attente peut être pleine (et donc vous devrez peut-être attendre pour y mettre un élément), ce qui peut ne pas être acceptable dans votre cas. Comme noté Omnifarious, il serait préférable de ne pas utiliser une liste liée (pour la localité de cache), sauf si vous allouez pour un pool. J'essayerais d'utiliser un std::deque comme backend, c'est beaucoup plus convivial pour la mémoire et il n'y aura pas de réallocation tant que vous ne faites que pousser et pousser (à l'avant et à l'arrière) ce qui est normalement le cas pour une file d'attente.