尧图建网站 尧图建网站 YAOTU WEB BUILD 免费咨询
ARTICLE DETAIL

资讯详情

深耕网站建设与建站编程的一线实战洞察。

SimdAnyof.h

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提供编译期展开工具arrayMaparrayReduce- 第 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 Pstruct AnyOfDelegate {三个模板参数分别是- PlatformSIMD 平台抽象- I迭代器或指针类型- P向量谓词类型。在当前实际调用中I T*Platform 可能是SimdSse42PlatformTSimdAvx2PlatformTSimdAarch64PlatformT它需要提供Platform::reg_tPlatform::logical_tPlatform::kCardinalPlatform::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 gccexplicit AnyOfDelegate(P _p) : p(_p) {}### _p构造参数命名为 _p是为了避免旧版本 GCC 的变量遮蔽警告。如果也叫 p可能被认为遮蔽了第 59 行的成员 p。### explicit防止 P 被隐式转换成 AnyOfDelegateAnyOfDelegate delegate predicate; // 不允许AnyOfDelegate delegate{predicate}; // 允许### p(_p)将传入的谓词复制到成员变量 p。因此当前实现一般要求谓词可复制。它没有使用p(std::move(_p))所以这里明确执行复制而不是移动。## 第 40–45 行处理一个寄存器### 第 40–41 行template typename Ignore, typename UnrollStepFOLLY_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 falseignore 非常重要。假设首块为实际区间 [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 NFOLLY_ALWAYS_INLINE bool unrolledStep(std::arrayI, N arr) {这是展开主循环使用的接口。arr 保存连续 N 个完整 SIMD 块的起始指针。例如arr[0] → 第一个寄存器arr[1] → 第二个寄存器arr[2] → 第三个寄存器arr[3] → 第四个寄存器只有完整块才会传给 unrolledStep因此这里不需要 ignore_extrema。N 通常等于 simdAnyOf 的 unrolling 参数默认是 4。### 第 49 行// Dont 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::arraytypename 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::arraytypename 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 行simdAnyOfPlatform, unrolling 4(f, l, p);展示调用形式。实际调用时默认模板参数不需要写成 4例如simdAnyOfPlatform(f, l, predicate);或者显式指定simdAnyOfPlatform, 1(f, l, predicate);simdAnyOfPlatform, 4(f, l, predicate);### 第 66–67 行它类似 std::any_of但谓词是向量谓词Platform::reg_t → Platform::logical_t区别是// 普通 std::any_ofbool predicate(T scalar);// simdAnyOfPlatform::logical_t predicate(Platform::reg_t vector);### 第 69–70 行默认展开因子是 4。对于简单谓词例如“是否相等”4 路展开通常能提高吞吐量。对于昂贵谓词展开 4 路可能导致- 寄存器压力增大- 代码体积增大- 同一批次做太多不必要工作- 编译器产生溢出到栈的临时数据。此时展开因子 1 可能更合适。### 第 72–74 行函数被标记为 FOLLY_ALWAYS_INLINE。这是内部构建模块不希望最终用户直接依赖。上层通常会为具体功能建立一个非内联调用边界例如containsU8containsU16containsU32containsU64内部 SIMD 模板则全部展开在这些明确边界之后。## 第 76–81 行simdAnyOf 主函数### 第 76 行template typename Platform, int unrolling 4, typename T, typename P四个模板参数- Platform必须由调用者显式指定- unrolling可选默认为 4- T根据 f、l 自动推导- P根据谓词 p 自动推导。例如simdAnyOfSimdPlatformstd::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 行AnyOfDelegatePlatform, T*, P delegate{p};将谓词包装成 SimdForEach 能理解的 delegate。实例化后的结构概念上是struct {P p;bool res false;bool step(...);bool unrolledStep(...);};这里再次复制 p 进入 delegate。### 第 79 行simdForEachAligningunrolling(Platform::kCardinal, f, l, delegate);启动底层 SIMD 遍历。Platform::kCardinal 表示一个 SIMD 寄存器包含多少个 TkCardinal 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 simdAnyOfPlatform, 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 语义的“加载—谓词—合并—归约—提前退出”流程。
返回列表