TBB одновременная неупорядоченная карта вызывает segfault
Мне нужно реализовать огромную хэш-таблицу, которая поддерживает несколько потоков для вставки и получения одновременно. Ключи являются int, а вторые элементы являются векторами объекта T.
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));
}
}
Чтобы отладить то, что произошло, я сначала изменил std :: vector на tbb :: concurrent_vector, а затем изменил функции get () и insert () следующим образом.
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));
}
}
Теперь мы видим причину сбоя параллельной программы в том, что в функции get_test () возвращается некоторый указатель NULL. Напомним, что в insert_test () функция NULL никогда не вставляется как вторые элементы.
Ниже приведены вопросы, которые нужно задать.
(1) Я откуда-то читал, что одновременная вставка в tbb :: concurrent_unordered_map может привести к неудачной попытке вставки, а затем к временным объектам. Это причина того, что в функции get_test () наблюдается NULL?
(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
Это означает, что не все объекты (T), возвращаемые в get (), имеют значение NULL.
Снова последовательный (или даже 1 поток) работает нормально.
Решение
TBB МОЖНО поддержка одновременной вставки и обхода Тем не менее, ваш исходный код имеет условия гонки: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 в то же время (многократная запись) ОЙ!
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
}
}
Другие решения
«TBB CAN поддерживает одновременную вставку и обход для контейнеров concurrent_xxx». — не совсем. Обход — сложная вещь, когда нет поддержки восстановления памяти, как в TBB, и одновременное удаление поддерживается контейнером (concurrent_hash_map). Тем не мение, concurrent_unordered_map не поддерживает потокобезопасность erase() и, таким образом, поддерживается потокобезопасный обход.
@ Нет, мой друг, контейнеры concurrent_unordered поддерживают параллельный обход и вставку; они реализованы в виде пропусков. В не мульти-случае проверяется результат изменения указателя, и в случае неудачи поиск начинается снова с точки вставки.
Сейчас 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??
}
Возвращаемым значением является вектор, а не ссылка или указатель на вектор, поэтому вы получите копии текущего содержимого в качестве возвращаемых значений, и вставка в копию не изменит ни один вектор из набора. Возможно, исправьте это и убедитесь, что нет асинхронной ссылки на вектор, а затем найдите оставшиеся ошибки.