有没有一种快速的方法将由8个ASCII十进制数字组成的字符串转换为二进制数？

Question

考虑像 12345678 这样的8位字符作为一个字符串。它可以转换为一个数字，其中每个字节都包含一个数字，如下：

const char* const str = "12345678";
const char* const base = "00000000";
const uint64_t unpacked = *reinterpret_cast<const uint64_t*>(str)
    - *reinterpret_cast<const uint64_t*>(base);

在小端系统上，unpacked 的值将会是 0x0807060504030201。

如何以最快的方式将这个数字转换成 12345678，也许通过乘以某些魔术数或使用 SIMD 直到 AVX2？

更新： 12345678 必须是存储在 32 位或 64 位整数中的数字，而不是字符串。

- Serge Rogatch

---

请查看 _mm_maddubs_epi16 和 _mm_madd_epi16。 - chtz

第一步编写测试（以检查有效性），第二步编写性能测试（以检查速度）-这一步相当困难。然后进行实验。编写代码并假设它是正确和最快的通常会偏离轨道。 - Marek R

更新：12345678 必须是存储在32位或64位整数中的数字，而不是字符串。如果您将数字存储为 uin64_t，则无需进行转换即可使用 uin64_t。 - Jarod42

@Jarod42，输入是一个字符串，在问题的代码片段中。我只是在寻找将字符串解析为整数的优化方法。 - Serge Rogatch

所以你正在寻找std::from_chars？ - Jarod42

Answer 1

二进制乘法只是一系列的移位和加法。采用SWAR方法并不难理解。详细步骤请参考以下链接：

• https://johnnylee-sde.github.io/Fast-numeric-string-to-int/
• https://kholdstare.github.io/technical/2020/05/26/faster-integer-parsing.html
• https://lemire.me/blog/2022/01/21/swar-explained-parsing-eight-digits/
• http://0x80.pl/articles/simd-parsing-int-sequences.html

// http://govnokod.ru/13461
static inline
uint32_t parse_8digits_swar_classic (char* str) {
    uint64_t v;

    memcpy(&v, str, 8);
    v = (v & 0x0F0F0F0F0F0F0F0F) * 2561 >> 8;
    v = (v & 0x00FF00FF00FF00FF) * 6553601 >> 16;
    v = (v & 0x0000FFFF0000FFFF) * 42949672960001 >> 32;
    return v;
}

// attempt to improve the latency
static inline
uint32_t parse_8digits_swar_aqrit (char* str) {
    const uint64_t mask = 0x000000FF000000FF;
    uint64_t v, t;

    memcpy(&v, str, 8);
    v = (v * 10) + (v >> 8);
    t = (v & mask) * 0x000F424000000064;
    v = ((v >> 16) & mask) * 0x0000271000000001;
    v = (v + t + 0xFF0915C600000000ULL) >> 32;
    return v;
}

// SSSE3 needs less `shift & mask` operations...
static inline
uint32_t parse_8digits_simd_ssse3 (char* str) {
    const __m128i mul1 = _mm_set_epi32(0, 0, 0x010A0A64, 0x14C814C8);
    const __m128i mul2 = _mm_set_epi32(0, 0, 0x0001000A, 0x00FA61A8);
    const __m128i mask = _mm_set1_epi8(0x0F);
    __m128i v;

    v = _mm_loadl_epi64((__m128i*)(void*)str);
    v = _mm_and_si128(v, mask);
    v = _mm_madd_epi16(_mm_maddubs_epi16(mul1, v), mul2);
    v = _mm_add_epi32(_mm_add_epi32(v, v), _mm_shuffle_epi32(v, 1));
    return (uint32_t)_mm_cvtsi128_si32(v);
}

- aqrit

---

我觉得这个问题看起来很熟悉；在谷歌上搜索 0x010A0A64 常量，找到了你回答的 SIMD string to unsigned int parsing in C# performance improvement。 - Peter Cordes

Answer 2

在没有AVX2的旧x86-64系统上，基于树形式收集数字的简单版本非常高效，并且根据我的测试，其性能与基于SWAR实现的简单版本相当。但是，这需要具有大量指令级并行处理器，因为当使用完整优化进行编译时，其指令数量比基于SWAR的代码多50%。

/* convert a string of exactly eight 'char' into a 32-bit unsigned integer */
uint32_t string_to_number (const char * s)
{
    uint32_t t0 = s[0] * 10 + s[1];
    uint32_t t1 = s[2] * 10 + s[3];
    uint32_t t2 = s[4] * 10 + s[5];
    uint32_t t3 = s[6] * 10 + s[7];
    uint32_t s0 = t0 * 100 + t1;
    uint32_t s1 = t2 * 100 + t3;
    uint32_t num = s0 * 10000 + s1;
    uint32_t corr =
        '0' * 10000000 +
        '0' * 1000000 +
        '0' * 100000 +
        '0' * 10000 +
        '0' * 1000 +
        '0' * 100 +
        '0' * 10 +
        '0' * 1;
    return num - corr;
}

- njuffa

---

你有比较过它和aqrit的SSSE3版本吗？对于单个整数，它只需要SSSE3，并且可以并行处理2个。（它高度优化吞吐量，大约为8个微操作。不包括加载向量常量。对于延迟来说仍然不算差，但所有微操作都互相依赖，包括两个SIMD整数乘法，除了一个paddd/ pshufd对。） - Peter Cordes

@PeterCordes 我没有比较它，因为在你指出之前我没有看到它。我主要对 SWAR 方法感到好奇，因为简单的树方法只需要简单、高吞吐量的操作，除了三个 IMUL。 - njuffa

好的。你是如何测试的（我假设是吞吐量而不是循环转换延迟）？使用了什么硬件？Zen / Ice Lake 比以前的 x86 有更宽的管道，并且有更多处理 LEA 的执行单元，我想编译器会经常使用，例如每个 x * 10 + y 操作需要 2 个。 - Peter Cordes

AArch64对于SWAR版本非常有趣；它可以编码立即数，用于像AND这样的位运算，作为重复的位模式，而不像x86-64需要笨拙的10字节指令。https://godbolt.org/z/c1EPsdW5K。对于您的版本，clang选择使用许多`madd`指令，其中一些具有常量10。但是AArch64可能可以有效地使用SIMD来执行类似于我们可以使用SSSE3的操作，甚至可能是基线，不像SSSE3。 - Peter Cordes

@PeterCordes (1) 吞吐量; (2) Ivybridge，我想; (3) 英特尔编译器。正如godbolt所显示的那样，当针对通用x86-64时，Clang、gcc和icc生成的代码非常相似，毫不奇怪地被Agner Fog的表格中过去十年中所有(?)英特尔CPU的2/cycle的movsx和2操作数lea所主导。指令总数为22或23。编译器意识到可以通过一个movsx来完成一个lea(例如godbolt)。 - njuffa

Answer 3

如果您将输入格式更改为广度优先元素顺序，就像这样：

Sample 9 numbers, interleaved
digit[]:
1 1 1 1 1 1 1 1 1 ... 2 2 2 2 2 2 2 2 2 ...
... 3 3 3 3 3 3 3 3 3 ....

for(int j=0; j<num_parse; j+=9)
{
    for(int i=0; i<9; i++)
    {
        value[i] += 
          (multiplier[i]*=10)*
          (digit[i+j]-'0');
    }
    // value vector copied to output
    // clear value & multiplier vectors
}

如果您转换的值不止9个，例如将512或8192填充到32的任意倍数，则编译器应该对其进行矢量化。

为了准备输入，您可以使用8个不同的通道，每个解析值的每个数字使用一个通道。

- huseyin tugrul buyukisik

Answer 4

我已经实现了一个小程序来测试一些想法。AVX2的实现比朴素的实现快约1.5倍，并且在表格实现中处于中间位置：

AVX2: 12345678 in 3.42759
Naive: 12345678 in 5.12581
Table: 12345678 in 4.49478

源代码：

#include <cstdlib>
#include <cstdint>
#include <immintrin.h>
#include <iostream>
using namespace std;

const __m256i mask = _mm256_set1_epi32(0xf);
const __m256i mul = _mm256_setr_epi32(10000000, 1000000, 100000, 10000, 1000, 100, 10, 1);

const volatile char* str = "12345678";
volatile uint32_t h;

const int64_t nIter = 1000LL * 1000LL * 1000LL;

inline void parse_avx2() {
  const char* const base = "00000000";
  const uint64_t unpacked = *reinterpret_cast<const volatile uint64_t*>(str)
    - *reinterpret_cast<const uint64_t*>(base);

  const __m128i a = _mm_set1_epi64x(unpacked);
  const __m256i b = _mm256_cvtepu8_epi32(a);
  const __m256i d = _mm256_mullo_epi32(b, mul);
  const __m128i e = _mm_add_epi32(_mm256_extractf128_si256(d, 0), _mm256_extractf128_si256(d, 1));
  const uint64_t f0 = _mm_extract_epi64(e, 0);
  const uint64_t f1 = _mm_extract_epi64(e, 1);
  const uint64_t g = f0 + f1;
  h = (g>>32) + (g&0xffffffff);
}

inline void parse_naive() {
  const char* const base = "00000000";
  const uint64_t unpacked = *reinterpret_cast<const volatile uint64_t*>(str)
    - *reinterpret_cast<const uint64_t*>(base);

  const uint8_t* a = reinterpret_cast<const uint8_t*>(&unpacked);
  h = a[7] + a[6]*10 + a[5]*100 + a[4]*1000 + a[3]*10000 + a[2]*100000 + a[1]*1000000 + a[0]*10000000;
}

uint32_t summands[8][10];
inline void parse_table() {
  const char* const base = "00000000";
  const uint64_t unpacked = *reinterpret_cast<const volatile uint64_t*>(str)
    - *reinterpret_cast<const uint64_t*>(base);

  const uint8_t* a = reinterpret_cast<const uint8_t*>(&unpacked);
  h = summands[7][a[0]] + summands[6][a[1]] + summands[5][a[2]] + summands[4][a[3]]
    + summands[3][a[4]] + summands[2][a[5]] + summands[1][a[6]] + summands[0][a[7]];
}

int main() {
  clock_t start = clock();
  for(int64_t i=0; i<nIter; i++) {
    parse_avx2();
  }
  clock_t end = clock();
  cout << "AVX2: " << h << " in " << double(end-start)/CLOCKS_PER_SEC << endl;

  start = clock();
  for(int64_t i=0; i<nIter; i++) {
    parse_naive();
  }
  end = clock();
  cout << "Naive: " << h << " in " << double(end-start)/CLOCKS_PER_SEC << endl;

  uint32_t mul=1;
  for(int i=0; i<8; i++, mul*=10) {
    for(int j=0; j<9; j++) {
      summands[i][j] = j*mul;
    }
  }

  start = clock();
  for(int64_t i=0; i<nIter; i++) {
    parse_table();
  }
  end = clock();
  cout << "Table: " << h << " in " << double(end-start)/CLOCKS_PER_SEC << endl;
  return 0;
}

- Serge Rogatch

---

立即转换为32位是相当慢的；vpmulld在Intel CPU从Haswell开始（支持AVX2）需要2个uops。广播unpacked在使用其低64位之前也是不必要的。而且，*reinterpret_cast<const volatile uint64_t*>是一种相当低效的方式，可能会绕过严格别名未定义行为（如果它能工作），而不是使用movq内部函数，如_mm_loadl_epi64和SIMD _mm_and_si128或_mm_sub_epi8从ASCII字符中获取0..9整数数字。 - Peter Cordes