C++中的HashTable性能优化

作者：leomryang，腾讯 PCG 后台开发工程师

HashTable是开发中常用的数据结构。本文从C++ STL中的HashTable讲起，分析其存在的性能问题，对比业界改进的实现方式。通过基准测试对比其实际性能表现，总结更优的实现版本。

STL中的HashTable实现为std::unordered_map，采用链接法(chAIning)解决hash碰撞，hash值相同的多个pair组织为链表，如图1所示。

图1 std::unordered_map内存布局

查找key值时，需要遍历对应的链表，寻找值相同的key。链表中节点内存分布不连续，相邻节点处于同一cache line的概率很小，因此会产生较多的cpu cache miss，降低查询效率。

改进版HashTable

google absl::flat_hash_map采用开放寻址法(open addressing)解决hash碰撞，并使用二次探测(quadratic probing)方式。absl::flat_hash_map改进了内存布局，将所有pair放在一段连续内存中，将hash值相同的多个pair放在相邻位置，如图2所示。

图2 absl::flat_hash_map内存布局

查找key时，以二次探测方式遍历hash值相等的pair，寻找值相等的key。hash值相同的pair存储在相邻内存位置处，内存局部性好，对cpu cache友好，可提高查询效率。

在内存用量方面，absl::flat_hash_map空间复杂度为 *O((sizeof(std::pair) + 1) * bucket_count())*。最大负载因子被设计为0.875，超过该值后，表大小会增加一倍。因此absl::flat_hash_map的size()通常介于 0.4375 * bucket_count() 和 0.875 * bucket_count() 之间。

需要注意，absl::flat_hash_map在rehash时，会对pair进行move，因此pair的指针会失效，类似下述用法会访问非法内存地址。

absl::flat_hash_map map;// ... init mapFoo& foo1 = map["f1"];Foo* foo2 = &(map["f2"]);// ... rehash mapfoo1.DoSomething(); // 非法访问，foo1引用的对象已被movefoo2->DoSomething(); // 非法访问，foo2指向的对象已被move

为了解决上述pair指针失效问题，google absl::node_hash_map将pair存储在单独分配的节点中，在连续内存中存放指向这些节点的指针，其他设计与flat_hash_map相同，如图3所示。

图3 absl::node_hash_map内存布局

absl::node_hash_map在rehash时，pair本身无需移动，只需将指针拷贝至新的地址。可保证pair的指针稳定性。

源码探究

下面对absl两种HashTable的核心逻辑源码进行探索（省略不相关部分的代码）：

1. 分配内存

\2. 添加元素

template class raw_hash_set { // 查找 // Attempts to find `key` in the table; if it isn't found, returns a slot that // the value can be inserted into, with the control byte already set to // `key`'s H2. template std::pair find_or_prepare_insert(const K& key) { prefetch_heap_block(); auto hash = hash_ref()(key); // 在相同hash值的桶中查找 auto seq = probe(ctrl_, hash, capacity_); while (true) { Group g{ctrl_ + seq.offset()}; for (uint32_t i : g.Match(H2(hash))) { // 如果key相等，则找到了目标元素 if (ABSL_PREDICT_TRUE(PolicyTraits::apply( EqualElement{key, eq_ref()}, PolicyTraits::element(slots_ + seq.offset(i))))) return {seq.offset(i), false}; } if (ABSL_PREDICT_TRUE(g.MaskEmpty())) break; seq.next(); assert(seq.index() <= capacity_ && "full table!"); } // 如果没有相等的key，则插入元素 return {prepare_insert(hash), true}; } // 找到下一个可用的slot // Given the hash of a value not currently in the table, finds the next // viable slot index to insert it at. size_t prepare_insert(size_t hash) ABSL_ATTRIBUTE_NOINLINE { auto target = find_first_non_full(ctrl_, hash, capacity_); if (ABSL_PREDICT_FALSE(growth_left() == 0 && !IsDeleted(ctrl_[target.offset]))) { rehash_and_grow_if_necessary(); target = find_first_non_full(ctrl_, hash, capacity_); } ++size_; growth_left() -= IsEmpty(ctrl_[target.offset]); SetCtrl(target.offset, H2(hash), capacity_, ctrl_, slots_, sizeof(slot_type)); infoz().RecordInsert(hash, target.probe_length); return target.offset; } // 在找到的slot处构造元素 template iterator lazy_emplace(const key_arg& key, F&& f) { auto res = find_or_prepare_insert(key); if (res.second) { slot_type* slot = slots_ + res.first; std::forward(f)((&alloc_ref(), &slot)); assert(!slot); } return iterator_at(res.first); }};

\3. rehash

template class raw_hash_set { // Called whenever the table *might* need to conditionally grow. void rehash_and_grow_if_necessary() { if (capacity_ == 0) { resize(1); } else if (capacity_ > Group::kWidth && size() * uint64_t{32} <= capacity_ * uint64_t{25}) { drop_deletes_without_resize(); } else { // Otherwise grow the container. resize(capacity_ * 2 + 1); } } void resize(size_t new_capacity) { assert(IsValidCapacity(new_capacity)); auto* old_ctrl = ctrl_; auto* old_slots = slots_; const size_t old_capacity = capacity_; capacity_ = new_capacity; initialize_slots(); size_t total_probe_length = 0; for (size_t i = 0; i != old_capacity; ++i) { if (IsFull(old_ctrl[i])) { size_t hash = PolicyTraits::apply(HashElement{hash_ref()}, PolicyTraits::element(old_slots + i)); auto target = find_first_non_full(ctrl_, hash, capacity_); size_t new_i = target.offset; total_probe_length += target.probe_length; SetCtrl(new_i, H2(hash), capacity_, ctrl_, slots_, sizeof(slot_type)); // 调用 policy transfer 在新地址处构造元素 PolicyTraits::transfer(&alloc_ref(), slots_ + new_i, old_slots + i); } } if (old_capacity) { SanitizerUnpoisonMemoryRegion(old_slots, sizeof(slot_type) * old_capacity); Deallocate( &alloc_ref(), old_ctrl, AllocSize(old_capacity, sizeof(slot_type), alignof(slot_type))); } infoz().RecordRehash(total_probe_length); }};// flat_hash_map在rehash时，将元素移动至新地址处template struct map_slot_policy { template static void transfer(Allocator* alloc, slot_type* new_slot, slot_type* old_slot) { emplace(new_slot); // 将元素 move 至新地址处 if (kMutableKeys::value) { absl::allocator_traits::construct( *alloc, &new_slot->mutable_value, std::move(old_slot->mutable_value)); } else { absl::allocator_traits::construct(*alloc, &new_slot->value, std::move(old_slot->value)); } destroy(alloc, old_slot); }};// node_hash_map在rehash时，将指向元素的指针拷贝至新地址处template struct node_slot_policy { template static void transfer(Alloc*, slot_type* new_slot, slot_type* old_slot) { // 将“指向元素的地址” copy 至新地址处 *new_slot = *old_slot; }};基准测试

基准测试场景如下：

• k、v均为std::string
• k长度约20字节
• v长度约40字节
• 写操作：向空map中，emplace N个k值不同的pair
• 读操作：从包含N个pair的map中，find N次随机k值（提前生成好的随机序列）

各容器读操作的cache miss情况如下：

# std::unordered_mapperf stat -e cpu-clock,cycles,instructions,L1-dcache-load-misses,L1-dcache-loads -p 2864179 ^C Performance counter stats for process id '2864179': 18,447.43 msec cpu-clock # 1.000 CPUs utilized 56,278,197,029 cycles # 3.051 GHz 25,374,763,394 instructions # 0.45 insn per cycle 265,164,336 L1-dcache-load-misses # 3.17% of all L1-dcache hits 8,377,925,973 L1-dcache-loads # 454.151 M/sec 18.453787989 seconds time elapsed# absl::node_hash_mapperf stat -e cpu-clock,cycles,instructions,L1-dcache-load-misses,L1-dcache-loads -p 2873181 ^C Performance counter stats for process id '2873181': 42,683.27 msec cpu-clock # 1.000 CPUs utilized 130,088,665,294 cycles # 3.048 GHz 134,531,389,793 instructions # 1.03 insn per cycle 334,111,936 L1-dcache-load-misses # 0.74% of all L1-dcache hits 44,998,374,652 L1-dcache-loads # 1054.239 M/sec 42.685607230 seconds time elapsed# absl::flat_hash_mapperf stat -e cpu-clock,cycles,instructions,L1-dcache-load-misses,L1-dcache-loads -p 2867048 ^C Performance counter stats for process id '2867048': 27,379.72 msec cpu-clock # 1.000 CPUs utilized 83,562,709,268 cycles # 3.052 GHz 82,589,606,600 instructions # 0.99 insn per cycle 188,364,766 L1-dcache-load-misses # 0.68% of all L1-dcache hits 27,605,138,227 L1-dcache-loads # 1008.233 M/sec 27.388859157 seconds time elapsed

可以看到std::unordered_map L1-dcache miss率为3.17%，absl::node_hash_map为0.74%，absl::flat_hash_map为0.68%，验证了上述关于不同内存模型下cpu cache性能表现的推论。

基准测试结果如下（为了显示更清晰，将元素个数小于1024的和大于1024的分开展示）：

图4 写操作，元素个数小于等于1024

图5 写操作，元素个数大于等于1024

图6 读操作，元素个数小于等于1024

图7 读操作，元素个数大于等于1024

从测试结果可以看出，写操作耗时：std::unordered_map < absl::flat_hash_map < absl::node_hash_map，absl::flat_hash_map比std::unordered_map耗时平均增加9%；读操作耗时：absl::flat_hash_map < absl::node_hash_map < std::unordered_map，absl::flat_hash_map比std::unordered_map耗时平均降低20%。

总结

三种HashTable对比如下：

HashTable类型

内存模型

性能表现

推荐使用场景

std::unordered_map

以链表存储hash值相同的元素

写操作：rehash友好，性能最好；读操作：内存不连续，cpu cache命中率较低，性能最差

写多读少

absl::node_hash_map

在连续内存中存储hash值相同的元素的指针

写操作：性能最差；读操作：性能略差于absl::flat_hash_map；

读多写少，且需要保证pair的指针稳定性

absl::flat_hash_map

在连续内存中存储hash值相同的元素

写操作：性能略差于std::unordered_map；读操作：内存连续，cpu cache命中率较高，性能最好

读多写少

在读多写少的场景使用HashTable，可以用absl::flat_hash_map替代std::unordered_map，获得更好的查询性能。但需注意absl::flat_hash_map在rehash时会将pair move到新的内存地址，导致访问原始地址非法。

absl::flat_hash_map的接口类似于std::unordered_map，详细介绍可参阅absl官方文档：https://abseil.io/docs/cpp/guides/container#hash-tables

• absl::flat_hash_map源码：abseil-cpp/flat_hash_map.h at master · abseil/abseil-cpp · Github
• std::unordered_map源码：gcc/unordered_map.h at master · gcc-mirror/gcc · GitHub
• folly 14-way hash table：folly/F14.md at main · facebook/folly · GitHub
• robin_hood hash table：GitHub - martinus/robin-hood-hashing: faster and more memory efficient hashtable based on robin hood hashing for C++11/14/17/20