我试图尽快将十六进制char
转换为整数。
这只是一行:int x = atoi(hex.c_str);
有更快的方法吗?
在这里,我尝试了一种更加动态的方法,而且速度稍快一些。
int hextoint(char number) {
if (number == '0') {
return 0;
}
if (number == '1') {
return 1;
}
if (number == '2') {
return 2;
}
/*
* 3 through 8
*/
if (number == '9') {
return 9;
}
if (number == 'a') {
return 10;
}
if (number == 'b') {
return 11;
}
if (number == 'c') {
return 12;
}
if (number == 'd') {
return 13;
}
if (number == 'e') {
return 14;
}
if (number == 'f') {
return 15;
}
return -1;
}
如果您的输入字符串始终是十六进制数字,则可以将查找表定义为unordered_map
:
std::unordered_map<char, int> table {
{'0', 0}, {'1', 1}, {'2', 2},
{'3', 3}, {'4', 4}, {'5', 5},
{'6', 6}, {'7', 7}, {'8', 8},
{'9', 9}, {'a', 10}, {'A', 10},
{'b', 11}, {'B', 11}, {'c', 12},
{'C', 12}, {'d', 13}, {'D', 13},
{'e', 14}, {'E', 14}, {'f', 15},
{'F', 15}, {'x', 0}, {'X', 0}};
int hextoint(char number) {
return table[(std::size_t)number];
}
constexpr
文字(C ++ 14)或者如果你想要更快的东西而不是unordered_map
,你可以使用具有用户文字类型的新C ++ 14工具,并在编译时将你的表定义为文字类型:
struct Table {
long long tab[128];
constexpr Table() : tab {} {
tab['1'] = 1;
tab['2'] = 2;
tab['3'] = 3;
tab['4'] = 4;
tab['5'] = 5;
tab['6'] = 6;
tab['7'] = 7;
tab['8'] = 8;
tab['9'] = 9;
tab['a'] = 10;
tab['A'] = 10;
tab['b'] = 11;
tab['B'] = 11;
tab['c'] = 12;
tab['C'] = 12;
tab['d'] = 13;
tab['D'] = 13;
tab['e'] = 14;
tab['E'] = 14;
tab['f'] = 15;
tab['F'] = 15;
}
constexpr long long operator[](char const idx) const { return tab[(std::size_t) idx]; }
} constexpr table;
constexpr int hextoint(char number) {
return table[(std::size_t)number];
}
我使用最近在isocpp.org上发布的Nikos Athanasiou编写的代码运行基准测试,作为C ++微基准测试的提议方法。
比较的算法是:
1. OP的原始if-else
:
long long hextoint3(char number) { if(number == '0') return 0; if(number == '1') return 1; if(number == '2') return 2; if(number == '3') return 3; if(number == '4') return 4; if(number == '5') return 5; if(number == '6') return 6; if(number == '7') return 7; if(number == '8') return 8; if(number == '9') return 9; if(number == 'a' || number == 'A') return 10; if(number == 'b' || number == 'B') return 11; if(number == 'c' || number == 'C') return 12; if(number == 'd' || number == 'D') return 13; if(number == 'e' || number == 'E') return 14; if(number == 'f' || number == 'F') return 15; return 0; }
2. Christophe提出的紧凑if-else:
long long hextoint(char number) { if (number >= '0' && number <= '9') return number - '0'; else if (number >= 'a' && number <= 'f') return number - 'a' + 0x0a; else if (number >= 'A' && number <= 'F') return number - 'A' + 0X0a; else return 0; }
3.修正了由g24l提出的处理大写字母输入的三元运算符版本:
long long hextoint(char in) { int const x = in; return (x <= 57)? x - 48 : (x <= 70)? (x - 65) + 0x0a : (x - 97) + 0x0a; }
4.查找表(unordered_map
):
long long hextoint(char number) { return table[(std::size_t)number]; }
其中table
是前面显示的无序地图。
5.查找表(用户constexpr
文字):
long long hextoint(char number) { return table[(std::size_t)number]; }
表是用户定义的文字,如上所示。
实验设置
我定义了一个将输入十六进制字符串转换为整数的函数:
long long hexstrtoint(std::string const &str, long long(*f)(char)) { long long ret = 0; for(int j(1), i(str.size() - 1); i >= 0; --i, j *= 16) { ret += (j * f(str[i])); } return ret; }
我还定义了一个用随机十六进制字符串填充字符串向量的函数:
std::vector<std::string> populate_vec(int const N) { random_device rd; mt19937 eng{ rd() }; uniform_int_distribution<long long> distr(0, std::numeric_limits<long long>::max() - 1); std::vector<std::string> out(N); for(int i(0); i < N; ++i) { out[i] = int_to_hex(distr(eng)); } return out; }
我创建了分别填充50000,100000,150000,200000和250000随机十六进制字符串的向量。然后,对于每个算法,我运行100个实验并平均时间结果。
编译器是GCC 5.2版,带有优化选项-O3
。
结果:
讨论
从结果我们可以得出结论,对于这些实验设置,建议的表方法优于所有其他方法。 if-else方法到目前为止是最糟糕的,因为unordered_map
虽然赢得了if-else方法,但它明显慢于其他提议的方法。
stgatilov提出的方法的结果,按位运算:
long long hextoint(char x) { int b = uint8_t(x); int maskLetter = (('9' - b) >> 31); int maskSmall = (('Z' - b) >> 31); int offset = '0' + (maskLetter & int('A' - '0' - 10)) + (maskSmall & int('a' - 'A')); return b - offset; }
编辑:
我还针对table方法测试了g24l的原始代码:
long long hextoint(char in) { long long const x = in; return x < 58? x - 48 : x - 87; }
请注意,此方法不处理大写字母A
,B
,C
,D
,E
和F
。
结果:
表格方法仍然更快。
对于不同的系统,这个问题显然可能有不同的答案,从这个意义上讲,它从一开始就是不适合的。例如,i486没有管道,奔腾没有SSE。
要问的正确问题是:“在X系统中将单个字符十六进制转换为dec的最快方法是什么,例如i686”。
在这里的方法中,对于具有多级流水线的系统,其答案实际上是相同或非常非常非常相同。任何没有管道的系统都会向查找表方法(LUT)弯曲,但如果内存访问速度慢,则条件方法(CEV)或按位评估方法(BEV)可能会受益于xor与负载的速度。给定CPU。
(CEV)将寄存器which is not prone to mis-prediction分解为2个加载有效地址进行比较和条件移动。所有这些命令在奔腾管道中都是可配对的。所以他们实际上进入了一个周期。
8d 57 d0 lea -0x30(%rdi),%edx
83 ff 39 cmp $0x39,%edi
8d 47 a9 lea -0x57(%rdi),%eax
0f 4e c2 cmovle %edx,%eax
(LUT)分解为寄存器之间的mov和来自数据相关存储器位置的mov以及用于对齐的一些nops,并且应该采用最小的1个周期。如前所述,只有数据依赖。
48 63 ff movslq %edi,%rdi
8b 04 bd 00 1d 40 00 mov 0x401d00(,%rdi,4),%eax
(BEV)是一个不同的野兽,因为它实际上需要2个mov + 2个xors + 1和一个条件mov。这些也可以很好地流水线化。
89 fa mov %edi,%edx
89 f8 mov %edi,%eax
83 f2 57 xor $0x57,%edx
83 f0 30 xor $0x30,%eax
83 e7 40 and $0x40,%edi
0f 45 c2 cmovne %edx,%eax
当然,这是一个非常罕见的场合,应用程序关键(可能是Mars Pathfinder是一个候选者)只转换一个信号char。相反,人们会期望通过实际制作循环并调用该函数来转换更大的字符串。
因此,在这种情况下,更好的可矢量化的代码是胜利者。 LUT没有矢量化,BEV和CEV具有更好的行为。一般来说,这样的微优化不会让你到任何地方,编写代码并让实时(即让编译器运行)。
所以我实际上已经在这个意义上构建了一些测试,它们可以在任何具有c ++ 11编译器和随机设备源的系统上轻松重现,例如任何* nix系统。如果一个人不允许矢量化-O2
CEV / LUT几乎相等,但是一旦设置了-O3
,编写更易分解的代码的优势就显示出差异。
总而言之,如果你有一个旧的编译器使用LUT,如果你的系统是低端或旧的考虑BEV,否则编译器将超越你,你应该使用CEV。
问题:问题是从字符集{0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f}转换为{的集合0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}。没有正在考虑的大写字母。
我们的想法是利用分段中ascii表的线性度。
[简单易行]:条件评估 - > CEV
int decfromhex(int const x)
{
return x<58?x-48:x-87;
}
[脏和复杂]:按位评估 - > BEV
int decfromhex(int const x)
{
return 9*(x&16)+( x & 0xf );
}
[编译时间]:模板条件评估 - > TCV
template<char n> int decfromhex()
{
int constexpr x = n;
return x<58 ? x-48 : x -87;
}
[查找表]:查找表 - > LUT
int decfromhex(char n)
{
static int constexpr x[255]={
// fill everything with invalid, e.g. -1 except places\
// 48-57 and 97-102 where you place 0..15
};
return x[n];
}
其中,最后看起来似乎是最快的。第二个是仅在编译时和常量表达式。
[结果](请确认):* BEV是最快的,处理大小写字母,但仅限于不处理大写字母的CEV。随着字符串大小的增加,LUT变得比CEV和BEV都慢。
str-size 16-12384的示例性结果可以在下面找到(越低越好)
显示平均时间(100次运行)。气泡的大小是正常的误差。
The script for running the tests is available.
已经在一组随机生成的字符串上对conditional
CEV,bitwise
BEV和lookup table
LUT进行了测试。测试相当简单,来自:
这些是可以验证的:
g++ -std=c++11 -O3 -march=native dectohex.cpp -o d2h
进行编译taskset -c 0 d2h
一起发布作为附注,我在练习版本3中看到使用较旧的c ++ 98编译器要快得多。
[BOTTOM LINE]:毫无顾虑地使用CEV,除非您在编译时知道您的变量,您可以使用版本TCV。只有在每个用例评估的重要性能之后才能使用LUT,并且可能在较旧的编译器之后使用。另一种情况是你的集合较大,即{0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f,A,B,C,D, E,F}。这也可以实现。最后,如果你是饥肠辘辘,请使用BEV。
unordered_map的结果已被删除,因为它们太慢而无法比较,或者最好的情况可能与LUT解决方案一样快。
我的个人电脑上的字符串大小为12384/256和100个字符串的结果:
g++ -DS=2 -DSTR_SIZE=256 -DSET_SIZE=100 -DUNITS=nanoseconds -O3 -std=c++11 -march=native dectohex.cpp -o d2h && taskset -c 0 ./d2h
sign: -2709
-------------------------------------------------------------------
(CEV) Total: 185568 nanoseconds - mean: 323.98 nanoseconds error: 88.2699 nanoseconds
(BEV) Total: 185568 nanoseconds - mean: 337.68 nanoseconds error: 113.784 nanoseconds
(LUT) Total: 229612 nanoseconds - mean: 667.89 nanoseconds error: 441.824 nanoseconds
-------------------------------------------------------------------
g++ -DS=2 -DSTR_SIZE=12384 -DSET_SIZE=100 -DUNITS=nanoseconds -O3 -std=c++11 -march=native hextodec.cpp -o d2h && taskset -c 0 ./h2d
-------------------------------------------------------------------
(CEV) Total: 5539902 nanoseconds - mean: 6229.1 nanoseconds error: 1052.45 nanoseconds
(BEV) Total: 5539902 nanoseconds - mean: 5911.64 nanoseconds error: 1547.27 nanoseconds
(LUT) Total: 6346209 nanoseconds - mean: 14384.6 nanoseconds error: 1795.71 nanoseconds
-------------------------------------------------------------------
Precision: 1 ns
将GCC 4.9.3系统的结果编译为金属而不将系统加载到大小为256/12384的字符串和100个字符串上
g++ -DS=2 -DSTR_SIZE=256 -DSET_SIZE=100 -DUNITS=nanoseconds -O3 -std=c++11 -march=native dectohex.cpp -o d2h && taskset -c 0 ./d2h
sign: -2882
-------------------------------------------------------------------
(CEV) Total: 237449 nanoseconds - mean: 444.17 nanoseconds error: 117.337 nanoseconds
(BEV) Total: 237449 nanoseconds - mean: 413.59 nanoseconds error: 109.973 nanoseconds
(LUT) Total: 262469 nanoseconds - mean: 731.61 nanoseconds error: 11.7507 nanoseconds
-------------------------------------------------------------------
Precision: 1 ns
g++ -DS=2 -DSTR_SIZE=12384 -DSET_SIZE=100 -DUNITS=nanoseconds -O3 -std=c++11 -march=native dectohex.cpp -o d2h && taskset -c 0 ./d2h
sign: -137532
-------------------------------------------------------------------
(CEV) Total: 6834796 nanoseconds - mean: 9138.93 nanoseconds error: 144.134 nanoseconds
(BEV) Total: 6834796 nanoseconds - mean: 8588.37 nanoseconds error: 4479.47 nanoseconds
(LUT) Total: 8395700 nanoseconds - mean: 24171.1 nanoseconds error: 1600.46 nanoseconds
-------------------------------------------------------------------
Precision: 1 ns
[如何阅读结果]
平均值显示在计算给定大小的字符串所需的微秒上。
给出每次测试的总时间。均值计算为计算一个字符串的时间总和/总数(该区域中没有其他代码但可以进行矢量化,这没关系)。误差是时间的标准偏差。
平均值告诉我们平均应该得到什么,以及错误在正常情况下的时间。在这种情况下,只有当它很小时,这才是公平的误差测量(否则我们应该使用适合于正分布的东西)。在高速缓存未命中,处理器调度和许多其他因素的情况下,通常应该期望高错误。
代码有一个唯一的宏定义为运行测试,允许定义编译时变量来设置测试,并打印完整的信息,如:
g++ -DS=2 -DSTR_SIZE=64 -DSET_SIZE=1000 -DUNITS=nanoseconds -O3 -std=c++11 -march=native dectohex.cpp -o d2h && taskset -c 0 ./d2h
sign: -6935
-------------------------------------------------------------------
(CEV) Total: 947378 nanoseconds - mean: 300.871 nanoseconds error: 442.644 nanoseconds
(BEV) Total: 947378 nanoseconds - mean: 277.866 nanoseconds error: 43.7235 nanoseconds
(LUT) Total: 1040307 nanoseconds - mean: 375.877 nanoseconds error: 14.5706 nanoseconds
-------------------------------------------------------------------
例如,使用2sec
暂停在大小为256
的大小为10000
的不同字符串,double precision
中的输出时间和nanoseconds
中的计数运行测试,以下命令编译并运行测试。
g++ -DS=2 -DSTR_SIZE=256 -DSET_SIZE=10000 -DUTYPE=double -DUNITS=nanoseconds -O3 -std=c++11 -march=native dectohex.cpp -o d2h && taskset -c 0 ./d2h
嗯,这是一个奇怪的问题。将单个十六进制字符转换为整数是如此之快,以至于很难判断哪个更快,因为所有方法几乎可能比您编写的代码更快以便使用它们=)
我会假设以下事项:
eax
。现在有几种解决问题的方法:第一种基于查找,第二种基于三元运算符,最后一种基于位运算:
int hextoint_lut(char x) {
static char lut[256] = {???};
return lut[uint8_t(x)];
}
int hextoint_cond(char x) {
uint32_t dig = x - '0';
uint32_t alp = dig + ('0' - 'a' + 10);
return dig <= 9U ? dig : alp;
}
int hextoint_cond2(char x) {
uint32_t offset = (uint8_t(x) <= uint8_t('9') ? '0' : 'a' - 10);
return uint8_t(x) - offset;
}
int hextoint_bit(char x) {
int b = uint8_t(x);
int mask = (('9' - b) >> 31);
int offset = '0' + (mask & int('a' - '0' - 10));
return b - offset;
}
以下是生成的相应装配清单(仅显示相关部件):
;hextoint_lut;
movsx eax, BYTE PTR [rax+rcx] ; just load the byte =)
;hextoint_cond;
sub edx, 48 ; subtract '0'
cmp edx, 9 ; compare to '9'
lea eax, DWORD PTR [rdx-39] ; add ('0' - 'a' + 10)
cmovbe eax, edx ; choose between two cases in branchless way
;hextoint_cond2; ; (modified slightly)
mov eax, 48
mov edx, 87 ; set two offsets to registers
cmp ecx, 57 ; compare with '9'
cmovbe edx, eax ; choose one offset
sub ecx, edx ; subtract the offset
;hextoint_bit;
mov ecx, 57 ; load '9'
sub ecx, eax ; get '9' - x
sar ecx, 31 ; convert to mask if negative
and ecx, 39 ; set to 39 (for x > '9')
sub eax, ecx ; subtract 39 or 0
sub eax, 48 ; subtract '0'
我将尝试估算吞吐量意义上每种方法所采用的周期数,这实质上是一次处理大量数字时每一个输入数所花费的时间。以Sandy Bridge架构为例。
hextoint_lut
函数由单个内存加载组成,在端口2或3上占用1个uop。这两个端口都专用于内存加载,并且它们内部也有地址计算,能够执行rax+rcx
而无需额外成本。有两个这样的端口,每个端口可以在一个周期内做一个uop。所以据说这个版本需要0.5个时钟。如果我们必须从内存加载输入数,那么每个值需要多一个内存负载,因此总成本为1个时钟。
hextoint_cond
版本有4个指令,但cmov
分为两个单独的uop。因此总共有5个uop,每个都可以在三个算术端口0,1和5中的任何一个上进行处理。因此可能需要5/3个周期时间。请注意,内存加载端口是空闲的,因此即使您必须从内存加载输入值,时间也不会增加。
hextoint_cond2
版本有5条指令。但是在紧密循环中,常量可以预加载到寄存器,因此只有比较,cmov和减法。它们总共为4个uop,每个值提供4/3个周期(即使读取内存)。
hextoint_bit
版本是一个保证没有分支和查找的解决方案,如果你不想总是检查你的编译器是否生成了cmov指令,这是很方便的。第一个mov是自由的,因为常量可以在紧密循环中预加载。其余的是5个算术指令,在端口0,1,5中有5个uop。因此它应该需要5/3个周期(即使存储器读取)。
我已经为上述C ++函数执行了基准测试。在基准测试中,生成64 KB的随机数据,然后每个函数在此数据上运行多次。所有结果都添加到校验和中,以确保编译器不会删除代码。使用手动8x展开。我在Ivy Bridge 3.4 Ghz核心上进行了测试,这与Sandy Bridge非常相似。每个输出字符串包含:函数名称,基准测试所用的总时间,每个输入值的周期数,所有输出的总和。
MSVC2013 x64 /O2:
hextoint_lut: 0.741 sec, 1.2 cycles (check: -1022918656)
hextoint_cond: 1.925 sec, 3.0 cycles (check: -1022918656)
hextoint_cond2: 1.660 sec, 2.6 cycles (check: -1022918656)
hextoint_bit: 1.400 sec, 2.2 cycles (check: -1022918656)
GCC 4.8.3 x64 -O3 -fno-tree-vectorize
hextoint_lut: 0.702 sec, 1.1 cycles (check: -1114112000)
hextoint_cond: 1.513 sec, 2.4 cycles (check: -1114112000)
hextoint_cond2: 2.543 sec, 4.0 cycles (check: -1114112000)
hextoint_bit: 1.544 sec, 2.4 cycles (check: -1114112000)
GCC 4.8.3 x64 -O3
hextoint_lut: 0.702 sec, 1.1 cycles (check: -1114112000)
hextoint_cond: 0.717 sec, 1.1 cycles (check: -1114112000)
hextoint_cond2: 0.468 sec, 0.7 cycles (check: -1114112000)
hextoint_bit: 0.577 sec, 0.9 cycles (check: -1114112000)
显然,LUT方法每个值需要一个周期(如预测的那样)。其他方法通常需要每个值2.2到2.6个周期。在GCC的情况下,hextoint_cond2
很慢,因为编译器使用cmp + sbb +和magic而不是所需的cmov指令。另请注意,默认情况下,GCC会对大多数方法进行矢量化(最后一段),这提供了比不可归一化的LUT方法更快的结果。请注意,手动矢量化会提供更大的提升。
请注意,hextoint_cond
与普通条件跳转而不是cmov
将有一个分支。假设随机输入十六进制数字,它几乎总是会被错误预测。因此,我认为表现会很糟糕。
我已经分析了吞吐量性能。但是如果我们必须处理大量的输入值,那么我们肯定应该对转换进行矢量化以获得更好的速度。 hextoint_cond
可以用SSE以非常直接的方式进行矢量化。它允许仅使用4条指令处理16个字节到16个字节,我认为大约需要2个周期。
请注意,为了查看性能差异,必须确保所有输入值都适合缓存(L1是最佳情况)。如果你从主存储器读取输入数据,即使std::atoi
与所考虑的方法同样快=)
此外,您应该将主循环展开4x甚至8x以获得最佳性能(以消除循环开销)。您可能已经注意到,两种方法的速度在很大程度上取决于代码周围的操作。例如。添加内存负载会使第一种方法花费的时间加倍,但不会影响其他方法。
附:很可能你真的不需要优化它。
假设你的函数被调用一个有效的十六进制数字,它将平均花费至少8个比较操作(和perhap的7次跳转)。很贵。
另一种选择是更紧凑:
if (number >= '0' && number<='9')
return number-'0';
else if (number >= 'a' && number <='f')
return number-'a'+0x0a;
else return -1;
另一个替代方案是使用查找表(交易空间与速度),您只需初始化一次,然后直接访问:
if (number>=0)
return mytable[number];
else return -1;
如果你想一次转换多个数字,你可以看看this question)
编辑:基准
根据Ike的观察,我写了一个小的非正式基准(这里有online),你可以在你最喜欢的编译器上运行。
结论:
这是我最喜欢的hex-to-int代码:
inline int htoi(int x) {
return 9 * (x >> 6) + (x & 017);
}
它对字母不区分大小写,即返回“a”和“A”的正确结果。
如果您(或其他人)实际上正在转换值数组,我制作了一个AVX2 SIMD编码器和解码器,其基准测试速度比最快的标量实现快12倍:https://github.com/zbjornson/fast-hex
16个十六进制值可方便地(两次)放入YMM寄存器,因此您可以使用PSHUFB
进行并行查找。解码有点困难,基于逐位操作。