SimdAnyof.h

仓库中的文件是 folly/algorithm/simd/detail/SimdAnyOf.h，它在 SimdForEach 的遍历框架上实现 SIMD 版 std::any_of：

加载一个或多个 SIMD 寄存器
↓
对每个寄存器执行向量谓词 p
↓
合并各 lane 的逻辑结果
↓
只要有一个有效 lane 为 true，就提前结束

## 第 1–24 行：声明和依赖

- 第 1–15 行：Apache 2.0 许可证。
- 第 17 行：

#pragma once

防止头文件在同一翻译单元中被重复包含。

- 第 19 行：

#include <folly/CPortability.h>

提供 FOLLY_ALWAYS_INLINE。

- 第 20 行：

#include <folly/algorithm/simd/detail/SimdForEach.h>

引入刚才分析的 SIMD 区间遍历框架。它负责：
- 地址对齐；
- 首尾不完整寄存器；
- ignore_extrema；
- 主循环展开；
- 提前退出。

- 第 21 行：

#include <folly/algorithm/simd/detail/UnrollUtils.h>

提供编译期展开工具：

arrayMap
arrayReduce

- 第 23–24 行：

namespace folly {
namespace simd::detail {

进入 Folly SIMD 内部实现命名空间。

## 第 26–34 行：AnyOfDelegate 的作用

/**
* AnyOfDelegate
*
* Implementation detail of simdAnyOf
* This is a delegate to simdForEach
*/

SimdForEach 本身不知道要执行什么算法，只负责遍历 SIMD 寄存器。具体操作由 delegate 提供。

AnyOfDelegate 实现了 SimdForEach 要求的两个接口：

step(...)
unrolledStep(...)

它把通用遍历转换成 any_of 语义：

某个有效元素满足谓词 → true
所有有效元素都不满足 → false

第 32–33 行说明实现思路参考了 EVE SIMD 库。

## 第 35–36 行：delegate 模板

template <typename Platform, typename I, typename P>
struct AnyOfDelegate {

三个模板参数分别是：

- Platform：SIMD 平台抽象；
- I：迭代器或指针类型；
- P：向量谓词类型。

在当前实际调用中：

I = T*

Platform 可能是：

SimdSse42Platform<T>
SimdAvx2Platform<T>
SimdAarch64Platform<T>

它需要提供：

Platform::reg_t
Platform::logical_t
Platform::kCardinal
Platform::loada(...)
Platform::any(...)
Platform::logical_or(...)

P 通常是 lambda，例如：

[](typename Platform::reg_t x) {
return Platform::equal(x, needle);
}

注意谓词接收的是整个 SIMD 寄存器，不是单个标量。

## 第 37–38 行：构造函数

// _p to deal with a shadow warning on an old gcc
explicit AnyOfDelegate(P _p) : p(_p) {}

### _p

构造参数命名为 _p，是为了避免旧版本 GCC 的变量遮蔽警告。如果也叫 p，可能被认为遮蔽了第 59 行的成员 p。

### explicit

防止 P 被隐式转换成 AnyOfDelegate：

AnyOfDelegate delegate = predicate; // 不允许
AnyOfDelegate delegate{predicate}; // 允许

### p(_p)

将传入的谓词复制到成员变量 p。

因此当前实现一般要求谓词可复制。它没有使用：

p(std::move(_p))

所以这里明确执行复制，而不是移动。

## 第 40–45 行：处理一个寄存器

### 第 40–41 行

template <typename Ignore, typename UnrollStep>
FOLLY_ALWAYS_INLINE bool step(I it, Ignore ignore, UnrollStep) {

这是 SimdForEach 要求的单寄存器处理接口。

参数：

- it：当前 SIMD 块的起始地址；
- ignore：哪些 lane 无效；
- UnrollStep：当前模板展开位置。

Ignore 会被推导为：

ignore_none

或者：

ignore_extrema

第三个参数没有变量名，因为本实现不需要知道当前是展开中的第几个寄存器，但为了满足 delegate 接口仍然保留这个参数。

FOLLY_ALWAYS_INLINE 确保加载、谓词和归约能够合并进最终算法。

### 第 42 行

auto test = p(Platform::loada(it, ignore));

这行包含两个步骤。

第一步，加载 SIMD 寄存器：

Platform::loada(it, ignore)

loada 从 it 开始加载一个完整 SIMD 寄存器。

如果是完整块：

ignore == ignore_none{}

所有 lane 都有效。

如果是首尾部分块：

ignore == ignore_extrema{first, last}

部分 lane 可能对应数组边界之外的垃圾值。

第二步，执行向量谓词：

p(加载出来的寄存器)

谓词必须返回 Platform::logical_t，即一个 SIMD 逻辑寄存器。

例如寄存器包含：

[3, 7, 9, 7]

谓词是“是否等于 7”，则 test 概念上是：

[false, true, false, true]

在 SSE/AVX 中，这通常不是四个 C++ bool，而是一个整数 SIMD 寄存器，其中匹配 lane 的所有位为 1。

### 第 43 行

res = Platform::any(test, ignore);

把 SIMD 逻辑寄存器横向归约成一个普通 bool：

任一有效 lane 为 true → res = true
所有有效 lane 为 false → res = false

ignore 非常重要。

假设首块为：

实际区间： [7, 9]
完整加载：[7, 7, 9, 7]
ignore ：前两个 lane 和最后一个 lane 无效

即使区间外 lane 满足谓词，也不能让结果变成 true。Platform::any(test, ignore) 会屏蔽这些无效 lane。

这里使用赋值而不是：

res |= ...

是安全的，因为一旦结果为 true，下一行就会要求遍历立即终止；只有当前结果为 false 时，后续块才会继续覆盖 res。

### 第 44 行

return res;

把结果同时作为 SimdForEach 的提前退出信号：

- true：已找到匹配元素，停止遍历；
- false：当前寄存器没有匹配，继续遍历。

### 第 45 行

结束 step。

## 第 47–57 行：一次处理多个寄存器

### 第 47–48 行

template <std::size_t N>
FOLLY_ALWAYS_INLINE bool unrolledStep(std::array<I, N> arr) {

这是展开主循环使用的接口。

arr 保存连续 N 个完整 SIMD 块的起始指针。例如：

arr[0] → 第一个寄存器
arr[1] → 第二个寄存器
arr[2] → 第三个寄存器
arr[3] → 第四个寄存器

只有完整块才会传给 unrolledStep，因此这里不需要 ignore_extrema。

N 通常等于 simdAnyOf 的 unrolling 参数，默认是 4。

### 第 49 行

// Don't have to forceinline - no user code dependency

这里表达的意思是，内部加载 lambda 没有用户自定义逻辑，不需要单独给 lambda 添加强制内联标记；外层 unrolledStep 和 arrayMap 本身已经强制内联。

### 第 50–52 行

auto loaded = detail::UnrollUtils::arrayMap(arr, [](I it) {
return Platform::loada(it, ignore_none{});
});

对 arr 中的每个地址执行 SIMD 加载。

假设 N == 4，概念上相当于：

std::array loaded{
Platform::loada(arr[0], ignore_none{}),
Platform::loada(arr[1], ignore_none{}),
Platform::loada(arr[2], ignore_none{}),
Platform::loada(arr[3], ignore_none{}),
};

返回的 loaded 类型大致是：

std::array<typename Platform::reg_t, N>

因为展开区间只包含完整块，所以统一传入：

ignore_none{}

这样先把加载集中起来，有利于 CPU 并行发射多个互不依赖的内存读取。

### 第 53 行

auto tests = detail::UnrollUtils::arrayMap(loaded, p);

对每个已加载的 SIMD 寄存器应用谓词 p。

概念上：

std::array tests{
p(loaded[0]),
p(loaded[1]),
p(loaded[2]),
p(loaded[3]),
};

tests 类型大致是：

std::array<typename Platform::logical_t, N>

每个元素代表一个寄存器内各 lane 的谓词结果。

注意 arrayMap 按值接收操作对象，所以成员谓词 p 在这里还可能被复制一次。

### 第 54 行

auto test =
detail::UnrollUtils::arrayReduce(tests, Platform::logical_or);

将多个 SIMD 逻辑寄存器按位“或”合并成一个逻辑寄存器。

如果：

tests[0] = [F, F, T, F]
tests[1] = [F, F, F, F]
tests[2] = [T, F, F, F]
tests[3] = [F, T, F, F]

合并后：

test = [T, T, T, F]

这里不关心匹配发生在哪个寄存器，只关心是否至少存在一个匹配。

arrayReduce 使用平衡树归约。对于 4 个值，类似：

logical_or(
logical_or(tests[0], tests[1]),
logical_or(tests[2], tests[3]));

而不是形成较长的串行依赖链：

(((tests[0] | tests[1]) | tests[2]) | tests[3])

平衡归约更利于 CPU 指令级并行。

### 第 55 行

res = Platform::any(test, ignore_none{});

把合并后的逻辑寄存器归约为一个 bool。

因为 unrolledStep 只处理完整块，所以所有 lane 都有效，使用：

ignore_none{}

这种设计还有一个性能优势：对于 N 个寄存器，只执行一次相对昂贵的横向 any/movemask 操作，而不是每个寄存器执行一次。

代价是：即使第一个寄存器已经匹配，当前整个展开组的加载、谓词和合并通常仍会完成，然后才退出。

### 第 56 行

return res;

将结果返回给 SimdForEach：

- true：停止后续遍历；
- false：继续下一展开组或尾部块。

### 第 57 行

结束 unrolledStep。

## 第 59–61 行：delegate 状态

### 第 59 行

P p;

保存用户提供的 SIMD 谓词。

例如 ContainsImpl.h 传入：

[&](typename Platform::reg_t x) {
return Platform::equal(x, needle);
}

### 第 60 行

bool res = false;

保存最终结果，默认值为 false。

这保证空区间返回 false：空区间中 step 和 unrolledStep 都不会执行，因此 res 保持初始值。

### 第 61 行

结束 AnyOfDelegate。

## 第 63–75 行：simdAnyOf 接口说明

### 第 64 行

simdAnyOf<Platform, unrolling = 4>(f, l, p);

展示调用形式。实际调用时默认模板参数不需要写成 = 4，例如：

simdAnyOf<Platform>(f, l, predicate);

或者显式指定：

simdAnyOf<Platform, 1>(f, l, predicate);
simdAnyOf<Platform, 4>(f, l, predicate);

### 第 66–67 行

它类似 std::any_of，但谓词是向量谓词：

Platform::reg_t → Platform::logical_t

区别是：

// 普通 std::any_of
bool predicate(T scalar);

// simdAnyOf
Platform::logical_t predicate(Platform::reg_t vector);

### 第 69–70 行

默认展开因子是 4。

对于简单谓词，例如“是否相等”，4 路展开通常能提高吞吐量。

对于昂贵谓词，展开 4 路可能导致：

- 寄存器压力增大；
- 代码体积增大；
- 同一批次做太多不必要工作；
- 编译器产生溢出到栈的临时数据。

此时展开因子 1 可能更合适。

### 第 72–74 行

函数被标记为 FOLLY_ALWAYS_INLINE。

这是内部构建模块，不希望最终用户直接依赖。上层通常会为具体功能建立一个非内联调用边界，例如：

containsU8
containsU16
containsU32
containsU64

内部 SIMD 模板则全部展开在这些明确边界之后。

## 第 76–81 行：simdAnyOf 主函数

### 第 76 行

template <typename Platform, int unrolling = 4, typename T, typename P>

四个模板参数：

- Platform：必须由调用者显式指定；
- unrolling：可选，默认为 4；
- T：根据 f、l 自动推导；
- P：根据谓词 p 自动推导。

例如：

simdAnyOf<SimdPlatform<std::uint8_t>, 4>(
first, last, predicate);

### 第 77 行

FOLLY_ALWAYS_INLINE bool simdAnyOf(T* f, T* l, P p) {

接收：

- f：起始指针；
- l：尾后指针；
- p：按值传入的 SIMD 谓词。

区间是标准半开区间：

[f,l)

函数没有标记 noexcept，所以如果谓词的复制或调用抛出异常，异常可以向上传播。

### 第 78 行

AnyOfDelegate<Platform, T*, P> delegate{p};

将谓词包装成 SimdForEach 能理解的 delegate。

实例化后的结构概念上是：

struct {
P p;
bool res = false;

bool step(...);
bool unrolledStep(...);
};

这里再次复制 p 进入 delegate。

### 第 79 行

simdForEachAligning<unrolling>(
Platform::kCardinal, f, l, delegate);

启动底层 SIMD 遍历。

Platform::kCardinal 表示一个 SIMD 寄存器包含多少个 T：

kCardinal = sizeof(Platform::reg_t) / sizeof(T);

simdForEachAligning 随后负责：

1. 空区间处理；
2. 将首地址向下对齐；
3. 用 ignore_extrema 处理首块；
4. 调用 step 处理少量完整块；
5. 调用 unrolledStep 处理展开组；
6. 用 ignore_extrema 处理尾块；
7. delegate 返回 true 时提前结束。

由于 delegate 按引用传入，对 delegate.res 的修改会保留到调用结束。

### 第 80 行

return delegate.res;

返回遍历结果。

可能情况：

空区间 → false
某个有效 lane 满足谓词 → true
所有有效 lane 均不满足 → false
只有区间外 lane 满足谓词 → false

### 第 81 行

结束 simdAnyOf。

### 第 83–84 行

} // namespace simd::detail
} // namespace folly

关闭命名空间。

## 与 contains 的连接

ContainsImpl.h 中这样调用：

return simdAnyOf<Platform, 4>(
haystack.data(),
haystack.data() + haystack.size(),
[&](typename Platform::reg_t x) {
return Platform::equal(x, needle);
});

数据流为：

SimdForEach
→ Platform::loada 加载多个元素
→ lambda 同时比较多个元素与 needle
→ Platform::logical_or 合并多个寄存器
→ Platform::any 判断是否至少一个 lane 相等
→ 找到后提前退出

假设一个寄存器包含 4 个元素，4 路展开时，一组最多检查 16 个元素：

寄存器 0 ─→ compare ─┐
寄存器 1 ─→ compare ─┼→ logical_or → any → bool
寄存器 2 ─→ compare ─┤
寄存器 3 ─→ compare ─┘

所以 SimdAnyOf.h 的核心职责是：把 SimdForEach 提供的“寄存器遍历能力”，包装成具有 any_of 语义的“加载—谓词—合并—归约—提前退出”流程。