hash_strmap 为什么那么快

测试结果(普通PC，CPU 3G HZ，内存2G)

• 单核达到了每秒30,000,000次查询，string 长度是32字节。
• iteration 的速度, 比 std::map 快180倍以上, 比 unordered_map 快150倍。

同样是 Hash Map，为什么 hash_strmap 的查询速度可以比标准 unordered_map<string...> 快 10 倍？比 std::map （这个就不是hash map了）快40倍？超大数据量测试对比更明显，达到了12倍和50倍。并且，内存占用量还要小一倍以上？

链接

• 测试脚本：run.sh
• 代码链接：hash_strmap.hpp ; hash_strmap_bench.cpp
• 更早的一篇介绍：HashMap<string, ...> 能有多快

关键技术

使用大块内存

• 整个 map 只需要 3 或 4（ValueOut 时，见下）块连续内存
  1. bucket 数组: unsigned int* bucket; // 32 位，4 字节
  2. Node 数组: 需要多分配一个数组元素。
     多的那个Node，其 offset 用来计算最后一个 strlen，link 用来做 iterator.++ 的 guard

     struct Node {
         unsigned offset; // 4 bytes, point to strpool
         unsigned link;   // 4 bytes, open addressed link list in same bucket
         size_t   hash;   // cached hash value
                          // 4 bytes on 32 bit arch, 8 bytes on 64 bit arch
         Value    value;  // if ValueOut, have no this field
     };
     

  3. strpool
  4. values，如果是 ValueOut，Value/mapped_type 将保存在这个数组，与 Node 数组是平行的
• 而如果使用标准的 hash map 来做 string map，需要大量的小块内存
• hash 开地址链接使用整数数组下标，而传统的做法是使用指针来链接
  • 指针做链接在64位平台中是8个字节
  • 数组下标作链接，只需要32位，可以表达 4G-2 个结点，一般每个结点的尺寸总大于16字节（64位平台），即使 wordcount，结点尺寸也至少需要20个字节，从而结点数组的最大空间可以达到 80G。这几乎可以满足所有应用了。
• 尽可能使用 realloc，原因如下
  1. 使代码更加简洁
  2. 现代的 realloc, 特别是 linux 下，即使返回的地址与传入的不同，也可能不需要拷贝内存，因为实现上可以使用 mremap 来重新将那块物理内存的虚拟地址映射到另一个有更大连续空间的虚拟地址，当内存块很大时，性能的提升是非常可观的。而使用 malloc+memcpy 或者 std::vector 就没有这个优势了。具体可以去google搜索一下相关资料。

String Pool

• 所有 string 的内容保存在一大块连续的内存中，避免了小块内存分配的时间和空间开销
• 每个 string 由指向 string pool 的 offset 确定，而非一个指针
• 每个 string 的长度由相邻两个 offset 想减得到，这样可以省去专门存储长度的内存开销（offset 数组末尾需要多加一个元素）
• 对齐，对齐的数据在访问时有非常良好的性能，并且，可以一次处理多个字节（64 bit 中是 8 个字节）
• offset 和对齐是高度相关的并且接合起来有额外好处
  • 即使在 64 位平台上，offset 也只有 4 个字节，32 位，从而，最大的寻址空间是4G （实际上是 4G-1），所以 string pool 中的 string 总长度不能超过 4G
  • 如果对齐了，那么最低的 2 位（4 bytes 对齐）或 3 位（8 bytes 对齐）总是 0，所以，我就把实际的 offset （offset 在 64 位平台下是 64 位）除以 4 或者 8 再存储，这样，在64位平台中最大的寻址空间就多了 8 倍，达到 32G（实际上是 32G-8），再加上结点和桶空间，可以耗用120G的内存。这几乎可以满足所有的应用了。
  • 另一个好处，如果编译器足够智能，它可以判断出 string pool base ptr + offset 是按 8 字节对齐的，从而 memcpy 时可以优化。

compile time dispatch

• ValueInline/ValueOut
  • 如果 mapped_type (也就是 Value) 太大，或者其它原因，我们希望 Value 分开存储到一个平行的数组中，需要使用 ValueOut
  • ValueOut 还有一个额外的好处：因为 hash_strmap 支持排序/二分查找（不需要额外空间），如果是按 Value 排序，二分查找时 ValueOut 将导致更好地内存局部性
  • ValueOut 还有另一个额外的好处：当 enlarge （类似 vector 的enlarge）时，如果 Value 不能 memcpy (下面将提到的 FastCopy)，Node 数组仍然可以使用 realloc
• SafeCopy/FastCopy
  • 大部分对象都可以直接 memcpy 到另一个内存地址并毫无问题地直接使用（C++11 中得 std::move 是这样的一个泛化）
    • 简单的对象如各种基本类型，复杂点的如 std::string, std::vector, std::deque 等，当然 hash_strmap 是可以 memcpy 的
  • 什么样的对象memcpy 到另一个内存地址就不能正确使用了呢？原则讲只有一种：自己或内嵌对象的地址被别的东西引用了！
    • 比如说 std::list, list 为了优化，内嵌了一个 partial node: 仅包含 prev/next 字段的 node，空 list 的 partial node 的 prev/next 都指向partial node 本身，list::end() 返回的 iterator 实际上就是该 partial node.
    • 再比如说 ostringstream，它是个很大的对象（在 64bit gnu c++ 是 352 字节，44 ptr），其基类包含一个指向 streambuf 的指针，为了避免申请多余的动态空间，ostringstream 将自己的streambuf内嵌在自身。
    • std::map/set 等也有可能这样实现。

元素删除

• 可以使用非常复杂的内存管理策略来实现删除，但是因为硬性限制：string length 由 offset 想减获得。使得即使 string pool 内存管理很牛逼了，Node 数组的管理仍然会很复杂。因为 string 长度不固定的，这样的复杂内存管理，其能力已接近通用的malloc/free了。
• 所以使用非常简单的策略，其平摊复杂度是O(avgstrlen)，如果认为avgstrlen(字符串的平均长度)是个常数，这个复杂度就是O(1)
• 删除元素会在 Node 数组和 string pool 中形成空洞，删除标识用 link 域来表达。
• 删除的数目达到一定阈值（目前是达到一半）时，压缩并回收这些空洞

Guard / Past The End

• 为计算 string 长度，string 的 offset 需要多一个元素
• 为加速 iterator，link 域需要多一个元素

排序

• 传统的 hash map 不能支持排序，如果非要支持，就需要一个额外的数组来实现。
• 因为 hash_strmap 的 hash 链接是用 数组下标 来实现的，排序就太简单了，不需要额外的空间，代码也很简单，并且可以按Key 或 Value 排序，大部分情况下，即使在排序过程中也不需要额外的空间。
• 排序前先要回收删除元素以消除空洞，如果是按 Key 排序，因为 Key string length 是由 offset 想减得到的，排序时顺序被打乱，就无法得到 正确的 string length，而排序后总是需要 relink 的，从而可以事先将 string length 算出来存在 link 域，排序时就可以使用。
• 按 Key 排序还有一个额外好处，如果对 Key 的访问按字典序有局部性，即使不用二分查找而使用 hash 进行精确查找，性能也有不少提高
  • 对 bucket 的访问仍然是随机的，但是对 bucket[...] 指向的 Node(包含KeyValue) 的访问有这种局部性
• 其它更详细的，可以参见代码

其它

hash_strmap 删除一个元素时，有可能导致指向其它元素的 iterator 失效，这是与 std::map 和 unordered_map 相比之下的缺点