开源库 parallel-hashmap 介绍：高性能 线程安全 内存友好的哈希表 和 btree

后台开发很常见一大类需求是 线程安全 高性能 容器数据结构 开源的 https://github.com/greg7mdp/parallel-hashmap parallel-hashmap 是对 Google 的 abseil-cpp 库的改进，可供开发中直接使用。

参考官网的英文文档，简单翻译介绍如下：

[TOC]

parallel-hashmap 提供了一组卓越的 hash map 实现， 和 可以替代 std::map 和 std::set 的 btree 实现，并有如下特点:

• Header only: 无需链接。直接 include 头文件即可用。

• drop-in replacement for std::unordered_map, std::unordered_set, std::map and std::set。 原样替换，api 完全兼容标准 stl 容器 。

• 要求支持 C++11 的编译器 , 并且提供 C++14 和 C++17 的 API (例如 try_emplace)

• Very efficient, 明显比编译器默认提供的 unordered map/set 快， 也比 boost 的实现快，比 sparsepp 快。这里有个 benchmark ： https://martin.ankerl.com/2019/04/01/hashmap-benchmarks-01-overview/ ，大概 比 std::unorder_map 就是 insert快1倍，find 快3倍

• Memory friendly: 低内存占用，尽管略微高于 sparsepp 。 参考 abseil 的数据，https://abseil.io/about/design/btree 目前 64位模式下， libstdc++ 实现的 std::set<int32_t> 对插入的每个value，分配 40 字节， 而 absl::btree_set<int32_t> 对每个 value 分配 ~4.3 至 ~5.1 字节

• 支持 heterogeneous lookup

• 很容易前向声明 forward declare: 只需要在头文件中 include phmap_fwd_decl.h 来声明 Parallel Hashmap 容器就行 [注: 目前这种对包含指针作为 key 的哈希表不适用。]

• Dump/load 特性: 当一个 flat 哈希表存储了 std::trivially_copyable 的数据时, 表可以被 dump 到磁盘文件，并作为一个简单的数组高效地 restore 恢复，并且过程中不需要进行 hash 计算。这通常比逐个元素地序列化到磁盘快 10倍，但是会额外占用 10% - 60% 的磁盘空间。 见 examples/serialize.cc. (flat hash map/set only)

• Tested 在这些平台上经过了测试： Windows (vs2015 & vs2017, vs2019, Intel compiler 18 and 19), linux (g++ 4.8.4, 5, 6, 7, 8, clang++ 3.9, 4.0, 5.0) 和 MacOS (g++ and clang++) - click on travis and appveyor icons above for detailed test status.

• 自动支持 boost 的 hash_value() 方法，用来提供哈希函数 (见 examples/hash_value.h). 并且提供 std::pair 和 std::tuple 的哈希函数实现.

• natvis visualization support in Visual Studio (hash map/set only)

快速 和 内存友好

作者有个介绍文章 讲解了 Parallel Hashmap 的设计和好处.

总结起来说，Google absl 的 flat_hash_map 由于采用 2倍的内存增长 resize 策略，所以有个内存占用的尖峰 peak， 在尖峰时刻，需要3倍的临时内存占用，来把旧的 bucket 里面的数据移动到 新的2倍大的 bucket 里面。

文章提出的想法就是，把一个大的 flat_hash_map 拆分成2的倍数个比如 16个，这样内存峰值就只有原来的 1/16 了。

并且这种拆分还便于进行并发。

本库提供的 hashmap 和 btree 基于 Google 在 Abseil 库中开源的实现。 hashmap 使用了 closed hashing，就是 value 直接存成一个内存数组，避免内存间接访问。通过使用并发的 SSE2 指令，这些 hashmap 可以允许一次并发查找 16 个槽位，即使当 hashmap 的填充率已经达到 87.5% ，也可以保持快速。

重要: 本仓库借鉴了 abseil-cpp 仓库的代码, 做了修改，并且可能和原版本行为不同。本仓库是独立工作，像其他开源项目一样不提供保证。请访问 abseil-cpp 获取官方的 Abseil 库。

无需安装，代码里面直接 include 就行。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <iostream>
#include <string>
#include <parallel_hashmap/phmap.h>

using phmap::flat_hash_map;
 
int main()
{
    // Create an unordered_map of three strings (that map to strings)
    flat_hash_map<std::string, std::string> email = 
    {
        { "tom",  "[email protected]"},
        { "jeff", "[email protected]"},
        { "jim",  "[email protected]"}
    };
 
    // Iterate and print keys and values 
    for (const auto& n : email) 
        std::cout << n.first << "'s email is: " << n.second << "\n";
 
    // Add a new entry
    email["bill"] = "[email protected]";
 
    // and print it
    std::cout << "bill's email is: " << email["bill"] << "\n";
 
    return 0;
}

提供的各种哈希表及其优缺点

头文件 parallel_hashmap/phmap.h 提供下列 8 种 哈希表 :

• phmap::flat_hash_set
• phmap::flat_hash_map
• phmap::node_hash_set
• phmap::node_hash_map
• phmap::parallel_flat_hash_set
• phmap::parallel_flat_hash_map
• phmap::parallel_node_hash_set
• phmap::parallel_node_hash_map

头文件 parallel_hashmap/btree.h 提供一下基于 btree 的有序容器 ordered containers:

• phmap::btree_set
• phmap::btree_map
• phmap::btree_multiset
• phmap::btree_multimap

btree 容器是直接移植了 Abseil，因此应该是 Abseil 的表现一样，除了细微不同（例如支持 std::string_view 而不是 absl::string_view，并且有前向声明）

当 btree 被修改，value 可能在内存中被移动。这意味着当 btree 容器被修改时，指向 btree 容器中的 value 的指针或者迭代器会失效。 这和 std::map / std::set 显著不同, std 容器提供指针稳定性的保证。 ‘flat’ hash map 和 set 也会有这种失效。

全部的类型和模板参数可以在这个头文件看到： parallel_hashmap/phmap_fwd_decl.h , 这个头文件也可以用于前向声明 Parallel Hashmap 库。

哈希容器的关键设计点

• 名字包含 flat 的哈希表内部会移动 key 和 value，所以如果在外部包含了指向 flat 哈希表中元素的指针，当哈希表被修改时，指针可能会变成野指针。而名字包含 node 的哈希表内部不会移动 key 和 value，可以用在这种场合。

• flat 系列哈希表内存占用更少，并且通常比 node 系列哈希表更快，所以尽可能使用 flat系列。当然，例外情况是 value 很大（比如大于 100字节），在内存中移动时很慢的话，此时应使用 node 系列。

• parallel 系列的哈希表。当你需要在少数个哈希表中存储非常大量的 value 时， 应该优先用 parallel 系列 哈希表。而如果你需要在大量 哈希表中，每个存储相对少量的元素时，优先用非 parallel系列的哈希表。

• parallel 系列哈希表的好处是:
  a. 减少了 resize 时候内存占用的峰值。
  b. 可以打开多线程支持 (由于内部拆分成多个子哈希表，所以可以借此实现并发安全。)

btree 系列容器中的关键设计

Btree 系列容器是有序容器，可以作为 std::map 和 std::set 的替代。他们在每个树节点中存储多个value，因此更缓存友好，并且内存占用显著更低。

通常都应该优先用 Btree 容器，来代替 STL 中默认的红黑树容器。也有例外：

• 要求指针稳定性，或者迭代器稳定性。
• value 类型巨大，在内存中移动起来比较昂贵。

当不需要顺序的时候， 通常哈希表容器是比 btree容器 更好的选择。

对 Abseil’s 哈希表的改动

• 默认哈希，从 absl::hash 改成了 std::hash。 可以通过定义宏PHMAP_USE_ABSL_HASH改变。

• erase(iterator) 和 erase(const_iterator) 都返回指向被删除的元素的下一个元素的迭代器，和 std::unordered_map 一样. 并提供了一个非标准的 void _erase(iterator) ，用于不需要返回 value 的场合。

• 没有提供 absl::string_view 这种新类型。 std::hash<> 支持的所有类型 phmap 都支持 (如果编译器提供了 std::string_view 那 phmap 当然也支持).

• Abseil 哈希表内部会随机初始化一个哈希种子，这样迭代顺序就是非确定性的，当哈希表被用于面向用户的 web 服务场合的时候，这可以用于阻止 Denial Of Service 攻击，但是这使得调试变困难了。 phmap 哈希表默认不会实现这种随机初始化，但可以通过在 include phmap.h 之前 定义宏 #define PHMAP_NON_DETERMINISTIC 1 来打开这种随机初始化 (参考 raw_hash_set_test.cc).

• 和 Abseil 哈希表不一样, 我们内部做了 哈希值的混合。这在用户提供的哈希函数熵分布比较差的时候， 可以避免哈希表出现严重性能下降。这代理的性能开销是非常低的，并且在使用 不完美 的哈希函数的时候， 也能提供稳定的性能。

• size() 是容器中的 value 数量，通过 size() 方法返回。
• load_factor() 是比例: size() / bucket_count(). 从 0.4375 (刚 resize 之后) 到 0.875 (在 resize 之前) 之间波动. bucket 数组的大小每次 resize 都 double。
• value 9 来自 sizeof(void *) + 1, 由于对 bucket 数组 中的每一个 entry， node 哈希表存储一个指针加一个字节的元数据，
• flat 哈希表存储 value， 加每个value 一个字节的元数据，直接存储在 bucket 数组中，因此得到 sizeof(C::value_type) + 1.
• resize 时候的额外峰值内存占用，取决于旧的 bucket 数组的大小（是新bucket数组大小的 0.5倍），就是需要被复制到新bucket数组的 value，并在复制完成后，老的 value 会被释放。
• parallel 哈希表,当用模板参数 N=4 时, 创建 16 个 submap. 当哈希值均匀分布，并在单线程模式下, 任何时间点都只有一个 submap 做 resize，因此比值约等于 0.03 即 0.5 / 16

哈希表容器的 Iterator 迭代器失效

规则和 std::unordered_map 相同。

btree 容器的 Iterator 失效

不同于 std::map 和 std::set, 任何修改操作都可能使得存活的迭代器失效。

Example 2 - 为用户自定义类提供 hash 函数

为了使用 flat_hash_set 或者 flat_hash_map，自定义类需要提供一个 哈希函数。可以通过以下2种方法之一实现：

• 通过 HashFcn 模板参数提供一个 hash 函数

• 使用 boost 的话，可以在自定义类中加一个 hash_value() friend 函数.

例子自己看官方文档吧， 就不贴了。

线程安全性

Parallel Hashmap 容器遵循 C++ 标准库的线程安全规则。具体地:

• 单个 phmap 哈希表从多个线程读，是线程安全的。例如，给定一个哈希表 A，从 thread 1 和 thread 2 并发读是安全的。

• 如果单个哈希表在被一个线程写，在任何线程进行的，对该哈希表的读写操作，都是不安全的，需要被保护。例如，给定哈希表 A， 如果 thread 1 在写 A， 比如避免 thread 2 在同时读或者写 A。

• 不同线程对同一种 type 的不同实例，并发进行读写，是安全的。例如，给定相同类型的哈希表 A 和 B , 在 thread 1 中写 A， 并且在 thread 2 中读 B ，是安全的。

• parallel 系列的哈希表，可以通过提供一个 synchronization type (例如 std::shared_mutex, boost::shared_mutex, std::mutex, ) 作为模板的最后一个参数， 变成读写操作内部线程安全的。因为内部是在 submap 子哈希表上进行了加锁，可以获得一种较大的并发水平。读操作可以通过 if_contains() 安全地进行, 通过持有 submap 的锁，并把 value 的引用传给回调函数。类似地， 用 modify_if 或 try_emplace_l可以进行安全的写操作。但是要注意，标准 API 返回的迭代器或者引用并没有被 mutex 保护，所以当另一个线程可能修改哈希表时，不能可靠地使用他们。

• 如果使用各种 mutex 类型的例子，包括 boost::mutex, boost::shared_mutex 和 absl::Mutex 可以参考 examples/bench.cc

parallel_系列容器的线程安全的函数有：

• insert()
• emplace()
• lazy_emplace()
• erase()
• merge()
• swap()
• rehash()
• find()
• bucket_count()
• has_element()
• if_contains()
• modify_if()
• try_emplace_l()

多线程的例子，例如

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

#include <assert.h>
#include <stdint.h>

#include <map>
#include <mutex>
#include <thread>
#include <unordered_map>
#include <vector>

#include "mm3rd/parallel-hashmap/parallel_hashmap/phmap.h"

// 替代：std::unordered_map<uint64_t, uint32_t>
typedef phmap::parallel_flat_hash_map<uint64_t, uint32_t, phmap::priv::hash_default_hash<uint64_t>,
                                     phmap::priv::hash_default_eq<uint64_t>,
                                     std::allocator<std::pair<const uint64_t, uint32_t>>, 4, std::mutex>
   MapT;

int main() {
   MapT index;
   const static uint32_t key_num = 10000;
   const static int thread_num = 10;
   
for (uint64_t key = 0; key < key_num; ++key) {
       index.try_emplace_l(
           key, [](uint32_t& val) { val = 0; }, 0);
   }
   std::vector<std::thread> thread_list;
   for (int i = 0; i < thread_num; ++i) {
       thread_list.push_back(std::thread([&]() {
           for (uint64_t key = 0; key < key_num * 10; ++key) {
               index.modify_if(key, [](uint32_t& val) { ++val; });
           }
       }));
   }
   for (auto& t : thread_list) {
       t.join();
   }

   uint32_t hit_num = 0;
   for (uint64_t key = 0; key < key_num * 10; ++key) {
       index.if_contains(key, [&](const uint32_t& val) {
           assert(thread_num == val);
           ++hit_num;
       });
   }

   assert(hit_num == key_num);

   return 0;
}