在哪里可以找到世界上最快的 atof 实施？
https://stackoverflow.com/questions/98586
-
01-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我正在寻找针对 US-en 语言环境、ASCII 和非科学记数法优化的 IA32 上的极快 atof() 实现。Windows 多线程 CRT 在这里严重失败，因为它在每次调用 isdigit() 时检查区域设置更改。我们当前的最佳方案源自 Perl + tcl 的 atof 实现的最佳方案，并且比 msvcrt.dll 的 atof 实现高出一个数量级。我想做得更好，但没有想法。BCD 相关的 x86 指令似乎很有前途，但我无法让它超越 perl/tcl C 代码。任何SO'ers都可以挖掘出那里最好的链接吗？也欢迎基于非 x86 汇编的解决方案。
根据初步答案进行澄清：
对于此应用来说，~2 ulp 的误差就足够了。
要转换的数字将以小批量的 ascii 消息形式通过网络到达，我们的应用程序需要以尽可能低的延迟来转换它们。
解决方案
您的准确度要求是什么？如果您确实需要它“正确”（始终获取指定的小数点最接近的浮点值），那么可能很难击败标准库版本（除了删除区域设置支持，您已经完成了），因为这需要进行任意精度的算术。如果您愿意容忍一两个 ulp 错误（并且比次正常错误更多），cruzer 提出的那种方法可以工作并且可能更快，但它绝对不会产生 <0.5ulp 输出。您将在精度方面做得更好，分别计算整数和小数部分，并计算最后的分数（例如对于 12345.6789，将其计算为 12345 + 6789 / 10000.0，而不是 6*.1 + 7*.01 + 8*.001 + 9*0.0001)，因为 0.1 是无理二进制分数，当您计算 0.1^ 时，误差会快速累积名词这还允许您使用整数而不是浮点数来完成大部分数学运算。
自 (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
您可能还对执行转换的状态机感兴趣：
我已经实现了一些你可能会觉得有用的东西。与 atof 相比，它的速度大约快 5 倍，如果与 __forceinline 大约快 10 倍。另一个好处是它的算法似乎与 crt 实现完全相同。当然它也有一些缺点：
- 它仅支持单精度浮点数，
- 并且不扫描任何特殊值，例如#INF等...
__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;
}
在我看来，你想（手动）构建一个相当于状态机的东西，其中每个状态处理第 N 个输入数字或指数数字；这个状态机的形状像一棵树（没有循环！）。目标是尽可能进行整数算术，并且（显然）隐式地记住状态中的状态变量（“前导减号”、“位置 3 处的小数点”），以避免分配、存储和稍后获取/测试这些值。仅在输入字符上使用普通的旧“if”语句实现状态机（因此您的树将成为一组嵌套的 if）。对缓冲区字符的内联访问；你不想要一个函数调用 getchar 让你慢下来。
前导零可以简单地被抑制；您可能需要一个循环来处理非常长的前导零序列。无需将累加器归零或乘以十即可收集第一个非零数字。前 4-9 个非零数字（对于 16 位或 32 位整数）可以通过整数乘以常量值 10 来收集（大多数编译器将其转换为一些移位和加法）。[越过高峰：零数字不需要任何工作，直到找到非零数字，然后需要乘以 10^N 来得到 N 个连续的零；您可以将所有这些连接到状态机中]。前 4-9 之后的数字可以使用 32 或 64 位乘法来收集，具体取决于机器的字大小。由于您不关心准确性，因此在收集了 32 或 64 位值后，您可以简单地忽略数字；我猜想，当您有一些固定数量的非零数字时，根据您的应用程序对这些数字的实际操作，您实际上可以停止。数字字符串中的小数点只会导致状态机树中出现分支。该分支知道该点的隐式位置，因此知道稍后如何适当地按十的幂进行缩放。如果您不喜欢此代码的大小，则可以通过努力组合一些状态机子树。
[越过高峰：将整数和小数部分保留为单独的（小）整数。这将需要在最后进行额外的浮点运算来组合整数和小数部分，可能不值得]。
[越过高峰：将数字对的 2 个字符收集为 16 位值，查找 16 位值。这避免了为了内存访问而在寄存器中进行乘法，这在现代机器上可能不是一个胜利]。
遇到“E”时，将指数收集为整数，如上所述；在预先计算的乘数表中查找精确的预先计算/缩放的十的幂（如果指数中存在“-”符号，则为倒数）并乘以收集的尾数。（永远不要进行浮动除法）。由于每个指数收集例程位于树的不同分支（叶）中，因此它必须通过偏移十指数的幂来调整小数点的表观或实际位置。
[越过高峰：您可以避免以下费用 ptr++ 如果您知道数字的字符线性存储在缓冲区中并且不跨越缓冲区边界。在沿着树枝的第 k 个状态中，您可以访问第 k 个字符： *(start+k). 。一个好的编译器通常可以在寻址模式下将“...+k”隐藏在索引偏移中。]
如果做得好，该方案大约对每个非零数字执行一次廉价的乘法加法，一次尾数转换为浮点，以及一次浮点乘法以按指数和小数点位置缩放结果。
我还没有实施上述内容。我已经用循环实现了它的版本，它们非常快。
我记得我们有一个 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，= 0.001，乘以6，获得0.006，添加到跑步总数，使123.456
当然，测试数字和负数的正确性会使事情变得更加复杂。但如果您可以“假设”输入是正确的，则可以使代码变得更简单、更快。
您是否考虑过让 GPU 来完成这项工作？如果您可以将字符串加载到 GPU 内存中并让它处理所有这些字符串，您可能会发现一个好的算法，其运行速度明显快于处理器。
或者，在 FPGA 中执行此操作 - 您可以使用 FPGA PCI-E 板来制作任意协处理器。使用 DMA 将 FPGA 指向包含要转换的字符串数组的内存部分，并让它快速浏览它们，留下转换后的值。
您看过四核处理器吗？无论如何，大多数情况下真正的瓶颈是内存访问......
-亚当
