Contains.h Contains.cpp

folly/algorithm/simd/Contains.h 定义公共 API、类型约束和编译期分派folly/algorithm/simd/Contains.cpp 提供四个固定宽度的非模板调用边界。整体调用链folly::simd::contains(range, needle)↓检查 range/needle 是否适合 SIMD↓将元素重新解释成 uint8/16/32/64_t↓containsU8/U16/U32/U64↓containsImpl├─ 支持 SIMD → simdAnyOf└─ 不支持 → memchr/wmemchr/std::find# 一、Contains.h## 第 1–25 行文件声明和依赖### 第 1–15 行Apache 2.0 许可证声明。### 第 17 行#pragma once防止头文件在同一个翻译单元内重复包含。### 第 19 行#include folly/CPortability.h提供 FOLLY_ERASE 等跨编译器宏。这里的 FOLLY_ERASE 主要意味着强制内联 隐藏内部符号### 第 20 行#include folly/algorithm/simd/detail/Traits.h提供前面分析过的 SIMD 类型转换设施AsSimdFriendlyUintFnasSimdFriendlyUintsimd_friendly_equivalent_scalar_thas_integral_simd_friendly_equivalent_scalar_v### 第 22 行#include iterator提供std::beginstd::iterator_traits### 第 23 行#include span提供 std::span。### 第 25 行namespace folly::simd {进入公共 SIMD 命名空间。## 第 26–28 行内部声明区### 第 26 行namespace detail {进入内部实现命名空间。### 第 28 行// no overloading for easier profiling.作者刻意不写一个重载函数contains(spanuint8_t, ...)contains(spanuint16_t, ...)contains(spanuint32_t, ...)contains(spanuint64_t, ...)而是给每种宽度不同的函数名containsU8containsU16containsU32containsU64这样 profiler、性能火焰图和符号分析中能直接区分四条调用路径而不需要查看被修饰后的重载签名。———## 第 30–37 行四个固定类型入口### 第 30–31 行bool containsU8(std::spanconst std::uint8_t haystack,std::uint8_t needle) noexcept;声明 8 位无符号搜索入口。- haystack不拥有内存的只读连续区间- needle待搜索的 8 位值- noexcept保证函数不会向调用方传播异常。### 第 32–33 行bool containsU16(std::spanconst std::uint16_t haystack,std::uint16_t needle) noexcept;声明 16 位搜索入口。### 第 34–35 行bool containsU32(std::spanconst std::uint32_t haystack,std::uint32_t needle) noexcept;声明 32 位搜索入口。### 第 36–37 行bool containsU64(std::spanconst std::uint64_t haystack,std::uint64_t needle) noexcept;声明 64 位搜索入口。这四个函数在 Contains.cpp 中定义是公共模板 API 和内部模板实现之间明确保留的调用边界。———## 第 39–41 行取得范围元素类型template typename Rusing std_range_value_t typename std::iterator_traitsdecltype(std::begin(std::declvalR()))::value_type;这个别名取得范围 R 的元素值类型。执行过程构造一个仅用于类型推导的 R↓调用 std::begin↓得到迭代器类型↓iterator_traitsIterator::value_type例如std_range_value_tstd::vectorint intstd_range_value_tstd::spanconst int intstd_range_value_tstd::arrayuint16_t, 4 uint16_tstd::declvalR() 只出现在 decltype 的未求值环境中不会真的创建 R。使用 value_type 而不是引用类型意味着元素上的 const 和引用属性通常被去掉这适合后面的数值宽度和 signedness 判断。———# 第 43–56 行无损转换检查## 第 43–45 行注释说明只有当 needle 总能安全转换成 haystack 元素类型时才允许 SIMD 实现。否则先转换再比较可能和标准 C 的原始比较语义不同。## 第 46–47 行template typename From, typename Toconstexpr bool convertible_with_no_loss() {编译期判断From 的任意可能值是否都能安全表示为 To在实际调用中- Fromneedle 的 SIMD 友好有符号/无符号类型- Tohaystack 元素的 SIMD 友好有符号/无符号类型。## 第 48–50 行拒绝窄化if (sizeof(From) sizeof(To)) {return false;}如果 needle 类型比 haystack 元素更宽拒绝转换。例如uint32_t needle → uint16_t haystack拒绝int64_t needle → int32_t haystack拒绝因为某些 needle 值无法由较窄类型表示。## 第 51–53 行有符号来源if (std::is_signed_vFrom) {return std::is_signed_vTo;}如果 needle 是有符号类型目标也必须是有符号类型。结合前面的宽度检查允许int8_t → int8_tint8_t → int16_tint16_t → int32_tint32_t → int64_t拒绝int8_t → uint8_tint8_t → uint16_tint32_t → uint64_t即使目标无符号类型更宽也会拒绝。原因是负数转换为无符号数后值会改变可能产生与原始比较不同的结果。## 第 55 行无符号来源return std::is_unsigned_vTo || sizeof(From) sizeof(To);走到这里说明 From 不是有符号类型在本文件的正常使用中就是无符号整数。允许两种情况。第一种目标也是无符号uint8_t → uint8_tuint8_t → uint16_tuint16_t → uint32_t第二种目标有符号但严格更宽uint8_t → int16_tuint16_t → int32_tuint32_t → int64_t更宽的有符号类型可以表示较窄无符号类型的所有值。拒绝同宽无符号到有符号uint8_t → int8_tuint16_t → int16_tuint32_t → int32_t因为无符号类型的上半区间无法由同宽有符号类型表示。## 第 56 行结束 convertible_with_no_loss。### 完整规则表From To 条件 结果━━━━━━━━━━ ━━━━━━━━━━ ━━━━━━━━━━━━━━━━━━━━━━━━━━━━ ━━━━━━signed signed sizeof(From) sizeof(To) 允许────────── ────────── ──────────────────────────── ──────signed unsigned 任意宽度 拒绝────────── ────────── ──────────────────────────── ──────unsigned unsigned sizeof(From) sizeof(To) 允许────────── ────────── ──────────────────────────── ──────unsigned signed sizeof(From) sizeof(To) 允许────────── ────────── ──────────────────────────── ──────unsigned signed 同宽 拒绝────────── ────────── ──────────────────────────── ──────任意 更窄目标 拒绝———# 第 58–75 行检查整个调用是否合法## 第 58–62 行注释列出 contains(haystack, needle) 的要求1. haystack 是 SIMD 友好的连续范围2. 只处理整数类标量3. needle 能无损转换成 haystack 元素类型4. 转换后比较必须保持原 equality 语义。“整数类标量”在这里还包含能够映射成整数的枚举和指针。## 第 63–64 行template typename R, typename Tconstexpr bool contains_haystack_needle_test() {定义总约束检查函数- Rhaystack 范围类型- Tneedle 类型。返回值完全在编译期计算。## 第 65–66 行检查 haystackif constexpr (!std::is_invocable_vAsSimdFriendlyUintFn, R) {return false;}检查AsSimdFriendlyUintFn{}(range)是否是合法表达式。这同时验证- R 能否构造 std::span- R 是否是连续范围- 元素类型能否映射成固定宽度整数- 元素类型能否转换成无符号 SIMD 友好类型。示例vectorint → 可以arrayuint16_t → 可以spanconst int → 可以setint → 不可以非连续vectordouble → 不可以浮点没有 unsigned SIMD 映射使用 if constexpr 很重要如果 haystack 本身不合法后面的 std_range_value_tR 不会被实例化避免产生额外模板错误。## 第 67–68 行检查 needle} else if constexpr (!has_integral_simd_friendly_equivalent_scalar_vT) {return false;}要求 needle 能映射成整数 SIMD 标量。允许的典型类型有符号整数无符号整数整数底层类型的枚举指针拒绝floatdouble普通 class/struct## 第 69 行} else {只有 haystack 和 needle 分别通过基本检查后才进入类型兼容性判断。## 第 70–71 行using simd_haystack_value simd_friendly_equivalent_scalar_tstd_range_value_tR;取得 haystack 元素的“保留 signedness”固定宽度类型。这里刻意没有使用无符号版本因为约束检查需要知道原始 signedness。例如vectorint → int32_tvectorunsigned short → uint16_tvectorEnum:int16_t → int16_tvectorint* → intptr_t## 第 72 行using simd_needle simd_friendly_equivalent_scalar_tT;同样取得 needle 的保留 signedness 映射类型。例如short → int16_tuint8_t → uint8_tenum:uint32 → uint32_tvoid* → intptr_t## 第 73 行return convertible_with_no_losssimd_needle,simd_haystack_value();检查 needle 是否可以无损转换到 haystack 元素类型。注意模板参数顺序From needleTo haystack value例如haystackint32_tneedleint16_t → 允许haystackint32_tneedleuint16_t → 允许haystackint16_tneedleuint16_t → 拒绝haystackuint32_tneedleint16_t → 拒绝haystackuint32_tneedleuint16_t → 允许## 第 74–75 行结束 else 和约束检查函数。## 第 77 行} // namespace detail关闭内部命名空间下面开始定义公共 API。———# 第 79–88 行公共 API 文档注释将folly::simd::contains描述为std::ranges::find(r, x) ! r.end()的向量化版本。它不适用于任意比较对象只适用于能够合理转换为uint8_tuint16_tuint32_tuint64_t的情况。与通用 std::ranges::find 的重要区别是- 没有自定义投影- 没有自定义比较器- 只处理连续范围- 类型必须通过前面的无损转换检查- 实际底层比较统一使用无符号定宽整数。———# 第 89–114 行contains_fn## 第 89 行struct contains_fn {使用函数对象实现公共 API类似标准库 ranges customization point object。这样可以定义inline constexpr contains_fn contains;然后使用folly::simd::contains(range, needle);## 第 90–94 行模板和 SFINAEtemplate typename R,typename T,typename std::enable_if_tdetail::contains_haystack_needle_testR, T()模板参数- R范围类型- Tneedle 类型- 第三个匿名参数SFINAE 约束。只有contains_haystack_needle_testR,T() true时std::enable_if_ttrue 才能形成有效类型。如果约束为 false当前 operator() 会从重载集合中消失而不是在函数体内部产生大量模板错误。## 第 95 行FOLLY_ERASE bool operator()(R r, T x) const {- R 是转发引用可以接收 mutable/const 左值以及临时范围- x 按值传递- 成员函数是 const因为函数对象本身无状态- FOLLY_ERASE 强制内联该薄包装。这里没有声明 noexcept。即使后面的固定类型入口是 noexcept从函数类型角度看公共 operator() 仍是潜在抛出函数。对于临时范围这里通常是安全的转换出的 span 只在当前调用内使用搜索结束前临时范围仍然存活不会像“返回 span”那样发生悬空。## 第 96 行auto castR detail::asSimdFriendlyUint(std::span(r));分两步1. 从范围 r 构造 std::span2. 将其元素类型按内存表示重新解释为等宽无符号整数。例如spanint8_t → spanuint8_tspanint16_t → spanuint16_tspanint32_t → spanuint32_tspanint64_t → spanuint64_t枚举数组会根据枚举宽度映射成对应无符号整数。指针数组在 64 位平台通常映射成std::spanstd::uint64_t这个转换不复制任何元素castR.data() 原 range.data()它只建立一个不同元素类型的内存视图。## 第 97 行using value_type detail::std_range_value_tdecltype(castR);取得转换后 span 的元素值类型。因此 value_type 最终应当是四种之一std::uint8_tstd::uint16_tstd::uint32_tstd::uint64_t即使 castR 是std::spanconst std::uint32_t其迭代器 value_type 仍然是std::uint32_t不会带 const。## 第 99 行auto castX static_castvalue_type(detail::asSimdFriendlyUint(x));先把 needle 转换成其自身宽度的无符号 SIMD 类型再转换成 haystack 的无符号元素宽度。例如haystack value_type uint32_tneedle int16_t{-1}但这种 signed needle 到 unsigned haystack 的情况已经被约束拒绝不会实例化到这里。允许的示例haystack int32_tneedle int16_t{7}asSimdFriendlyUint(needle) → uint16_t{7}static_castuint32_t → uint32_t{7}前面的 convertible_with_no_loss 保证该扩宽转换不会改变合法输入值的比较语义。## 第 101 行if constexpr (std::is_same_vvalue_type, std::uint8_t) {编译期检查 haystack 转换后的元素宽度是否为 8 位。因为是 if constexpr最终只保留一条分派路径不产生运行时类型判断。## 第 102 行return detail::containsU8(castR, castX);调用 8 位固定入口。castR 可以隐式转换成std::spanconst std::uint8_t## 第 103–104 行} else if constexpr (std::is_same_vvalue_type, std::uint16_t) {return detail::containsU16(castR, castX);}16 位类型调用 containsU16。## 第 105–106 行} else if constexpr (std::is_same_vvalue_type, std::uint32_t) {return detail::containsU32(castR, castX);}32 位类型调用 containsU32。## 第 107 行} else {剩余的合法情况理论上只能是 uint64_t。## 第 108–110 行static_assert(std::is_same_vvalue_type, std::uint64_t,internal error, unknown type);防御性编译期检查。如果未来 Traits.h 意外允许了其他整数宽度例如某个 128 位类型却没有给 contains 增加对应分支这里会给出明确错误internal error, unknown type## 第 111 行return detail::containsU64(castR, castX);调用 64 位固定入口。## 第 112–114 行结束分支、调用运算符和 contains_fn。———## 第 116 行公共函数对象inline constexpr contains_fn contains;创建公共无状态函数对象。调用形式folly::simd::contains(values, needle);等价于folly::simd::contains_fn{}(values, needle);- inline允许头文件在多个翻译单元中定义同一对象- constexpr对象本身可在常量上下文中存在- 但 operator() 并不是 constexpr搜索本身不是编译期算法。## 第 118 行} // namespace folly::simd关闭命名空间。———# 二、Contains.cpp## 第 1–17 行声明与主头文件### 第 1–15 行Apache 2.0 许可证。### 第 17 行#include folly/algorithm/simd/Contains.h首先包含对应公共头文件确保实现签名与公开声明一致。———## 第 19–22 行实现依赖### 第 19 行#include algorithm提供标准搜索算法。直接使用发生在 ContainsImpl.h 中。### 第 20 行#include cstring提供 std::memchr。直接使用同样位于 ContainsImpl.h。### 第 21 行#include span提供 std::span。### 第 22 行#include folly/algorithm/simd/detail/ContainsImpl.h引入实际实现包括containsImplStdcontainsImplHandwrittencontainsImpl其中containsImpl会在编译期选择手写 SIMD 实现或标准库实现ContainsImpl.h 自身已经包含所需标准头因此第 19–21 行有一定显式依赖或历史冗余性质。———## 第 24 行namespace folly::simd::detail {进入与头文件声明一致的内部命名空间。———## 第 26–29 行8 位入口bool containsU8(std::spanconst std::uint8_t haystack,std::uint8_t needle) noexcept {return containsImpl(haystack, needle);}这是公共模板分派之后保留的实际函数调用边界。模板推导得到T std::uint8_t随后 containsImpluint8_t 编译期选择支持 SIMDsimdAnyOfPlatform,4不支持 SIMDcontainsImplStd→ memchr函数声明为 noexcept。如果内部意外抛出异常程序会调用 std::terminate当前内部操作均设计为不抛异常。———## 第 30–33 行16 位入口bool containsU16(std::spanconst std::uint16_t haystack,std::uint16_t needle) noexcept {return containsImpl(haystack, needle);}模板参数T std::uint16_t可能执行SIMD 平台逐寄存器 uint16_t 相等比较非 SIMDsizeof(uint16_t) sizeof(wchar_t)→ 可能使用 wmemchr否则→ std::find具体标准回退取决于目标平台的 sizeof(wchar_t)。———## 第 34–37 行32 位入口bool containsU32(std::spanconst std::uint32_t haystack,std::uint32_t needle) noexcept {return containsImpl(haystack, needle);}模板参数T std::uint32_t在 Linux/macOS 等 sizeof(wchar_t) 4 的平台上非 SIMD 回退可能使用 std::wmemchr其他情况下使用 std::find。———## 第 38 行空行仅用于将 containsU64 与前面的入口视觉分隔没有语义。## 第 39–42 行64 位入口bool containsU64(std::spanconst std::uint64_t haystack,std::uint64_t needle) noexcept {return containsImpl(haystack, needle);}模板参数T std::uint64_t支持 SIMD 时- SSE 一次比较 2 个 uint64_t- AVX2 一次比较 4 个 uint64_t- NEON 一次比较 2 个 uint64_t。没有 SIMD 时通常回退到 std::find。## 第 44 行} // namespace folly::simd::detail关闭内部命名空间。———# 三、为什么把实现分成 .h 和 .cpp如果公共 contains_fn::operator() 直接调用containsImpl(castR, castX);那么包含 Contains.h 的每个翻译单元都可能实例化复杂的SimdForEachSimdAnyOfSimdPlatform平台 intrinsic循环展开代码当前结构改为公共头文件contains_fn::operator()↓四个很薄的固定类型函数声明↓ 跨越 .cpp 调用边界Contains.cppcontainsU8/U16/U32/U64↓containsImpl 模板实例化效果包括1. SIMD 重型模板只集中在 Contains.cpp2. 减少调用方编译时间3. 避免多个翻译单元重复实例化4. 控制二进制代码体积5. profiler 中保留清晰的 containsU8/U16/U32/U64 符号6. 公共头文件不需要暴露平台 intrinsic 细节。———# 四、类型转换示例## 例 1同类型有符号整数std::vectorint32_t values{1, 2, 3};bool found folly::simd::contains(values, int32_t{2});转换haystack: spanint32_t → spanuint32_tneedle: int32_t → uint32_tdispatch: containsU32## 例 2较窄有符号 needlestd::vectorint32_t values;int16_t needle;约束int16_t → int32_t无损允许执行needle → uint16_t → uint32_thaystack → spanuint32_tcontainsU32## 例 3较窄无符号 needle 到更宽有符号 haystackstd::vectorint32_t values;uint16_t needle;允许因为uint16_t 的所有值都能由 int32_t 表示## 例 4同宽无符号 needle 到有符号 haystackstd::vectorint32_t values;uint32_t needle;拒绝因为 uint32_t 的上半范围无法由 int32_t 表示。## 例 5有符号 needle 到无符号 haystackstd::vectoruint32_t values;int16_t needle;拒绝。负 needle 转换成 uint32_t 后可能与某个大正数错误匹配改变原比较语义。## 例 6枚举enum class State : uint16_t {idle,running,};std::arrayState, 2 states;folly::simd::contains(states, State::running);转换为spanState → spanuint16_tState::running → uint16_tcontainsU16## 例 7指针int a;int b;std::arrayint*, 2 pointers{a, b};folly::simd::contains(pointers, b);64 位系统上spanint* → spanuint64_tb → uint64_tcontainsU64比较的是指针的整数表示。———# 五、最终职责划分Contains.h├─ 判断 range 是否连续且元素可映射├─ 判断 needle 是否为整数友好类型├─ 检查 needle → haystack 是否无损├─ 将数据统一成 uint8/16/32/64└─ 编译期选择 containsU8/U16/U32/U64Contains.cpp├─ 提供四个非模板、可分析的调用边界├─ 集中实例化 containsImpl└─ 隔离复杂 SIMD 模板与平台 intrinsicContainsImpl.h├─ 有 SIMDsimdAnyOf└─ 无 SIMDmemchr/wmemchr/std::find这两个文件共同完成了“宽松易用的公共范围 API”到“严格固定类型 SIMD 内核”之间的适配。