整数转字符串（2014）

# 整数转字符串 —— L. Pereira 的博客 来源: https://tia.mat.br/posts/2014/06/23/integer_to_string_conversion.html 整数转字符串2014\-06\-23 将整数转换为字符串表示有多种方法。这种转换很少成为性能瓶颈，但在分析某些应用程序的性能时经常出现。例如，在Lwan (http://lwan.ws/) 构建响应头时就非常常见。 以 Lwan 为例：最初使用 `snprintf()` 来转换数字。虽然这样做可行，但从性能角度来看相当无聊。第二种方法是使用朴素算法，基本原理是将数字依次除以 10，将对 10 取模的结果反向写入字符串，然后当数字变为 0 时反转字符串。 ``` // Code based on https://code.google.com/p/stringencoders/ size_t naive_uint32_to_str(uint32_t value, char *str) { char *wstr = str; // Conversion. Number is reversed. do *wstr++ = (char) decimal_digits[uvalue % 10]; while (uvalue /= 10); *wstr = '\0'; // Reverse string strreverse(str, wstr - 1); return wstr - str; } ``` 这在一段时间内表现不错，但字符串反转这一步总是让我困扰。为什么不直接反向写入字符串呢？于是我将 Lwan 中的代码改成了下面的片段。注意这个巧妙的技巧：将整数的字节大小乘以 3，即可近似得到 `MAX_INT` 的位数（包括零终止符），无论 `sizeof(int)` 的值是多少。 ``` #define INT_TO_STR_BUFFER_SIZE (3 * sizeof(int)) char *lwan_uint32_to_str(uint32_t value, char buffer[static INT_TO_STR_BUFFER_SIZE], size_t *len) { char *p = buffer + INT_TO_STR_BUFFER_SIZE - 1; *p = '\0'; do { *--p = "0123456789"[value % 10]; } while (value /= 10); size_t difference = (size_t)(p - buffer); *len = (size_t)(INT_TO_STR_BUFFER_SIZE - difference - 1; return p; } ``` 减少对数组的写入操作使这个算法的速度显著提升。然而，最终我还是做了在这种事情上应该避免的事情：我把数组查找改成了加法运算，却没有测量是否真的能提升性能就直接提交了代码。事实上查找表快了约 9%。哎呀！ 去年，Facebook 工程团队发布了一个将整数转换为字符串的函数 (https://www.facebook.com/notes/facebook-engineering/three-optimization-tips-for-c/10151361643253920)，速度更快。他们同样采用了避免在转换每个数位后反转字符串的思路，也使用了查找表。但最巧妙的地方在于：不是为 10 个数字建立查找表，而是为从 00 到 99 的所有两位数组合建立一个表。这将除法次数减半，从而获得了显著的性能提升：比上面的代码快约 31%： ``` size_t facebook_uint32_to_str(uint32_t value, char *dst) { static const char digits[201] = "0001020304050607080910111213141516171819" "2021222324252627282930313233343536373839" "4041424344454647484950515253545556575859" "6061626364656667686970717273747576777879" "8081828384858687888990919293949596979899"; size_t const length = digits10(value); size_t next = length - 1; while (value >= 100) { auto const i = (value % 100) * 2; value /= 100; dst[next] = digits[i + 1]; dst[next - 1] = digits[i]; next -= 2; } // Handle last 1-2 digits if (value < 10) { dst[next] = '0' + uint32_t(value); } else { auto i = uint32_t(value) * 2; dst[next] = digits[i + 1]; dst[next - 1] = digits[i]; } return length; } ``` `digits10()` 函数也是一种以非常高效的方式计算数字位数的函数。不过，即使它已经很快，也可以完全去掉这个调用：使用一个类似 `numeric_limits::digits10` 的常量可以保持相同的接口。这是可行的，因为 `dst` 缓冲区本身就足够大，可以容纳最大的 32 位无符号整数的所有数位。由于实现细节的原因——该函数基本上是将数字与 10 的幂进行比较，当数位数超过比较的最大幂时进行递归——对于较小的数字（一位数和两位数），使用常量长度带来的加速并不明显；但如果你已经优化到这个程度，使用常量不会有任何坏处。事实上，在我的机器上（一台 Core i7 2640M 笔记本，运行最新版 64 位 Arch Linux），使用常量始终更快： 相对加速比 使用 `digits10()` 和常量值的 `facebook_uint32_to_str()` 的相对加速比 该图表是通过一个基准测试程序 (https://gist.github.com/lpereira/c0bf3ca3148321395037) 获得的，这是我编写的用于测试所有这些整数转字符串方法的程序。为了与其他方法进行比较，下面是完整的图表： 基准测试结果 省略了 `snprintf()` 的结果以避免扭曲数据。剧透：它很慢。 不幸的是，存在一个许可证问题，导致我不能在 Lwan 中使用这段代码。博客文章没有提及许可证。我也在与 Facebook 无关的地方发现过这个两位数查找表 (https://mail-archives.apache.org/mod_mbox/apr-dev/200704.mbox/%[email protected]%3E)，所以我不确定谁先想出了这个主意。我通常在这类知识上的首选来源是 *Hacker's Delight* (http://www.hackersdelight.org/)，但即使是那里也没有收录这个方法。