首页 / 知识

关于c ++：在哪里可以找到世界上最快的atof实现？

2023-04-17 12:17:00

Where can I find the world's fastest atof implementation?

我正在寻找针对美国语言环境，ASCII和非科学符号进行了优化的IA32上极其快速的atof()实现。 Windows多线程CRT在此痛苦地崩溃，因为它在每次调用isdigit()时检查区域设置的更改。我们目前的最佳表现来自于perl + tcl的atof实现的最佳表现，并且比msvcrt.dll的atof表现高出一个数量级。我想做得更好，但是没有主意。与BCD相关的x86指令似乎很有希望，但我无法胜过perl / tcl C代码。任何SO's员工都能挖掘出与最佳人才的联系吗？也欢迎非基于x86程序集的解决方案。

根据初步答案作出的澄清：

约2 ulp的误差对此应用程序很好。
要转换的数字将以小批量的形式通过网络以ascii消息的形式到达，我们的应用程序需要以尽可能低的延迟来转换它们。

您的准确性要求是什么？如果您真正需要它"正确"(总是获得最接近指定小数点的浮点值)，则可能很难击败标准库版本(除了删除已经支持的语言环境之外)，因为这需要进行任意精度的算术运算。如果您愿意容忍一个或两个错误(并且超过次标准错误的容忍度)，那么cruzer提出的这种方法可以行得通，并且可能会更快，但绝对不会产生<0.5ulp的输出。您将在精度方面做得更好，分别计算整数和小数部分，并在末尾计算分数(例如，对于12345.6789，将其计算为12345 + 6789 / 10000.0，而不是6 * .1 + 7 * .01 + 8 * .001 + 9 * 0.0001)，因为0.1是不合理的二进制分数，并且当您计算0.1 ^ n时，误差会迅速累积。这也使您可以使用整数而不是浮点数来进行大多数数学运算。

自(IIRC)286起，BCD指令就尚未在硬件中实现，如今已被微码化。它们不太可能具有很高的性能。

我刚刚完成编码的此实现的运行速度是台式机上内置的" atof"的两倍。它可以在2秒内转换1024 * 1024 * 39个数字输入，而与我系统的标准gnu'atof'相比则是4秒。 (包括设置时间和获取内存等)。

更新：
抱歉，我必须撤销两倍于我的快速索偿。如果要转换的内容已经在字符串中，则速度会更快，但是如果将其传递给硬编码的字符串文字，则它与atof几乎相同。但是，我将其保留在此处，因为可能需要对ragel文件和状态机进行一些调整，因此您可能能够为特定目的生成更快的代码。

https://github.com/matiu2/yajp

有趣的文件是：

https://github.com/matiu2/yajp/blob/master/tests/test_number.cpp

https://github.com/matiu2/yajp/blob/master/number.hpp

另外，您可能对执行转换的状态机感兴趣：

Number parsing state machine diagram

在我看来，您想要手动构建一个状态机，其中每个状态都处理第N个输入数字或指数数字。这个状态机的形状像一棵树(没有循环！)。目标是在可能的情况下进行整数算术，并且(显然)要隐式记住状态中的状态变量("前导负号"，"位置3的小数点")，以避免赋值，存储和以后取回/测试这些值。仅在输入字符上使用普通的旧" if"语句实现状态机(这样，您的树将成为一组嵌套的ifs)。内联访问缓冲区字符；您不希望对getchar进行函数调用来降低速度。

可以简单地抑制前导零。您可能需要在此处循环以处理可笑的长前导零序列。可以在不将累加器置零或乘以十的情况下收集第一个非零数字。前4-9个非零数字(对于16位或32位整数)可以用整数乘以常数10(由大多数编译器转换为几个移位和加法)来收集。 [最重要的是：零数字不需要任何工作，直到找到一个非零数字，然后需要对N个连续零乘以10 ^ N；您可以将所有这些连接到状态机]。根据您计算机字的大小，可以使用32或64位乘法来收集前4-9之后的数字。由于您不关心准确性，因此在收集了32或64位的值之后，您就可以简单地忽略数字。我猜想，当您有固定数量的非零数字时，实际上可以停止运行，具体取决于您的应用程序对这些数字的实际处理方式。在数字字符串中找到一个小数点只会在状态机树中引起一个分支。该分支知道该点的隐式位置，因此知道以后如何按十的幂进行缩放。如果您不喜欢此代码的大小，则可以轻松地组合一些状态机子树。

[在顶部：将整数和小数部分保留为单独的(小)整数。这将需要在末尾进行额外的浮点运算以将整数部分和小数部分组合在一起，这可能不值得]。

[在顶部：将数字对的2个字符收集到一个16位值中，查找16位值。
这避免了在存储器访问权交易中增加寄存器，这在现代机器上可能不是胜利。

遇到" E"时，如上收集指数作为整数；在一个预先计算的乘数表中精确地查找预先计算的/按比例缩放的10的幂(如果指数中存在"-"号，则为倒数)，然后将所收集的尾数相乘。 (永远不要进行浮点分隔)。由于每个指数采集例程位于树的不同分支(叶)中，因此它必须通过抵消十索引的幂来调整小数点的表观或实际位置。

[最重要的是：如果知道数字的字符线性存储在缓冲区中并且没有越过缓冲区边界，则可以避免ptr++的开销。在沿着树枝的第k个状态下，您可以将第k个字符作为*(start+k)访问。一个好的编译器通常可以在寻址模式下以索引偏移量隐藏" ... + k"。]

如果做得正确，此方案将对每个非零数字进行一次廉价的乘法加法，对尾数进行一次强制转换为浮点运算，并进行一次浮点乘法以按指数和小数点位置缩放结果。

我还没有实现以上。我已经用循环实现了它的版本，它们非常快。

我已经实施了一些您可能会觉得有用的东西。
与atof相比，它的速度快了大约x5，如果与__forceinline一起使用，则大约快了x10。
另一件好事是，它接缝的算法与crt实现完全相同。
当然，它也有一些缺点：

它仅支持单精度浮点数，
并且不扫描任何特殊值，例如#INF等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203

__forceinline bool float_scan(const wchar_t* wcs, float* val)
{
int hdr=0;
while (wcs[hdr]==L' ')
hdr++;

int cur=hdr;

bool negative=false;
bool has_sign=false;

if (wcs[cur]==L'+' || wcs[cur]==L'-')
{
if (wcs[cur]==L'-')
negative=true;
has_sign=true;
cur++;
}
else
has_sign=false;

int quot_digs=0;
int frac_digs=0;

bool full=false;

wchar_t period=0;
int binexp=0;
int decexp=0;
unsigned long value=0;

while (wcs[cur]>=L'0' && wcs[cur]<=L'9')
{
if (!full)
{
if (value>=0x19999999 && wcs[cur]-L'0'>5 || value>0x19999999)
{
full=true;
decexp++;
}
else
value=value*10+wcs[cur]-L'0';
}
else
decexp++;

quot_digs++;
cur++;
}

if (wcs[cur]==L'.' || wcs[cur]==L',')
{
period=wcs[cur];
cur++;

while (wcs[cur]>=L'0' && wcs[cur]<=L'9')
{
if (!full)
{
if (value>=0x19999999 && wcs[cur]-L'0'>5 || value>0x19999999)
full=true;
else
{
decexp--;
value=value*10+wcs[cur]-L'0';
}
}

frac_digs++;
cur++;
}
}

if (!quot_digs && !frac_digs)
return false;

wchar_t exp_char=0;

int decexp2=0; // explicit exponent
bool exp_negative=false;
bool has_expsign=false;
int exp_digs=0;

// even if value is 0, we still need to eat exponent chars
if (wcs[cur]==L'e' || wcs[cur]==L'E')
{
exp_char=wcs[cur];
cur++;

if (wcs[cur]==L'+' || wcs[cur]==L'-')
{
has_expsign=true;
if (wcs[cur]=='-')
exp_negative=true;
cur++;
}

while (wcs[cur]>=L'0' && wcs[cur]<=L'9')
{
if (decexp2>=0x19999999)
return false;
decexp2=10*decexp2+wcs[cur]-L'0';
exp_digs++;
cur++;
}

if (exp_negative)
decexp-=decexp2;
else
decexp+=decexp2;
}

// end of wcs scan, cur contains value's tail

if (value)
{
while (value<=0x19999999)
{
decexp--;
value=value*10;
}

if (decexp)
{
// ensure 1bit space for mul by something lower than 2.0
if (value&0x80000000)
{
value>>=1;
binexp++;
}

if (decexp>308 || decexp<-307)
return false;

// convert exp from 10 to 2 (using FPU)
int E;
double v=pow(10.0,decexp);
double m=frexp(v,&E);
m=2.0*m;
E--;
value=(unsigned long)floor(value*m);

binexp+=E;
}

binexp+=23; // rebase exponent to 23bits of mantisa

// so the value is: +/- VALUE * pow(2,BINEXP);
// (normalize manthisa to 24bits, update exponent)
while (value&0xFE000000)
{
value>>=1;
binexp++;
}
if (value&0x01000000)
{
if (value&1)
value++;
value>>=1;
binexp++;
if (value&0x01000000)
{
value>>=1;
binexp++;
}
}

while (!(value&0x00800000))
{
value<<=1;
binexp--;
}

if (binexp<-127)
{
// underflow
value=0;
binexp=-127;
}
else
if (binexp>128)
return false;

//exclude"implicit 1"
value&=0x007FFFFF;

// encode exponent
unsigned long exponent=(binexp+127)<<23;
value |= exponent;
}

// encode sign
unsigned long sign=negative<<31;
value |= sign;

if (val)
{
*(unsigned long*)val=value;
}

return true;
}

我记得我们有一个Winforms应用程序，它在解析某些数据交换文件时执行得如此缓慢，我们都认为这是数据库服务器的崩溃，但是我们的老大实际上发现瓶颈在于将解析后的字符串转换为小数点！

最简单的方法是为字符串中的每个数字(字符)循环，保持连续的总数，将总数乘以10，然后加上下一个数字的值。继续这样做，直到到达字符串的末尾或遇到一个点。如果遇到点，则将整数部分与小数部分分开，然后使用乘数将其自身除以每个数字10。继续添加它们。

示例：123.456

跑步总数= 0，加1(现在是1)
总计= 1 * 10 = 10，加2(现在是12)
运行总计= 12 * 10 = 120，加3(现在是123)
遇到一个点，准备小数部分
乘数= 0.1，乘以4，得到0.4，将总和相加，得出123.4
乘数= 0.1 / 10 = 0.01，乘以5，得出0.05，将总和相加，得出123.45
乘数= 0.01 / 10 = 0.001，乘以6，得到0.006，加到运行总计中，得出123.456

当然，测试一个数字的正确性以及负数将使它更加复杂。但是，如果您可以"假设"输入正确，则可以使代码更加简单和快捷。

您是否考虑过让GPU完成这项工作？如果您可以将字符串加载到GPU内存中并对其进行处理，那么您可能会发现一种好的算法，其运行速度将比处理器快得多。

或者，在FPGA中进行操作-有一些FPGA PCI-E板可用于制造任意协处理器。使用DMA将FPGA指向包含您要转换的字符串数组的内存部分，并使其通过它们，从而将转换后的值抛在后面。

您是否看过四核处理器？在大多数情况下，真正的瓶颈是内存访问。

-亚当

优化美国语言环境崩溃