TBB gleichzeitige ungeordnete Karte verursacht segfault

Question

Ich muss eine riesige Hash-Tabelle implementieren, die mehrere Threads unterstützt, die gleichzeitig eingefügt und abgerufen werden. Die Tasten sind int und die zweiten Elemente sind Vektoren Objekt T.

class T { 
     //class definitions here 
} 

Derzeit ist die Umsetzung mit TBB :: concurrent_unordered_map geholfen wird. In der Dokumentation scheint es, Einfügen und Durchlaufen gleichzeitig zu ermöglichen. Das Ausführen mit mehreren PThreads führt jedoch zu einem Segmentierungsfehler, obwohl der sequenzielle Test vollkommen in Ordnung ist. Beachten Sie, dass es definitiv keine Lösch- oder Popup-Operationen gibt, d. H. Die Hash-Tabelle darf nur wachsen.

std::vector<T*> get(int key) { 
     //Note that the hash table hashTable is shared by multiple threads 
     tbb::concurrent_unordered_map<int, std::vector<T*>>::iterator it = hashTable.find(key); 
     if (it != hashTable.end()) 
       return it->second; 
     else { 
       std::vector<T*> newvector; 
       return newvector; 
     } 
} 

void insert(int key, T *t) { 
     tbb::concurrent_unordered_map<int, std::vector<T*>>::iterator it = hashTable.find(key); 
     if (it != hashTable.end()) 
       it->second.push_back(t); 
     else { 
       std::vector<T*> newTs; 
       newTs.push_back(t); 
       hashTable.insert(it, makepair(key, newTs)); 
     } 
} 

zu debuggen, was passiert ist, habe ich geändert erste std :: vector :: concurrent_vector, auf TBB und dann die Funktion get ändern() und insert() wie folgt.

std::vector<T*> get_test(int key) { 
     std::vector<T*> test; 
     //Note that the hash table hashTable is shared by multiple threads 
     tbb::concurrent_unordered_map<int, tbb::concurrent_vector<T*>>::iterator it = hashTable.find(key); 
     if (it != hashTable.end()) 
       test.insert(test.end(), it->second.begin(), it->second.end()); 
     for (T* _t : test) 
       if (!_t) 
         printf("Bug happens here!\n"); //Segfault is originated here because a NULL is returned in the vector 
     return test; 
} 

void insert_test(int key, T *t) { 
     //Here t is guaranteed to be not NULL 
     if(!t) 
       std::terminate(); 
     tbb::concurrent_unordered_map<int, tbb::concurrent_vector<T*>>::iterator it = hashTable.find(key); 
     if (it != hashTable.end()) 
       it->second.push_back(t); 
     else { 
       std::vector<T*> newTs; 
       newTs.push_back(t); 
       hashTable.insert(it, makepair(key, newTs)); 
     } 
} 

Jetzt können wir den Grund sehen, dass das Parallelprogramm abstürzt wird einige NULL-Zeiger wird in get_test() Funktion zurückgegeben. Erinnern Sie sich, dass in der Funktion insert_test() niemals NULL als zweite Elemente eingefügt wird.

Die folgenden Fragen sind zu stellen.

(1) Ich habe von irgendwo gelesen, dass die gleichzeitige Einfügung in tbb :: concurrent_unordered_map dazu führen kann, dass ein Teil des Einfügeversuchs fehlschlägt und dann die temporären Objekte zerstört werden. Ist das der Grund dafür, dass NULL in der Funktion get_test() beobachtet wird?

(2) Kann TBB das Einfügen und Traversieren wirklich gleichzeitig erlauben? Das bedeutet, während einige Threads eingefügt werden, können die anderen gleichzeitig get() aufrufen.

(3) Gibt es eine bessere Implementierung, d. H. Eine bessere gleichzeitige Hash-Tabelle, die gleichzeitiges Einfügen und Lesen unterstützt?

---

Wie @for_stack vorgeschlagen habe ich die zweiten Elemente überprüft sind concurrent_vectors und das gesamte Programm ist lauffähig. Ein weiterer Test wird wie folgt durchgeführt:

tbb::concurrent_vector<T*> get_test(int key) { 
      tbb::concurrent_vector<T*> test; 
      //Note that the hash table hashTable is shared by multiple threads 
      tbb::concurrent_unordered_map<int, tbb::concurrent_vector<T*>>::iterator it = hashTable.find(key); 
      if (it != hashTable.end()) 
        test = it->second; 
      int i = 0; 
      for (T* _t : test) 
        if (!_t) 
          i++; 
      if (i > 0) 
        printf("%d of %lu Ts are NULL\n", i, test.size()); //Segfault is originated here because a NULL is returned in the vector 
      return test; 
} 

void insert_test(int key, T *t) { 
     //Here t is guaranteed to be not NULL 
     if(!t) 
       std::terminate(); 
     tbb::concurrent_unordered_map<int, tbb::concurrent_vector<T*>>::iterator it = hashTable.find(key); 
     if (it != hashTable.end()) 
       it->second.push_back(t); 
     else { 
       tbb::concurrent_vector<T*> newTs; 
       newTs.push_back(t); 
       hashTable.insert(it, make_pair(key, newTs)); 
     } 
} 

Der Ausgang ist

1 of 2 Ts are NULL 

Das bedeutet, nicht alle Objekte (T) zurück in get() sind NULL.

---

Wieder ist der sequentielle (oder sogar 1 Thread) läuft in Ordnung.

Answer 1

TBB CAN unterstützt das gleichzeitige Einfügen und Traversieren für concurrent_xxx Container. jedoch Ihr ursprünglicher Code hat Rennbedingungen:

std::vector<T*> get(int key) { 
    // other code 
    return it->second; # race condition 1 
    // other code 
} 

Die get Funktion versuchen, eine Kopie von vector<T*> zurückzukehren ( lesen), während anderen Threads insert nennen könnten den vector<T*> (Schreib) zu ändern.

void insert(int key, T *t) { 
    // other code 
    it->second.push_back(t); # race condition 2 
    // other code 
} 

Die insert Funktion versuchen, die vector<T*> ohne Schloss-Schutz zu ändern. Wenn mehrere Threads vorhanden sind, rufen Sie insert gleichzeitig auf (multiple schreiben), OOPS!

concurrent_unordered_map hat nur sichere Garantie für den Containerbetrieb, während es keine Garantie für Operationen auf der mapped_value. Du musst es selber machen.

Genau wie Sie es versucht haben, können Sie die vector<T*> durch concurrent_vector<T*> ersetzen. Allerdings ist der neue Code, den Sie geschrieben nicht kompilieren, müssen Sie die Implementierung von insert_test ändern: „TBB CAN gleichzeitige Einsetzen und Traversal für concurrent_xxx Container unterstützen“

void insert_test(int key, T *t) { 
    //Here t is guaranteed to be not NULL 
    if(!t) 
      std::terminate(); 
    tbb::concurrent_unordered_map<int, tbb::concurrent_vector<T*>>::iterator it = hashTable.find(key); 
    if (it != hashTable.end()) 
      it->second.push_back(t); 
    else { 
      // std::vector<T*> newTs; # this is wrong! 
      tbb::concurrent_vector<T*> newTs; 
      newTs.push_back(t); 
      hashTable.insert(it, make_pair(key, newTs)); // it should be make_pair not makepair 
    } 
} 

Answer 2

- nicht genau. Traversal ist eine knifflige Sache, wenn es keine Speicher-Wiederherstellungsunterstützung wie in TBB gibt und gleichzeitige Löschung von einem Container unterstützt wird (concurrent_hash_map). concurrent_unordered_map unterstützt jedoch nicht threadsichere erase() und somit wird das thread-sichere Traversal unterstützt.

Answer 3

@Anton mein Freund, die Concurrent_Unordered Container unterstützen gleichzeitige Traversal und Insertion; Sie sind als Skip-Listen implementiert. In dem Nicht-Multi-Fall wird das Ergebnis des Zeigerschwungs getestet, und wenn es fehlschlägt, wird die Suche vom Einfügepunkt aus erneut gestartet.

Jetzt C++ in den letzten Wochen verändert hat, seit ich bei Intel gearbeitet, aber ich denke, dass es schwerwiegende Fehler im ursprünglichen Code ist:

if (it != hashTable.end()) 
     return it->second;   // return a copy??? 
else { 
     std::vector<T*> newvector; // this is stack-allocated 
     return newvector;   // return a copy?? 
} 

Der Rückgabewert ist der Vektor, Referenz oder Zeiger nicht auf Vektor, so erhalten Sie Kopien der aktuellen Inhalte als Rückgabewerte, und das Einfügen in die Kopie wird keinen Vektor ändern, der in der Menge ist. Vielleicht beheben Sie das und stellen Sie sicher, dass es keinen asynchronen Verweis auf einen Vektor gibt, und suchen Sie nach verbleibenden Fehlern.