<返回更多

C++中的HashTable性能优化

2023-03-22  网易号  腾讯技术工程
加入收藏

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

 

HashTable是开发中常用的数据结构。本文从C++ STL中的HashTable讲起，分析其存在的性能问题，对比业界改进的实现方式。通过基准测试对比其实际性能表现，总结更优的实现版本。
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. 分配内存
// flat_hash_map和node_hash_map均以raw_hash_set为父类实现，区别在于policy不同template , class Eq = absl::container_internal::hash_default_eq, class Allocator = std::allocator>>class flat_hash_map : public absl::container_internal::raw_hash_map< absl::container_internal::FlatHashMAppolicy, Hash, Eq, Allocator> {};template , class Eq = absl::container_internal::hash_default_eq, class Alloc = std::allocator>>class node_hash_map : public absl::container_internal::raw_hash_map< absl::container_internal::NodeHashMapPolicy, Hash, Eq, Alloc> {};template class raw_hash_map : public raw_hash_set{};// raw_hash_set分配连续内存的大小取决于 capacity_ 和 slot_typetemplate class raw_hash_set { using slot_type = typename Policy::slot_type; void initialize_slots() { // 分配连续内存的大小为 capacity_ * slot_size 并对齐 slot_align char* mem = static_cast(Allocate( &alloc_ref(), AllocSize(capacity_, sizeof(slot_type), alignof(slot_type)))); ctrl_ = reinterpret_cast(mem); slots_ = reinterpret_cast( mem + SlotOffset(capacity_, alignof(slot_type))); ResetCtrl(capacity_, ctrl_, slots_, sizeof(slot_type)); reset_growth_left(); infoz().RecordStorageChanged(size_, capacity_); } inline size_t AllocSize(size_t capacity, size_t slot_size, size_t slot_align) { return SlotOffset(capacity, slot_align) + capacity * slot_size; }};// flat_hash_map的slot包含pairtemplate struct FlatHashMapPolicy { using slot_type = typename map_slot_type;};template union map_slot_type { using value_type = std::pair; using mutable_value_type = std::pair, absl::remove_const_t>; value_type value; mutable_value_type mutable_value; absl::remove_const_t key;};// node_hash_map的slot为指向pair的指针template class NodeHashMapPolicy : public absl::container_internal::node_slot_policy< std::pair&, NodeHashMapPolicy>{};template struct node_slot_policy { using slot_type = typename std::remove_cv< typename std::remove_reference::type>::type*; // slot为指向pair的指针};

 

\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; }};基准测试

基准测试场景如下：

 

 

各容器读操作的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

 

声明：本站部分内容来自互联网,如有版权侵犯或其他问题请与我们联系，我们将立即删除或处理。
▍相关推荐
更多资讯 >>>
Copyright @ 简易百科 V 2.0 京ICP备14042104号