Мне нужно реализовать огромную хеш-таблицу, которая поддерживает несколько потоков для вставки и получения одновременно. Ключи — int, а вторые элементы — векторы объекта T.
class T {
//class definitions here
}
В настоящее время реализации помогает tbb::concurrent_unordered_map. В документации кажется, что вставка и обход одновременно. Однако работа с несколькими потоками приведет к ошибке сегментации, хотя последовательный тест вполне подойдет. Обратите внимание, что определенно нет операций стирания или извлечения, т.е. хеш-таблица может только расти.
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));
}
}
Теперь мы можем видеть причину сбоя параллельной программы в том, что какой-то указатель NULL возвращается в функцию get_test(). Напомним, что в функции 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 поток) запуск в порядке.
