TBB одновременная неупорядоченная карта вызывает segfault

Question

Мне нужно реализовать огромную хеш-таблицу, которая поддерживает несколько потоков для вставки и получения в одно и то же время. Клавиши ИНТ и вторые элементы являются векторами объекта Т.

class T { 
     //class definitions here 
} 

В настоящее время реализация помогла с TBB :: concurrent_unordered_map. По документации, похоже, разрешено вставлять и обходить в одно и то же время. Тем не менее, работа с несколькими pthreads приведет к ошибке сегментации, хотя последовательный тест совершенно прекрасен. Обратите внимание, что нет никаких операций удаления или удаления, т. Е. Хеш-таблица разрешается только расти.

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)); 
     } 
} 

Для отладки, что случилось, я первый изменил зЬй :: вектор к TBB :: concurrent_vector, а затем изменить функцию Get() и вставить() следующим образом.

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)); 
     } 
} 

Теперь мы можем видеть причину, что параллельная программа падает некоторая указатель NULL возвращается в функции get_test(). Напомним, что в функции insert_test() NULL никогда не вставлен в качестве вторых элементов.

Следующие вопросы задавать.

(1) Я где-то читал, что одновременная вставка в tbb :: concurrent_unordered_map может привести к сбою некоторых попыток вставки, а затем темповые объекты будут уничтожены. Это причина, по которой NULL наблюдается в функции get_test()?

(2) Может ли TBB действительно разрешить вставку и обход в одно и то же время? Это означает, что в то время как некоторые потоки вставляются, другие могут одновременно вызвать get().

(3) Есть ли лучшая реализация, т. Е. Улучшенная параллельная хеш-таблица, поддерживающая параллельную вставку и чтение?

---

Как @for_stack предложил, я проверил вторые элементы concurrent_vectors и вся программа является работоспособной. Дальнейшее испытание проводят следующим образом:

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)); 
     } 
} 

Выход

1 of 2 Ts are NULL 

Это означает, что не все объекты (Т) возвращаются в GET() равны нулю.

---

Опять же последовательный (или даже 1 поток) работает нормально.

Answer 1

TBB CAN Поддержка параллельного ввода и обхода для concurrent_xxx контейнеров. Однако исходный код имеет условие гонки:

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

get функция пытается вернуть копию vector<T*> (чтения), в то время как другие потоки могли бы назвать insert изменить vector<T*> (записи).

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

insert функция попытаться изменить vector<T*>, не охранник замка. Если есть несколько потоков, звоните insert в то же время (несколько пишите), OOPS!

concurrent_unordered_map имеет только безопасную гарантию на операции с контейнером, в то время как у нее нет гарантий на операции на mapped_value. Вы должны сделать это сами.

Как и вы, вы можете заменить vector<T*> на concurrent_vector<T*>. Тем не менее, новый код размещен не компилировать, вы должны изменить реализацию insert_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; # 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

«Т могут поддерживать одновременную установку и обход для concurrent_xxx контейнеров.» - не совсем. Traversal - сложная вещь, когда нет поддержки восстановления памяти, как в TBB, и одновременное стирание поддерживается контейнером (concurrent_hash_map). Однако concurrent_unordered_map не поддерживает потоковую защиту erase() и, таким образом, поддерживается обходной поток.

Answer 3

@ Антон, мой друг, контейнеры concurrent_unordered поддерживают параллельный обход и вставку; они реализованы как списки пропуска. В не-multi случае результат проверки указателя проверяется, и если он не выполняется, поиск начинается снова с точки вставки.

Теперь C++ может быть изменен в течение последних нескольких недель, так как я работал в Intel, но я думаю, что есть серьезные ошибки в исходном коде:

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

Возвращаемое значение является вектором, а не ссылаться или указатель вектор, поэтому вы получите копии текущего содержимого в качестве возвращаемых значений, а вставка в копию не изменит вектор, который находится в наборе. Возможно, исправить это и убедиться, что нет асинхронной ссылки на вектор, а затем искать оставшиеся ошибки.