你好鸭，Kirito 今天又来分享性能优化的骚操作了。
在很多追求性能的程序挑战赛中，经常会遇到一个操作：将 String 转换成 Integer/Long。如果你没有开发过高并发的系统，或者没有参加过任何性能挑战赛，可能会有这样的疑问：这有啥好讲究的，Integer.valueOf/Long.valueOf 又不是不能用。实际上，很多内置的转换工具类只满足了功能性的需求，在高并发场景下，可能会是热点方法，成为系统性能的瓶颈。
文章开头，我先做一下说明，本文的测试结论出自：https://kholdstare.github.io/technical/2020/05/26/faster-integer-parsing.html 。测试代码基于 C++，我会在翻译原文的同时，添加了部分自己的理解，以协助读者更好地理解其中的细节。
问题提出
假设现在有一些文本信息，固定长度为 16 位 ，例如下文给出的时间戳，需要尽可能快地解析这些时间戳
timestamp 1585201087123567 1585201087123585 1585201087123621
方法体如下所示：
std::uint64_t parse_timestamp(std::string_view s) { // ??? }
问题提出后，大家不妨先思考下，如果是你，你会采取什么方案呢？带着这样的思考，我们进入下面的一个个方案。
基于 Spring Boot + MyBatis Plus + Vue & Element 实现的后台管理系统 + 用户小程序，支持 RBAC 动态权限、多租户、数据权限、工作流、三方登录、支付、短信、商城等功能
Native 方案
我们有哪些现成的转换方案呢？
- 继承自 C 的
std::atoll std::stringstream- C++17 提供的
charconv boost::spirit::qi
评测程序采用 Google Benchmark 进行对比评测。同时，我们以不做任何转换的方案来充当 baseline，以供对比。（baseline 方案在底层，相当于将数值放进来了寄存器中，所以命名成了 BM_mov）
下面给出的评测代码不是那么地关键，只是为了给大家展示评测是如何运行的。
static void BM_mov(benchmark::State& state) { for (auto _ : state) { benchmark::DoNotOptimize(1585201087123789); } } static void BM_atoll(benchmark::State& state) { for (auto _ : state) { benchmark::DoNotOptimize(std::atoll(example_timestamp)); } } static void BM_sstream(benchmark::State& state) { std::stringstream s(example_timestamp); for (auto _ : state) { s.seekg(0); std::uint64_t i = 0; s >> i; benchmark::DoNotOptimize(i); } } static void BM_charconv(benchmark::State& state) { auto s = example_timestamp; for (auto _ : state) { std::uint64_t result = 0; std::from_chars(s.data(), s.data() + s.size(), result); benchmark::DoNotOptimize(result); } } static void BM_boost_spirit(benchmark::State& state) { using boost::spirit::qi::parse; for (auto _ : state) { std::uint64_t result = 0; parse(s.data(), s.data() + s.size(), result); benchmark::DoNotOptimize(result); } }
Native
可以发现 stringstream 表现的非常差。当然，这并不是一个公平的比较，但从测评结果来看，使用 stringstream 来实现数值转换相比 baseline 慢了 391 倍。相比之下， <charconv> 和 boost::spirit 表现的更好。
既然我们已经知道了目标字符串包含了要解析的数字，而且不需要做任何的数值校验，基于这些前提，我们可以思考下，还有更快的方案吗？
基于 Spring Cloud Alibaba + Gateway + Nacos + RocketMQ + Vue & Element 实现的后台管理系统 + 用户小程序，支持 RBAC 动态权限、多租户、数据权限、工作流、三方登录、支付、短信、商城等功能
Naive 方案
我们可以通过一个再简单不过的循环方案，一个个地解析字符。
inline std::uint64_t parse_naive(std::string_view s) noexcept { std::uint64_t result = 0; for(char digit : s) { result *= 10; result += digit - '0'; } return result; }
Naive
虽然这层 for 循环看起来呆呆的，但如果这样一个呆呆的解决方案能够击败标准库实现，何乐而不为呢？前提是，标准库的实现考虑了异常场景，做了一些校验，这种 for 循环写法的一个前提是，我们的输入一定是合理的。
之前我的文章也提到过这个方案。显然， naive 的方案之后还会有更优的替代方案。
循环展开方案
记得我们在文章的开头加了一个限定，限定了字符串长度固定是 16 位，所以循环是可以被省略的，循环展开之后，方案可以更快。
inline std::uint64_t parse_unrolled(std::string_view s) noexcept { std::uint64_t result = 0; result += (s[0] - '0') * 1000000000000000ULL; result += (s[1] - '0') * 100000000000000ULL; result += (s[2] - '0') * 10000000000000ULL; result += (s[3] - '0') * 1000000000000ULL; result += (s[4] - '0') * 100000000000ULL; result += (s[5] - '0') * 10000000000ULL; result += (s[6] - '0') * 1000000000ULL; result += (s[7] - '0') * 100000000ULL; result += (s[8] - '0') * 10000000ULL; result += (s[9] - '0') * 1000000ULL; result += (s[10] - '0') * 100000ULL; result += (s[11] - '0') * 10000ULL; result += (s[12] - '0') * 1000ULL; result += (s[13] - '0') * 100ULL; result += (s[14] - '0') * 10ULL; result += (s[15] - '0'); return result; }
unrolled
关于循环展开为什么会更快，可以参考我过去关于 JMH 的文章。
byteswap 方案
先思考下，如果继续围绕上述的方案进行，我们可能只有两个方向：
- 并发执行加法和乘法计算，但这种 CPU 操作似乎又不能通过多线程之类的手段进行加速，该如何优化是个问题
- 将乘法和加法运算转换成位运算，获得更快的 CPU 执行速度，但如果转换又是个问题
相信读者们都会有这样的疑问，那我们继续带着这样疑问往下看原作者的优化思路是什么。
紧接着上述的循环展开方案，将 “1234” 解析为 32 位整数对应的循环展开操作绘制为图，过程如下：
Unrolled solution graph
我们可以看到，乘法和加法的操作次数跟字符的数量是线性相关的。由于每一次乘法都是由不同的乘数进行，所以我们不能只乘“一次”，在乘法的最后，我们还需要将所有结果相加。乍一看，好像很难优化。
下面的优化技巧，需要一些操作系统、编译原理相关的知识作为辅助，你需要了解 byteswap 这个系统调用，了解大端序和小端序的字节序表示方法（后面我也会分享相关的文章），如果你不关心这些细节，也可以直接跳到本段的最后，直接看结论。
理解清楚下图的含义，需要理解几个概念：
- 字符
1对应的 ascii 值是31，相应的2对应32，4对应34 - 在小端序机器上（例如 x86），字符串是以大端序存储的，而 Integer 是以小端序存储的
- byteswap 可以实现字节序调换
byteswap
上图展示了十六进制表示下的转换过程，可以在更少的操作下达到最终的解析状态。
将上图的流程使用 C++ 来实现，将 String 重新解释为 Integer，必须使用 std::memcpy（避免命名冲突），执行相减操作，然后通过编译器内置的 __builtin_bswap64 在一条指令中交换字节。到目前为止，这是最快的一个优化。
template <typename T> inline T get_zeros_string() noexcept; template <> inline std::uint64_t get_zeros_string<std::uint64_t>() noexcept { std::uint64_t result = 0; constexpr char zeros[] = "00000000"; std::memcpy(&result, zeros, sizeof(result)); return result; } inline std::uint64_t parse_8_chars(const char* string) noexcept { std::uint64_t chunk = 0; std::memcpy(&chunk, string, sizeof(chunk)); chunk = __builtin_bswap64(chunk - get_zeros_string<std::uint64_t>()); // ... }
我们看上去得到了想要的结果，但是这个方案从时间复杂度来看，仍然是 O(n) 的，是否可以在这个方案的基础上，继续进行优化呢？
