将9个字符数字转换为int或无符号int的最快方法

Question

#include <stdio.h>
#include <iostream>
#include <string>
#include <chrono>
#include <memory>
#include <cstdlib>
#include <cstdint>
#include <cstring>
#include <immintrin.h>
using namespace std;

const int p[9] =   {1, 10, 100, 
                    1000, 10000, 100000, 
                    1000000, 10000000, 100000000};
                    
class MyTimer {
 private:
  std::chrono::time_point<std::chrono::steady_clock> starter;

 public:
  void startCounter() {
    starter = std::chrono::steady_clock::now();
  }

  int64_t getCounterNs() {    
    return std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::steady_clock::now() - starter).count();
  }
};
                    
int convert1(const char *a) {
    int res = 0;
    for (int i=0; i<9; i++) res = res * 10 + a[i] - 48;
    return res;
}

int convert2(const char *a) {
    return (a[0] - 48) * p[8] + (a[1] - 48) * p[7] + (a[2] - 48) * p[6]
            + (a[3] - 48) * p[5] + (a[4] - 48) * p[4] + (a[5] - 48) * p[3]
            + (a[6] - 48) * p[2] + (a[7] - 48) * p[1] + (a[8] - 48) * p[0];
}

int convert3(const char *a) {
    return (a[0] - 48) * p[8] + a[1] * p[7] + a[2] * p[6] + a[3] * p[5]
            + a[4] * p[4] + a[5] * p[3] + a[6] * p[2] + a[7] * p[1] + a[8]
            - 533333328;
}

const unsigned pu[9] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000,
    100000000};

int convert4u(const char *aa) {
  const unsigned char *a = (const unsigned char*) aa;
  return a[0] * pu[8] + a[1] * pu[7] + a[2] * pu[6] + a[3] * pu[5] + a[4] * pu[4]
      + a[5] * pu[3] + a[6] * pu[2] + a[7] * pu[1] + a[8] - (unsigned) 5333333328u;
}

int convert5(const char* a) {
    int val = 0;
    for(size_t k =0;k <9;++k) {
        val = (val << 3) + (val << 1) + (a[k]-'0');
    }
    return val;
}

const unsigned pu2[9] = {100000000, 10000000, 1000000, 100000, 10000, 1000, 100, 10, 1};

int convert6u(const char *a) {
  return a[0]*pu2[0] + a[1]*pu2[1] + a[2]*pu2[2] + a[3] * pu2[3] + a[4] * pu2[4] + a[5] * pu2[5] + a[6] * pu2[6] + a[7] * pu2[7] + a[8] - (unsigned) 5333333328u;
}

constexpr std::uint64_t zeros(char z) {
    std::uint64_t result = 0;
    for (int i = 0; i < sizeof(result); ++i) {
        result = result*256 + z;
    }
    return result;
}

int convertX(const char *a) {
    constexpr std::uint64_t offset = zeros('0');
    constexpr std::uint64_t o1 = 0xFF00FF00FF00FF00;
    constexpr std::uint64_t o2 = 0xFFFF0000FFFF0000;
    constexpr std::uint64_t o3 = 0xFFFFFFFF00000000;

    std::uint64_t buffer;
    std::memcpy(&buffer, a, sizeof(buffer));
    const auto bytes = buffer - offset;
    const auto b1 = (bytes & o1) >> 8;
    const auto words = (bytes & ~o1) + 10*b1;
    const auto w1 = (words & o2) >> 16;
    const auto dwords = (words & ~o2) + 100*w1;
    const auto d1 = (dwords & o3) >> 32;
    const auto qwords = (dwords & ~o3) + 1000*d1;

    const auto final = 10*static_cast<unsigned>(qwords) + (a[9] - '0');
    return static_cast<int>(final);
}

//########################  ACCEPTED ANSWER
//########################
//########################
typedef struct {             // for output into memory
    alignas(16) unsigned hours;
    unsigned minutes, seconds, nanos;
} hmsn;

void str2hmsn(hmsn *out, const char str[15])  // HHMMSSXXXXXXXXX  15 total, with 9-digit nanoseconds.
{    // 15 not including the terminating 0 (if any) which we don't read
    //hmsn retval;
    __m128i digs = _mm_loadu_si128((const __m128i*)str);
    digs = _mm_sub_epi8( digs, _mm_set1_epi8('0') );
    __m128i hms_x_words = _mm_maddubs_epi16( digs, _mm_set1_epi16( 10U + (1U<<8) ));   // SSSE3  pairs of digits => 10s, 1s places.

    __m128i hms_unpacked = _mm_cvtepu16_epi32(hms_x_words);                           // SSE4.1  hours, minutes, seconds unpack from uint16_t to uint32
    //_mm_storeu_si128((__m128i*)&retval, hms_unpacked);                                  // store first 3 struct members; last to be written separately
    _mm_storeu_si128((__m128i*)out, hms_unpacked);
    // or scalar extract with _mm_cvtsi128_si64 (movq) and shift / movzx

    __m128i xwords = _mm_bsrli_si128(hms_x_words, 6);  // would like to schedule this sooner, so oldest-uop-first starts this critical path shuffle ahead of pmovzx
    // 8 bytes of data, lined up in low 2 dwords, rather than split across high 3
    // could have got here with an 8-byte load that starts here, if we didn't want to get the H,M,S integers cheaply.

    __m128i xdwords = _mm_madd_epi16(xwords, _mm_setr_epi16(100, 1, 100, 1,  0,0,0,0));   // low/high uint32 chunks, discard the 9th x digit.
    uint64_t pair32 = _mm_cvtsi128_si64(xdwords);
    uint32_t msd = 100*100 * (uint32_t)pair32;     // most significant dword was at lower address (in printing order), so low half on little-endian x86.  encourage compilers to use 32-bit operand-size for imul
    uint32_t first8_x = msd + (uint32_t)(pair32 >> 32);
    uint32_t nanos = first8_x * 10 + ((unsigned char)str[14] - '0');   // total*10 + lowest digit
    out->nanos = nanos;
    //retval.nanos = nanos;
    //return retval;

  // returning the struct by value encourages compilers in the wrong direction
  // into not doing separate stores, even when inlining into a function that assigns the whole struct to a pointed-to output
}
hmsn mystruct;

int convertSIMD(const char* a)
{
    str2hmsn(&mystruct, a);
    return mystruct.nanos;
}


//########################
//########################
using ConvertFunc = int(const char*);

volatile int result = 0; // do something with the result of function to prevent unexpected optimization
void benchmark(ConvertFunc converter, string name, int numTest=1000) {
    MyTimer timer;
    const int N = 100000;
    char *a = new char[9*N + 17];
    int64_t runtime = 0;    

    for (int t=1; t<=numTest; t++) {        
        // change something to prevent unexpected optimization
        for (int i=0; i<9*N; i++) a[i] = rand() % 10 + '0'; 

        timer.startCounter();
        for (int i=0; i<9*N; i+= 9) result = converter(a+i);
        runtime += timer.getCounterNs();
    }
    cout << name << ": " << (runtime / (double(numTest) * N)) << "ns average\n";
    delete[] a;
}

int main() {
    benchmark(convert1, "slow");
    benchmark(convert2, "normal");    
    benchmark(convert3, "fast");
    benchmark(convert4u, "unsigned");
    benchmark(convert5, "shifting");
    benchmark(convert6u, "reverse");
    benchmark(convertX, "swar64");
    benchmark(convertSIMD, "manualSIMD");

    return 0;
}

我想找到将char a[9]转换为int的最快方法。完整的问题是将形式为HHMMSSxxxxxxxxx时间戳的char a[15]转换为纳秒，其中x分配后约50个字节，可以安全地读取（但不能写入）。我们只关心这个问题中的最后9位数字。

版本1是基本版本，版本2,3尝试保存一些计算。我使用-O3标志编译，在数组中存储10s的能力很好，因为它经过了优化（使用Godbolt检查）。

我怎样才能更快？是的，我知道这听起来像是过早的优化，但让我们假设我需要最终2-3%的提升。

版本3明显更快，而版本2由于代码大小而更慢。但我们能做得比版本3更好吗 基准无效

编辑2：函数可以返回无符号int而不是int（即

unsigned convert1(char *a);

编辑3：我注意到新代码是无效的基准，因为convert（a）只执行一次。使用原始代码，差异仅约为1%。

编辑4：新的基准测试。使用无符号（转换4u，转换6u）始终比使用int快3-5%。我将运行一个长（10分钟）的基准测试，看看是否有赢家。我已经编辑了代码以使用新的基准测试。它生成大量数据，然后运行转换器函数。

编辑5：结果：4.19、4.51、3.82、3.59、7.64、3.72秒。未签名的版本速度最快。是否可以仅在9个字节上使用SIMD？如果不是，那么我想这是最好的解决方案。不过我还是希望有更疯狂的解决方案

编辑6：AMD Ryzen 4350G上的基准测试结果，gcc版本10.3，编译命令gcc-o mainmain.cpp-std=c 17-O3-mavx-mavx2-游行=本机

slow: 4.17794ns average
normal: 2.59945ns average
fast: 2.27917ns average
unsigned: 2.43814ns average
shifting: 4.72233ns average
reverse: 2.2274ns average
swar64: 2.17179ns average
manualSIMD: 1.55203ns average

接受的答案甚至比问题要求的还要多，并且计算HH/MM/SS/nanosec，因此它甚至比这个基准测试显示的还要快。

Answer 1

并行计算不一定需要使用特殊的SIMD指令。通过使用64位无符号整数，我们可以并行处理九个字节中的八个，然后在最后将第九个字节作为一次性处理。

constexpr std::uint64_t zeros(char z) {
    std::uint64_t result = 0;
    for (int i = 0; i < sizeof(result); ++i) {
        result = result*256 + z;
    }
    return result;
}

unsigned convertX(const char *a) {
    constexpr std::uint64_t offset = zeros('0');
    constexpr std::uint64_t o1 = 0xFF00FF00FF00FF00;
    constexpr std::uint64_t o2 = 0xFFFF0000FFFF0000;
    constexpr std::uint64_t o3 = 0xFFFFFFFF00000000;

    std::uint64_t buffer;
    std::memcpy(&buffer, a, sizeof(buffer));
    const auto bytes = buffer - offset;
    const auto b1 = (bytes & o1) >> 8;
    const auto words = (bytes & ~o1) + 10*b1;
    const auto w1 = (words & o2) >> 16;
    const auto dwords = (words & ~o2) + 100*w1;
    const auto d1 = (dwords & o3) >> 32;
    const auto qwords = (dwords & ~o3) + 1000*d1;

    const auto final = 10*static_cast<unsigned>(qwords) + (a[9] - '0');
    return static_cast<unsigned>(final);
}

我使用MS Visual C（64位）进行了测试，该解决方案的基准时间刚刚超过200 MS，而其他所有解决方案的基准时间都是400 MS。这很有意义，因为它使用了“正常”解决方案所使用的大约一半的乘法和加法指令。

我知道memcpy看起来很浪费，但它避免了未定义的行为和对齐问题。

Answer 2

备选候选人

使用无符号数学避免UB of int溢出，并允许将所有的-48取出来，然后取为常数。

const unsigned p[9] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000,
    100000000};

int convert4u(const char *aa) {
  const unsigned char *a = (const unsigned char*) aa;
  return a[0] * p[8] + a[1] * p[7] + a[2] * p[6] + a[3] * p[5] + a[4] * p[4]
      + a[5] * p[3] + a[6] * p[2] + a[7] * p[1] + a[8] - (unsigned) 5333333328u;
}

也可以试着像排序一样排序。或许更容易并行计算。我看不出再订购有什么不好的地方。

const unsigned p[9] = {100000000, 10000000, ..., 1};

int convert4u(const char *aa) {
  const unsigned char *a = (const unsigned char*) aa;
  return a[0]*p[0] + a[1]*p[1] ... a[1]*p[1] + a[8] - (unsigned) 5333333328u;
}

Answer 3

是的，如评论中所述，SIMD是可能的。您可以利用它同时解析字符串的HH、MM和SS部分。

由于您有一个100%固定的格式，在必要时带有前导0，这比如何使用SIMD实现atoi更容易？-位置值是固定的，我们不需要任何比较/位扫描或pcmpistri来查找随机控制掩码或比例因子。此外，在C#中对无符号int解析的SIMD字符串进行性能改进也有一些好主意，例如调整位置值乘法器以避免最后的步骤（待办事项，在这里执行。）

9个十进制数字分解为两个DWORD和一个剩余字节，这可能是最好单独获取的。

假设您更关心吞吐量（与周围代码重叠的能力，或在独立元素上的循环中这样做的能力），而不是从输入指针和内存中的数据准备就绪到纳秒整数准备就绪的关键路径延迟，那么SSSE3 SIMD在现代x86上应该非常好。（如果要将小时、分钟、秒解压缩到连续的uint32\t元素中（例如在结构中），SSE4.1非常有用）。与标量相比，它在延迟方面也可能具有竞争力。

有趣的事实：clang自动矢量化您的转换2/转换3函数，在vpmulld的YMM寄存器中扩展到8倍dword（2 uops），然后是一系列的随机/添加。

策略是使用pmaddubsw和pmaddwd水平相乘相加对，以使每个数字乘以其位值的方式。例如10和1对，然后100和1表示来自两位数的整数对。然后提取最后一对的标量：将最高有效部分乘以100*100，并添加到最低有效部分。我很确定对于实际上是'0'...'9'的输入，任何步骤都不可能溢出；这运行并编译到我预期的高潮，但我没有验证数字结果。

#include <immintrin.h>

typedef struct {             // for output into memory
    alignas(16) unsigned hours;
    unsigned minutes, seconds, nanos;
} hmsn;

void str2hmsn(hmsn *out, const char str[15])  // HHMMSSXXXXXXXXX  15 total, with 9-digit nanoseconds.
{    // 15 not including the terminating 0 (if any) which we don't read
    //hmsn retval;
    __m128i digs = _mm_loadu_si128((const __m128i*)str);
    digs = _mm_sub_epi8( digs, _mm_set1_epi8('0') );
    __m128i hms_x_words = _mm_maddubs_epi16( digs, _mm_set1_epi16( 10U + (1U<<8) ));   // SSSE3  pairs of digits => 10s, 1s places.

    __m128i hms_unpacked = _mm_cvtepu16_epi32(hms_x_words);                           // SSE4.1  hours, minutes, seconds unpack from uint16_t to uint32
    //_mm_storeu_si128((__m128i*)&retval, hms_unpacked);                                  // store first 3 struct members; last to be written separately
    _mm_storeu_si128((__m128i*)out, hms_unpacked);
    // or scalar extract with _mm_cvtsi128_si64 (movq) and shift / movzx

    __m128i xwords = _mm_bsrli_si128(hms_x_words, 6);  // would like to schedule this sooner, so oldest-uop-first starts this critical path shuffle ahead of pmovzx
    // 8 bytes of data, lined up in low 2 dwords, rather than split across high 3
    // could have got here with an 8-byte load that starts here, if we didn't want to get the H,M,S integers cheaply.

    __m128i xdwords = _mm_madd_epi16(xwords, _mm_setr_epi16(100, 1, 100, 1,  0,0,0,0));   // low/high uint32 chunks, discard the 9th x digit.
    uint64_t pair32 = _mm_cvtsi128_si64(xdwords);
    uint32_t msd = 100*100 * (uint32_t)pair32;     // most significant dword was at lower address (in printing order), so low half on little-endian x86.  encourage compilers to use 32-bit operand-size for imul
    uint32_t first8_x = msd + (uint32_t)(pair32 >> 32);
    uint32_t nanos = first8_x * 10 + ((unsigned char)str[14] - '0');   // total*10 + lowest digit
    out->nanos = nanos;
    //retval.nanos = nanos;
    //return retval;

  // returning the struct by value encourages compilers in the wrong direction
  // into not doing separate stores, even when inlining into a function that assigns the whole struct to a pointed-to output
}

在Godbolt上使用测试循环，该循环使用asm（“：：“m”（sink）：“memory”）使编译器在循环中重做工作。或者是一种让MSVC也不会优化掉循环的黑客攻击。在我的i7-6700k上，使用GCC 11.1、x86-64 GNU/Linux，energy\u performance\u preference=performance，我让它每5个周期运行一次迭代。

IDK为什么不以每4c一个的速度运行；我调整了GCC选项，以避免JCC勘误表在没有填充的情况下变慢，并希望在4个uop缓存行中有循环。（6个uop，1个uop以32B边界结束，6个uop，2个uop以dec/jnz结束）。性能计数器表示前端“正常”，uops\U dispatched\U port显示所有4个ALU端口，每次迭代的uops数小于4个，最高为port0，为3.34。手动填充早期指令可以将其减少到3行，共3行、6行、6行UOP，但与每个iter的5c相比仍然没有任何改进，所以我想前端确实可以。

LLVM-MCA在预测每个iter的3c方面似乎雄心勃勃，显然是基于错误的Skylake模型，其“调度”（我认为前端重命名）宽度为6。即使使用合适的4宽型号，mcpu=haswell，它也可以预测4.5c。（我在Godbolt上使用了asm（“\LLVM-MCA-BEGIN”）等宏，并为测试循环包含了一个LLVM-MCA输出窗口。）它没有完全准确的uop-

吞吐量可能会受到在多个迭代中发现指令级并行性和重叠的能力的限制，例如在理解lfence对具有两个长依赖链的循环的影响时，会增加长度

测试回路为：

#include <stdlib.h>
#ifndef __cplusplus
#include <stdalign.h>
#endif
#include <stdint.h>

#if 1 && defined(__GNUC__)
#define LLVM_MCA_BEGIN  asm("# LLVM-MCA-BEGIN")
#define LLVM_MCA_END  asm("# LLVM-MCA-END")
#else
#define LLVM_MCA_BEGIN
#define LLVM_MCA_END
#endif


#if defined(__cplusplus)
    #include <atomic>
    using std::atomic_thread_fence, std::memory_order_acq_rel;
#else
    #include <stdatomic.h>
#endif

unsigned testloop(const char str[15]){
    hmsn sink;
    for (int i=0 ; i<1000000000 ; i++){
        LLVM_MCA_BEGIN;
        str2hmsn(&sink, str);
        // compiler memory barrier 
        // force materializing the result, and forget about the input string being the same
#ifdef __GNUC__
        asm volatile("" ::"m"(sink): "memory");
#else
  //#warning happens to be enough with current MSVC
        atomic_thread_fence(memory_order_acq_rel); // strongest barrier that doesn't require any asm instructions on x86; MSVC defeats signal_fence.
#endif
    }
    LLVM_MCA_END;
    volatile unsigned dummy = sink.hours + sink.nanos;  // make sure both halves are really used, else MSVC optimizes.
    return dummy;
}



int main(int argc, char *argv[])
{
    // performance isn't data-dependent, so just use a handy string.
    // alignas(16) static char str[] = "235959123456789";
    uintptr_t p = (uintptr_t)argv[0];
    p &= -16;
    return testloop((char*)p);   // argv[0] apparently has a cache-line split within 16 bytes on my system, worsening from 5c throughput to 6.12c
}

我编译如下，以压缩循环，使其在即将到达的32字节边界之前结束。请注意，march=haswell允许它使用AVX编码，保存一两条指令。

$ g++ -fno-omit-frame-pointer -fno-stack-protector -falign-loops=16 -O3 -march=haswell foo.c -masm=intel
$ objdump -drwC -Mintel a.out | less

...
0000000000001190 <testloop(char const*)>:
    1190:       55                      push   rbp
    1191:       b9 00 ca 9a 3b          mov    ecx,0x3b9aca00
    1196:       48 89 e5                mov    rbp,rsp
    1199:       c5 f9 6f 25 6f 0e 00 00         vmovdqa xmm4,XMMWORD PTR [rip+0xe6f]        # 2010 <_IO_stdin_used+0x10>
    11a1:       c5 f9 6f 15 77 0e 00 00         vmovdqa xmm2,XMMWORD PTR [rip+0xe77]        # 2020 <_IO_stdin_used+0x20> # vector constants hoisted
    11a9:       c5 f9 6f 0d 7f 0e 00 00         vmovdqa xmm1,XMMWORD PTR [rip+0xe7f]        # 2030 <_IO_stdin_used+0x30>
    11b1:       66 66 2e 0f 1f 84 00 00 00 00 00        data16 cs nop WORD PTR [rax+rax*1+0x0]
    11bc:       0f 1f 40 00             nop    DWORD PTR [rax+0x0]
### Top of loop is 16-byte aligned here, instead of ending up with 8 byte default
    11c0:       c5 d9 fc 07             vpaddb xmm0,xmm4,XMMWORD PTR [rdi]
    11c4:       c4 e2 79 04 c2          vpmaddubsw xmm0,xmm0,xmm2
    11c9:       c4 e2 79 33 d8          vpmovzxwd xmm3,xmm0
    11ce:       c5 f9 73 d8 06          vpsrldq xmm0,xmm0,0x6
    11d3:       c5 f9 f5 c1             vpmaddwd xmm0,xmm0,xmm1
    11d7:       c5 f9 7f 5d f0          vmovdqa XMMWORD PTR [rbp-0x10],xmm3
    11dc:       c4 e1 f9 7e c0          vmovq  rax,xmm0
    11e1:       69 d0 10 27 00 00       imul   edx,eax,0x2710
    11e7:       48 c1 e8 20             shr    rax,0x20
    11eb:       01 d0                   add    eax,edx
    11ed:       8d 14 80                lea    edx,[rax+rax*4]
    11f0:       0f b6 47 0e             movzx  eax,BYTE PTR [rdi+0xe]
    11f4:       8d 44 50 d0             lea    eax,[rax+rdx*2-0x30]
    11f8:       89 45 fc                mov    DWORD PTR [rbp-0x4],eax
    11fb:       ff c9                   dec    ecx
    11fd:       75 c1                   jne    11c0 <testloop(char const*)+0x30>
  # loop ends 1 byte before it would be a problem for the JCC erratum workaround
    11ff:       8b 45 fc                mov    eax,DWORD PTR [rbp-0x4]

因此，GCC在以这种方式编写内部函数之前，手工设计了asm，使用尽可能少的指令来优化吞吐量。（Clang支持此循环中的延迟，使用单独的添加，而不是三分量LEA）。

这比任何只解析X的标量版本都要快，而且它也在解析HH、MM和SS。尽管转换器3的clang自动矢量化可能会让它在该部门中发挥作用，但奇怪的是，它在内联时并没有这样做。

GCC的标量convert3每次迭代需要8个周期。clang的标量转换器3在一个循环中需要7个，以4.0融合域uop/时钟运行，最大化前端带宽，并使端口1饱和，每个周期一个imul uop。（这是使用movzx重新加载每个字节，并在每次迭代时将标量结果存储到堆栈本地。但不涉及HHMMSS字节。）

$ taskset -c 3 perf stat --all-user -etask-clock,context-switches,cpu-migrations,page-faults,cycles,instructions,uops_issued.any,uops_executed.thread,idq.mite_uops,idq_uops_not_delivered.cycles_fe_was_ok -r1 ./a.out

 Performance counter stats for './a.out':

          1,221.82 msec task-clock                #    1.000 CPUs utilized          
                 0      context-switches          #    0.000 /sec                   
                 0      cpu-migrations            #    0.000 /sec                   
               105      page-faults               #   85.937 /sec                   
     5,079,784,301      cycles                    #    4.158 GHz                    
    16,002,910,115      instructions              #    3.15  insn per cycle         
    15,004,354,053      uops_issued.any           #   12.280 G/sec                  
    18,003,922,693      uops_executed.thread      #   14.735 G/sec                  
         1,484,567      idq.mite_uops             #    1.215 M/sec                  
     5,079,431,697      idq_uops_not_delivered.cycles_fe_was_ok #    4.157 G/sec                  

       1.222107519 seconds time elapsed

       1.221794000 seconds user
       0.000000000 seconds sys

请注意，这是针对1G迭代的，因此5.08G周期意味着每次迭代平均吞吐量为5.08周期。

除去生成输出的HHMMSS部分（vpsrldq、vpmovzxwd和vmovdqa存储）的额外工作，仅是9位整数部分，它在Skylake上以每次迭代4.0个周期运行。或3.5，末尾没有标量存储。（我编辑了GCC的asm输出以注释该指令，所以我知道它仍在做所有工作。）

事实上，这里存在某种后端瓶颈（而不是前端瓶颈），这可能是将其与独立工作重叠的一件好事。