std::list comme primitive thread-safe ?

Version imprimable

06/10/2012, 11h39
germinolegrand

std::list comme primitive thread-safe ?

Bonjour,
je travaille actuellement avec les sf::Thread sur un système de réseau.
Mais les mutexes ne font que ralentir la procédure de traitement, de réception et d'envoi. En fouillant un peu dans la STL comme à mon habitude, les spécifications de std::list m'ont apparues comme extrêmement favorable au thread-safe lorsqu'on les utilise comme des FIFO. Je m'explique :
push_back n'invalide aucune référence ni aucun itérateur.
pop_front n'invalide que les références et les itérateurs sur l'objet supprimé (autrement dit il invalide begin()).
Or push_back n'utilise que end() ?
Et pop_front seulement begin() ?
la fonction de liaison qui permet de savoir si la file contient un élément est empty() qui se contente de retourner begin() == end().

A votre avis est-ce suffisant pour ne pas avoir de collision entre les threads ? ou bien pop et push invalident temporairement les itérateurs avant de les rendre valides ?

Ça ne sera pas suffisant non.

Ton thread qui va appeler pop_front() doit savoir avant si empty() retourne false, et il y a de grande chance que cette fonction là utilise des données qui pourraient être atteintes/modifiées simultanément par l'autre thread via push_back().

Personnellement, j'ai utilisé le concept de cet article de Herb Sutter. Ce conteneur n'utilise a priori aucun mécanisme de lock, mais l'ajout de std::atomic<T> fait par le C++11.

Voici le code que j'utilise (celui de l'article est un peu ancien et ne compile pas directement) :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#ifndef LOCK_FREE_QUEUE_HPP
#define LOCK_FREE_QUEUE_HPP
 
#include <atomic>
 
// Note : implementation is from
// http://www.drdobbs.com/parallel/writing-lock-free-code-a-corrected-queue/210604448
 
template<typename T>
class lock_free_queue
{
    struct node
    {
        node() : next(nullptr) {}
        node(const T& t) : data(t), next(nullptr) {}
 
        T     data;
        node* next;
    };
 
    node* first;
    std::atomic<node*> dummy, last;
 
public :
 
    lock_free_queue() {
        // Always keep a dummy separator between head and tail
        first = last = dummy = new node();
    }
 
    ~lock_free_queue() {
        // Clear the whole queue
        while (first != nullptr)
        {
            node* temp = first;
            first = temp->next;
            delete temp;
        }
    }
 
    // Disable copy
    lock_free_queue(const lock_free_queue& q) = delete;
    lock_free_queue& operator = (const lock_free_queue& q) = delete;
 
    // To be called by the 'producer' thread
    void push(const T& t) {
        // Add the new item to the queue
        (*last).next = new node(t);
        last = (*last).next;
 
        // Clear consumed items
        while (first != dummy)
        {
            node* temp = first;
            first = temp->next;
            delete temp;
        }
    }
 
    // To be called by the 'consumer' thread
    bool pop(T& t) {
        // Return false if queue is empty
        if (dummy != last)
        {
            // Consume the value
            t = (*dummy).next->data;
            dummy = (*dummy).next;
            return true;
        }
        else
            return false;
    }
 
    // To be called by the 'consumer' thread
    bool empty() const {
        return dummy == last;
    }
 
    // This method should not be used in concurrent situations
    void clear() {
        while (first != dummy)
        {
            node* temp = first;
            first = temp->next;
            delete temp;
        }
 
        first = dummy.load();
 
        while (first->next != nullptr)
        {
            node* temp = first;
            first = temp->next;
            delete temp;
        }
 
        last = dummy = first;
    }
};
 
#endif

A noter donc :

le thread "consommateur" n'a le droit d'appeler que pop() et empty(),
le thread "producteur" n'a le droit d'appeler que push(),
les autres méthodes et constructeurs doivent être appelés dans un environnement non concurrent (i.e. quand on sait qu'un seul thread a accès au conteneur).

À voir si ça améliore les performances de ton code.

06/10/2012, 12h29
gbdivers

en théorie, si ton thread qui remplit ta liste le fait que lorsqu'il a fini de travailler sur l’élément et fait juste un push et que le thread qui vide la liste en faisant bien un pop avant de lire les données, le risque de collision est faible (ou pas, sur le long terme), faudrait un push et un pop en même temps sur une liste vide

Mais très clairement, faire ça est une très mauvaise pratique, ça peut provoquer des bugs silencieux et non reproductible, donc très complexe à corriger

Et normalement, un mutex, c'est juste un flag atomique. Ca devrait pas tuer les perfs. Si c'est le cas, c'est probablement que tes threads ne font pas juste push et pop, mais travaille sur la liste pendant le lock. Et là, supprimer le mutex serait une catastrophe

Bref, a priori donc, tu devrais utiliser les mutex mais ça devrait pas tuer les perfs

Voilà le code pour le thread interne :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 if(!m_pendingToSendMessages.empty()) { for(auto &s : m_otherServers) { if(s.second) { if(s.second->send(*m_pendingToSendMessages.front()) != sf::Socket::Done) throw s.first; m_pendingToSendMessages.pop_front(); } } }
et pour les threads externes :
Code:

1 2 std::unique_ptr<sf::Packet> uni(new sf::Packet(packet)); m_pendingToSendMessages.push_back(std::move(uni));
Le problème des mutexes c'est qu'elles synchronisent les threads or ceci ralentit considérablement le thread de gestion des messages qui est lui critique (il traite en interne bien plus de messages que ce que les autres threads vont traiter). Dans l'idéal il me faudrait un try_lock, mais bon... c'est pas encore supporté dans ma version de g++ :(

06/10/2012, 12h50
gbdivers
boost.thread pour try lock ?

Sinon tu utilises quel libs de thread ? SFML ?
Tu peux regarder aussi du côté de boost.asio ou de TBB (http://threadingbuildingblocks.org/d...s_overview.htm) pour les conteneurs threads safe
Code:

1 2 std::unique_ptr<sf::Packet> uni(new sf::Packet(packet)); m_pendingToSendMessages.push_back(std::move(uni));
utilise emplace à la place

Tiens, merci pour le emplace, j'avais mis push parce que je faisais quelques manips dessus avant, mais en refactorisant je suis passé à côté ^^.

J'utilise les threads de la SFML 2.0, ainsi que g++4.7 (pas accès à boost).
TBB a l'air bien mais la licence est prohibitive.

@Kalith : J'ai été voir l'article sur drdobb's ainsi que ton code mais l'usage de std::atomic n'est pas implémenté dans ma version de g++ (d'après la doc : Order and consistency : Not yet, section 29 de cette page : http://gcc.gnu.org/onlinedocs/libstd...tatus.iso.200x ), mais je me trompe peut-être et les parties manquante ne me concernent pas ?

Pour le try_lock j'ai fait ma propre version avec un bool est-ce correcte ?
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 class Mutex { public: Mutex() = default; Mutex(const Mutex&) = delete; ~Mutex() = default; bool try_lock() { if(m_prim) return false; m_prim = true; return true; } void lock() { while(!try_lock()); } void unlock() { m_prim = false; } private: bool m_prim = false; }; class Lock { public: Lock(Mutex &m): m_mut(m) { m_mut.lock(); } Lock(const Lock&) = delete; ~Lock() { m_mut.unlock(); } private: Mutex &m_mut; };

06/10/2012, 16h50
Kalith

J'ai également gcc 4.7 et ça compile, tout du moins. Maintenant je ne sais pas si tout fonctionne comme prévu, mais ça m'étonnerais que les gars de chez gcc sortent sciemment une version buggée de leur compilateur. De mon côté, je n'ai pas vu de problème quoi qu'il en soit.

Edit : Sur cette page, il est écrit que les opérations atomiques sont supportées depuis gcc 4.4
06/10/2012, 17h11
germinolegrand

Disons que j'ai déjà fait l'expérience des std::regex qui sont parfaitement bien déclarée mais les implémentations sont vides :D
06/10/2012, 18h31
germinolegrand

Allez, une petite question : est-ce que bool est thread-safe ? J'aurais tendance à dire oui vu que théoriquement la valeur est codée sur un bit et que deux threads ne peuvent pas modifier un même bit au même moment...
06/10/2012, 18h38
Kalith

J'aurais tendance à dire que non, sinon il n'y aurait pas de classe atomic_bool dans le nouveau standard, cf. §29.5.1.4 :

Citation:

The atomic_bool type provides an atomic boolean.

Peut être qu'il est effectivement atomique sur la plupart des plateformes, je ne sais pas.
06/10/2012, 18h45
germinolegrand

D'après cppreference :

Citation:

The standard library provides full specializations of the std::atomic template for the following types:

1) One specialization for the type bool and its typedef name is defined that is treated as a non-specialized std::atomic<T> except that it has standard layout, trivial default constructor, trivial destructors, and supports aggregate initialization syntax:
Typedef name Full specialization
std::atomic_bool std::atomic<bool>

Ce qui laisserait entendre que le bool est déjà atomique et que le standard ne propose une spécialisation particulière que pour une question d'esthétique...

Edit: en fait c'est surtout le Full specialization qui me fait dire ça...
06/10/2012, 19h18
gbdivers
J'aurais tendance à dire qu'il faudrait que tu lises un livre sur la programmation concurrente...
The Art of Concurrency
C++ Concurrency
Un type n'est jamais thread-safe ou non. Ce qui est thread-safe ou atomic, ce sont les accès.

Si tu écris
Code:

1 2 3 T mybool = f(); mybool = !mybool; f(mybool);
que T soit bool, std::atomic<bool> ou MyVerySafeAtomicBool, ce code ne sera jamais thread-safe. Il y a toujours une possibilité d'écriture par un autre entre la lecture et l'écriture

std::atomic<bool> fournit des fonctions qui sont garantie atomique (donc lecture + écriture), comme += ou ++. Pour bool, il n'y a pas ces garanties
07/10/2012, 21h24
Emmanuel Deloget

Citation:

Envoyé par germinolegrand

Allez, une petite question : est-ce que bool est thread-safe ? J'aurais tendance à dire oui vu que théoriquement la valeur est codée sur un bit et que deux threads ne peuvent pas modifier un même bit au même moment...

Non.

Pour qu'un type de donné soit thread safe, il faut que son accès en lecture ET en écriture soit atomique. Le nombre de bit a écrire ou à lire n'a aucun impact sur l'atomicité des accès qui sont fait à cette variable. Par exemple, un thread teste une valeur pendant qu'un autre l'écrit. Pour tester la valeur, il faut la mettre dans un registre et faire le test - ce qui nécessite deux instructions. Il y a donc la possibilité pour que l'écriture d'une autre valeur se place dans l'intervalle.

(edit: module le problème de sémantique soulevé par gbdivers)