c++ - TBB 并发无序映射导致段错误

Question

我需要实现一个巨大的哈希表，支持多个线程同时插入和获取。键是 int，第二个元素是对象 T 的 vector 。

class T { 
        //class definitions here
}

目前，tbb::concurrent_unordered_map 帮助实现。在文档中，它似乎允许同时插入和遍历。但是，尽管顺序测试非常好，但使用多个 pthread 运行会导致段错误。请注意，绝对没有删除或弹出操作，即哈希表只允许增长。

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

这意味着并非所有在 get() 中返回的对象 (T) 都是 NULL。

---

同样，顺序(甚至 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同时(多次写入)，糟糕!

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