关于后端:这波操作看麻了十亿行数据从71s到17s的优化之路

你好呀，我是歪歪。

春节期间关注到了一个对于 Java 方面的较量，很有意思。因为是开源的，我把我的项目拉下来试图学（白）习（嫖）他人的做题思路，在这期间一度让我产生了一个自我狐疑：

他们写的 Java 和我会的 Java 是同一个 Java 吗？

不能让我一个人狐疑，所以这篇文章我打算带你盘一下这个较量，并且试图让你也产生狐疑。

赛题

在 2024 年 1 月 1 日，一个叫做 Gunnar Morling 的帅哥，发了这样一篇文章：

https://www.morling.dev/blog/one-billion-row-challenge/

文章的题目叫做《The One Billion Row Challenge》，十亿行挑战，简称就是 1BRC，挑战的工夫是一月份整个月。

赛题的内容非常简单，你只须要看懂这个文件就行了：

文件的每一行记录的是一个气象站的温度值。气象站和温度分号分隔，温度值只会保留一位小数。

参赛者只须要解析这个文件，而后并计算出每个气象站的最小、最大和平均温度。依照字典序的格局输入就行了：

出题人还配了一个简图：

需要十分明确、简略，对不对？

为了让你彻底明确，我再给你举一个具体的例子。

假如文件中的内容是这样的：

chengdu;12.0
guangzhou;7.2;
chengdu;6.3
beijing;-3.6;
chengdu;23.0
shanghai;9.8;
chengdu;24.3
beijing;17.8;

那么 chengdu (成都) 的最低气温是 6.3，最高气温是 24.3，平均气温是 (12.0+6.3+23.0+24.3)/4=16.4，就是这么朴实无华的计算形式。

最终后果输入的时候，再留神一下字典序就行。

这有啥好挑战的呢？

难点在于出题人给出的这个文件有 10 亿行数据。

在我的垃圾电脑上，光是跑出题人提供的数据生成的脚本，就跑了 20 分钟：

跑进去之后文件大小都有靠近 13G，记事本打都打不开：

所以挑战点就在于“十亿行”数据。

具体的一些规定形容和细节补充，都在 github 上放好了：

https://github.com/gunnarmorling/1brc

针对这个挑战，出题人还提供了一个基线版本：

https://github.com/gunnarmorling/1brc/blob/main/src/main/java/dev/morling/onebrc/CalculateAverage_baseline.java

首先封装了一个 MeasurementAggregator 对象，外面放的就是要记录的最小温度、最大温度、总温度和总数。

整个外围代码就二三十行，应用了流式编程：

首先是一行行的读取文本，接着每一行都依照分号进行拆分，取出对应的气象站和温度值。

而后依照气象站维度进行 groupingBy 聚合，并且计算最大值、最小值和平均值。

在计算平均值的时候，为了防止浮点计算，还特意将温度乘 10，转换为 int 类型。

最初用 TreeMap 按字典序输入各个气象站的温度数据。

这个基线版本官网的数据是在跑分环境下，2 分钟内能够运行结束。

而在我的电脑上跑了靠近 14 分钟：

很失常，毕竟人家的测评环境配置都是很高的：

Results are determined by running the program on a Hetzner AX161 dedicated server (32 core AMD EPYC™ 7502P (Zen2), 128 GB RAM).

加入挑战的各路大神，最终拿出的 TOP 10 问题是这样的：

过后看到这个问题的霎时，我人都是麻的，第一个疑难是：我靠，13G 的文件啊？1.5s 内实现了读取、解析、计算的过程？这不可能啊，光是读取 13G 大小的文件，也须要一点工夫吧？

然而须要留神的是，歪徒弟有这个想法是走入了一个小误区，就是我认为这 13G 的文件一次性加载不实现，怎么疾速的从硬盘把文件读取到内存中也是一个考点。

起初发现是我多虑了，人家间接就说了，不必思考这一点，跑分问题运行的时候，文件间接就在内存中：

所以，最终的问题中不蕴含读取文件的工夫。

然而也很牛逼了啊，毕竟有十亿条数据。

第一名

我尝试着看了一下第一名的代码：

https://github.com/gunnarmorling/1brc/blob/main/src/main/java/dev/morling/onebrc/CalculateAverage_thomaswue.java

过于硬核，切实是看不懂。我只能通过作者写的一点正文、办法名称、代码提交记录去尝试了解他的代码。

在他的代码结尾的局部，有这样的一段形容：

这是他的破题思路，联合了这些信息之后再去看代码，略微好一点，然而我发现他外面还是有十分多的微操、太多针对性的优化导致代码可读性较差，尽管他的代码加上正文一共也才 400 多行，然而我看还是看不懂。

我轻易截个代码片段吧：

问 GPT 这个哥们，他也是能说个大略进去：

所以我放弃了了解第一名的代码，开始去看第二名，发现也是十分的艰涩难懂，再到第三名 …

最初，我产生了文章开始时的疑难：他们写的 Java 和我会的 Java 是同一个 Java 吗？

然而有一说一，尽管我看不懂他们的某些操作，然而会发现他们整体的思路都简直是统一。

尽管我没有看懂第一名的代码，然而我还是专门列出了这一个大节，给你指个路，有趣味你能够去看看。

另外，取得第一名的老哥，其实是一个巨佬：

是 GraalVM 我的项目的负责人之一:

伟人肩膀

在官网的 github 我的项目的最初，有这样的一个局部：

其中最初一篇文章，是一个叫做 Marko Topolnik 的老哥写的。

我看了一下，这个哥们的官网问题是 2.332 秒，榜单第九名：

然而依照他本人的形容，在较量完结后他还持续优化了代码，最终能够跑到 1.7s，排名第四。

在他的文章中具体的形容了他的挑战过程和思路。

我就站在伟人的肩膀上，带大家看看这位大佬从 71s 到 1.7s 的破题之道：

https://questdb.io/blog/billion-row-challenge-step-by-step/

最惯例的代码

首先，他给了一个惯例实现的代码，和基线版本的代码大同小异，只不过是应用了并行流来解决：

https://github.com/mtopolnik/billion-row-challenge/blob/main/src/Blog1.java

平时看到流式编程我是有点头疼的，须要略微的反馈一下，然而在看了前三名的最终代码后再看这个代码，我感觉很亲切。

依据作者的形容，这段代码：

• 应用并行 Java 流，将所有 CPU 外围都用起来了。
• 也不会陷入任何已知的性能陷阱，比方 Java 正则表达式

在一台装有 OpenJDK 21.0.2 的 Hetzner CCX33 机器上，跑完须要的工夫为 71 秒。

第 0 版优化：换个好的 JVM

叫做第 0 版优化的起因是作者对于代码其实啥也没动，只是换了一个 JVM：

默认应用 GraalVM 之后，最惯例的代码，运行工夫从 71s 到了 66s，相当于白捡了 5s，我问就你香不香。

同时作者还提到一句话：

When we get deeper into optimizing and bring down the runtime to 2-3 seconds, eliminating the JVM startup provides another 150-200ms in relief. That becomes a big deal.

当咱们把程序优化到运行工夫只须要 2-3 秒的时候，应用 GraalVM，会打消 JVM 的启动工夫，从而提供额定的 150-200ms 的晋升。

到那个时候，这个就变得十分重要了。

数据指标很重要

在正式进入优化之前，作者先介绍了他应用到的三个十分重要的工具：

对于工具我就不过多介绍了，这里独自提一嘴次要是想表白一个贯通整个优化过程的中心思想：数据指标很重要。

你只有收集到了以后程序足够多的运行指标，能力对你进行下一步优化时提供直观的、优化方向上的领导。

工欲善其事必先利其器，就是这个情理。

第一版优化：并行 I/O 搞起来

通过查看以后代码对应的火焰图：

https://questdb.io/html/blog/profile-blog1

通过火焰图以及察看 GC 状况，作者发现以后耗时的中央留神是这三个中央：

1. BufferedReader 将每行文本输入为字符串
2. 解决每一行的字符串
3. 垃圾收集 (GC)：应用 VisualGC 能够看到，差不多每秒要 GC 10 次甚至更多。

能够发现 BufferedReader 占用了大量的性能，因为以后读取文件还是一行行读取的嘛，性能很差。

于是大多数人意识到的第一件事就是采纳并行化 I/O。

所以，咱们须要把待处理的文件分块。分多少块呢？

有多少个线程就分成多少个块，每个线程各自解决一个块，这样性能就下来了。

文件分块读取，大家自然而然的就想到了 mmap 相干的办法。

mmap 能够用 ByteBuffer API 来搞事件，然而应用的索引是 int 类型，所以可映射的大小有 2GB 的限度。

后面说了，在这个挑战中，光是文件大小就有 13G，所以 2GB 是顾此失彼的。

然而在 JDK 21 中，反对一个叫做 MemorySegment 的货色，也能够干 mmap 一样的事件，然而它的索引应用的是 long，相当于没有内存限度了。

除了应用 MemorySegment 外，还有一些细节的解决，比方找到正确的宰割文件的地位、启动线程、期待线程解决实现等等。

解决这些细节会导致这一版的代码从最后的 17 行减少到了 120 行。

这是优化后的代码地址：

https://github.com/mtopolnik/billion-row-challenge/blob/main/src/Blog2.java

在这个赛题下，咱们必定是须要再循环中进行数据的解析和解决的，所以循环就是十分重要的一个点。

咱们能够关注一下代码中的循环局部，这外面有一个小细节：

这个循环是每个线程在按块读取文件大小，外面用到了 findByte 办法和 stringAt 办法。

在第一个版本中，咱们是用的 BufferedReader 把一行内容以字符串的模式读进来，而后依照分号分隔，并生成城市和温度两个字符串。

这个过程就波及到三个字符串了。

然而这个哥们的思路是啥？

自定义一个 findByte 办法，先找到分号的地位，而后把下标返回回去。

再用自定义的 stringAt 办法，联合后面找到的下标，间接解析出“城市和温度”这两个字符串，缩小了整行读取的内存耗费。

相当于少了十亿个字符串，在字符串解决和 GC 方面获得了不错的体现。

这一波操作下来，解决工夫间接从 66s 降落到了 17s：

而后再看火焰图：

https://questdb.io/html/blog/profile-blog2-variant1

能够发现 GC 的工夫简直隐没了。

CPU 当初大部分工夫都花在自定义的 stringAt 上。还有相当多的工夫花在 Map.computeIfAbsent 办法、Double.parseDouble 办法和 findByte 办法

其中 Double.parseDouble 办法是解析温度用的。

作者打算先把这个中央给攻下来。

第二版优化：优化温度解析办法

在这版优化中，作者间接将温度解析为整数。

首先，目前的做法是，首先调配一个字符串，而后对其调用 parseDouble() 办法，最初转换为整数以进行高效的存储和计算。

然而，其实咱们应该间接创立整数进去，没必要走字符串绕一圈。

同时咱们晓得，温度的取值范畴是 [-99.9,99.9]，所以针对这个范畴，咱们搞个自定义办法就行了：

private int parseTemperature(long semicolonPos) {
    long off = semicolonPos + 1;
    int sign = 1;
    byte b = chunk.get(JAVA_BYTE, off++);
    if (b == '-') {
        sign = -1;
        b = chunk.get(JAVA_BYTE, off++);
    }
    int temp = b - '0';
    b = chunk.get(JAVA_BYTE, off++);
    if (b != '.') {
        temp = 10 * temp + b - '0';
        // we found two integer digits. The next char is definitely '.', skip it:
        off++;
    }
    b = chunk.get(JAVA_BYTE, off);
    temp = 10 * temp + b - '0';
    return sign * temp;
}

这波操作下来，解决工夫又缩小了 6s，来到了 11s：

再看对应火焰图：

https://questdb.io/html/blog/profile-blog2-variant2

温度解析局部的耗时占比从 21.43% 升高到 6%，阐明是一次正确的优化。

接下来，能够再搞一搞 stringAt 办法了。

第三版优化：自定义哈希表

首先，要优化 stringAt 办法，咱们得晓得它是干啥的。

咱们看一眼代码：

在经验了上一波优化之后，stringAt 目前在代码中的惟一作用就是为了获取气象站的名称。

而获取到这个名称的惟一目标是看看以后的 HashMap 中有没有这个气象站的数据，如果没有就新建一个 StationStats 对象，如果有就把之前的 StationStats 对象拿进去进行数据保护。

此外，在赛题中还有这样的一个信息，尽管有十亿行数据，然而只有 413 个气象站：

既然 key 的大小是可控的，那基于这个条件，作者想了一个什么样的骚操作呢？

他间接不必 HashMap 了，自定义了一个哈希表，长这样的：

https://github.com/mtopolnik/billion-row-challenge/blob/main/src/Blog3.java

次要看一下代码中的 findAcc 办法，你就能明确它是干啥的了：

通过 hash 办法计算出指定字符串，即气象站名称的 hash 值之后，从自定义的 hashtable 中取出该地位的数据。

首先标号为 ① 的中央，如果没有取到数据，则阐明没有这个气象站的数据，新建一个放好，返回就完事。

如果取到了数据，来到标号为 ② 的中央，看看取到的数据和以后要放的数据对应的气象站名称是不是一样的。

如果是则阐明曾经有了，取出来，而后返回。

如果不是，阐明啥状况？

阐明 hash 抵触了，来到标号为 ③ 的中央进行下标加一的动作。

而后再次进行循环。

来，你通知我，这是什么手法？

这不就是凋谢寻址来解决 hash 抵触吗？

所以 findAcc 办法，就能够代替 computeIfAbsent 办法。

通过自定义的 StatsAcc 哈希表来代替原生的 HashMap。

而且后面说了，key 的大小是可控的，如果自定义 hash 表的初始化大小管制的适合，那么整个 hash 抵触的状况也不会十分重大。

这一波组合拳下来，运行工夫来到了 6.6s，火焰图变成了这样：

https://questdb.io/html/blog/profile-blog3

大量的工夫花在了后面剖析的 findAcc 办法上。

同时作者提到了这样一句话：

同样的代码，如果放到 OpenJDK 上跑须要运行 9.6s，比 GraalVM 慢了 3.3s。

我滴个乖乖，这就是一个 45% 的性能晋升啊。

第四版优化：应用 Unsafe 和 SWAR

在这一版优化开始之前，作者先写了这样一段话：

大略意思就是说，到目前为止，咱们用到的都是惯例且无效的解决方案，并且是 Java 规范、平安的用法。

即便止步于此也能学到很多优化技巧，能够在理论的我的项目中进行应用。

如果你持续往下摸索，那么：

Readability and maintainability also take a big hit, while providing diminishing returns in performance. But, a challenge is a challenge, and the contestants pressed on without looking back!
可读性和可维护性也会受到重创，同时性能的收益会递加。然而，挑战就是挑战，参赛者们持续致力，没有回头！

简略来说，作者的意思就是打个预防针：接下来就要开始上强度了。

所以，在这个版本中，作者利用一些排名靠前的选上都在用的计划：

• 应用 sun.misc.Unsafe 而不是 MemorySegment，来防止边界查看
• 防止从新读取雷同的输出字节：重复使用加载的值进行哈希和分号搜寻
• 每次解决 8 个字节的数据，应用 SWAR 技术找到分号分隔符。
• 应用 merykitty 老哥提供的牛逼的 SWAR（SIMD Within A Register）代码解析温度。

这是这一版的代码：

https://github.com/mtopolnik/billion-row-challenge/blob/main/src/Blog4.java

比方其中对于循环解决数据的局部，看起来就很之前很不一样了：

而后你再看外面 semicolonMatchBits、nameLen、maskWord、dotPos、parseTemperature 这些办法的调用，间接就是一个懵逼的状态，看着头都大了：

然而你认真看，你会发现这几个办法是作者从其他人那边学来的：

比方这个叫做 merykitty 的老哥，提供了解析温度的代码，尽管作者退出了大量的正文阐明，然而我也只是大略就看懂了不到三层吧。

这外面大量的应用了位运算的技巧，同时你认真看：简直没有 if 判断的存在。这是重点，用间接的位运算替换了分支指令，从而缩小了分支预测谬误的老本。

此外，还有很多我第一次见、叫不上名字的奇技淫巧。

通过这一波“我看不懂，然而我大受震撼”的操作搞下来，工夫升高到了 2.4s：

第五版优化：统计学用起来

当初，咱们的火焰图变成了这样：

https://questdb.io/html/blog/profile-blog4

耗时次要还是在于 findAcc 办法：

而 findAcc 办法的耗时在于 nameEquals 办法，判断以后气象站名称是否呈现过：

然而这个办法外面有个 if 判断，以字节为单位比拟两个字符串的内容，每次比拟 8 个字节。

首先，它通过循环逐渐比拟两个字符串中的对应字节。在每次迭代中，它应用 getLong 办法从输出字符串中获取一个 64 位的长整型值，并与另一个字符串中的相应地位进行比拟。如果发现不相等的字节，则返回 false，示意两个字符串不相等。

如果循环完结后没有发现不相等的字节，它会持续查看是否曾经比拟了输出字符串的所有字节，或者最初一个输出字符串的字节与相应地位的字符串字节相等，那么示意两个字符串相等，则返回 true。

那么问题就来了？

如果气象站名称长度全都是小于 8 个字节，会呈现啥状况？

假如有这样的一个前提条件，是不是咱们就不必在 for 循环中进行 if 判断了，间接一把就比拟实现了？

很惋惜，没有这样一个提前条件。

然而，如果在数据集中，气象站名称长度绝大部分都小于 8 个字节那是不是就能够独自解决一下？

那到底数据分布是怎么样的呢？

这个问题问题进来的一瞬间，统计学啪的一下就站进去了：这个老子在行，我算算。

所以，作者写了一个程序来统计分析数据集中气象站名称的长度：

https://github.com/mtopolnik/billion-row-challenge/blob/main/src/Statistics.java

基于程序运行后果，最终的论断如下：

通过剖析作者发现，赛题的数据集中气象站名称长度简直均匀分布在 8 字节以上和 8 字节以下。

运行 Statistics.branchPrediction 办法，当条件是 nameLen > 8 时导致了 50% 的分支预测失败。

也就是说，十亿数据中有一半的数据，都是小于 8 字节的，都是不必特意进行 if 判断的。

但如果将条件更改为 nameLen > 16，那么预测失败率将降至 2.5%。

依据这一发现，很显著，如果要进一步优化代码，就须要编写一些特定的代码来防止在 nameLen > 8 上应用任何 if 判断，间接应用 nameLen > 16 就行。

这是这一版的最终代码，可读性越来越差了：

https://github.com/mtopolnik/billion-row-challenge/blob/main/src/Blog5.java

然而最终的问题是 1.8s：

哦，对了，如果你对于分支预测技术不太分明，那你可能看得比拟懵。

然而分支预测，在性能挑战中，特地是最初大家比分都咬的十分紧的状况下，每次都是屡立奇功，战功赫赫，属于高手间过招杀手锏级别的优化伎俩。

持续优化

再前面作者还有这两个局部。

打消启动 / 清理老本：

应用更小的文件分块和工作窃取机制：

这前面就齐全是基于这个赛题进行定制化的优化，可移植性不强了，作者就没有进行详细描述，再加上一个我也是没怎么看明确，就不开展讲了。

反正这两个组合拳下来，又搞了 0.1s 的工夫下来，最终的问题为 1.7s：

我切实是学不动了，有趣味的同学能够本人去看看原文的对应局部。

写在前面

其实对于这篇文章，我原想法是看懂前三名的代码，而后对代码进行解析、比照，找到他们思路的共同点和差别点，然而起初他们的代码的确我看不懂，所以我放弃了这个想法。

然而我晓得，只有我违心花工夫、有足够的工夫，我必定能够缓缓地把他们的这几百行代码啃透，然而我也只是想了想而已，很快就放弃了这个思路。

我想如果是大学的时候，我看到这个较量，我会感觉，真牛逼，我得好好钻研一下。

然而当初不一样了，加入工作了，看到了这个较量，我还是会感觉，真牛逼，然而对我写业务代码帮忙不大，就不深究了，浅尝辄止。

大学的时候学习是靠本人无穷的精力和对于把握新常识的乐趣撑着，当初学习次要靠一时冲动。

然而我还是强烈建议感兴趣的敌人，依照我问中提到的地址，本人去钻研一波他人提交的代码。

兴许你也会产生一样的疑难：他们写的 Java 和我会的 Java 是同一个 Java 吗？

我的答案是：不是的，他们写的 Java 是本人酷爱的 Java，咱们写的 Java 只是挣钱的 Java。

没有高低贵贱之分，然而能让你不经意间，从业务代码的深海中低头看一眼，看到本人相熟的畛域中，更广大的世界。