The fastest double-to-string algorithm you’ve never heard of

你从未听说过的最快 double-to-string 算法

Żmij, the binary-to-decimal conversion library I wrote about a few posts back, started as an optimized port of Schubfach. Later I switched its core to a different algorithm, defined in yy_double.c from yyjson by ibireme. It has no paper, no name beyond the file it lives in (I’ll refer to it as yy), and almost no public profile outside the JSON performance crowd. It also happens to be one of the fastest dtoa implementations. This post is a tour of yy through a small visualization, with a close look at one boundary case.

我在几篇文章前介绍过的二进制转十进制库 Żmij，最初是 Schubfach 算法的一个优化移植版。后来，我将其核心切换为另一种算法，该算法定义在 ibireme 所著 yyjson 库的 yy_double.c 文件中。它没有发表过论文，除了它所在的文件名外没有其他名称（我将其称为 yy），在 JSON 性能圈子之外几乎没有知名度。但它恰好是目前最快的 dtoa（double-to-string）实现之一。本文将通过一个小型的可视化演示来介绍 yy，并深入探讨一个边界情况。

Where yy fits in

yy 的定位

yy is in the Schubfach family. The shared idea, which I covered in an earlier post, is to find the shortest decimal $\sigma \cdot 10^{e_{10}}$ that round-trips back to a binary float $v$ by intersecting $v$‘s rounding interval with decimal grids of various spacings, and picking the coarsest grid that still has a tick in the interval.

yy 属于 Schubfach 家族。我在之前的文章中介绍过，它们的核心思想是一致的：通过将二进制浮点数 $v$ 的舍入区间与不同间距的十进制网格相交，找到能精确还原回 $v$ 的最短十进制表示 $\sigma \cdot 10^{e_{10}}$，并选择其中最粗糙（即位数最少）的网格刻度。

yy’s trick is doing this very cheaply. The whole algorithm runs on fixed-width integer arithmetic and uses only one multiplication by a precomputed power of 10, where classic Schubfach needs two or three.

yy 的诀窍在于以极低的成本完成这一过程。整个算法运行在定宽整数算术上，并且仅使用一次预计算的 10 的幂乘法，而经典的 Schubfach 算法则需要两次或三次。

Four candidates

四个候选值

For each binary float $v = c \cdot 2^{e_2}$, yy picks a decimal exponent $e_{10}$ via a fixed-point approximation of $\log_{10} 2$, then re-expresses $v$ at the decimal scale as $\bar v \approx v \cdot 10^{-e_{10}}$ using a precomputed power-of-10 table $p_{10}$, a fixed-point value with $p_{10} \cdot 2^{e_p} \approx 10^{-e_{10}}$ for some binary exponent $e_p$. $\bar v$ then sits between four candidate decimal values:

对于每个二进制浮点数 $v = c \cdot 2^{e_2}$，yy 通过 $\log_{10} 2$ 的定点近似值选取十进制指数 $e_{10}$，然后利用预计算的 10 的幂表 $p_{10}$（其中 $p_{10} \cdot 2^{e_p} \approx 10^{-e_{10}}$，且 $e_p$ 为某个二进制指数），将 $v$ 在十进制尺度上重新表示为 $\bar v \approx v \cdot 10^{-e_{10}}$。此时，$\bar v$ 位于四个候选十进制值之间：

• $d_1 = \lfloor \bar v \rfloor$ and $u_1 = d_1 + 1$, the integers immediately below and above $\bar v$.

• $d_0 = 10 \cdot \lfloor \bar v / 10 \rfloor$ and $u_0 = d_0 + 10$, the multiples of 10 below and above.

• $d_1 = \lfloor \bar v \rfloor$ 和 $u_1 = d_1 + 1$，即紧邻 $\bar v$ 下方和上方的整数。

• $d_0 = 10 \cdot \lfloor \bar v / 10 \rfloor$ 和 $u_0 = d_0 + 10$，即紧邻 $\bar v$ 下方和上方的 10 的倍数。

Outputting $d_0$ or $u_0$ gives a decimal one digit shorter than $d_1$ or $u_1$, because the trailing zero folds into the exponent. Like classic Schubfach, yy prefers $d_0$ or $u_0$ when they round-trip and falls back to $d_1$ or $u_1$ otherwise.

输出 $d_0$ 或 $u_0$ 会比输出 $d_1$ 或 $u_1$ 少一位十进制数字，因为末尾的零被合并到了指数中。与经典的 Schubfach 一样，yy 在 $d_0$ 或 $u_0$ 能精确还原时优先选择它们，否则回退到 $d_1$ 或 $u_1$。

A boundary case that looks like a bug

一个看起来像 Bug 的边界情况

Set the encoding to 116 in the explorer, or work out $v = 12 \cdot 2^{4} = 192$ by hand. The bits are 0 1110 100, so $c = 12$, $e_2 = 4$, and yy picks $e_{10} = \lfloor 4 \log_{10} 2 \rfloor = 1$, so $\bar v = 192 \cdot 10^{-1} = 19.2$ and the fine-grid fallback is $d_1 = \lfloor \bar v \rfloor = 19$, printed as 19e1. The shorter grid is multiples of $10^{2} = 100$, with $d_0 = 100$ and $u_0 = 200$. If $v$‘s rounding interval reaches $u_0 = 200$, yy can emit the shorter 2e2 instead.

在浏览器中将编码设置为 116，或者手动计算 $v = 12 \cdot 2^{4} = 192$。其位表示为 0 1110 100，因此 $c = 12$，$e_2 = 4$，yy 选取 $e_{10} = \lfloor 4 \log_{10} 2 \rfloor = 1$，得到 $\bar v = 192 \cdot 10^{-1} = 19.2$，细网格回退值为 $d_1 = \lfloor \bar v \rfloor = 19$，输出为 19e1。较粗的网格是 $10^{2} = 100$ 的倍数，即 $d_0 = 100$ 和 $u_0 = 200$。如果 $v$ 的舍入区间触及 $u_0 = 200$，yy 就可以输出更短的 2e2。