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_constantI它等价于std::integral_constantstd::size_t, I用来把循环展开位置编码进类型。- 第 21 行#include folly/algorithm/simd/Ignore.h提供ignore_noneignore_extrema- 第 22 行#include folly/algorithm/simd/detail/UnrollUtils.h提供基于模板展开的 unrollUntilN。- 第 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 行simdForEachAligningunrolling(cardinal, f, l, delegate);概括函数调用形式。参数含义- unrolling主循环一次展开多少个 SIMD 寄存器- cardinal一个 SIMD 寄存器能容纳多少个 T- f、l半开区间 [f,l)- delegate实际执行 SIMD 运算的对象。例如 128 位 SSET uint8_t → cardinal 16T uint16_t → cardinal 8T uint32_t → cardinal 4T uint64_t → cardinal 2### 第 43–47 行为什么可以向前读取算法可能把 f 向下对齐到 f 之前的地址然后加载整个 SIMD 寄存器。假设cardinal 4f 指向索引 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::arrayT*, unrolling);它一次处理 unrolling 个完整 SIMD 块。当 unrolling 1 时不会调用这个接口。delegate 通过引用传入所以它可以保存结果和状态。例如 simdAnyOf 的 delegate 会保存“是否已有任何 lane 匹配”。## 第 64–66 行提前声明template int unrolling, typename T, typename DelegateFOLLY_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 TFOLLY_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_tcardinal 4对齐字节数 4 × 4 16如果 ptr 地址为 0x1014向下按 16 字节对齐后得到 0x1010。align_floor 内部通过类似操作实现address ~(alignment - 1)因此传入的字节对齐量必须是非零的 2 的幂。### 第 77 行结束 previousAlignedAddress。## 第 79–93 行主循环类说明SimdForEachMainLoop 只负责处理首尾部分块之间的完整 SIMD 块。它有两个版本- 展开因子为 1- 展开因子大于 1。其 operator() 返回- truedelegate 要求提前结束- false正常处理到 l。## 第 93–105 行不展开版本### 第 93 行struct SimdForEachMainLoop {用函数对象承载两个 operator() 重载。### 第 94–96 行template typename T, typename DelegateFOLLY_ALWAYS_INLINE bool operator()(int cardinal, T* f, T* l, Delegate delegate, index_constant1) const {这是 unrolling 1 的专门版本。注意 f 是 T*即“指针的引用”。函数推进 f 后调用者看到的 af 也会同步改变。最后一个参数 index_constant1 用于在编译期选择此重载。### 第 97 行while (f ! l) {遍历所有完整 SIMD 块。这里要求 f、l 均已对齐且距离是 cardinal 的整数倍。### 第 98 行if (delegate.step(f, ignore_none{}, index_constant0{})) {处理从 f 开始的一个完整寄存器- ignore_none{}全部 lane 有效- index_constant0{}展开位置为 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 Delegatestruct 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 iFOLLY_ALWAYS_INLINE bool operator()(index_constanti 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 unrollingFOLLY_ALWAYS_INLINE bool operator()(int cardinal, T* f, T* l, Delegate delegate, index_constantunrolling)const {这是一般展开版本。最后一个参数把展开因子编码进类型。调用index_constant4{}就会实例化 unrolling 4 的版本。index_constant1 会优先匹配前面的专门重载。### 第 131–142 行为什么先做单步作者比较了三种方法1. Duff’s device2. 先运行展开循环再处理剩余单步3. 先做一组普通单步再运行展开循环。这里选择第 3 种。原因是 unrolledStep 往往需要准备多个寄存器、多个中间值。如果数组很短先执行普通 step 可以在到达末尾后直接返回完全避免初始化展开处理逻辑。### 第 144–146 行while (true) {外层循环通常执行一次最多因为末尾剩余的零散完整块再执行一次。例如共有 11 个完整块、展开因子为 4先单步处理 4 个展开处理 4 个剩余 3 个回到 while再单步处理 3 个### 第 147–149 行bool shouldBreak false;记录单步阶段停止的原因- truedelegate 请求终止- false只是到达 l。### 第 151–153 行if (UnrollUtils::unrollUntilunrolling(SmallStepsLambdaT, Delegate{shouldBreak, cardinal, f, l, delegate})) {构造 SmallStepsLambda然后将其在编译期展开 unrolling 次。对于 unrolling 4概念上相当于op(index_constant0{}) ||op(index_constant1{}) ||op(index_constant2{}) ||op(index_constant3{});由于使用逻辑或的短路规则一次调用返回 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 8unrolling 4每个展开组处理 32 个元素。使用 std::ptrdiff_t因为两个指针相减的结果类型就是 ptrdiff_t。### 第 158–159 行bigStepsCount ! 0;--bigStepsCount每轮消耗一个完整展开组直到没有完整组为止。### 第 160 行std::arrayT*, unrolling arr;创建指针数组保存这一展开组中每个 SIMD 块的起始地址。例如 cardinal 4、unrolling 3arr[0] farr[1] f 4arr[2] f 8### 第 161 行注释说明填充数组的 lambda 完全可内联所以不需要额外回调结构。### 第 162–166 行UnrollUtils::unrollUntilunrolling([](auto idx) {arr[idx()] f;f cardinal;return false;});模板展开地填充 arr。idx 是 index_constantI 对象调用 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 DelegateFOLLY_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 4f base 6af base 4### 第 184 行T* al previousAlignedAddress(l, cardinal);把尾后指针 l 也向下对齐。al 表示 aligned last。注意它不是向上取整。例如l base 15al base 12从 al 开始的寄存器就是最后一个可能部分有效的 SIMD 块。### 第 186 行ignore_extrema ignore{static_castint(f - af), 0};计算首块需要忽略多少个前导 lane。例如af base 4f 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_constant0{})) {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_constantunrolling{})) {处理 [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_castint(af cardinal - l);计算最后一个 SIMD 块末端超出 l 的 lane 数量。例如af base 12cardinal 4l base 15则ignore.last 12 4 - 15 1;尾块布局为索引 12 13 14 15状态 有效 有效 有效 忽略如果整个区间位于同一块中此时 ignore.first 和 ignore.last 会同时非零。例如cardinal 4f base 1l base 3得到ignore.first 1;ignore.last 1;只有中间两个 lane 有效。### 第 207 行delegate.step(af, ignore, index_constant0{});处理最后一个部分有效的 SIMD 块。这里没有检查返回值因为它已经是最后一次调用无论 delegate 返回什么函数都会立即结束。### 第 208 行结束 simdForEachAligning。### 第 210–211 行关闭 folly::simd::detail 和 folly 命名空间。## 一个完整例子假设cardinal 4f base 1l 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, {first1,last0}, index 0)SimdForEachMainLoop 处理 [base4, base16)delegate.step(base 16, {first0,last1}, index 0)核心思想可以压缩为af floor_align(f);al floor_align(l);处理首块屏蔽 f 之前的 lane处理 [首块之后, al) 的完整块处理尾块屏蔽 l 之后的 lane这让上层 SIMD 算法只需要实现“如何处理一个或多个寄存器”不用反复处理地址未对齐、短数组、尾部残余和循环展开等边界问题。