快速解析8位整数

假设您想要从 ASCII/UTF-8 字符串中快速解析 8 位整数 (0, 1, 2, …, 254, 255)。这个问题出现在 Jeroen Koekkoek（NLnet Labs）领导的 simdzone 项目中。给定一个字符串及其长度：例如，“22”，长度为 2。C 中的简单方法可能是：

 int parse_uint8_naive ( const char * str , size_t len , uint8_t * num ) {     uint32_t n = 0 ;   for ( size_t i = 0 , r = len & 0x3 ; i < r ; i ++ ) {       uint8_t d = ( uint8_t ) ( str [ i ] - '0' ) ;   如果( d > 9 )   返回0 ；       n = n * 10 + d ；   }   * num = ( uint8_t ) n ;   返回n < 256 && len && len < 4 ;   }   

此代码是一个 C 函数，它将字符串、其长度以及指向无符号 8 位整数的指针作为输入参数。该函数返回一个布尔值，指示输入字符串是否可以解析为无符号8位整数。

该函数首先将 32 位无符号整数n初始化为零，我们将把答案存储在那里。然后，该函数迭代输入字符串，从字符串中提取每个数字字符并将其转换为无符号 8 位整数。然后，提取的数字乘以 10 后与n相加。此过程一直持续到字符串末尾或函数处理完字符串的 4 个字节。最后，该函数将n的值赋给num指向的无符号 8 位整数。然后它返回一个布尔值，指示解析的整数是否小于 256 并且输入字符串的长度是否在 1 到 3 个字符之间。如果输入字符串包含任何非数字字符或字符串长度大于 3 个字节，则该函数返回 false。

在 C++ 中，您可以调用from_chars ：

 int parse_uint8_fromchars ( const char * str , size_t len , uint8_t * num ) {   auto [ p , ec ] = std :: from_chars ( str , str + len , * num ) ;   返回( ec == std :: errc ( ) ) ;   }      

std::from_chars函数采用三个参数：指向输入字符序列开头的指针、指向输入字符序列结尾的指针以及对将保存解析的整数值的输出变量的引用。该函数返回一个std::from_chars_result对象，该对象包含两个成员：指向未解析的第一个字符的指针，以及指示解析是否成功的错误代码。

在此函数中，使用输入字符串及其长度作为参数以及指向将保存解析值的无符号 8 位整数的指针std::from_chars函数。然后该函数检查std::from_chars返回的错误代码是否等于std::errc() ，这表明解析成功。如果解析成功，该函数返回true 。否则，它返回false 。

我们能比这些功能做得更好吗？假设您始终可以读取 4 个字节，即使字符串较短（即有缓冲区）。这通常是一个安全的假设。然后，您可以将输入加载到 32 位字中，并在单个寄存器中一次性处理所有字节。这通常称为 SWAR：在计算机科学中，SWAR 表示寄存器内的 SIMD，这是一种对处理器寄存器中包含的数据执行并行操作的技术。

Jeroen Koekkoek 首先提出了一种有效的 SWAR 方法，但在我们有不可预测的输入的情况下，它只比朴素方法大约 40%，并且在给定可预测输入的情况下并不比朴素方法快。让我们研究一种可能具有全面竞争力的方法：

 int parse_uint8_fastswar ( const char * str , size_t len , uint8_t * num ) {   联盟{       uint8_t as_str [ 4 ] ;       uint32_t as_int ;   }数字；   memcpy ( & digits.as_int , str , sizeof ( digits ) ) ;     数字. as_int ^ = 0x30303030卢;     数字. as_int < < = ( 4 - ( len & 0x3 ) ) * 8 ;     uint32_t y = ( ( UINT64_C ( 0x640a0100 ) *位数.as_int ) >> 32 ) & 0xff ;   * num = ( uint8_t ) ( y ) ;   return ( digits.as_int & 0xf0f0f0f0 ) == 0 && y < 256 && len ! _ = 0    &&长度< 4 ;   }      

同样，此代码是一个 C 函数，它将字符串、其长度以及指向无符号 8 位整数的指针作为输入参数。该函数返回一个布尔值，指示输入字符串是否可以解析为无符号8位整数。该函数首先初始化一个联合digits ，其中包含 4 个无符号 8 位整数和一个 32 位无符号整数的数组。然后，该函数使用memcpy函数将输入字符串复制到 32 位无符号整数中。 memcpy函数将输入字符串复制到 32 位无符号整数中。

然后，该函数使用 XOR 运算符和常量值0x30303030lu翻转 32 位无符号整数的位。此操作将输入字符串中的每个数字字符转换为其相应的十进制值。事实上，从 0 到 9 的 ASCII 字符在 ASCII 中的代码点值为 0x30 到 0x39。然后，该函数将 32 位无符号整数向左移动一定位数，具体取决于输入字符串的长度。此操作将删除不属于输入字符串的所有尾随字节。

下一部分是我对例程做出贡献的地方。然后，该函数使用 64 位无符号整数将 32 位无符号整数乘以常量值0x640a0100 。这是一次执行两次乘法（乘以 100 和乘以 10）和两次求和的简洁方法。观察到 0x64 是 100，0x0a 是 10。然后，该乘法的结果右移 32 位，并用值0xff进行掩码。此操作提取 32 位无符号整数的最低有效字节，它表示解析后的无符号 8 位整数。最后，该函数将解析后的无符号8位整数的值分配给num指向的无符号8位整数。然后它返回一个布尔值，指示解析的整数是否小于 256 并且输入字符串的长度是否在 1 到 3 个字符之间。

为了测试这些功能，我编写了一个基准测试。该基准测试使用随机输入或顺序输入（0,1,…），并且最终非常相关。我使用 GCC 12 和运行频率为 3.2 GHz 的 Ice Lake (Intel) Linux 服务器。我报告了每秒解析的数百万个数字的数量。

因此，当输入不可预测时，SWAR 方法的速度实际上是朴素方法的两倍。否则，对于可预测的输入，根据我的数据，我们仍然有 30% 的增益。 from_chars 结果令人失望。

你能做得更好吗？基准可用。

图片来源：我很感谢 NLnet Labs 的 Jeroen Koekkoek 提出了这个问题。

原文： https://lemire.me/blog/2023/11/28/parsing-8-bit-integers-quickly/