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

Question

我需要实现一个巨大的散列table，它支持多个线程同时插入和获取。键是 int，第二个元素是对象 T 的向量。

class T { 
        //class definitions here
}

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

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)有没有更好的实现，即支持并发插入和读取的更好的并发散列table？

正如@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函数尝试returnvector<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

"TBB CAN support concurrent insertion and traversal for concurrent_xxx containers." - 不完全是。当没有像 TBB 那样的内存回收支持并且容器支持并发擦除时，遍历是一件棘手的事情（concurrent_hash_map）。但是concurrent_unordered_map不支持线程安全erase()所以支持线程安全遍历

Answer 3

@Anton 我的朋友，concurrent_unordered 容器支持并发遍历和插入；它们被实现为跳过列表。在非多情况下测试指针摆动的结果，如果失败则从插入点重新开始搜索。

自从我在 Intel 工作以来，最近几周 C++ 可能发生了变化，但我认为原始代码中存在严重错误：

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

return 值是矢量，不是引用或指向矢量的指针，因此您将获得当前内容的副本作为 return 值，并且插入到副本中不会改变任何内容集合中的向量。也许修复它，并确保没有对向量的异步引用，然后寻找剩余的错误。

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

TBB concurrent unordered map causes segfault

c++

c++11

pthreads

tbb

concurrenthashmap