将 9 个 char 数字转换为 int 或 unsigned int 的最疯狂最快的方法
Most insanely fastest way to convert 9 char digits into an int or unsigned int
#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% 的提升。
**大修改：**我替换了代码以减少 std::chrono 对测量时间的影响。 结果大不相同：2700ms、810ms、670ms。 在我的 i7 8750H 笔记本电脑上，带有 -O3 标志的 gcc 9.3.0，结果是：355、387、320 毫秒。
版本 3 明显更快，而版本 2 由于代码大小而较慢。但是我们能比版本 3 做得更好吗？ 无效基准
编辑 2： 函数可以 return unsigned int 而不是 int（即
unsigned convert1(char *a);
编辑 3： 我注意到新代码是无效的基准，因为 convert(a) 只执行一次。使用原始代码，差异仅~1%。
编辑 4： 新基准。使用 unsigned (convert4u, convert6u) 始终比使用 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 main main.cpp -std=c++17 -O3 -mavx -mavx2 -march=native
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，因此它甚至比基准测试显示的还要快。
备选候选人
使用 unsigned 数学来避免 int 的 UB 溢出并允许将所有 - 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;
}
也尝试像 a[] 一样订购 p[9]。也许更容易并行计算。我认为重新订购没有缺点。
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;
}
是的，如评论中所述，SIMD 是可能的。您可以利用它同时解析字符串的 HH、MM 和 SS 部分。
因为你有一个 100% 固定的格式，必要时前导 0，这比 - Place-values are fixed and we don't need any compare / bit-scan or pcmpistri to look up a shuffle control mask or scale-factor. Also SIMD string to unsigned int parsing in C# performance improvement 有一些好主意，比如调整位值乘数以避免最后的步骤（TODO，在这里做。）
9 个十进制数字分解为两个双字和一个可能最好单独获取的剩余字节。
假设您关心的是吞吐量（将其与周围代码重叠的能力，或者在独立元素的循环中执行此操作的能力），而不是从输入指针和内存中的数据就绪到纳秒整数就绪的周期中的关键路径延迟，SSSE3 SIMD 在现代 x86 上应该非常好。 （如果您想将小时、分钟、秒解压缩为连续的 uint32_t 元素，例如在结构中，SSE4.1 很有用）。与标量相比，它在延迟方面也可能具有竞争力。
有趣的事实：clang 自动向量化您的 convert2 / convert3 函数，在 YMM 寄存器中扩大到 8x dword vpmulld（2 微指令），然后是 [= =87=].
策略是使用 pmaddubsw 和 pmaddwd 水平相乘和相加对 ，使每个数字乘以它的方式位值。例如10 和 1 对，然后 100 和 1 来自两位数的整数对。然后提取最后一对的标量：将最重要的部分乘以 100 * 100，然后加上最不重要的部分。我敢肯定，对于实际为 '0'..'9' 的输入，在任何步骤都不可能发生溢出； 运行s 并编译为我预期的 asm，但我没有验证数字结果。
#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
}
On Godbolt 带有一个测试循环，该循环使用 asm("" ::"m"(sink): "memory" ) 让编译器在循环中重做工作。或者 std::atomic_thread_fence(acq_rel) hack 使 MSVC 也不会优化循环。在我的带有 GCC 11.1、x86-64 GNU/Linux、energy_performance_preference = performance、 的 i7-6700k 上，我每 5 个周期迭代一次 运行 。
IDK 为什么它不 运行 每 4c 一个；我调整了 GCC 选项以避免 JCC erratum slowdown 没有填充，并希望在 4 uop 缓存行中有循环。 （6 微指令，1 微指令以 32B 边界结束，6 微指令，2 微指令以 dec/jnz 结束）。性能计数器表示前端“正常”，并且 uops_dispatched_port 显示所有 4 个 ALU 端口每次迭代都不到 4 微指令，最高的是 3.34 的端口 0。
手动填充早期指令将其减少到 3 行，分别为 3、6、6 微指令，但仍然没有比每个迭代器 5c 有任何改进，所以我猜前端真的没问题。
LLVM-MCA 在每个 iter 投影 3c 方面似乎非常雄心勃勃，显然是基于错误的 Skylake 模型，“调度”（我认为是前端重命名）宽度为 6。即使 -mcpu=haswell 使用适当的 4 宽模型，它可以预测 4.5c。 （我在 Godbolt 上使用了 asm("# LLVM-MCA-BEGIN") 等宏，并为测试循环包含了一个 LLVM-MCA 输出 window。）它没有完全准确的 uop-> 端口映射，显然不知道慢- LEA 运行仅在端口 1 上，但如果重要，则 IDK。
吞吐量可能会受到找到指令级并行性和跨多个迭代重叠的能力的限制，如
测试循环是：
#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 支持此循环中的延迟，使用单独的 add 而不是 3 分量 LEA）。
这比 仅 解析 X 的任何标量版本都快，而且它还能解析 HH、MM 和 SS。 尽管 convert3 的 clang 自动矢量化可能会在那个部门给它一个 运行 的钱，但奇怪的是在内联时它不会这样做。
GCC 的标量 convert3 每次迭代需要 8 个周期。 clang 的标量 convert3 在一个循环中需要 7，运行 在 4.0 融合域 uops/clock，最大化前端带宽并使端口 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 输出以评论该指令，所以我知道它仍在执行所有工作。）
这里（而不是前端）存在某种后端瓶颈这一事实可能 好 将其与独立工作重叠。
您不一定需要使用特殊的 SIMD 指令来并行计算。通过使用 64 位无符号整数，我们可以并行处理九个字节中的八个，然后将第九个字节视为末尾的 one-off。
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 毫秒，而所有其他解决方案的基准测试时间恰好为 400 毫秒。这是有道理的，因为它使用了“正常”解决方案所做的大约一半的乘法和加法指令。
我知道 memcpy 看起来很浪费，但它避免了未定义的行为和对齐问题。
#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： 函数可以 return unsigned int 而不是 int（即
unsigned convert1(char *a);
编辑 3： 我注意到新代码是无效的基准，因为 convert(a) 只执行一次。使用原始代码，差异仅~1%。
编辑 4： 新基准。使用 unsigned (convert4u, convert6u) 始终比使用 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 main main.cpp -std=c++17 -O3 -mavx -mavx2 -march=native
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，因此它甚至比基准测试显示的还要快。
备选候选人
使用 unsigned 数学来避免 int 的 UB 溢出并允许将所有 - 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;
}
也尝试像 a[] 一样订购 p[9]。也许更容易并行计算。我认为重新订购没有缺点。
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;
}
是的，如评论中所述，SIMD 是可能的。您可以利用它同时解析字符串的 HH、MM 和 SS 部分。
因为你有一个 100% 固定的格式，必要时前导 0，这比 pcmpistri to look up a shuffle control mask or scale-factor. Also SIMD string to unsigned int parsing in C# performance improvement 有一些好主意，比如调整位值乘数以避免最后的步骤（TODO，在这里做。）
9 个十进制数字分解为两个双字和一个可能最好单独获取的剩余字节。
假设您关心的是吞吐量（将其与周围代码重叠的能力，或者在独立元素的循环中执行此操作的能力），而不是从输入指针和内存中的数据就绪到纳秒整数就绪的周期中的关键路径延迟，SSSE3 SIMD 在现代 x86 上应该非常好。 （如果您想将小时、分钟、秒解压缩为连续的 uint32_t 元素，例如在结构中，SSE4.1 很有用）。与标量相比，它在延迟方面也可能具有竞争力。
有趣的事实：clang 自动向量化您的 convert2 / convert3 函数，在 YMM 寄存器中扩大到 8x dword vpmulld（2 微指令），然后是 [= =87=].
策略是使用 pmaddubsw 和 pmaddwd 水平相乘和相加对 ，使每个数字乘以它的方式位值。例如10 和 1 对，然后 100 和 1 来自两位数的整数对。然后提取最后一对的标量：将最重要的部分乘以 100 * 100，然后加上最不重要的部分。我敢肯定，对于实际为 '0'..'9' 的输入，在任何步骤都不可能发生溢出； 运行s 并编译为我预期的 asm，但我没有验证数字结果。
#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
}
On Godbolt 带有一个测试循环，该循环使用 asm("" ::"m"(sink): "memory" ) 让编译器在循环中重做工作。或者 std::atomic_thread_fence(acq_rel) hack 使 MSVC 也不会优化循环。在我的带有 GCC 11.1、x86-64 GNU/Linux、energy_performance_preference = performance、 的 i7-6700k 上，我每 5 个周期迭代一次 运行 。
IDK 为什么它不 运行 每 4c 一个；我调整了 GCC 选项以避免 JCC erratum slowdown 没有填充，并希望在 4 uop 缓存行中有循环。 （6 微指令，1 微指令以 32B 边界结束，6 微指令，2 微指令以 dec/jnz 结束）。性能计数器表示前端“正常”，并且 uops_dispatched_port 显示所有 4 个 ALU 端口每次迭代都不到 4 微指令，最高的是 3.34 的端口 0。 手动填充早期指令将其减少到 3 行，分别为 3、6、6 微指令，但仍然没有比每个迭代器 5c 有任何改进，所以我猜前端真的没问题。
LLVM-MCA 在每个 iter 投影 3c 方面似乎非常雄心勃勃，显然是基于错误的 Skylake 模型，“调度”（我认为是前端重命名）宽度为 6。即使 -mcpu=haswell 使用适当的 4 宽模型，它可以预测 4.5c。 （我在 Godbolt 上使用了 asm("# LLVM-MCA-BEGIN") 等宏，并为测试循环包含了一个 LLVM-MCA 输出 window。）它没有完全准确的 uop-> 端口映射，显然不知道慢- LEA 运行仅在端口 1 上，但如果重要，则 IDK。
吞吐量可能会受到找到指令级并行性和跨多个迭代重叠的能力的限制，如
测试循环是：
#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 支持此循环中的延迟，使用单独的 add 而不是 3 分量 LEA）。
这比 仅 解析 X 的任何标量版本都快，而且它还能解析 HH、MM 和 SS。 尽管 convert3 的 clang 自动矢量化可能会在那个部门给它一个 运行 的钱，但奇怪的是在内联时它不会这样做。
GCC 的标量 convert3 每次迭代需要 8 个周期。 clang 的标量 convert3 在一个循环中需要 7，运行 在 4.0 融合域 uops/clock，最大化前端带宽并使端口 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 输出以评论该指令，所以我知道它仍在执行所有工作。）
这里（而不是前端）存在某种后端瓶颈这一事实可能 好 将其与独立工作重叠。
您不一定需要使用特殊的 SIMD 指令来并行计算。通过使用 64 位无符号整数，我们可以并行处理九个字节中的八个，然后将第九个字节视为末尾的 one-off。
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 毫秒，而所有其他解决方案的基准测试时间恰好为 400 毫秒。这是有道理的，因为它使用了“正常”解决方案所做的大约一半的乘法和加法指令。
我知道 memcpy 看起来很浪费，但它避免了未定义的行为和对齐问题。