Google V8 引擎運用了哪些優秀的演算法？

01-15

我來說一個, Grisu3

近月研究過 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 == "" 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. http://kurtstephens.com/files/p372-steele.pdf

[3] Gay, David M. "Correctly rounded binary-decimal and decimal-binary conversions." Numerical Analysis Manuscript 90-10 (1990). http://ampl.com/REFS/rounding.pdf

[4] Burger, Robert G., and R. Kent Dybvig. "Printing floating-point numbers quickly and accurately." ACM SIGPLAN Notices. Vol. 31. No. 5. ACM, 1996. http://www.cs.indiana.edu/~dyb/pubs/FP-Printing-PLDI96.pdf

[5] Loitsch, Florian. "Printing floating-point numbers quickly and accurately with integers." ACM Sigplan Notices 45.6 (2010): 233-243. http://www.cs.tufts.edu/~nr/cs257/archive/florian-loitsch/printf.pdf

-------------------

補充答案：其實正確的dtoa()實現只需要char buffer[26]（包括""）。

再補個圖：測試不同演算法／實現下的性能（VC2013 64-bit），fpconv、grisu2、milo 都是 Grisu2 的實現，doubleconv 是V8 的 Grisu3 實現。milo 對 sprintf 的加速比約是 9x。

Design Elements 關於V8高性能的原因，官網說得挺不錯。

話說Fast Property Access一項其實挺像Python的__slots__，區別在於Python用了__slots__，類就變成了沒法增刪方法的靜態類，而理想的狀況是像V8這樣用靜態類的編譯方法，不用dictionary，但是保留了動態的語義，仍然能增刪方法。沒記錯的話PyPy已經有這項優化了。

字元串匹配用的是 Boyer-Moore-Horspool 演算法 // string-search.h