c++ - std::unordered_map:多线程插入?
问题描述
我有一堆数据(0 到 ULLONG_MAX 之间的巨大整数列表),我想提取所有唯一值。我的方法是创建一个 unordered_map,使用整数列表值作为键,使用一次性布尔值作为映射值。我迭代列表并为每个键插入一次性值。最后,我迭代地图以获取所有唯一键。很直接。
但是,我的列表是如此之大(数以百万计),以至于我想对这个过程进行多线程处理。我知道简单的线程方法是行不通的,因为 unordered_map 插入会影响底层数据结构,因此它不是线程安全的。并且在每个插入周围添加锁会很慢,并且可能会抵消任何线程加速。
但是,大概不是每次插入都会更改数据结构(只有那些无法放入现有分配的存储桶的数据结构?)。有没有办法在插入之前检查特定插入是否需要重新分配 unordered_map?这样我只能在地图发生变化时锁定线程,而不是在每次插入时锁定。然后,在每次插入之前,线程只检查是否存在锁……而不是完全锁定/解锁。那可能吗?
解决方案
并行化的基本规则是分解工作,处理各个部分,然后合并各个部分。
哈希/项目查找是整个 shebang 中最昂贵的部分,因此我们将重点关注并行化。
如果您绝对需要将结果作为哈希表,那么我给您带来了一些坏消息:您必须自己编写。话虽如此,让我们开始吧。
首先,让我们串行解决问题。这很简单。下面的函数接受一个向量和一个回调。我们将获取向量,将其转换为unordered_set
,并将 传递给unordered_set
回调。简单的?是的。
现在,因为我们要在一个线程上执行此操作,所以我们不能立即执行此操作。相反,我们将返回一个不带参数的 lambda。当调用该 lambda 时,它将创建unordered_set
并将其提供给回调。这样,我们可以将每个 lambda 分配给它自己的线程,每个线程将通过调用 lambda 来运行作业。
template<class Vector, class Callback>
auto lazyGetUnique(Vector& vector, Callback callback) {
using Iterator = decltype(vector.begin());
auto begin = vector.begin();
auto end = vector.end();
using elem_t = typename std::iterator_traits<Iterator>::value_type;
//We capture begin, end, and callback
return [begin, end, callback]() {
callback(std::unordered_set<elem_t>(begin, end));
};
}
现在 - 这个回调应该做什么?答案很简单:回调应该将 的内容分配unordered_set
给一个向量。为什么?因为我们要合并结果,合并向量比合并要快得多unordered_set
。
让我们编写一个函数来给我们回调:
template<class Vector>
auto assignTo(Vector& v) {
return [&](auto&& contents) {
v.assign(contents.begin(), contents.end());
};
}
假设我们想要获取向量的唯一元素,并将它们分配回该向量。这现在真的很简单:
std::vector<int> v = /* stuff */;
auto new_thread = std::thread( lazyGetUnique(v, assignTo(v)) );
在此示例中,当new_thread
完成执行时,v
将仅包含唯一元素。
让我们看一下完成所有操作的完整功能。
template<class Iterator>
auto getUnique(Iterator begin, Iterator end) {
using elem_t = typename std::iterator_traits<Iterator>::value_type;
std::vector<elem_t> blocks[4];
//Split things up into blocks based on the last 4 bits
//Of the number. This allows us to guarantee that no two blocks
//share numbers.
for(; begin != end; ++begin) {
auto val = *begin;
blocks[val & 0x3].push_back(val);
}
//Each thread will run their portion of the problem.
//Once it's found all unique elements, it'll stick the result in the block used as input
auto thread_0 = std::thread( lazyGetUnique(blocks[0], assignTo(blocks[0])) );
auto thread_1 = std::thread( lazyGetUnique(blocks[1], assignTo(blocks[1])) );
auto thread_2 = std::thread( lazyGetUnique(blocks[2], assignTo(blocks[2])) );
//We are thread_3, so we can just invoke it directly
lazyGetUnique(blocks[3], assignTo(blocks[3]))(); //Here, we invoke it immediately
//Join the other threads
thread_0.join();
thread_1.join();
thread_2.join();
std::vector<elem_t> result;
result.reserve(blocks[0].size() + blocks[1].size() + blocks[2].size() + blocks[3].size());
for(int i = 0; i < 4; ++i) {
result.insert(result.end(), blocks[i].begin(), blocks[i].end());
}
return result;
}
这个函数把东西分成 4 个块,每个块都是不相交的。它在 4 个块中的每个块中找到唯一元素,然后组合结果。输出是一个向量。
推荐阅读
- ruby-on-rails - 在 Rails 中使用 RSpec 测试互连进程(特别是 Kafka 进程)
- android - 运行程序时不显示 TableRow 和 textviews
- python - 在python中更改xml树的属性
- vue.js - Vue3相当于通过new Vue()创建组件实例
- database - 如何设置密码来锁定 Qt 中的数据库?
- debezium - 使用外部资源的 Debezium 引擎状态持久性
- http - 本地站点重定向到 https 并收到 ssl 错误 - nginx
- amazon-s3 - AWS DMS 将 RDS(MariaDB) 迁移到镶木地板中的 S3
- flutter - 如何在颤动中删除一些线的填充?
- linux - 在每行的最后一个字段中将具有特定条件的行打印到另一个文件中