计算机使用字节表示字符串。大多数情况下，我们使用 Unicode 标准以字节表示字符。在线交换字符串的通用格式称为 UTF-8。它可以表示超过一百万个字符，同时保持与古老的 ASCII 格式的兼容性。
尽管我们的大部分软件堆栈已转移到 Unicode 字符串，但仍有较旧的标准，如用于欧洲字符串的 Latin 1。因此我们经常需要将 Latin 1 字符串转换为 UTF-8。首先计算最终 UTF-8 字符串的大小（以字节为单位）很有用。
幸运的是，这是一个简单的问题：对于每个设置了最高有效位的输入字节，计算两个输出字节就足够了，对于其他字节计算一个输出字节就足够了。一个相对简单的 C++ 函数就足够了：
size_t scalar_utf8_length ( const char * c , size_t len ) { size_t答案= 0 ; 对于( size_t i = 0 ; i < len ; i + + ) { 如果( ( c [ i ] > > 7 ) ) {回答+ + ; } } 返回答案+ len ; }
为了更快，我们可能想使用奇特的“SIMD”指令：一次处理多个字节的指令。您的编译器可能已经使用简单的 C 函数进行了一些自动向量化。在编译时，它会使用一些 SIMD 指令。但是，您可以尝试手动编写您自己的版本。
我们有多种指令集可供选择，但让我们选择 AVX2 指令集，它在当今大多数 x64 处理器上可用。 AVX2 有一个可以提取所有最高有效位的快速掩码函数，然后是另一个可以对它们进行计数的快速函数（popcount）。因此，以下例程应该很好（归功于 Anna Henningsen）：
size_t avx2_utf8_length_basic ( const uint8_t * str , size_t len ) { size_t answer = len / sizeof ( __m256i ) * sizeof ( __m256i ) ; 大小我; 对于( i = 0 ; i + sizeof ( __m256i ) < = len ; i + = 32 ) { __m256i 输入= _mm256_loadu_si256 ( ( const __m256i * ) ( str + i ) ) ; answer + = __builtin_popcount ( _mm256_movemask_epi8 (输入) ) ; } 返回答案+ scalar_utf8_length ( str + i , len - i ) ; }
你能做得更好吗？在 Intel 处理器上，“移动掩码”和人口计数指令都很快，但它们有一些延迟：它们需要几个周期才能执行。它们也可能有额外的执行约束。对于像 AVX-512 这样的指令集，部分延迟和约束不会变得更好，因为它需要在每次迭代时从 SIMD 寄存器移动到通用寄存器。将此例程移植到 ARM 处理器同样会有些挑战。
因此我们希望依靠更便宜的指令，并留在 SIMD 寄存器中直到结束。即使它没有提高 AVX 代码的速度，它也可能在算法上与其他指令集一起工作得更好。
为此，我们可以从论文Faster Population Counts Using AVX2 Instructions (Computer Journal 61 (1), 2018) 中借用一个方法。这个想法是快速提取位，并将它们添加到 SIMD 寄存器内的计数器中，并且只在最后精确计算值。
代码稍微复杂一些，因为我们有一个内部循环。在内循环中，我们使用 8 位计数器，在内循环结束时才移动到 64 位计数器。为保证不溢出，内循环只能运行255次迭代。代码如下所示……
size_t avx2_utf8_length_mkl ( const uint8_t * str , size_t len ) { size_t answer = len / sizeof ( __m256i ) * sizeof ( __m256i ) ; 尺寸_t我= 0 ; __m256i four_64bits = _mm256_setzero_si256 ( ) ; while ( i + sizeof ( __m256i ) < = len ) { __m256i 转轮= _mm256_setzero_si256 ( ) ; size_t迭代次数= ( len - i ) / sizeof ( __m256i ) ; 如果（迭代次数> 255 ） {迭代次数= 255 ； } size_t max_i = i + iterations * sizeof ( __m256i ) - sizeof ( __m256i ) ; 对于( ; i < = max_i ; i + = sizeof ( __m256i ) ) { __m256i 输入= _mm256_loadu_si256 ( ( const __m256i * ) ( str + i ) ) ; 转轮= _mm256_sub_epi8 ( 转轮， _mm256_cmpgt_epi8 （ _mm256_setzero_si256 （ ） ，输入） ） ； } four_64bits = _mm256_add_epi64 ( four_64bits , _mm256_sad_epu8 （转轮， _mm256_setzero_si256 （ ） ） ） ； } 答案+ = _mm256_extract_epi64 ( four_64bits , 0 ) + _mm256_extract_epi64 ( four_64bits , 1 ) + _mm256_extract_epi64 ( four_64bits , 2 ) + _mm256_extract_epi64 ( four_64bits , 3 ) ; 返回答案+ scalar_utf8_length ( str + i , len - i ) ; }
我们还可以进一步展开内部循环以节省指令数量。
我用 AMD Rome (Zen2) 服务器和 GCC 11 ( -O3 -march=native ) 编写了一个带有8kB 随机输入的小型基准测试。结果将根据您的输入、编译器和处理器而有所不同。
| 功能 | 周期/字节 | 指令/字节 | 指令/周期 |
|---|---|---|---|
| 标量（无 autovec） | 0.89 | 3.3 | 3.8 |
| 标量（w. autovec） | 0.56 | 0.71 | 1.27 |
| AVX2（移动掩码） | 0.055 | 0.15 | 2.60 |
| AVX2（在 SIMD 中） | 0.039 | 0.15 | 3.90 |
| AVX2（SIMD 内/展开） | 0.028 | 0.07 | 2.40 |
所以我测试中最快的方法比纯标量版本快 30 多倍。如果我允许编译器对标量向量进行“自动向量化”，它的速度会提高大约 50%。
这是一个有趣的场景，因为按周期退出的指令数量变化很大。稍微复杂一点的“in-SIMD”函数比“movemask”函数做得更好，因为在这些测试中，它设法在每个周期退出更多指令。展开版本速度很快，每个周期需要的指令很少，但每个周期退出的指令数量“相对”较少。
我的代码可用。应该可以进一步调整此代码。您需要特权访问才能运行基准测试，因为我依赖性能计数器。
进一步的工作：没有必要明确地使用 SIMD 指令，您可以使用SWAR 来代替可移植性和性能之间的折衷。
原文： https://lemire.me/blog/2023/02/16/computing-the-utf-8-size-of-a-latin-1-string-quickly-avx-edition/