Google V8 引擎运用了哪些优秀的算法？ - Milo Yip 的回答 - 知乎

Google V8 引擎运用了哪些优秀的算法？ - Milo Yip 的回答 - 知乎

在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 库。没想到读到最后是广告吧。

Read full article from Google V8 引擎运用了哪些优秀的算法？ - Milo Yip 的回答 - 知乎