SIMD in Velox - BigintValuesUsingHashTable

BigintValuesUsingHashTable 用一个整数哈希集合实现精确成员过滤。批量路径先让不同 lane 分别查询一个输入值，发生冲突后再用整个 SIMD batch 连续检查同一个值的候选槽。两阶段使用同一类寄存器，lane 的含义却不同。

执行流程与相关实现核对于 2026-09-29，Velox 源码版本为 48883e8521b2。下文源码节选、历史资料和宿主集成引用各自注明版本；教学输入用于解释状态变化，未作为性能基准运行。

1. 整数集合过滤器的语义与 SIMD 使用位置

BigintValuesUsingHashTable 实现整数集合成员测试：给定一组允许值，判断输入整数是否属于该集合。它是 common::Filter 的一种实现，不负责保存 Join payload，也不承担完整 HashJoin 语义。扫描或过滤路径能否使用它，还取决于表达式转换、类型和 connector 的能力。

位置	输入与结果	本文关注的成本
过滤器构造	允许值集合 → 可查询的内部表示	值域、稠密度、容量、冲突和空槽标记
标量测试	一个整数 → 是否命中	hash、槽位探测及终止条件
批量测试	多个整数 → 每个 lane 的命中结果	批量范围检查、首槽 gather 与冲突处理
null 测试	null 值 → nullAllowed 对应结果	与数值 batch 和内部 empty marker 分开处理

这里有两种 SIMD 并行方式。第一轮让多个输入值各自检查自己的首槽；发生冲突后，再对某一个输入值连续检查多个槽。一次向量操作处理“多个查询”还是“同一查询的多个候选”，决定了 gather、连续加载和 mask 的意义，不能只看寄存器宽度。

在进入 SIMD 细节前，还要先看表示选择。稠密集合可能适合 bitmask，单值或连续范围也有更直接的测试方式；哈希表示服务于相应的数据分布。后面保留构造、探测、边界回绕和全部 intrinsics 的分析，最后回到这种组合在什么条件下有价值。

本文于 2026-09-19 对照 Velox 1d1b76567870 重写。当前代码在 velox/type/Filter.h 与 Filter.cpp；旧文中的直接 AVX2 写法保留为理解指令的背景，正文以 xsimd 和 Velox 的 simd 封装为准。基础指令语义见 SIMD Basic。

代码片段分别标明源码节选或流程示意；流程示意省略统计、异常包装与无关分支，不是可独立编译的程序。历史资料与宿主集成保留各自版本，不能据此推断它们组成了经过构建验证的发行版本。

2. 介绍

2.1 它过滤什么，又不负责什么

这是整数 IN-list 的精确集合过滤器。例如 k IN (1, 10, 100, 10000)，非空输入的输出是一个布尔值，批量接口则返回逐 lane 的布尔 mask。它不保存 join 的 payload、不枚举重复 key 对应的多行，也不是 exec::HashTable。

Filter 提供标量测试、批量测试、范围测试和 null 测试。 testNull() 与 testInt64() 分开；testValues 的输入是数值 batch，里面没有 SQL null bitmap。调用方负责根据 nullAllowed 处理 null，不能把某个特殊整数当作 SQL NULL。参见 Filter 的批量接口、集合过滤器定义。

扫描侧可利用 Filter 在数据读取过程中筛选，但不能据此断言每个 SQL IN 表达式都会下推成这个类：表达式转换、connector 能力、读取格式和类型都会决定执行路径。

SIMD使用CPU中的特殊寄存器同时操作多个primitive data。在一些基本情况下，编译器能够为我们将紧密循环转换为SIMD指令，但通常需要显式调用SIMD内在函数。Velox中有几个地方明确使用SIMD来获得更好的性能。

Velox使用SIMD的一个非常典型的例子就是BigintValuesUsingHashTable::testValues方法，BigintValuesUsingHashTable是Velox的common::Filter的一个子类，Filter用于TableScan的数据过滤（oerling出品，我也有所贡献:) ），在这篇SIMD Usage in Velox的官方文章中也简单介绍了该方法的实现，BigintValuesUsingHashTable::testValues使用SIMD来同时检查多个values是否在一个哈希表中。在哈希表中使用特殊的empty marker来标识值缺失：

如果所有值都超出了范围，直接返回false。
如果有empty marker插入哈希表中，则回退到逐个检查值的方式。
使用SIMD乘法和取模计算所有有效值的哈希值，然后使用maskGather获取哈希表中对应的状态。
如果状态为空标记，则表示值缺失；如果状态等于值，则表示找到了该值。否则，我们遇到了哈希冲突，需要查看哈希表中的下一个位置。如果没有发生冲突，我们可以立即返回结果。
对于每个发生冲突的值，使用SIMD一次性推进多个位置，直到找到匹配的值或空标记。

先用四个输入 lane 走完一次探测，再逐层解释构造、首槽 gather、冲突扫描、边界回绕与 intrinsics。xsimd 提供编译期的类型和架构封装；batch 宽度、指令序列与成本由构建目标决定，不代表自动跨 CPU 运行时分派。本文以 AVX2 的 256 位、四个 int64 lane 分析。

SIMD一些基本概念和指令可以看这篇SIMD Basic文章。

3. 四个输入 lane 怎样得到最终 mask

用 AVX2 的四个 int64 lane 观察完整路径。直接构造允许集合 [1,17,33,10000]，不包含 empty marker。构造函数按 floor(log2(4×5)) 得到 16 个逻辑槽，sizeMask=15；M 的低四位为 5，所以前三个数的首槽都是 5，线性插入后 slots[5..7]=[1,17,33]，10000 放在 slot 0。表尾另有 padding，稍后单独解释回绕。

步骤	lane 0	lane 1	lane 2	lane 3
输入 x	1	17	2	10001
范围检查	有效	有效	有效	超出 max=10000
首槽 (uint64(x)×M)&15	5	5	10	被 mask 排除，不取表
masked gather	1	1	empty marker	默认 empty marker
第一轮判断	命中	不同且非空，未解决	遇到空槽，未命中	未命中
冲突阶段	完成	broadcast(17)，从 slot 6 连续加载，找到 17	完成	完成
最终结果	true	true	false	false

约定 lane 0 对应最低 bit，第一轮 resultBits=0001、missed=1100，因此 unresolved=0010；解决 lane 1 后最终 resultBits=0011，再转回 batch_bool。连续加载的四个槽属于“17 这一个输入”的候选集合，不再分别对应最初四个输入。这也是从多查询并行切换到单查询多候选比较的时刻。

这个算例直接选定 HashTable 类来隔离探测机制；实际工厂会先按集合的范围和密度选择 range、bitmask 或 hash 表。null 不在上述数值 batch 中，交由 testNull / null bitmap 协议处理；若集合本身包含 kEmptyMarker，testValues 回退到基类逐值路径。

源码：构造与 padding、testValues / testInt64。后面的构造、连续扫描、回绕与 intrinsics 细节都可以回到这四个 lane 对照。

4. BigintValuesUsingHashTable分析

4.1 工厂先选表示，再谈 SIMD

createBigintValuesFilter 按数据分布选择表示。对于正向集合：

输入集合	表示	原因
空集合	AlwaysFalse 或 IsNull	只需处理 null 策略
单元素	BigintRange 的单点范围	一次相等比较即可
所有整数构成连续区间	BigintRange	不必存储逐个值
范围较紧凑	BigintValuesUsingBitmask	用偏移后的 bit 表示成员
大范围的稀疏值	BigintValuesUsingHashTable	不为稀疏空洞分配位图

当前 bitmask 条件是范围差 range < 32 * 64 或 range < values.size() * 4 * 64；减法溢出时跳过这一选择。数值是此版本的实现策略，不是 IN-list 的语义要求。负向集合有对应的 negated 类；它的 null 语义也不能从布尔按位取反推断。

4.2 BigintValuesUsingHashTable构造函数

4.3 哈希表的布局与不变量

构造函数要求 min < max、至少两个唯一元素，调用者应满足参数契约。逻辑槽数取：

size = 2 ^ floor(log2(5 * n))
sizeMask = size - 1
position = (uint64(value) * M) & sizeMask
M = 0xc6a4a7935bd1e995

因此容量通常在 2.5n 到 5n 之间；例如 10 个值得到 32 个逻辑槽，不是固定 5n。低装载率是为了让经常失败的查询尽快遇到空槽。乘法按无符号位模式理解，SIMD 路径也显式转成 unsigned 来避免有符号溢出问题。参见构造函数。

冲突用线性探测解决；槽中直接存 int64_t。空槽使用 0xdeadbeefbadefeed。当集合本身包含这个值时，它不放进普通槽，而是记录 containsEmptyMarker_，标量查询先单独处理，批量查询退回基类的逐元素测试。

表尾额外分配 4 个元素，复制的是最后一个逻辑槽，不是表头四个槽。这样，在 AVX2 四个 int64 lane 的连续 load 越过逻辑表尾时，不会人为插入一个“空槽终止符”。下一步仍要显式回绕到槽 0。不要把这个固定 padding 直接推广成任意寄存器宽度都足够的证明。

流程化代码节选：省略外围声明与非主线分支；实现位置以相邻固定版本源码链接为准。

BigintValuesUsingHashTable::BigintValuesUsingHashTable(
    int64_t min,
    int64_t max,
    const std::vector<int64_t>& values,
    bool nullAllowed)
    : Filter(true, nullAllowed, FilterKind::kBigintValuesUsingHashTable),
      min_(min),
      max_(max),
      values_(values) {
  constexpr int32_t kPaddingElements = 4;
  VELOX_CHECK(min < max, "min must be less than max");
  VELOX_CHECK(values.size() > 1, "values must contain at least 2 entries");

  // Size the hash table to be 2+x the entry count, e.g. 10 entries
  // gets 1 << log2 of 50 == 32. The filter is expected to fail often so we
  // wish to increase the chance of hitting empty on first probe.
  auto size = 1u << (uint32_t)std::log2(values.size() * 5);
  hashTable_.resize(size + kPaddingElements);
  sizeMask_ = size - 1;
  std::fill(hashTable_.begin(), hashTable_.end(), kEmptyMarker);
  for (auto value : values) {
    if (value == kEmptyMarker) {
      containsEmptyMarker_ = true;
    } else {
      auto position = ((value * M) & sizeMask_);
      for (auto i = position; i < position + size; i++) {
        uint32_t index = i & sizeMask_;
        if (hashTable_[index] == kEmptyMarker) {
          hashTable_[index] = value;
          break;
        }
      }
    }
  }
  // Replicate the last element of hashTable kPaddingEntries times at 'size_' so
  // that one can load a full vector of elements past the last used index.
  for (auto i = 0; i < kPaddingElements; ++i) {
    hashTable_[sizeMask_ + 1 + i] = hashTable_[sizeMask_];
  }
  std::sort(values_.begin(), values_.end());
}

从BigintValuesUsingHashTable这个名字不难看出这个哈希表的数据类型是int64_t，其成员values_就是一个int64_t类型的vector，是构建这个哈希表的数据，min_，max_分别是values_的最小与最大值。
Line 17就是一个经验公式用于计算哈希表的size（一般是2的n次方），比如10个entries时size为32，为什么不是16？注释中提到“The filter is expected to fail”，这是因为在计算引擎中的TableScan的场景下，Filter预期的行为是能够过滤掉很多数据，所以希望通过更大的哈希表size来增加第一次probe就立马失败（遇到empty marker）的几率，一定程度的空间换时间（oerling大神对细节的把控真是极致，详见PR-#587）。
Line 18是resize哈希表的实际size，注意，这里实际size增加了kPaddingElements（kPaddingElements = 4），这是给了simd batch操作预留空间，因为在设计这个类的时候erling默认使用avx/avx2指令集，寄存器宽度256，而BigintValuesUsingHashTable的数据类型是int64_t，正好批处理step是4，详见后面probe部分。
Line19-34，初始化哈希表默认值为empty marker，使用开放寻找+线性探测的方式构建哈希表，如果values中有empty marker则设置*containsEmptyMarker_*为true（与介绍那一节中的步骤2对应），填充部分用哈希表最后一个slot的value填充。

4.4 BigintValuesUsingHashTable::testValues

4.5 第一轮：多个查询各看自己的首槽

testValues(int64 batch) 的前半部分依次做：

比较 min_ 和 max_，若全部越界则立即返回全 false。
如果集合含哨兵值，走 Filter::testValues 的标量 fallback。
计算各 lane 的初始槽下标。
maskGather 只读取未越界的 lane；其他 lane 保留初始 allEmpty。
比较取回值，生成命中 bitset 和空槽 bitset，把剩余 lane 标为 unresolved。

以 AVX2 为例，一个 batch 有 4 个 int64 查询，但每个查询可能访问不同缓存行。这里的 SIMD 并不把哈希访问变连续；它让多个查询一起完成下标计算、gather 和比较。

simd::maskGather 的默认 scale 是 sizeof(T)，int64 即 8。地址含义是 base + index * 8 个字节。禁用 lane 保留 src，不是自动置零。参见 maskGather 契约。

4.5.1 一个必须保留的哨兵边界

当前快照直接用 result = x == data，没有再与 ~outOfRange 合并。若集合不含哨兵，而输入 batch 同时有普通范围内的值和 kEmptyMarker，被禁用的哨兵 lane 会保留 allEmpty，从而比较相等。全越界的提前返回也无法覆盖这个混合 batch。

例如集合 {1, 10, 100, 10000} 和输入 {kEmptyMarker, 1, 10, 100}，可以从这段代码直接推导出哨兵 lane 的标量/SIMD 不一致。因此，containsEmptyMarker_ fallback 不能被描述成“已经处理所有哨兵情况”。本文如实记录这一源码边界；没有修改 Velox 实现，也不把阅读现有测试说成已运行整套 FilterTest。

4.6 冲突阶段：按 lane 串行，按槽 SIMD

如果还有 unresolved lane，代码把初始下标加 1 后存到数组，查询值也存到对齐数组。之后每次从 unresolved bitset 取出一个 lane，处理该 lane 的探测链：

value = 当前查询
index = 初始槽 + 1

循环：
    line = 连续加载一整个 batch 的槽
    若任一槽等于 value：命中
    否则若任一槽为空：未命中
    否则 index += batch 宽度
         超过 sizeMask 时回到 0

这个阶段没有让所有未决 lane 持续做 masked gather。它逐个处理冲突查询，用连续 load 把一个查询与多个候选槽比较；line.size 决定每次前进几个槽。

为什么先判断命中，再判断空槽？这张表由线性插入形成，没有删除制造的中间洞。对同一个初始槽，若某值确实存在，探测路径不会先经过空槽再到达它；边界 padding 又不会额外制造空槽。这个推理依赖表的构造规则，不能照搬到有 tombstone、删除或不同探测策略的哈希表。

图 3：表尾 padding 复制末槽；连续 load 与逻辑回绕是两个独立步骤。

resultBits 用 bit i 表示输入 lane i，最后通过 fromBitMask 返回 batch_bool。这里压缩的是比较结果，不是压缩或搬动原始输入数据。

xsimd::batch_bool<int64_t> BigintValuesUsingHashTable::testValues(
    xsimd::batch<int64_t> x) const { // xsimd::batch<long long, xsimd::fma3<xsimd::avx2>>
  // outOfRange = {xsimd::batch_bool<long long, xsimd::fma3<xsimd::avx2>>}
  auto outOfRange = (x < xsimd::broadcast<int64_t>(min_)) |
      (x > xsimd::broadcast<int64_t>(max_)); //return _mm256_set1_epi64x(val), _mm256_cmpgt_epi64(other, self), _mm256_or_si256

  // _mm256_movemask_pd(reinterpret_cast<__m256d>(mask.data))
  if (simd::toBitMask(outOfRange) == simd::allSetBitMask<int64_t>()) {
    return xsimd::batch_bool<int64_t>(false);
  }
  if (containsEmptyMarker_) {
    return Filter::testValues(x);
  }
  // broadcast _mm256_set1_epi64x
  auto allEmpty = xsimd::broadcast<int64_t>(kEmptyMarker);
  // Temporarily casted to unsigned to suppress overflow error.
  auto indices = simd::reinterpretBatch<int64_t>(
      simd::reinterpretBatch<uint64_t>(x) * M & sizeMask_);
  // ~outOfRangne: _mm256_xor_si256
  // maskGather : _mm256_mask_i64gather_epi64
  auto data =
      simd::maskGather(allEmpty, ~outOfRange, hashTable_.data(), indices);
  // The lanes with kEmptyMarker missed, the lanes matching x hit and the other
  // lanes must check next positions.
  auto result = x == data; // _mm256_cmpeq_epi64
  auto resultBits = simd::toBitMask(result);
  auto missed = simd::toBitMask(data == allEmpty);
  static_assert(decltype(result)::size <= 16);
  // allSetBitMask : bits::lowMask(xsimd::batch_bool<T, A>::size);
  uint16_t unresolved = simd::allSetBitMask<int64_t>() ^ (resultBits | missed);
  if (!unresolved) {
    return result;
  }
  constexpr int kAlign = xsimd::default_arch::alignment();
  constexpr int kArraySize = xsimd::batch<int64_t>::size;
  alignas(kAlign) int64_t indicesArray[kArraySize];
  alignas(kAlign) int64_t valuesArray[kArraySize];
  (indices + 1).store_aligned(indicesArray);
  // store_aligned -> broadcast -> _mm256_set1_epi64x
  x.store_aligned(valuesArray);
  while (unresolved) {
    auto lane = bits::getAndClearLastSetBit(unresolved);
    // Loop for each unresolved (not hit and
    // not empty) until finding hit or empty.
    int64_t index = indicesArray[lane];
    int64_t value = valuesArray[lane];
    auto allValue = xsimd::broadcast<int64_t>(value);
    for (;;) {
      // _mm256_loadu_si256
      auto line = xsimd::load_unaligned(hashTable_.data() + index);

      if (simd::toBitMask(line == allValue)) {
        resultBits |= 1 << lane;
        break;
      }
      if (simd::toBitMask(line == allEmpty)) {
        resultBits &= ~(1 << lane);
        break;
      }
      index += line.size;
      if (index > sizeMask_) {
        index = 0;
      }
    }
  }
  return simd::fromBitMask<int64_t>(resultBits);
}

xsimd::batch<T, A>是xsimd对SIMD寄存器的封装，其底层data是一个SIMD数据类型，比如xsimd::batch<int64_t>底层数据类型是__m256i，本文默认是avx family指令集，256位寄存器。
范围比较得到的是 xsimd::batch_bool<int64_t>，不是整数值 batch。AVX2 下 min/max 广播可用 _mm256_set1_epi64x；64 位有符号比较对应 _mm256_cmpgt_epi64 一类指令，真 lane 全位为 1、假 lane 为 0；两项越界结果按位 OR 得到 outOfRange。具体反向比较可通过交换操作数等方式生成，应以目标编译结果为准。
当前源码用 simd::all(outOfRange) 检查是否全部越界；本文早期片段以 toBitMask 加位掩码比较说明同一逻辑，不能据旧行号推断当前代码仍原样如此。AVX2 的 movemask 可从 lane 提取符号位形成标量 mask。集合自身包含 empty marker 时回退标量，但这并未覆盖后文记录的“输入含 marker、集合不含”的混合 batch 边界。
Line 14-22，这里开始进入了SIMD实现hash probe的首次探测部分
- 生成一个empty marker的batch，allEmpty
- 计算x的哈希值在哈希表中的index的batch，indices
- 将~outRange（_mm256_xor_si256操作）中非0的lane（本文场景4个lane）在indices中的index索引的hashTable_.data()load到data对应的lane中，其它lane从allEmpty中load。
- 上述就是一个经典的smid gather操作，底层是__m256i _mm256_mask_i64gather_epi64 (__m256i src, __int64 const* base_addr, __m256i vindex, __m256i mask, const int scale)，通过vindex索引oad其lane对应的mask MSB为1的base_addr地址开始的数据，其它lane则load在src中对于lane的数据。
- 最后的结果是变量data，它是一个batch，包含x中没有超出range的整数第一次探测到的哈希表数据（可能会有冲突），以及超出range而load的empty marker
Line 23-33，这里开始计算需要进行后续探测的lane，其中
- x == data底层是_mm256_cmpeq_epi64得到实际值对比结果的batch，即result，首次探测成功，也就是实际值相同的lane的所有bit都是1（本文场景为0xFFFFFFFFFFFFFFFF），然后转成bit mask也就是resultBits
- missed = simd::toBitMask(data == allEmpty)是首次探测即失败（其index对应的hash表的slot中的value位emtpy marker)
- unresolved = simd::allSetBitMask<int64_t>() ^ (resultBits | missed)就可以得到首次探测没有失败，但是实际值不同（也就是哈希冲突）的lane转成的bit mask
- 如果没有unresolved的lane那么直接返回结果result
Line 34-40，开始后续探测的准备，前面提到该类的哈希实现是开放寻找+线性探测，所以发生冲突之后需要index后移一位后继续探测，
- (indices + 1).store_aligned(indicesArray)初始化indicesArray，x.store_aligned(valuesArray)初始化valuesArray
- 这里的 store_aligned 将寄存器元素写入已经按要求对齐的数组；在 AVX2 的 256-bit 整数路径中通常对应对齐存储。它不是 broadcast：广播把一个标量复制到各 lane，存储则把已有各 lane 的不同值逐项写到内存。转换为数组后，冲突阶段才能按 unresolved bitmask 逐个选择查询 lane。
- 这里之所以转成数组是因为后续探测需要一个一个lane的操作
Line 41-65，获取unresolved当前最后一位为1的bit位并清零，算出其对应的lane（本文场景中x有4个lane），然后用lane获取当前需要继续探测的index和value
- allValue = xsimd::broadcast(value)把需要继续探测的value加载到一个batch中，即allValues
- 把需要探测的index索引的哈希表的值load到一个batch中，即line，这里底层是_mm256_loadu_si256
- 这里比较line与value，如果结果不是0就设置resultBits对应的bit位，如果line == allEmpty则设置resultBits对应的bit位位0
- 这个循环里面有个优化是，_mm256_loadu_si256加载的是index索引的哈希表的数据和它之后的几个数据（本文是3），实际上是一次进行了多次探测，所以后面更新index是index += line.size，这里也对应了前面提到的那个kPaddingElements填充

5. 一些intrinsics的解释

5.1 int32、int16 与架构边界

接口	当前实现	阅读重点
int64 batch	首轮 gather + 冲突连续扫描	主实现
int32 batch	两半扩展成 int64，调用主实现后拼接 mask	表中存储仍是 64 位
int16 batch	genericTestValues 调用标量 testInt64	不能仅凭 API 名称断言内部向量化
基类 Filter 的默认 batch 测试	泛型逐元素测试	batch 接口本身不保证指令级 SIMD

AVX2 下可把常见操作联系到如下 intrinsic，但这是语义对应，不是承诺每个封装恰好发射一条该指令：

操作	AVX2 语义参考
广播整数	`_mm256_set1_epi64x`
有符号大小比较	`_mm256_cmpgt_epi64`
带 mask 的 64 位 gather	`_mm256_mask_i64gather_epi64`
64 位相等比较	`_mm256_cmpeq_epi64`
每个 64 位 lane 提取一位	cast 后 `_mm256_movemask_pd`
连续非对齐读取	`_mm256_loadu_si256`

loadu 取消的是对齐前提，不取消有效内存范围要求。「xsimd」提供架构封装，实际 batch 宽度和代码生成仍受构建目标影响；它不等于这个函数自动实现了面向所有 CPU 的运行时分派。旧文把 _mm256_lddqu_si256 单独解释成普遍更快的 load，也不应保留为优化规则。

5.2 __m256i _mm256_set1_epi64x (long long a)

Synopsis

__m256i _mm256_set1_epi64x (long long a) #include <immintrin.h> Instruction: Sequence CPUID Flags: AVX

Description Broadcast 64-bit integer a to all elements of dst. This intrinsic may generate the vpbroadcastq.

Operation

FOR j := 0 to 3
    i := j*64
    dst[i+63:i] := a[63:0]
ENDFOR
dst[MAX:256] := 0

5.3 __m256i _mm256_cmpgt_epi64 (m256i a, m256i b)

Synopsis __m256i _mm256_cmpgt_epi64 (__m256i a, __m256i b) #include <immintrin.h> Instruction: vpcmpgtq ymm, ymm, ymm CPUID Flags: AVX2

Description Compare packed signed 64-bit integers in a and b for greater-than, and store the results in dst.

Operation

FOR j := 0 to 3
    i := j*64
    dst[i+63:i] := ( a[i+63:i] > b[i+63:i] ) ? 0xFFFFFFFFFFFFFFFF : 0
ENDFOR
dst[MAX:256] := 0

5.4 __m256i _mm256_mask_i64gather_epi64 (m256i src, int64 const* base_addr, m256i vindex, m256i mask, const int scale)

Synopsis

__m256i _mm256_mask_i64gather_epi64 (__m256i src, __int64 const* base_addr, __m256i vindex, __m256i mask, const int scale) #include <immintrin.h> Instruction: vpgatherqq ymm, vm64x, ymm CPUID Flags: AVX2

Description

Gather 64-bit integers from memory using 64-bit indices. 64-bit elements are loaded from addresses starting at base_addr and offset by each 64-bit element in vindex (each index is scaled by the factor in scale). Gathered elements are merged into dst using mask (elements are copied from src when the highest bit is not set in the corresponding element). scale should be 1, 2, 4 or 8.

Operation

FOR j := 0 to 3 i := j64 m := j64 IF mask[i+63] addr := base_addr + vindex[m+63:m] * ZeroExtend64(scale) * 8 dst[i+63:i] := MEM[addr+63:addr] ELSE dst[i+63:i] := src[i+63:i] FI ENDFOR mask[MAX:256] := 0 dst[MAX:256] := 0

5.5 __m256i _mm256_cmpeq_epi64 (m256i a, m256i b)

Synopsis

__m256i _mm256_cmpeq_epi64 (__m256i a, __m256i b) #include <immintrin.h> Instruction: vpcmpeqq ymm, ymm, ymm CPUID Flags: AVX2

Description

Compare packed 64-bit integers in a and b for equality, and store the results in dst. Operation FOR j := 0 to 3 i := j*64 dst[i+63:i] := ( a[i+63:i] == b[i+63:i] ) ? 0xFFFFFFFFFFFFFFFF : 0 ENDFOR dst[MAX:256] := 0

5.6 int _mm256_movemask_pd (__m256d a)

Synopsis

int _mm256_movemask_pd (__m256d a) #include <immintrin.h> Instruction: vmovmskpd r32, ymm CPUID Flags: AVX

Description Set each bit of mask dst based on the most significant bit of the corresponding packed double-precision (64-bit) floating-point element in a. Operation FOR j := 0 to 3 i := j*64 IF a[i+63] dst[j] := 1 ELSE dst[j] := 0 FI ENDFOR dst[MAX:4] := 0

5.7 __m256i _mm256_loadu_si256 (__m256i const * mem_addr)

Synopsis __m256i _mm256_loadu_si256 (__m256i const * mem_addr) #include <immintrin.h> Instruction: vmovdqu ymm, m256 CPUID Flags: AVX Description Load 256-bits of integer data from memory into dst. mem_addr does not need to be aligned on any particular boundary. Operation dst[255:0] := MEM[mem_addr+255:mem_addr] dst[MAX:256] := 0

5.8 __m256i _mm256_lddqu_si256 (__m256i const * mem_addr)

Synopsis

__m256i _mm256_lddqu_si256 (__m256i const * mem_addr) #include <immintrin.h> Instruction: vlddqu ymm, m256 CPUID Flags: AVX

Description

Load 256-bits of integer data from unaligned memory into dst. This intrinsic may perform better than _mm256_loadu_si256 when the data crosses a cache line boundary. Operation dst[255:0] := MEM[mem_addr+255:mem_addr] dst[MAX:256] := 0

6. 从集合表示到访存方式的优化取舍

这个例子体现了两层选择：先选适合数据分布的表示，再让所选表示的访问方式适应批处理。SIMD 可以减少部分指令和并行检查多个候选，但不能消除 hash 冲突或随机访存本身。

选择	利用的条件	需要维护的代价或不变量
工厂选择 range、bitmask 或哈希表示	不同值域与密度对应不同空间和查询成本	需要保留统一过滤语义，不能仅按实现名字推断适用性
第一轮批量首槽查询	输入 lane 之间存在独立查询	gather 的真实成本受缓存和硬件影响，批宽不等于加速倍数
冲突后连续检查多个槽	线性探测提供连续候选位置	必须正确处理回绕、空槽终止、命中顺序与加载边界
用内部 empty marker 表达空槽	简化槽位状态与查找终止	当集合包含该整数时要走正确处理路径，marker 不能表示 SQL NULL
xsimd 与架构分支	在公共批量接口下使用不同平台能力	可编译的抽象不保证所有平台具有相同指令序列与吞吐

这些工程技巧首先要满足正确性条件：mask 应排除越界 lane，回绕应保持探测序列，所有合法整数也应有明确的成员查询语义。当前快照的 marker 混合 batch 恰好暴露了第一项边界，不能因为存在 containsEmptyMarker_ fallback 就声称全部满足。优化讨论应在这些条件经过验证之后展开。

测量时应覆盖集合大小、范围、命中率、冲突、边界值和不同 ISA，并区分构造时间与查询时间。若应用只查询少量值，表示构造成本可能更重要；若过滤器远大于缓存，访存又可能成为主要限制。这个例子的可迁移经验，是从数据表示和访问模式找并行机会，而不是把每段标量代码都机械改写成 SIMD。

7. References

7.1 怎样验证正确性和性能

源码中 bigintValuesUsingHashTableSimd 构造了所有值落到相同槽的长冲突链、相对分散的集合、int32 输入，以及末槽被占用时的 padding 测试。这些用例解释了实现为什么需要 fallback、批量扫描和末尾保护。

阅读或修改这条路径时，还应覆盖：

查询值等于哨兵，集合包含/不包含哨兵，混合越界与范围内 lane。
含 INT64_MIN / INT64_MAX、空槽首次 miss、长冲突链与回绕。
每种实际构建 ISA 的 batch 宽度与 padding 契约。
SIMD 与标量逐元素比较，尾部由调用方安全处理。

FilterBenchmark 比较 scalar 与 SIMD，并使用不同输入分布。分析结果时至少记录命中率、冲突率、集合是否装入 cache、batch 宽度、CPU 与编译选项。长冲突链既可能受益于连续加载，也可能让按 lane 的串行处理成为瓶颈；gather 延迟和缓存未命中不能从指令数量推算。

本文做了源码与测试用例核对，未运行该 Velox benchmark，也不引用旧版本的加速比作为当前性能结论。

7.2 继续读哪些代码

建议按“表示选择 → 构造布局 → 标量语义 → 批量快路径 → 冲突慢路径 → 测试”的顺序阅读：

过滤器工厂：为什么本次调用选择哈希表。
构造与 padding：哪些条件保证探测终止。
testInt64 与 testValues：语义基线与优化路径。
SIMD 工具契约：mask、scale、batch 的含义。
正确性用例与性能实验入口。
Velox 官方 SIMD 文档：背景资料；具体函数行为以本文固定提交为准。

源码核对（2026-09-20）：本轮按 Velox 1d1b76567870 核对关键接口、控制流、默认值与边界条件。当前源码摘录附固定版本链接；流程伪代码用于说明分支，不是可直接编译的程序。未对全文示例做独立编译或性能复测。涉及宿主集成与历史实验的数据，按各节标注的来源理解。

1. 整数集合过滤器的语义与 SIMD 使用位置

2. 介绍

2.1 它过滤什么，又不负责什么

3. 四个输入 lane 怎样得到最终 mask

4. BigintValuesUsingHashTable分析

4.1 工厂先选表示，再谈 SIMD

4.2 BigintValuesUsingHashTable构造函数

4.3 哈希表的布局与不变量

4.4 BigintValuesUsingHashTable::testValues

4.5 第一轮：多个查询各看自己的首槽

4.5.1 一个必须保留的哨兵边界

4.6 冲突阶段：按 lane 串行，按槽 SIMD

5. 一些intrinsics的解释

5.1 int32、int16 与架构边界

5.2 __m256i _mm256_set1_epi64x (long long a)

5.3 __m256i _mm256_cmpgt_epi64 (__m256i a, __m256i b)

5.4 __m256i _mm256_mask_i64gather_epi64 (__m256i src, __int64 const* base_addr, __m256i vindex, __m256i mask, const int scale)

5.5 __m256i _mm256_cmpeq_epi64 (__m256i a, __m256i b)

5.6 int _mm256_movemask_pd (__m256d a)

5.7 __m256i _mm256_loadu_si256 (__m256i const * mem_addr)

5.8 __m256i _mm256_lddqu_si256 (__m256i const * mem_addr)

6. 从集合表示到访存方式的优化取舍

7. References

7.1 怎样验证正确性和性能

7.2 继续读哪些代码

5.3 __m256i _mm256_cmpgt_epi64 (m256i a, m256i b)

5.4 __m256i _mm256_mask_i64gather_epi64 (m256i src, int64 const* base_addr, m256i vindex, m256i mask, const int scale)

5.5 __m256i _mm256_cmpeq_epi64 (m256i a, m256i b)