我在哪里可以找到世界上最快的实施方案？

Question

我正在寻找IA32上极其快速的atof()实现,针对US-en语言环境,ASCII和非科学表示法进行了优化.Windows多线程CRT在这里惨败,因为它检查每次调用isdigit()时的语言环境变化.我们目前最好的是源自perl + tcl的最佳实现,并且优于msvcrt.dll的atof一个数量级.我想做得更好,但我没有想法.与BCD相关的x86指令似乎很有希望,但我无法让它超越perl/tcl C代码.任何SO'ers都可以找到最好的链接吗？也欢迎基于非x86组件的解决方案.

根据初步答案澄清:

对于该应用,~2 ulp的不准确性是好的.
要转换的数字将通过网络小批量地到达ascii消息,我们的应用程序需要以尽可能低的延迟转换它们.

Answer 1

你的准确度要求是多少？如果你确实需要它"正确"(总是得到最接近指定十进制的浮点值),它可能很难超越标准库版本(除了删除你已经完成的语言环境支持),因为这需要进行任意精度算术.如果你愿意容忍一个或两个误差(并且超过次正规误),那么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指令尚未在硬件中实现,现在简单地进行了微编码.它们不太可能是特别高性能的.

Answer 2

我刚完成编码的这个实现运行速度是我桌面上内置'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

您也可能对进行转换的状态机感兴趣:

Answer 3

在我看来，你想（手动）构建一个相当于状态机的东西，其中每个状态处理第 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”隐藏在索引偏移中。]

如果做得好，该方案大约对每个非零数字执行一次廉价的乘法加法，一次尾数转换为浮点，以及一次浮点乘法以按指数和小数点位置缩放结果。

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