英特尔TBB https://software.intel.com/en-us/tbb是开源的,并且在GitHub https://github.com/intel/tbb:
https://github.com/intel/tbb
为了安装 TBB,我使用了vcpkg https://github.com/Microsoft/vcpkg这是兼容的Linux
, Windows
and Mac
。是的,vcpkg来自微软,但它是100%跨平台、开源的,而且非常流行。
Linux:
./vcpkg search tbb # Find the package.
./vcpkg install tbb:x64-linux # Install the package.
Windows:
vcpkg search tbb # Find the package.
vcpkg install tbb:x64-windows # Install the package.
Compile:
- 与任何现代编译器兼容,包括 MSVC、GCC、LLVM、Intel 编译器 (ICC) 等。我使用过
CMake
for gcc
.
还可以下载源代码并将标头和库提取到源代码树中,这也同样有效。
Code.
#include "tbb/concurrent_hash_map.h" // For concurrent hash map.
tbb::concurrent_hash_map<int, string> dict;
typedef tbb::concurrent_hash_map<int, string>::accessor dictAccessor; // See notes on accessor below.
print(" - Insert key, method 1:\n");
dict.insert({1,"k1"});
print(" - 1: k1\n");
print(" - Insert key, method 2:\n");
dict.emplace(2,"k2");
print(" - 2: k2\n");
string result;
{
print(" - Read an existing key:\n");
dictAccessor accessor;
const auto isFound = dict.find(accessor, 2);
// The accessor functions as:
// (a) a fine-grained per-key lock (released when it goes out of scope).
// (b) a method to read the value.
// (c) a method to insert or update the value.
if (isFound == true) {
print(" - {}: {}\n", accessor->first, accessor->second);
}
}
{
print(" - Atomically insert or update a key:\n");
dictAccessor accessor;
const auto itemIsNew = dict.insert(accessor, 4);
// The accessor functions as:
// (a) a fine-grained per-key lock (released when it goes out of scope).
// (b) a method to read the value.
// (c) a method to insert or update the value.
if (itemIsNew == true) {
print(" - Insert.\n");
accessor->second = "k4";
}
else {
print(" - Update.\n");
accessor->second = accessor->second + "+update";
}
print(" - {}: {}\n", accessor->first, accessor->second);
}
{
print(" - Atomically insert or update a key:\n");
dictAccessor accessor;
const auto itemIsNew = dict.insert(accessor, 4);
// The accessor functions as:
// (a) a fine-grained per-key lock which is released when it goes out of scope.
// (b) a method to read the value.
// (c) a method to insert or update the value.
if (itemIsNew == true) {
print(" - Insert.\n");
accessor->second = "k4";
}
else {
print(" - Update.\n");
accessor->second = accessor->second + "+update";
}
print(" - {}: {}\n", accessor->first, accessor->second);
}
{
print(" - Read the final state of the key:\n");
dictAccessor accessor;
const auto isFound = dict.find(accessor, 4);
print(" - {}: {}\n", accessor->first, accessor->second);
}
印刷用途{fmtlib} https://github.com/fmtlib/fmt用于印刷;可以替换为cout <<
.
Output:
- Insert key, method 1:
- 1: k1
- Insert key, method 2:
- 2: k2
- Read an existing key:
- 2: k2
- Atomically insert or update a key:
- Insert.
- 4: k4
- Atomically insert or update a key:
- Update.
- 4: k4+update
- Read the final state of the key:
- 4: k4+update
其他哈希图
- See: https://tessil.github.io/2016/08/29/benchmark-hopscotch-map.html https://tessil.github.io/2016/08/29/benchmark-hopscotch-map.html
- See:
std::unordered_map
。这有一个更标准的 API,并且在很多情况下都是线程安全的,请参阅:unordered_map线程安全 https://stackoverflow.com/questions/9685486/unordered-map-thread-safety。如果可能的话,建议使用它,因为它有一个更简单的 API。
- 还有
concurrent_unordered_map
来自英特尔 TBB。它本质上是同一件事,即键/值映射。然而,它的历史要长得多,级别要低得多,而且使用起来更困难。必须提供一个哈希器、一个相等运算符和一个分配器。即使在英特尔官方文档中,也没有任何示例代码。尽管我进行了几个月的偶尔尝试,但我从未成功过。它可能已过时,因为在所述免费书中未提及(它仅涵盖concurrent_hash_map
)。不建议。
更新:读取器/写入器锁
实际上有两种访问器,一种是读锁,一种是写锁:
如果使用find
, use const_accessor
这是一个读锁。如果使用insert
or erase
, use accessor
这是一个写锁(即它将等待任何读取完成,并阻止进一步的读取直到完成)。
这实际上相当于读/写锁 https://en.wikipedia.org/wiki/Readers%E2%80%93writer_lock,但是在字典中的单个字典键上,而不是整个字典上。
Update
学习曲线的最后部分:对于键写入,在访问器超出范围之前不会发生任何事情。因此,任何锁定都不会超过几个机器指令,可能使用 CAS(比较和交换)。
与数据库相比,访问器的范围就像一个事务。当访问器超出范围时,整个事务将提交到哈希映射。
Update
上面提到的免费书籍在以下章节中提供了精彩的性能技巧:concurrent_hash_map
.
结论
这个哈希图的 API 很强大,但有些笨拙。但是,它支持插入/更新时的细粒度、每键锁定。任何锁都仅为少数机器指令而持有,使用CAS https://en.wikipedia.org/wiki/Compare-and-swap。这是其他任何语言的哈希图都无法提供的。建议从std::unordered_map
为了简单起见;这是只要两个线程不写入同一个键,线程就是安全的 https://stackoverflow.com/questions/9685486/unordered-map-thread-safety。如果需要极快的性能,可以选择重构,或者在上面编写兼容的包装器[]
访问器和insert_or_update()
.