，鸭子你好，桐人今天又来分享性能优化操作了。在很多追求性能的程序挑战中，经常会遇到一个操作：将String转为Integer/Long。如果你没有开发过高并发的系统，或者没有参加过任何性能挑战，你可能会有这样的疑问：这有什么特别的，Integer.valueOf/Long.valueOf不是不能用。事实上，很多内置的转换工具类只是满足功能需求，在高并发场景下可能成为热点方法，成为系统性能的瓶颈。文章开头，我来解释一下。本文测试结论来自：https://kholdstare.github.io/technical/2020/05/26/faster-integer-parsing.html。测试代码基于C++。在翻译原文的同时，我会加入一些自己的理解，帮助读者更好地理解其中的细节。提出问题。假设有一些固定长度为16位的文本信息。比如下面给出的时间戳需要尽快解析这些时间戳timestamp158520108712356715852010871235851585201087123621。//???}问题提出后，不妨先想一想。如果是你，你会采取怎样的方案？带着这样的想法，我们一一进入下面的方案。原生方案我们有哪些现成的转换方案？继承自C的std::atollstd::stringstream的C++17提供的charconvboost::spirit::qi评测程序使用GoogleBenchmark进行对比评测。同时，我们使用未经任何转换的方案作为基准进行比较。（baseline方案在最底层，相当于把值放到寄存器中，所以取名为BM_mov）下面给出的评估代码并不是那么关键，只是展示一下评估是如何进行的。staticvoidBM_mov(benchmark::State&state){for(auto_:state){benchmark::DoNotOptimize(1585201087123789);}}staticvoidBM_atoll(benchmark::State&state){for(auto_:state){benchmark::DoNotOptimize(std::atoll(example_timestamp));}}staticvoidBM_sstream(benchmark::State&state){std::stringstreams(example_timestamp);for(auto_:state){s.seekg(0);std::uint64_ti=0;s>>i;基准测试：：DoNotOptimize(i)；}}staticvoidBM_charconv(benchmark::State&state){autos=example_timestamp;for(auto_:state){std::uint64_tresult=0;std::from_chars(s.data(),s.data()+s.size(),result);benchmark::DoNotOptimize(result);}}staticvoidBM_boost_spirit(benchmark::State&state){usingboost::spirit::qi::parse;for(auto_:state){std::uint64_tresult=0;parse(s.data(),s.data()+s.size(),result);benchmark::DoNotOptimize(result);}}Native可以发现stringstream表现很差。当然，这不是一个公平的比较，但从评估结果来看，使用stringstream实现数值转换比baseline慢了391倍。相比之下，boost::spirit表现更好。既然我们知道目标字符串中包含了要解析的数字，不需要做任何数值验证，那么基于这些前提，我们可以思考是否有更快的解决方案？我们可以使用一个简单的Naive解决方案但是，循环方案是一个一个地解析字符。inlinestd::uint64_tparse_naive(std::string_views)noexcept{std::uint64_tresult=0;for(chardigit:s){result*=10;result+=digit-'0';}returnresult;}naive虽然这层for循环看起来它看起来很笨，但如果这样一个笨的解决方案可以击败标准库实现，为什么不这样做呢？前提是标准库的实现考虑了异常场景，做了一些验证。这种for循环的写法的一个前提是我们的输入一定要合理。我在上一篇文章中也提到了这个解决方案。显然，未来会有更好的替代方案来替代naive的解决方案。循环展开方案记得我们在文章开头加了一个限制，限制字符串长度为16位，所以循环可以省略。循环展开后，该方案可以更快。inlinestd::uint64_tparse_unrolled(std::string_views)noexcept{std::uint64_tresult=0;result+=(s[0]-'0')*1000000000000000ULL;result+=(s[1]-'0')*100000000000000ULL;result+=(s[2]-'0')*10000000000000ULL;结果+=(s[3]-'0')*1000000000000ULL;结果+=(s[4]-'0')*100000000000ULL;结果+=(s[5]-'0')*10000000000ULL;结果+=(s[6]-'0')*1000000000ULL;结果+=(s[7]-'0')*100000000ULL;结果+=(s[8]-'0')*10000000ULL;结果+=(s[9]-'0')*1000000ULL;结果+=(s[10]-'0')*100000ULL;结果+=(s[11]-'0')*10000ULL;结果+=(s[12]-'0')*1000ULL;结果+=(s[13]-'0')*100ULL;结果+=(s[14]-'0')*10ULL;结果+=(s[15]-'0');returnresult;}unrolled为什么循环展开更快，可以参考我之前在JMH上的文章。首先考虑byteswap解决方案。如果我们继续关注上述解决方案，我们可能只有两个方向：同时进行加法和乘法计算。不过，这种CPU运算似乎并没有通过多线程的方式来加速。如何优化是个问题。问题是将乘法和加法运算转换成位运算以获得更快的CPU执行速度，但是如果转换是另一个问题，相信读者会有这样的疑问，那我们带着这个问题继续往下看。原作者的优化思路是什么。紧接着上述的循环展开方案，将解析成32位整数的“1234”对应的循环展开操作画成图。过程如下：Unrolledsolutiongraph我们可以看到，乘法和加法运算的次数与字符的个数是线性相关的。由于每次乘法是由不同的乘法器执行的，我们不能只乘“一次”，在乘法结束时，我们还需要将所有结果相加。乍一看，似乎很难优化。以下优化技术需要一些操作系统知识和编译原理作为辅助。需要了解byteswap系统调用和big-endian和little-endian的字节序表示方式（后面会分享相关文章），如果不关心这些细节，也可以直接跳到文末这一段，直接读结论。要想清楚下图的意思，需要理解几个概念：字符1对应的ascii值是31，对应的2对应32，对应的4对应34。在little-endian机器上（比如x86),strings是以big-endian顺序存储的，而Integer是以little-endianbyteswap存储的，可以实现字节序交换。上面的Byteswap以16进制的方式展示了转换过程，可以用更少的操作达到最终的解析状态。在C++中实现上述过程，要将String重新解释为Integer，必须使用std::memcpy（避免命名冲突），进行减法，然后通过编译器内置的__builtin_bswap64在一条指令中交换字节。这是迄今为止优化最快的一个。templateinlineTget_zeros_string()noexcept;template<>inlinestd::uint64_tget_zeros_string()noexcept{std::uint64_tresult=0;constexprcharzeros[]="00000000";std::memcpy(&result,zeros,sizeof(result));returnresult;}inlinestd::uint64_tparse_8_chars(constchar*string)noexcept{std::uint64_tchunk=0;std::memcpy(&chunk,string,sizeof(chunk));chunk=__builtin_bswap64(chunk-get_zeros_string());//...}我们似乎得到了想要的结果，但是这个方案在时间复杂度上还是O(n)，是否可以基于这个方案继续呢优化？上一节从原来的Native方案到byteswap方案的分治方案，我们只是优化了CPU运算，并没有优化复杂度。既然我们不满足于O(n)，那接下来的复杂度可能性是多少呢？O（登录）！我们可以将每个相邻的数字组合成一对，然后继续将每一对组合成一组四个，依此类推，直到我们得到完整的整数。如何同时处理相邻数是使算法跑进O(logn)的关键。这个方案的要点是：偶数位的数乘10次方，奇数位的数不加。这可以通过位掩码来实现分而治之的方案。通过位掩码，我们可以一次对多个数字进行操作，将它们组合成一个更大的组合。通过使用这个掩码技巧，我们可以实现前面提到的parse_8_chars函数。.使用位掩码的另一个优点是我们不需要减去'0'，因为位掩码的副作用允许我们省略这一步。inlinestd::uint64_tparse_8_chars(constchar*string)noexcept{std::uint64_tchunk=0;std::memcpy(&chunk,string,sizeof(chunk));//1-bytemasktrick(workson4pairsofsingledigits)std::uint64_tlower_digits=(chunk&0x0f000f)000f>8;std::uint64_tupper_digits=（块＆0x000f000f000f000f）*10;chunk=lower_digits+上格+upper_digits;//2-bytemasktrick（workson2pairsoftwodigits）;//4-bytemasktrick(worksonpairofourdigits)lower_digits=(chunk&0x0000ffff00000000)>>32;upper_digits=(chunk&0x000000000000ffff)*10000;chunk=lower_digits+upper_digits;返回块；将它分成两个8字节的块，运行您刚刚编写的parse_8_chars，并对其进行基准测试！inlinestd::uint64_tparse_trick(std::string_views)noexcept{std::uint64_tupper_digits=parse_8_chars(s.data());std::uint64_tlower_digits=parse_8_chars(s.data()+8);returnupper_digits*100000000+lower_digits;}staticvoidBM_trick(benchmark::State&state){for(auto_:state){benchmark::DoNotOptimize(parse_trick(example_stringview));}}trick似乎优化的很好，我们已经优化了循环展开方案的基准测试由于我们手动执行了一系列CPU优化操作，因此性能提高了近56%，尽管这些并不是特别通用的技巧。这是一个糟糕的开始吗？我们似乎对CPU的操作干预太多了，或许我们应该放弃这些优化，让CPU自由飞翔。SIMDtrick解决方案你认为以上是最终的解决方案吗？不，还剩下最后一步优化。我们得出了一个结论同时组合数字组以实现O(logn)复杂度如果您要解析一个包含16个字符或128位的字符串，您也可以使用SIMD。有兴趣的读者可以参考SIMD，即SingleInstructionMultipleData。Intel和AMD的CPU都支持SSE和AVX指令，一般都使用更宽的寄存器。SIMA简单来说就是一组CPU扩展指令，可以通过调用多组寄存器实现并行乘法，从而提高系统性能。我们一般所说的向量化运算就是SIMA。让我们先设置16个字节中的每一个：inlinestd::uint64_tparse_16_chars(constchar*string)noexcept{autochunk=_mm_lddqu_si128(reinterpret_cast(string));autozeros=_mm_set1_epi8('0');chunk=chunk-zeros;//...}现在，主角变成了madd系统调用。这些SIMD函数的作用与我们使用位掩码技巧所做的完全相同——它们采用相同的宽寄存器，将其解释为较小整数的向量，将每个乘以特定的乘数，然后将相邻位的结果添加到更宽的向量中整数。所有操作一步完成。//The1-byte"trick"inoneinstructionconstautomult=_mm_set_epi8(1,10,1,10,1,10,1,10,1,10,1,10,1,10,1,10);chunk=_mm_maddubs_epi16(chunk,多个);2字节方案其实还有一条指令，可惜我没有找到4字节方案的指令，还是需要两条指令。这是完整的parse_16_chars方案：inlinestd::uint64_tparse_16_chars(constchar*string)noexcept{autochunk=_mm_lddqu_si128(reinterpret_cast(string));autozeros=_mm_set1_epi8('0');chunk=chunk-zeros;{constautomult=_mm_set_epi8(1,10,1,10,1,10,1,10,1,10,1,10,1,10,1,10);chunk=_mm_maddubs_epi16(chunk,mult);}{constautomult=_mm_set_epi16(1,100,1,100,1,100,1,100);chunk=_mm_madd_epi16(chunk,mult);}{chunk=_mm_packus_epi32(chunk,chunk);constautomult=_mm_set_epi16(0,0,0,0,1,10000,1,10000);chunk=_mm_madd_epi16(chunk,mult);}return((chunk[0]&0xffffffff)*100000000)+(chunk[0]>>32);}SIMDtrick0.75纳秒！是惊喜吗？可能有人总结总体比较我会问，为什么要用C++引入，用Java不行吗？补充一下，本文的测试结论均来自老外的文章。来源见文章开头。其次，本文后半部分的优化，都是基于一些系统调用和CPU指令的优化。这些用C++实现起来比较方便，Java只能用系统调用。在最近的性能挑战赛中，由于无法使用JNI的限制，选手只能将解法止步于循环扩展解法。试想一下，如果允许系统调用，而比赛中的字符串基本都是定长的，完全可以采用SIMD的trick方案，String到Long的转换会更快。polardb优化点其实在之前的polarDB比赛中，Puge给我介绍了bswap的向量化方案，这也是Java方案不如C++方案的原因之一。C++在执行一些CPU指令集和系统调用方面，比Java方便多了。您如何看待这一系列的优化？从std::stringstream的86.23到simatrick的0.75，这个优化过程很精彩，但是我们也发现，越往前走，我们越用到一些底层的优化技巧，比如方案中的trick，适用性有限。也有声音说：花那么多精力在优化上，为什么不写汇编呢？这又回到了“优化是万恶之源”的话题。在业务项目中，你可能不需要过多关注String如何转换为Long和Integer，也许Integer.valueOf和Long.valueOf可以满足你的诉求，但如果你是大数据分析系统，String转换是一个关于系统的瓶颈，相信本文的解决方案会给你一些启发。另外，对于这些SIMD方案，我还想多说一点。其实在一些性能挑战的最后，大家的整体规划都差不多。只是参数上的差异，因为比赛场景通常不会太复杂，最终前几名的差距就在于一些非常小的细节。就像SIMA提供的向量化运算等优化技术，可以帮助你比别人快几百毫秒，甚至1~2秒。这时候你会感叹，原来我和大神的差距就在这些细节上。但回顾整个过程，这些优化似乎并不能帮助编程比赛发挥出更多的能量。如果一个比赛只能靠CPU优化来实现差异化，我想肯定是不会成功的。因此，对于主办方来说，禁用部分类库可以有效避免卷入，对于参赛者来说，是一种减负。希望以后的比赛也能把重点放在让选手把更多的精力花在优化方案上，而不是优化笼统的细节上。回到String解析成Long/Integer的话题。在实际使用中，您不必回避使用Integer.valueOf或Long.valueOf。在大多数情况下，这不是系统的瓶颈。而如果你恰好在某些场景下遇到了String转换的瓶颈，希望本文能对你有所帮助。
