Existe-t-il des conteneurs concurrents dans C++11 ?

Question

En particulier, je cherche une file d'attente bloquante. Existe-t-il une telle chose en C++11 ? Si non, quelles sont mes autres options ? Je n'ai vraiment plus envie de descendre moi-même au niveau du thread. Trop d'erreurs.

Answer 1

Selon Diego Dagum de l'équipe Visual C++ de Microsoft :

Une question récurrente (enfin, l'une des nombreuses) concerne les conteneurs STL et s'ils sont thread safe.

En prenant les mots de Stephan ici, la réalité est qu'ils ne le sont pas, non pas comme un bug mais comme une fonctionnalité : avoir chaque fonction membre de chaque conteneur STL acquérant un verrou interne annihilerait les performances. Comme bibliothèque générale, hautement réutilisable, elle ne fournirait pas non plus de correction pas non plus la correction : le niveau correct pour placer les verrous est est déterminé par ce que fait le programme. Dans ce sens, les fonctions membres individuelles fonctions membres individuelles n'ont pas tendance à être ce niveau correct.

La bibliothèque de modèles parallèles (PPL) comprend plusieurs conteneurs qui offrent un accès sécurisé à leurs éléments :

• El Classe vecteur_concurrent est une classe de conteneur de séquence qui permet un accès aléatoire à tout élément. Elle permet des opérations d'ajout, d'accès à l'élément, d'accès à l'itérateur et de traversée de l'itérateur à sécurité concurrentielle.
• El Classe concurrent_queue est une classe de conteneur de séquence qui permet un accès premier entré, premier sorti à ses éléments. Elle permet un ensemble limité d'opérations sûres pour les concurrents, telles que push et try_pop, pour n'en citer que quelques-unes.

Quelques échantillons aquí .

Intéressant aussi : http://www.justsoftwaresolutions.co.uk/threading/implementing-a-thread-safe-queue-using-condition-variables.html .

Answer 2

C++11 ne fournit pas de conteneurs concurrents en soi. Cependant, il existe des options de bibliothèque. Outre la PPL déjà mentionnée, n'oubliez pas la bibliothèque TBB d'Intel.

Il dispose d'un concurrent queue , hash_map , set y vector de la bibliothèque. Il ne s'agit pas seulement d'une bibliothèque de conteneurs à sécurité thread, mais aussi d'une version parallèle des algorithmes standard (for-loop, reduce, sort,...).

Site Web du TBB d'Intel

Answer 3

Je suis surpris que personne n'ait mentionné moodycamel::ConcurrentQueueue . Nous l'utilisons depuis un certain temps et il fonctionne très bien. Il est spécifique que son implémentation est sans verrou, ce qui apporte immédiatement une énorme rapidité. Autres raisons de l'utiliser (citation du site officiel) :

Il n'existe pas beaucoup de files d'attente sans verrou pour le C++. Boost en possède une, mais elle est limitée aux objets avec des opérateurs d'affectation triviaux et des destructeurs triviaux, par exemple. La queue TBB d'Intel n'est pas lock-free, et nécessite des constructeurs triviaux également. Il y a de nombreux articles académiques qui implémentent des files d'attente sans verrou en C++, mais le code source mais le code source utilisable est difficile à trouver, et les tests encore plus.

Quelques repères et comparaisons sont disponibles aquí , aquí y aquí .

Attention : dans le cas de producteurs multiples, il n'est pas garanti que l'ordre des éléments "poppés" soit le même que l'ordre des éléments "poussés" (@IgorLevicki), donc si vous avez besoin de cette garantie, cherchez une autre option.

Answer 4

Les interfaces des conteneurs n'ont tout simplement pas été conçues dans cet objectif. Pour les interfaces qu'ils utilisent, un verrou visible par le client est vraiment le seul moyen d'y parvenir tout en garantissant la correction et un comportement prévisible. Ce serait également terriblement inefficace car le nombre d'acquisitions serait très élevé (par rapport à une bonne implémentation).

Solution 1

Pass by value (le cas échéant).

Solution 2

Créez une collection d'implémentations simples que vous pouvez utiliser pour passer des conteneurs tout en gardant un verrou de portée (considérez cela comme du pseudo c++) :

template <typename TCollection>
class t_locked_collection {
public:
    t_locked_collection(TCollection& inCollection, t_lock& lock) : collection(inCollection), d_lock(lock), d_nocopy() {
    }

    TCollection& collection;
    // your convenience stuff
private:
    t_scope_lock d_lock;
    t_nocopy d_nocopy;
};

L'appelant associe alors le verrou à la collection, puis vous mettez à jour vos interfaces pour utiliser (passer par) le type de conteneur le cas échéant. C'est juste une extension de classe du pauvre.

Ce conteneur verrouillé est un exemple simple, et il existe quelques autres variantes. C'est la voie que j'ai choisie parce qu'elle vous permet vraiment d'utiliser le niveau de granularité qui est idéal pour votre programme, même si elle n'est pas aussi transparente (syntaxiquement) que les méthodes verrouillées. C'est aussi relativement facile d'adapter des programmes existants. Au moins, il se comporte d'une manière prévisible, contrairement aux collections avec des verrous internes.

Une autre variante serait :

template <typename TCollection>
class t_lockable_collection {
public:
// ...
private:
    TCollection d_collection;
    t_mutex d_mutex;
};

// example:
typedef t_lockable_collection<std::vector<int> > t_lockable_int_vector;

...où un type similaire à t_locked_collection pourrait être utilisé pour exposer la collection sous-jacente. Je ne veux pas dire que cette approche est infaillible, mais simplement résistante.

Answer 5

Ma version d'une carte concurrente non ordonnée espace de noms concurrent {

template<typename T,typename T1>
class unordered_bucket: private std::unordered_map<T,T1>
{
mutable std::recursive_mutex m_mutex;

public:
T1 &operator [](T a)
{
    std::lock_guard<std::recursive_mutex> l(m_mutex);
    return std::unordered_map<T,T1>::operator [](a);
}

size_t size() const noexcept {
    std::lock_guard<std::recursive_mutex> l(m_mutex);
    return  std::unordered_map<T,T1>::size();
}

vector<pair<T,T1>> toVector() const
{
    std::lock_guard<std::recursive_mutex> l(m_mutex);

    vector<pair<T,T1>> ret;
    for(const pair<T,T1> &p:*this)
    {
        ret.push_back(p);
    }
    return ret;
}

bool find(const T &t) const
{
    std::lock_guard<std::recursive_mutex> l(m_mutex);
    if(this->std::unordered_map<T,T1>::find(t) == this->end())
        return false;  //not found
    return true;
}
void erase()
{
    std::lock_guard<std::recursive_mutex> l(m_mutex);
    this->unordered_map<T,T1>::erase(this->begin(),this->end());
}
void erase(const T &t)
{
    std::lock_guard<std::recursive_mutex> l(m_mutex);
    this->unordered_map<T,T1>::erase(t);
}
};

#define BUCKETCOUNT 10
template<typename T,typename T1>
class ConcurrentMap
{
std::vector<unordered_bucket<T,T1>> m_v;
public:
ConcurrentMap():m_v(BUCKETCOUNT){}   //using 10 buckets

T1 &operator [](T a)
{
    std::hash<T> h;
    return m_v[h(a)%BUCKETCOUNT][a];
}

size_t size() const noexcept {
    size_t cnt=0;

    for(const unordered_bucket<T,T1> &ub:m_v)
        cnt=cnt+ub.size();

    return  cnt;
}

vector<pair<T,T1>> toVector() const
{
    vector<pair<T,T1>> ret;
    for(const unordered_bucket<T,T1> &u:m_v)
    {
        const vector<pair<T,T1>> &data=u.toVector();
        ret.insert(ret.end(),data.begin(),data.end());
    }
    return ret;
}

bool find(const T &t) const
{
    for(const unordered_bucket<T,T1> &u:m_v)
        if(true == u.find(t))
            return true;
    return false;
}
void erase()
{
    for(unordered_bucket<T,T1> &u:m_v)
        u.erase();
}
void erase(const T &t)
{
    std::hash<T> h;
    unordered_bucket<T,T1> &ub = m_v[h(t)%BUCKETCOUNT];
    ub.erase(t);
}
};
}