如何最快在元素唯一的小型数组中查找匹配元素

在Erlang运行时系统中，持久化哈希表在数据规模较大时采用hash-array-mapped-trie结构表示，规模较小时则采用flatmap结构表示。我最近被这个技术点吸引，开始着手研究相关优化方案。

flatmap 核心特性 #

• 最多存储32个键，以及对应的32个值
• 键值对无序存储在C数组中
• 不存在重复键
• 键为unboxed类型：直接比较两个uint64_t类型的值即可判断键是否匹配

初始实现与问题 #

当前版本的查找实现代码如下：

uint64_t *original_flatmap_get(uint64_t *keys, uint64_t *vals, uint64_t key, uint64_t max_size) {
  uint64_t n = max_size;
  uint64_t i;

  for (i = 0; i < n; ++i) {
    if (keys[i] == key) {
      return &vals[i];
    }
  }
  return NULL;
}

（代码简化自Erlang/OTP运行时源码的对应实现）

这个原始实现完全没有利用到flatmap的固有特性。我做优化时首先让编译器明确两个前提约束：

• 键数组最多包含32个元素
• 由于键全局唯一，整个数组里最多只会存在一个匹配项，不需要遍历过程中提前返回第一个匹配结果，遍历完成后返回匹配到的结果即可

调整后的优化版本 #

基于上述约束调整后的实现代码如下：

uint64_t *latereturn_flatmap_get(uint64_t *keys, uint64_t *vals, uint64_t key, uint64_t max_size) {
  uint64_t n = min(max_size, 32);
  uint64_t i;

  uint64_t *res = NULL;
  for (i = 0; i < n; ++i) {
    if (keys[i] == key) {
      res = &vals[i];
    }
  }
  return res;
}

查看编译输出可以发现，Clang和GCC已经能够对这个版本的循环做自动向量化和循环展开优化，实际基准测试显示，这个简单调整就能带来5%-15%的性能提升。

待探索的进一步优化方向 #

目前仍在探索是否存在进一步提升查找性能的可能，核心疑问包括两点：

• 是否可以通过特定语法或编译器内置函数告知编译器，数组内所有键值均唯一，从而触发更激进的编译优化？
• 是否可以跳过编译器自动向量化，直接手动编写SIMD指令实现更高性能的查找逻辑？

内容的提问来源于stack exchange，提问作者Qqwy