Google V8 引擎运用了哪些优秀的算法?

我来说一个, Grisu3
关注者
1,432
被浏览
34,399
收录于 编辑推荐 ·
近月研究过 Grisu,就在这里简单说两句。

Grisu 是把浮点数转换为字符串的算法。在Chrome里执行这段Javascript实际上就调用了Grisu。

document.write(1/3); // 0.3333333333333333

这个问题看似简单,实际上是很复杂的事情。

在1980年之前,许多C语言标准库中的 printf() 都会产生「不正确」的结果。Coonen在那时候做了相关的博士研究[1],但并没有受到广泛的知悉和应用。1990年Steele等人发表了名为Dragon4的算法[2],通过使用大数运算来确保精确的转换。而这个算法应用在大部分C程序语言库的 printf(),以及其他用 printf() 来实现这功能的语言之中。

这样就20年过去,虽然中间有一些小改进[3][4],但基本的思路仍然是这样。到了2010年,Loitsch发表了Grisu算法[5],而V8也实现了这个算法。

该篇文章阐述了3个算法,分别是原始的Grisu,及其改进版Grisu2和Grisu3。Grisu算法比Dragon4等算法优越的地方就是一个字──快。以下简单介绍一下它们的特点。

首先,什么是「正确」的转换?其定义是,一个浮点数转换成的十进位字符串之后,该字符串可以完美的转换回去原来的浮点数,如果用C语言来描述的话:

// 除+/-inf及NaN外的浮点数都应该传回true。
bool Verify(double d) {
    assert(!isnan(d) && !isinf(d));
    char buffer[32]; // 足够大么?
    dtoa(buffer, d); // 双精度浮点数转换至字符串,是double-to-ascii,不是dota
    char* end;
    double d2 = strtod(buffer, &end); // 字符串转换至双精度浮点数
    return *end == '\0' && d == d2;
}

如前所述,Dragon4使用大数运算,还涉及动态内存分配(你知道printf()里可能会做malloc()么?)。而Grisu则不需要,只需要用到64位整数运算便可以实现转换!所以那篇文章题目就以"... with integers"作结尾。

Grisu 的算法非常简单,但它有一个缺点,就是其结果并不像是给人看的。如文中的例子,Grisu 把 0.3 的打印成 29999999999999998e-17。这是「正确的」转换结果,它可以通过 Verify() 验证。

虽然该算法非常快,但一般人大概不会接受这样的结果。作者也因此研发出改进版本Grisu2,在使用64位整数实现 double 的转换时,可以利用额外的 64 - 53 = 11 位去缩减转换的结果(53为double的尾数位数)。Grisu2可以把>99.9%的浮点数转换成最短的「正确」字符串,其馀<0.1%的浮点数仍然是「正确」的,但不是最短的答案。

也许一般人就见好就收了,不竟已证明算法的正确性,只是有那么<0.1%情况未达至最完美的结果。不过该作者还是继续研究出 Grisu3。Grisu3并不能解决那一小撮麻烦制造者,但它能在计算期间侦查到哪些 double 在这算法中未能得出最优的结果。既然办事快捷的小部门搞不定,就可以把它交给Dragon4或其他较慢的算法。

V8 里实现了 Grisu3 以及大整数的算法(我不肯定是Dragon4还是其他),后来Google也把它分离成为一个独立的C++程序库 http://code.google.com/p/double-conversion/

为了优化 RapidJSON (miloyip/rapidjson 路 GitHub) 的浮点数转换,也由于 RapidJSON 是仅需头文件的JSON库,我就按 Loitsch 的实现编写了一个 Grisu2 的头文件库,可以在 miloyip/dtoa-benchmark · GitHub 取得,那里还比较了多个 dtoa() 实现的性能。因为 Grisu3 需要另一个更庞大的大数实现,而暂时 RapidJSON 不需要最优结果,所以就仅实现了一个性能更好及更简短的 Grisu2。

加入了 Grisu2 之后,RapidJSON 的 JSON 字符串化(stringify)性能远超其他 JSON 库。没想到读到最后是广告吧。

[1] Coonen, Jerome T. "an Implementation Guide to a Proposed Standard for Floating-Point Arithmetic." Computer 13.1 (1980): 68-79.
[2] Steele Jr, Guy L., and Jon L. White. "How to print floating-point numbers accurately." ACM SIGPLAN Notices. Vol. 25. No. 6. ACM, 1990. kurtstephens.com/files/
[3] Gay, David M. "Correctly rounded binary-decimal and decimal-binary conversions." Numerical Analysis Manuscript 90-10 (1990). ampl.com/REFS/rounding.
[4] Burger, Robert G., and R. Kent Dybvig. "Printing floating-point numbers quickly and accurately." ACM SIGPLAN Notices. Vol. 31. No. 5. ACM, 1996. cs.indiana.edu/~dyb/pub
[5] Loitsch, Florian. "Printing floating-point numbers quickly and accurately with integers." ACM Sigplan Notices 45.6 (2010): 233-243. cs.tufts.edu/~nr/cs257/

-------------------
补充答案:其实正确的dtoa()实现只需要char buffer[26](包括'\0')。
再补个图:测试不同算法/实现下的性能(VC2013 64-bit),fpconv、grisu2、milo 都是 Grisu2 的实现,doubleconv 是V8 的 Grisu3 实现。milo 对 sprintf 的加速比约是 9x。