SimdForEach.h

folly/algorithm/simd/detail/SimdForEach.h 是 Folly SIMD 算法的底层遍历框架。它负责把任意未对齐区间 [f, l) 拆成：

首个部分有效的 SIMD 块
↓
若干完整 SIMD 块
↓
最后一个部分有效的 SIMD 块

区间外的 SIMD lane 不会单独避免读取，而是通过 ignore_extrema 标记为无效，让 delegate 在计算结果时忽略它们。

## 第 1–30 行：文件声明和依赖

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

#pragma once

防止头文件重复包含。

- 第 19 行：

#include <folly/CPortability.h>

提供 FOLLY_ALWAYS_INLINE 等跨平台编译器宏。

- 第 20 行：

#include <folly/Traits.h>

提供 index_constant<I>，它等价于：

std::integral_constant<std::size_t, I>

用来把循环展开位置编码进类型。

- 第 21 行：

#include <folly/algorithm/simd/Ignore.h>

提供：

ignore_none
ignore_extrema

- 第 22 行：

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

提供基于模板展开的 unrollUntil<N>。

- 第 23 行：

#include <folly/lang/Align.h>

提供 align_floor，用于把地址向下对齐。

- 第 25 行：

#include <array>

用于保存一次展开中的多个 SIMD 块指针。

- 第 26 行：

#include <cstdint>

提供固定宽度整数和相关底层类型。

- 第 27 行：

#include <type_traits>

提供模板元编程类型工具。

- 第 29–30 行：

namespace folly {
namespace simd::detail {

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

## 第 32–38 行：设计来源和内联策略

第 32–33 行说明算法设计参考了 EVE SIMD 库的 for_each_iteration。

第 35–37 行：

// Everything is ALWAYS_INLINE because we want to have one top level noinline
// function that does everything.

这些内部模板被强制内联，目的是让最终算法集中在一个明确的顶层函数边界中，避免编译器意外留下多层 SIMD 辅助函数调用。

## 第 40–63 行：接口与 delegate 契约

### 第 41 行

simdForEachAligning<unrolling>(cardinal, f, l, delegate);

概括函数调用形式。

参数含义：

- unrolling：主循环一次展开多少个 SIMD 寄存器；
- cardinal：一个 SIMD 寄存器能容纳多少个 T；
- f、l：半开区间 [f,l)；
- delegate：实际执行 SIMD 运算的对象。

例如 128 位 SSE：

T = uint8_t → cardinal = 16
T = uint16_t → cardinal = 8
T = uint32_t → cardinal = 4
T = uint64_t → cardinal = 2

### 第 43–47 行：为什么可以向前读取

算法可能把 f 向下对齐到 f 之前的地址，然后加载整个 SIMD 寄存器。

假设：

cardinal = 4
f 指向索引 2

那么实际加载可能从索引 0 开始：

加载：[0, 1, 2, 3]
忽略：[0, 1]
有效： [2, 3]

作者依据的硬件事实是：内存页通常按 4 KiB 对齐。如果原始地址有效，把它向下对齐到一个较小 SIMD 边界，通常仍位于同一页，因此硬件读取不会跨入未映射页面。

不过，这属于底层 SIMD 技巧：

- 必须在结果中屏蔽数组外 lane；
- 相关读取需要关闭或特殊处理 ASan；
- 它依赖 Folly 的底层平台加载封装，不应作为普通 C++ 指针访问模式模仿。

### 第 49–53 行

说明四个接口参数。

### 第 54–62 行：delegate 必须提供的操作

delegate 概念上是回调对象，但需要支持两个成员函数。

第一个：

bool step(T*, ignore, unrollIndex);

代码中的实际调用还包含第三个“展开位置”参数。

它处理一个 SIMD 寄存器：

- 首尾块传入 ignore_extrema；
- 完整块传入 ignore_none；
- 返回 true 表示要求提前终止。

第二个：

bool unrolledStep(std::array<T*, unrolling>);

它一次处理 unrolling 个完整 SIMD 块。

当 unrolling == 1 时不会调用这个接口。

delegate 通过引用传入，所以它可以保存结果和状态。例如 simdAnyOf 的 delegate 会保存“是否已有任何 lane 匹配”。

## 第 64–66 行：提前声明

template <int unrolling, typename T, typename Delegate>
FOLLY_ALWAYS_INLINE void simdForEachAligning(
int cardinal, T* f, T* l, Delegate& delegate);

声明主入口，定义位于第 176–208 行。

模板参数：

- unrolling：编译期展开因子；
- T：元素类型，可由指针推导；
- Delegate：处理对象类型，可由参数推导。

返回 void。处理结果由 delegate 自己保存。

## 第 68–77 行：计算前一个对齐地址

### 第 74–75 行

template <typename T>
FOLLY_ALWAYS_INLINE T* previousAlignedAddress(T* ptr, int to) {

定义辅助函数，将 ptr 向下对齐。

to 的单位是“元素个数”，而非字节。

### 第 76 行

return align_floor(ptr, sizeof(T) * to);

align_floor 接受的是字节对齐值，所以换算为：

sizeof(T) × cardinal

例如：

T = uint32_t
cardinal = 4
对齐字节数 = 4 × 4 = 16

如果 ptr 地址为 0x1014，向下按 16 字节对齐后得到 0x1010。

align_floor 内部通过类似操作实现：

address & ~(alignment - 1)

因此传入的字节对齐量必须是非零的 2 的幂。

### 第 77 行

结束 previousAlignedAddress。

## 第 79–93 行：主循环类说明

SimdForEachMainLoop 只负责处理首尾部分块之间的完整 SIMD 块。

它有两个版本：

- 展开因子为 1；
- 展开因子大于 1。

其 operator() 返回：

- true：delegate 要求提前结束；
- false：正常处理到 l。

## 第 93–105 行：不展开版本

### 第 93 行

struct SimdForEachMainLoop {

用函数对象承载两个 operator() 重载。

### 第 94–96 行

template <typename T, typename Delegate>
FOLLY_ALWAYS_INLINE bool operator()(
int cardinal, T*& f, T* l, Delegate& delegate, index_constant<1>) const {

这是 unrolling == 1 的专门版本。

注意 f 是 T*&，即“指针的引用”。函数推进 f 后，调用者看到的 af 也会同步改变。

最后一个参数 index_constant<1> 用于在编译期选择此重载。

### 第 97 行

while (f != l) {

遍历所有完整 SIMD 块。

这里要求 f、l 均已对齐，且距离是 cardinal 的整数倍。

### 第 98 行

if (delegate.step(f, ignore_none{}, index_constant<0>{})) {

处理从 f 开始的一个完整寄存器：

- ignore_none{}：全部 lane 有效；
- index_constant<0>{}：展开位置为 0，因为没有展开。

### 第 99 行

return true;

delegate 请求终止，向上传递提前退出信号。

### 第 101 行

f += cardinal;

把指针移动一个 SIMD 寄存器的元素数量。

### 第 104 行

return false;

完整处理到 l，没有提前终止。

## 第 107–125 行：单步展开辅助对象

这个对象用于 unrolling > 1 时连续执行最多 unrolling 次普通 step。

### 第 107–108 行

template <typename T, typename Delegate>
struct SmallStepsLambda {

它是传给 UnrollUtils::unrollUntil 的函数对象。

### 第 109 行

bool& shouldBreak;

引用外部布尔值，用来保存 delegate 是否请求终止。

### 第 110 行

int cardinal;

一个 SIMD 寄存器包含的元素数。

### 第 111 行

T*& f;

当前位置指针的引用。每处理一个寄存器都会推进外部指针。

### 第 112 行

T* l;

完整块区间的尾后指针。

### 第 113 行

Delegate& delegate;

实际处理 SIMD 数据的对象。

### 第 115–116 行

template <std::size_t i>
FOLLY_ALWAYS_INLINE bool operator()(index_constant<i> unrollI) {

每次模板展开调用一次。

i 是编译期常量：

0, 1, 2, ..., unrolling - 1

### 第 117–119 行

if (f == l) {
return true;
}

完整块已经处理完毕，要求 unrollUntil 停止继续展开。

这里返回 true 只表示“停止模板展开”，不代表 delegate 请求提前退出。因此并不会设置 shouldBreak。

### 第 121 行

shouldBreak = delegate.step(f, ignore_none{}, unrollI);

处理当前完整 SIMD 块，并把当前展开编号传给 delegate。

delegate 可以利用 unrollI 区分多组独立累加器，降低依赖链。

### 第 122 行

f += cardinal;

移动到下一个 SIMD 块。

即使 delegate 返回 true，这里仍会推进一次指针；由于随后整个遍历会退出，这个差异不影响算法结果。

### 第 123 行

return shouldBreak;

如果 delegate 请求终止，利用 unrollUntil 的短路行为停止后续展开调用。

### 第 125 行

结束辅助对象。

## 第 127–173 行：展开版本主循环

### 第 127–130 行

template <typename T, typename Delegate, std::size_t unrolling>
FOLLY_ALWAYS_INLINE bool operator()(
int cardinal, T*& f, T* l, Delegate& delegate, index_constant<unrolling>)
const {

这是一般展开版本。

最后一个参数把展开因子编码进类型。调用：

index_constant<4>{}

就会实例化 unrolling == 4 的版本。

index_constant<1> 会优先匹配前面的专门重载。

### 第 131–142 行：为什么先做单步

作者比较了三种方法：

1. Duff’s device；
2. 先运行展开循环，再处理剩余单步；
3. 先做一组普通单步，再运行展开循环。

这里选择第 3 种。

原因是 unrolledStep 往往需要准备多个寄存器、多个中间值。如果数组很短，先执行普通 step 可以在到达末尾后直接返回，完全避免初始化展开处理逻辑。

### 第 144–146 行

while (true) {

外层循环通常执行一次，最多因为末尾剩余的零散完整块再执行一次。

例如共有 11 个完整块、展开因子为 4：

先单步处理 4 个
展开处理 4 个
剩余 3 个
回到 while，再单步处理 3 个

### 第 147–149 行

bool shouldBreak = false;

记录单步阶段停止的原因：

- true：delegate 请求终止；
- false：只是到达 l。

### 第 151–153 行

if (UnrollUtils::unrollUntil<unrolling>(SmallStepsLambda<T, Delegate>{
shouldBreak, cardinal, f, l, delegate})) {

构造 SmallStepsLambda，然后将其在编译期展开 unrolling 次。

对于 unrolling == 4，概念上相当于：

op(index_constant<0>{}) ||
op(index_constant<1>{}) ||
op(index_constant<2>{}) ||
op(index_constant<3>{});

由于使用逻辑或的短路规则，一次调用返回 true 后，后续调用不会执行。

### 第 154 行

return shouldBreak;

如果单步阶段停止：

- 因 f == l 停止时，shouldBreak == false；
- 因 delegate 返回 true 停止时，shouldBreak == true。

因此可以准确向调用者区分“正常结束”和“提前结束”。

### 第 157 行

for (std::ptrdiff_t bigStepsCount = (l - f) / (cardinal * unrolling);

计算剩余区间包含多少个完整的“展开组”。

一个展开组处理：

cardinal × unrolling

个元素。

例如：

cardinal = 8
unrolling = 4

每个展开组处理 32 个元素。

使用 std::ptrdiff_t，因为两个指针相减的结果类型就是 ptrdiff_t。

### 第 158–159 行

bigStepsCount != 0;
--bigStepsCount

每轮消耗一个完整展开组，直到没有完整组为止。

### 第 160 行

std::array<T*, unrolling> arr;

创建指针数组，保存这一展开组中每个 SIMD 块的起始地址。

例如 cardinal == 4、unrolling == 3：

arr[0] = f
arr[1] = f + 4
arr[2] = f + 8

### 第 161 行

注释说明填充数组的 lambda 完全可内联，所以不需要额外回调结构。

### 第 162–166 行

UnrollUtils::unrollUntil<unrolling>([&](auto idx) {
arr[idx()] = f;
f += cardinal;
return false;
});

模板展开地填充 arr。

idx 是 index_constant<I> 对象，调用 idx() 得到编译期值 I。

lambda 永远返回 false，所以一定执行全部 unrolling 次。

对于展开因子 4，逻辑等价于：

arr[0] = f; f += cardinal;
arr[1] = f; f += cardinal;
arr[2] = f; f += cardinal;
arr[3] = f; f += cardinal;

### 第 167 行

if (delegate.unrolledStep(arr)) {

把整组指针交给 delegate。

delegate 可以：

1. 连续加载多个寄存器；
2. 对每个寄存器执行 SIMD 谓词；
3. 合并多个寄存器的逻辑结果；
4. 最后只执行一次横向归约。

例如 simdAnyOf 会先分别比较，再用 SIMD logical_or 合并，最后调用一次 Platform::any。

### 第 168 行

return true;

delegate 请求提前终止。

### 第 170 行

结束展开组循环。

### 第 171 行

结束本轮 while (true)。

如果展开组之后还剩少于 unrolling 个完整 SIMD 块，重新进入循环，由开头的 SmallStepsLambda 处理它们。

### 第 172–173 行

结束展开版本和 SimdForEachMainLoop。

## 第 175–208 行：主遍历入口

### 第 176–178 行

template <int unrolling, typename T, typename Delegate>
FOLLY_ALWAYS_INLINE void simdForEachAligning(
int cardinal, T* f, T* l, Delegate& delegate) {

定义主函数。

隐含前置条件包括：

- [f,l) 是合法半开区间；
- f <= l；
- cardinal > 0；
- sizeof(T) * cardinal 是合法的 2 的幂对齐值；
- unrolling >= 1。

### 第 179–181 行

if (f == l) {
return;
}

空区间直接返回。

这也避免后续对空区间地址执行对齐、加载和指针距离计算。

### 第 183 行

T* af = previousAlignedAddress(f, cardinal);

把起点 f 向下对齐到 SIMD 寄存器边界。

af 表示 aligned first。

例如：

cardinal = 4
f = base + 6
af = base + 4

### 第 184 行

T* al = previousAlignedAddress(l, cardinal);

把尾后指针 l 也向下对齐。

al 表示 aligned last。

注意它不是向上取整。例如：

l = base + 15
al = base + 12

从 al 开始的寄存器就是最后一个可能部分有效的 SIMD 块。

### 第 186 行

ignore_extrema ignore{static_cast<int>(f - af), 0};

计算首块需要忽略多少个前导 lane。

例如：

af = base + 4
f = base + 6

那么：

ignore.first = 2;
ignore.last = 0;

首块布局为：

索引： 4 5 6 7
状态： 忽略 忽略 有效 有效

### 第 187 行

if (af != al) {

判断起点和终点是否位于不同的对齐块。

- af == al：整个区间位于同一个 SIMD 块中；
- af != al：存在独立首块，之后还可能有完整块和尾块。

### 第 188–191 行：处理首块

if (delegate.step(af, ignore, index_constant<0>{})) {
return;
}

从向下对齐的 af 加载一个完整 SIMD 寄存器，但通过 ignore.first 忽略 f 之前的 lane。

首块使用展开编号 0。

如果 delegate 已找到结果，例如 any_of 找到匹配值，就立即返回。

### 第 192 行

ignore.first = 0;

首块已处理完。后续最终尾块不会有前导无效元素，因此清除 first。

如果 af == al，代码不会进入此分支，所以同一块同时作为首尾块时，原来的 ignore.first 会保留下来。

### 第 193 行

af += cardinal;

移动到首块之后的下一个对齐块。

从这里开始，af 指向完整 SIMD 块区间的起点。

### 第 195–196 行

if (SimdForEachMainLoop{}(
cardinal, af, al, delegate, index_constant<unrolling>{})) {

处理 [af,al) 中的所有完整 SIMD 块。

af 按引用传入，因此正常完成后：

af == al

最后一个参数在编译期选择：

- unrolling == 1 的简单循环；
- 一般展开循环。

### 第 197–198 行

return;

中间处理阶段如果 delegate 请求提前终止，整个遍历立即结束。

### 第 200 行

// Here af might be exactly at the end of page.

处理完中间块后，af 可能正好等于内存页末端或区间尾端，不能无条件再加载一个寄存器。

### 第 201–203 行

if (af == l) {
return;
}

如果 l 本身已经对齐，那么没有尾部部分块。

此时必须直接返回，不能再执行：

delegate.step(af, ...)

否则会从尾后地址额外读取一个 SIMD 寄存器，甚至可能跨入未映射页面。

### 第 204 行

结束“首尾位于不同对齐块”的分支。

### 第 206 行

ignore.last = static_cast<int>(af + cardinal - l);

计算最后一个 SIMD 块末端超出 l 的 lane 数量。

例如：

af = base + 12
cardinal = 4
l = base + 15

则：

ignore.last = 12 + 4 - 15 = 1;

尾块布局为：

索引： 12 13 14 15
状态： 有效 有效 有效 忽略

如果整个区间位于同一块中，此时 ignore.first 和 ignore.last 会同时非零。

例如：

cardinal = 4
f = base + 1
l = base + 3

得到：

ignore.first = 1;
ignore.last = 1;

只有中间两个 lane 有效。

### 第 207 行

delegate.step(af, ignore, index_constant<0>{});

处理最后一个部分有效的 SIMD 块。

这里没有检查返回值，因为它已经是最后一次调用；无论 delegate 返回什么，函数都会立即结束。

### 第 208 行

结束 simdForEachAligning。

### 第 210–211 行

关闭 folly::simd::detail 和 folly 命名空间。

## 一个完整例子

假设：

cardinal = 4
f = base + 1
l = base + 19

即有效区间是 [1,19)。

地址被拆分为：

块 [0,4) ：忽略第 0 个 lane，处理 1、2、3
块 [4,8) ：完整
块 [8,12) ：完整
块 [12,16) ：完整
块 [16,20) ：处理 16、17、18，忽略第 19 个 lane

对应执行顺序：

delegate.step(base + 0, {first=1,last=0}, index 0)
SimdForEachMainLoop 处理 [base+4, base+16)
delegate.step(base + 16, {first=0,last=1}, index 0)

核心思想可以压缩为：

af = floor_align(f);
al = floor_align(l);

处理首块，屏蔽 f 之前的 lane；
处理 [首块之后, al) 的完整块；
处理尾块，屏蔽 l 之后的 lane；

这让上层 SIMD 算法只需要实现“如何处理一个或多个寄存器”，不用反复处理地址未对齐、短数组、尾部残余和循环展开等边界问题。