字符串长度函数不稳定

Question

所以我刚才做了这个 strlen，一切似乎都很好。但是我开始注意到我的代码库中存在错误，过了一会儿我将其追踪到了这个 strlen 函数。我使用 SIMD 指令来编写它，我是编写内在函数的新手，所以代码可能也不是最好的。

函数如下：

inline size_t strlen(const char* data) {
        const __m256i terminationCharacters = _mm256_setzero_si256();
        const size_t shiftAmount = ((size_t)&data) & 31;
        const __m256i* pointer = (const __m256i*) (data - shiftAmount);

        size_t length = 0;

        for (;; length += 32, ++pointer) {
            const __m256i comparingData = _mm256_load_si256(pointer);
            const __m256i comparison = _mm256_cmpeq_epi8(comparingData, terminationCharacters);

            if (!_mm256_testc_si256(terminationCharacters, comparison)) {
                const auto mask = _mm256_movemask_epi8(comparison);

                return length + _tzcnt_u32(mask >> shiftAmount);
            }
        }
    }

Answer 1

您尝试将启动处理合并到对齐向量循环中至少有 2 个 showstopper 错误：

如果您的对齐加载发现任何零字节，您将退出循环，即使它们来自字符串的正确开始之前。（@James Griffin 在评论中发现了这一点）。您需要执行 mask >>= shiftAmount 并检查它是否为非零，以查看在字符串开始之后的负载部分是否有任何匹配项。（不要使用 _mm256_testc_si256，只需移动遮罩并检查）。
_tzcnt_u32(mask >> shiftAmount); 对于第一个之后的任何向量都是错误的。整个向量来自字符串开头之后的字节，因此您需要 tzcnt 来查看所有位。相反，你想要 _tzcnt_u32(mask) - shiftAmount，我想。

自己制作一些测试用例，在实际字符串之前但在第一个对齐向量内有 0 个字节。并在相对于向量的不同位置测试具有最终 0 且非零的用例，并针对 libc strlen 测试您的版本。（甚至可能是前 32 个字节内的一些随机 0 位置，然后是之后的前 64 个字节内。）

如果您将处理未对齐启动的策略与循环分开，那么您的策略应该会起作用。 ().

另一个选项是在从字符串的实际开头加载第一个未对齐矢量之前进行页面交叉检查。（但是你需要回退到其他东西）。然后对齐：重叠很好；只要你正确计算出最终的长度，你是否两次检查同一个字节是否为零都没有关系。

（您也不希望编译器在循环内浪费指令，增加指针和一个单独的长度，因此请检查生成的 asm。指针减法在循环之后应该可以解决问题。甚至可以转换为 uintptr_t.
此外，您可以从初始函数 arg 中减去最终的零位置，而不是从对齐的指针中减去，因此除了初始对齐之外，您根本不使用它，而不是减去两次 shiftAmount。）

根本不要使用 vptest 内在函数 (_mm256_testc_si256)，即使在您应该检查所有字节的主循环中也是如此； _mm_cmp* 结果并不好。 vptest 是 2 微指令，不能与分支指令进行宏融合。但是 vpmovmskb eax, ymm0 是 1 个微指令，而 test eax,eax / jz .loop 是另一个宏融合微指令。更好的是，您实际上需要循环后的整数 movemask 结果，所以您已经有了它。

相关

（包括指向 glibc 的 strlen 实现的手写 x86-64 asm 的链接。）除非你在一个 C 库更差的平台上，否则通常你应该使用它，因为 glibc 在动态链接到 select 期间使用 CPU 检测，为您的 CPU 提供了一个好的版本的 strlen（和 memcpy 等）。 strlen 的未对齐启动有点棘手，我认为 glibc 做出了合理的选择，除非函数调用开销是一个大问题。它还具有用于大字符串的良好循环展开技术（如 _mm256_min_epu8 如果 2 个输入向量中的任何一个为零，则在向量元素中获得零，因此它可以分摊实际的 movemask/branch 工作整个缓存行的数据）。不过，对于中等长度的字符串，它可能过于激进。

请注意，glibc 的许可证是 LGPL，因此除非您的许可证兼容，否则您不能将代码从 glibc 复制到您的项目中。即使编写与其 asm 等效的内在函数也可能有问题。
- 一个简单的 SSE2 strlen 不处理错位，在手写的 asm 中。以及对基准测试的评论。
https://agner.org/optimize/ - 指南和指令表，他的子程序库（手写的 asm）包括一个 strlen。（但请注意，它已获得 GPL 许可。）

我假设某些 BSD 和 MacOS 在更宽松的许可下具有 asm strlen，您可以使用/查看您的项目是否与 GPL 兼容。

Answer 2

没有冒犯但是

size_t strlen(char *p)
{
    size_t ret_val = 0;

    while (*p++) ret_val++;

    retirn ret_val;
}

很久很久以前就很好用了。另外，今天的优化编译器会为它编写非常紧凑的代码，您的代码无法阅读。

字符串长度函数不稳定

String length function is unstable

c

simd

memory-alignment

avx

strlen