资讯

历史

科技

环境与自然

成长

游戏

财经

文学与艺术

美食

健康

家居

文化

情感

汽车

三农

军事

旅行

运动

教育

生活

星座命理

phmap 学习和思考

创作时间:

作者:

@小白创作中心

phmap 学习和思考

引用

CSDN

https://blog.csdn.net/weixin_42877425/article/details/139884650

Hashing 分类

Closed Hashing

Closed hashing，也称为开放寻址（open addressing），是hashmap的一种实现方式，在这种方法中，所有元素都直接存储在hashmap的数组里。当发生hash碰撞时，按照某种方法在hashmap的底层数组中寻找另一个空槽位，这个过程称为探测。探测方法包括：

线性探测：当发生冲突时，顺序检查表中的下一个槽位，直到找到一个空槽位。这种方法简单，但可能导致聚集（clustering）问题，即连续的槽位被占用，从而影响性能。
二次探测：当发生冲突时，探测序列不是简单地检查下一个槽位，而是检查当前位置加上探测次数的平方的位置。这种方法可以减少聚集问题，但仍然可能存在次级聚集。
双重散列探测：使用两个哈希函数，当发生冲突时，使用第二个哈希函数计算探测的步长。这种方法通常可以避免聚集，并且分布更加均匀。

Closed hashing的优点非常明显：

不需要额外的指针和链表，占用的内存更少。
不像链表hash中，元素在内存中较为分散，closed hashing使用连续数组存储的，可以提高缓存命中率（cache-friendly）。
由于连续存储，序列化和反序列化容易。

Closed hashing的缺点也非常明显：

装填因子限制。当哈希表变得过于满时，性能会显著下降（探测开销变大），因此需要定期调整哈希表的大小。
删除复杂。由于探测序列的存在，简单删除探测序列中的某个值，会造成探测序列的中断，因此需要为删除的值添加一个特殊标记以防止探测序列中断。

Open Hashing

Open hashing，也称为链表哈希（chaining），其在哈希表的每个槽位上维护一个链表。当多个元素发生hash碰撞时，这些元素会被添加到这个槽位指向的链表中。

phmap

全称为parallel hashmap。其中的hashmap类是基于google开源的abseil库中的absl::flat_hash_map实现的。它们都使用前文提到的closed hashing。

相比于stl库中的unordered_hashmap的open hashing，其使用的是closed hashing，将k-v pair直接存储在数组中。下图是寻址的过程。

phmap提供了：

phmap::flat_hash_map
phmap::parallel_flat_hash_map

前者的使用场景是，有大量的hash map（即hashmap中有大量item），而每个item的value长度较小。后者的使用场景是，只有少量的hash map（即少量的item），而每个item的value长度非常大（其支持并行处理，能同时分别更新不同item的value）。

absl::flat_hash_map与std::unordered_map的比较

上面的图是往map中插入1亿个k-v对（大小为两个8-byte的int类型）的过程中，所统计的内存占用和耗时。从图中可以观察到无论是内存占用还是插入耗时，absl::flat_hash_map的性能都是优于std:unordered_map的。

Peak Memory Usage Issue

从上图中可以观察到，absl::flat_hash_map存在peak memory问题。该问题存在的原因是absl::flat_hash_map底层数组的扩容。当底层数组的容量到达总容量的87.5%的时候，就会进行扩容，扩容之后的总容量将会是扩容前总容量的2倍，扩容之后，原来数组中的元素会被重新hash，存到新申请的数组中。当老数组中的元素全部移动到新数组之后，老数组才会被销毁。也就是说当新数组和老数组并存时，占用的内存就是老数组占用内存的3倍。

举个例子，假设运行当前程序的机器的RAM为32GB，当absl::flat_hash_map插入10GB数据时想要进行扩容（也就是说老数组容量为11.42GB，新分配的数组的容量为22.85GB）此时的peak memory为34.28GB，这显然会造成OOM问题。

为了避免peak memory issue，只能使用sparsepp或者google的cpp-btree。

phmap中的parallel hashmap是如何解决peak memory usage问题

为了解决peak memory问题。phmap提出了parallel hashmap，其内部维护了一个submap的列表，每个submap自己又是一个hashmap，当submap的容量到达87.5%的时候，会自动进行扩容，而不是整个parallel hashmap一起进行扩容。下图是对要插入的key被分配到哪个submap的过程（真是天才）。（不过相对于不使用submap来说，增加了确定插入的submap的index的计算时间，和存储submap带来的一些额外开销）。

此处对phmap::parallel_flat_hash_map引入submap所带来的额外开销进行分析。

以插入为例子，可以拆解为三步：

计算key的hash值
对hash值计算index，index = (hash ^ (h >> 3)) & 0x7
将k-v插入到submap中

对于步骤2实现仅仅只需要几条指令，执行速度快。

对于步骤1，开销会比较大，但是其通过给submap传递这个hash值，来帮助submap节省一次hash运算（真是天才）。

然而从上图可以发现盲目使用parallel_flat_hash_map可能会带来轻微得增大插入耗时的问题。

比较phmap::flat_hash_map、phmap::parallel_flat_hash_map和std::unordered_hash_map的性能

上图表明parallel_flat_hash_map的性能出奇得好，而且可以观察到submap的内存扩容基本上发生在同一个时间点附近，由此可以表明，其提出的将key进行hashing然后来寻找submap的算法也是非常优秀的。

Parallel_flat_hash_map带来的天然的并行优势

因为parallel_flat_hash_map内部维护了16个submap，因此其天然就是支持多线程处理的（只要让不同的线程同时写入的是不同的submap就可以）。

但是当线程访问的是同一个submap的时候，仍然存在数据竞争问题，因此parallel_flat_hash_map模板参数可以传递一个std::mutex，利用互斥来解决多线程访问同一个submap的问题，当然这又会引入开锁解锁的的开销。

要解决锁带来的开销，实现真正的lock-free。可以魔改如下代码：

template <class HT>
void _fill_random_inner_mt(int64_t cnt, HT &hash, RSU &rsu)
{
    constexpr int64_t num_threads = 8;   // has to be a power of two
    std::unique_ptr<std::thread> threads[num_threads];
    auto thread_fn = [&hash, cnt, num_threads](int64_t thread_idx, RSU rsu) {
        size_t modulo = hash.subcnt() / num_threads;        // subcnt() returns the number of submaps
        for (int64_t i=0; i<cnt; ++i)                       // iterate over all values
        {
            unsigned int key = rsu.next();                  // get next key to insert
            size_t hashval = hash.hash(key);                // compute its hash
            size_t idx  = hash.subidx(hashval);             // compute the submap index for this hash
            if (idx / modulo == thread_idx)                 // if the submap is suitable for this thread
            {
                hash.insert(typename HT::value_type(key, 0)); // insert the value
                ++(num_keys[thread_idx]);                     // increment count of inserted values
            }
        }
    };
    // create and start 8 threads - each will insert in their own submaps
    // thread 0 will insert the keys whose hash direct them to submap0 or submap1
    // thread 1 will insert the keys whose hash direct them to submap2 or submap3
    // --------------------------------------------------------------------------
    for (int64_t i=0; i<num_threads; ++i)
        threads[i].reset(new std::thread(thread_fn, i, rsu));
    // rsu passed by value to threads... we need to increment the reference object
    for (int64_t i=0; i<cnt; ++i)
        rsu.next();
    
    // wait for the threads to finish their work and exit
    for (int64_t i=0; i<num_threads; ++i)
        threads[i]->join();
}

也就是为每个线程分配其能够处理的submap的index，对插入的全量数据计算submap的index，发现不是自负责的submap就不处理，发现是自己负责的submap就插入到submap中。使用这种方式的性能开销见下图

这里分析一下，在扩容时peak memory问题稍微被放大的原因。这是因为上图是在8线程下运行的，也就说同时会有8个submap进行扩容（一共有16个submap），peak memory将是不使用submap的1/2。

可以看到利用无锁还是比较麻烦的（自己要实现寻找submap的代码），因此我们还是使用phmap::flat_hash_map的互斥来实现吧（只要开多线程往phmap::flat_hash_map里面塞数据就好，其能够帮我们解决数据竞争）。上图比较的是使用1个线程往phmap::flat_hash_map插入1亿k-v和使用8个线程并发得往phmap::parallel_flat_hash_map插入1亿k-v的性能。