在 GitHub 上很少有用 Java “搞事情”的开源项目，大多都是严肃的企业级开源项目。今天 HelloGitHub 就给大家带来一个有趣的 Java 开源项目，更确切地说，这是一个有趣的 Java 编程挑战——1brc。

该项目名为“十亿行挑战”（1 Billion Row Challenge，1BRC），看谁写的 Java 程序更快！挑战的内容非常简单：用 Java 语言编写一个程序，读取包含多个气象站温度值的文件（10 亿行、13 GB），然后计算每个气象站的最小、平均和最大值，最后按照站点名称排序后输出结果。

GitHub 地址→github.com/gunnarmorling/1brc

接下来，让我们一起来了解这个在 GitHub 上“红极一时”的开源项目吧。

一、项目起源

该项目的作者 Gunnar Morling 是一位开源爱好者、Java Champion，从事基于 Apache Flink 的流处理工作，发起 1brc 编程挑战纯属个人兴趣爱好。

作者表示以开源的形式举办这项挑战的初衷是因为自己想学点新东西。每六个月就会有一些有新的 Java 版本出现，带来新的 API 和功能。要走在 Java 的“最前沿”并非易事。他又想了解这些新版本中有哪些新特性，以及可以用它们做些什么。同时也希望为开源社区提供一平台，让大家都能学习 Java 新知识。

在这个挑战中，参与者可以从其他人的实现中汲取灵感。此外，Gunnar 还希望纠正很多人认为 Java 很慢的偏见。因为如果你看看 Java 新版本及其特性，就会发现这种看法是完全错误的。下面开始挑战！

二、挑战内容

1BRC 提供一个包含温度测量值的文件，格式类似于 CSV 但使用分号作为分隔符。文件很简单就两列数据：一列是站点名称，如汉堡或慕尼黑；另一列是与站点相关的温度测量值（随机生成）。

挑战任务是处理该文件，汇总文件中的值，并为每个站点确定最小值、最大值和平均温度值。唯一要注意的是，正如挑战的名称所示，它有 10 亿行，生成文件的大小约为 13 GB，相当大。最后你必须打印出结果，如上图。

三、规则

关于规则，还有几点需要说明。首先，这项挑战主要针对 Java。原因在于，这是作者最熟悉的语言，同时希望传播关于 Java 的知识。参与者可以选择任何版本的 Java，包括新版本、预览版本、所有类型的发行版（如 GraalVM）以及各种 JDK 提供商的版本。为方便管理，推荐使用一个名为 SDKMAN（github.com/sdkman/sdkman-cli）的工具，它是一个非常优秀的工具，可以管理多个 Java 版本，并在不同版本之间自由切换。

仅限使用 Java，且不允许依赖任何外部库。引入库来完成任务并无意义，手搓实现更有成就感。每次运行之间不允许使用缓存，允许缓存的话，你只需执行一次任务，保存结果到文件中，然后读取文件，这样会非常快，但这没有多大意义。在这个挑战中，鼓励从他人的实现中获得灵感。下面让我们跟随作者的文字，看看 Java 程序“提速”的全过程吧！

四、开发环境

作者 Gunnar 用的是一台 32 核 CPU 的机器，其中主要使用 8 个内核。内存相当充足，实际上文件总是从 RAM 盘读取，以确保磁盘 I/O 不会影响性能，因为磁盘 I/O 的可预测性要差得多。

上面是作者的基本实现。他使用了 Java Streams API 和 files.lines 方法，从磁盘读取文件并生成一个包含文件行的流。接着，他使用 split 方法将每行数据拆分为站名和对应的值，并将结果（行）收集到一个分组收集器中，按站名对其分组。

对于每个站点，作者聚合这些值，并在聚合器实现中处理：追踪最小值和最大值；为计算平均值，追踪值的总和和计数。如果并行运行操作，还需要合并两个聚合器的结果。完成后，汇总结果并发出：包含最小值和最大值；计算平均值（总数除以计数）并打印输出。

在当前机器上，完成整个处理大约需要五分钟，性能尚可。编写这段代码花费不到半小时。对于日常工作而言，这样的解决方案已足够好，甚至可以在完成后享受一杯咖啡。然而，为了本次挑战，我们希望能进一步优化速度，看看可以取得多大进展。

五、第一个提交

这项挑战的关键在于需要有人参与。第一位参与者是一位来自荷兰的 Roy Van Rijn，他在作者发布帖子后大约一小时，就创建了自己的第一个实现，虽然不算花哨或复杂，但这开了个好头。只要有第一个人参与，其他人也会纷纷加入。

六、并行

接下来，让我们一起深入探讨如何加快这个程序的速度。整个一月份，人们都在研究这个问题，深挖到了一个非常深的层次，基本上涉及到计算 CPU 指令的优化。

首先，先谈谈并行，因为我们有很多 CPU 核。在作者用来评估的服务器上，配备了 32 个核和 64 个线程。只使用一个核显然是种浪费，我们应该充分利用这些资源。那么，我们该怎么做呢？回到上面简单的基础实现，可以做的第一件事就是添加并行调用，也就是利用 Java Streams API 的并行处理功能。

这段代码实现了并行处理管道，或者说流管道的一部分。只需添加一个方法调用，就可以将执行时间缩短到 71 秒，取得了显著的提升。

如果仔细考虑，这确实加快了速度，但并没有达到 8 倍的提升。尽管有 8 个 CPU，但并行处理的部分主要是处理逻辑。所有的聚合和分组逻辑都是并行发生的，但从内存中读取文件仍然是按顺序进行的。由于读取部分是顺序进行的，其他 CPU 核仍然处于空闲状态，因此需要将读取过程也进行并行化。

新的 Java 版本引入了新的 API 和 JEP（JDK 增强提案）。其中之一是最近添加的外部函数和内存 API。

本质上，这是一个 Java API，允许使用原生方法。它比旧的 JNI API 更易用，并且还允许使用本机内存。你可以管理自己的内存部分（如堆外内存），而不是由 JVM 管理的堆，并且你将负责维护和释放它。我们希望在这里使用这个 API，因为可以通过内存映射文件，然后在内存中并行处理它。

首先我们确定并行度。我们的例子中是 8 个核，这就是我们的并行度。接下来我们要对这个文件进行内存映射。在早期的 Java 版本中，你也可以使用内存映射文件，但你有大小之类的限制，你无法一次对整个 13 GB 的文件进行内存映射。而现在有了新的外部内存 API，我们就可以做到这一点。你映射文件。我们有这个 Arena 对象。这本质上是我们对这个内存的表示。有不同类型的 Arena，这里我只是使用这个全局 Arena，它可以从我的应用程序中的任何位置访问。现在我可以使用多个线程并行访问整个内存部分。

为了做到这一点，我们需要分割文件和内存表示。首先，我们将其大致分成 8 个相等的块。我们将整个大小除以 8。当然，很有可能我们会分割到某一行的中间，而理想情况下，我们希望我们的工作进程能够处理整行。这里发生的事情是，我们转到了文件的大约八分之一，然后继续转到下一个行结束符。那么这里就是这个块的结尾，也是下一个块的起点。然后我们处理这些块，我们启动线程，然后将它们连接起来。现在我们真正在整个周期内都利用了所有 8 个内核，进行 I/O 时也一样。

有一个警告。从本质上讲，其中一个 CPU 核总是最慢的。在某个时候，其他七个核都会等待最后一个核完成，因为数据的分布有点不均匀。人们最终的做法是不再使用 8 个块，而是将这个文件分成更小的块。本质上，他们积压了这些块。每当其中一个工作线程处理完当前块时，它就会去处理下一个块。通过这种方式，你可以确保所有 8 个线程始终得到平等利用。事实证明，理想的块大小是 2 兆字节。为什么是 2 兆字节？我使用的这台机器上的这个 CPU 有 16 兆字节的二级缓存，8 个线程每次处理 2 兆字节。这个数值在预测 I/O 等方面是最好的。这也表明，我们确实深入到了具体的 CPU 和架构的层面来真正优化该问题。

七、解析

我们更深入地分析一下。我们已经了解了如何利用多个 CPU 核，但具体在处理每一行时究竟发生了什么？让我们仔细看看。

为了提高效率，我们希望摆脱使用正则表达式分割文件的方法。取而代之的是，可以逐个字符地处理这些输入行。这样做能够更高效地解析和处理数据。

这个过程基本上就是一个状态机。我们逐个读取字符，直到读取完整行。使用分号字符将站点名称与温度值分隔开，根据不同的状态决定是读取站点名称的字节，还是读取测量值的字节。需要将它们添加到某个构建器或缓冲区中，以聚合这些值。

当遇到行结束符时，使用这两个缓冲区记录站点和测量值。对于测量值，需要将其转换为整数值。虽然问题被描述为双精度或浮点运算，但实际数据总是只有一个小数位。可以将数字乘以 10 或 100 视为整数问题，然后在最后除以 10 或 100。这种方法利用了数据集的特定特性，显著提高了计算效率。

所以我们处理或使用这些值。如果看到减号，就取反这个值。如果看到两位数字中的第一个，就将它乘以 100 或 10。通过这种方法，可以将时间缩短到 20 秒，比最初的基线实现快了一个数量级。

到目前为止，并没有什么神奇的地方。你可能会想，继续进行这样的优化有多大意义？如果这是你在日常工作中面临的问题，也许到此为止就可以了。它具有良好的可读性和可维护性，并且比原生基线实现快了一个数量级，这已经相当不错了。

当然，为了应对这一挑战，我们可能需要走得更远。我们还能做什么？我们可以再次回到并行的概念，尝试一次处理多个值。现在我们有了不同的并行方法。我们已经看到了如何充分利用所有 CPU 核，这是并行度的一方面。还可以考虑扩展到多个计算节点，这通常是大规模数据存储的做法。对于这个问题，拆分文件并将其分发到网络中可能不是最理想的，但这是一个极端。另一个方向是，在特定的 CPU 指令内进行并行化，这就是 SIMD（单指令多数据）的作用。

基本上，所有这些 CPU 都有扩展指令，允许一次将相同类型的操作应用于多个值。例如，在这里，我们想找到行尾字符。现在我们不再逐字节对比，而是可以使用 SIMD 指令将操作应用于 8 个或 16 个甚至更多字节，这会大大加快速度。问题是，在 Java 中，没有很好的方法来利用这些 SIMD 指令，因为 Java 是一种可移植的抽象语言，不允许你降低到这种级别的 CPU 底层上。

好消息是，我们可以使用上面提到的向量 API，它仍在孵化中，目前大约是第八个孵化版本。这个 API 现在允许在扩展中使用向量化指令。可以使用这个相等运算符进行比较调用，然后它将被转换为底层架构的正确 SIMD 指令，适用于 Intel 或 AMD64 扩展，对于 Arm 也同样适用。如果机器没有任何向量扩展，它将回退到标量执行。这是指令级别的并行化。

这种模式可以一次将相同的操作应用于多个值。此外，我们还可以执行所谓的 SWAR，即寄存器内的 SIMD。

这里的想法是，进行相等操作时，可以一次处理多个值，也可以在单个变量中执行此操作。例如，如果有 8 个字节，可以将其视为一个 long 值，那是 64 位，也是 8 个字节。可以对 long 值应用适当级别的位级操作，然后将此操作应用于所有 8 个字节。这包括位级屏蔽和移位等操作。

这里把数学公式放在右边，你会看到，这实际上给了你一个长整型的第一个零字节。这就是寄存器内的 SIMD，或称 SWAR。现在有趣的是，如果你看一下这段代码，会发现这里缺少了一些东西。有人意识到我们这里缺了什么吗？这段代码中没有 if、没有条件、没有分支。这实际上非常重要，因为我们需要记住 CPU 实际上是如何工作的。如果你看看 CPU 如何获取和执行我们的代码，会发现它总是采用这种流水线方法。每条指令都有不同的阶段，包括从内存中获取、解码、执行，最后写回结果。多个操作是并行发生的。当我们解码一条指令时，CPU 已经去获取下一条指令了。这是一种流水线并行化方法。

当然，CPU 实际上需要知道下一条指令是什么，否则就不知道要获取什么。为了让它知道，我们实际上不能有任何 if 语句，因为那样的话，CPU 就不知道要往哪个方向走。如果能够用无分支的方式表达这个问题（就像我们之前看到的那样），那么这对 CPU 中的分支预测器非常有益，这样它就总能知道下一条指令是什么。这样一来，我们就不会遇到需要刷新管道的情况，只因为在预测执行中走了一条错误的路径。

八、灾难发生了

有一天醒来，作者突然发现所有的结果都不一样了，速度比以前快了两倍。运行了前一天的一个实现，突然间速度快了很多，这让人疑惑不已。

其实是因为这个负载最初是在虚拟服务器上运行的，使用了专用的虚拟 CPU 核，这样就不会在那台机器上有任何其他干扰。没想到的是，负载被直接转移到了另一台机器上。不知道为什么会这样，可能是随机的，或者是因为那台机器上有很多负载。无论如何，它只是被转移到了另一台比以前更快的主机上。这对比测试来说是一个大问题，因为到目前为止所有的对比都是错误的，不再具有可比性。作者意识到需要一台专用服务器。

因为作者不是运维方面的专家。例如，可能需要关闭超线程，或关闭核加速功能以获得稳定的结果，在这方面并不擅长，但社区的 René 主动提出帮助设置这些。有很多这样的人来帮忙，然后人们实际上构建了一个 TCK，一个测试套件。

这里实际上是一个必须通过的测试套件。你不仅希望程序运行得快，还希望它正确。人们构建了这个测试套件，并且随着时间的推移不断扩展。每当有新的提交或条目进来时，首先必须通过这些测试。如果测试通过，那么作者会去评估并运行实现。这就是它的工作方式。

它有带测量值的示例文件和一个预期文件，然后测试运行器将针对这一组文件处理实现，并确保结果正确。另一件非常重要的事情是，必须在同一台机器上运行所有这些程序。这涉及很多事情，例如确保机器配置正确。对所有程序都会运行五次，丢弃最快和最慢的结果。

九、再谈一件事

回到作者最初展示的代码，里面有一个 Java Streams 实现，使用收集器将值分组到不同的存储桶中，每个气象站名称都是如此。人们意识到，这里也可以进行大量优化。凭直觉，会想到使用 HashMap，并将气象站名称作为该 HashMap 中的键。Java HashMap 是一种通用结构，适用于一系列用例。然而，如果想为一个特定用例获得最佳性能，那么最好自己实现一个定制的数据结构。

这就是我们在这里看到的，它比较简单。这里我们想跟踪每个气象站名称的测量值。它就像一张地图，由一个数组支持。

现在的想法是，我们获取站点名称的哈希键，并将其用作该数组中的索引，在数组中的特定位置，我们将管理特定站点名称的聚合器对象。我们获取哈希码，并希望不会溢出。这就是为什么我们将其与数组大小的逻辑结尾一起获取。我们始终在数组中对其进行良好的索引。然后我们需要检查，在数组中的特定位置是否已经存在某些内容？如果没有，则意味着我们手中有特定站点的第一个实例，因此是汉堡市的第一个值或慕尼黑的第一个值。我们只需在那里创建这个聚合器对象并将其存储在数组中的特定偏移量处。当然另一种情况是，我们转到数组中的特定索引，并且那里很可能已经存在某些内容。

如果你有同一站点的另一个值，则那里已经存在某些内容。 问题是我们还不知道，这实际上是我们手中的特定键的聚合器对象，还是其他东西？因为多个站名可能具有相同的键。这意味着，在这种情况下，如果某个东西已经存在于这个特定的数组槽中，则需要回退并对比实际名称。只有当传入的名称也是该槽中聚合对象的名称时，我们才能将值添加到该名称中。这就是为什么它被称为线性探测。否则，我们将继续在该数组中迭代，直到我们找到一个空闲的槽，然后我们可以在那里安装它，或者我们找到了我们手中的键的槽。对于这个案例，它的性能实际上比我们仅使用 Java HashMap 所能获得的性能要好得多。

当然，这在很大程度上取决于我们用来查找该索引的特定哈希函数。这可以追溯到人们真正针对特定数据集进行了大量优化的工作上，他们使用了对特定数据集无冲突的哈希函数。这有点违背我的想法，因为问题在于这个文件，正如我提到的，它的大小为 13 GB，而我没有很好的方法将 13 GB 分发给大家，所以他们必须自己生成它。我有数据生成器，每个人都可以使用这个生成器为自己创建文件，然后将其用于自己的测试目的。问题是在这个数据生成器中，我有一个特定的密钥集。我有大约 400 个不同的站点名称，这只是一个例子，但人们非常字面地理解了它，然后他们针对这 400 个站点名称进行了大量优化。他们对这 400 个名称使用了不会发生任何冲突的哈希函数。人们会利用他们能利用的一切。

所有这些的问题在于它也给我带来了很多工作，因为你无法真正证明没有哈希冲突。实际上，每当有人提交他们的实现时，我都必须去检查他们是否真的处理过这种情况，即两个站会创建相同的密钥，他们是否相应地处理了这些冲突？因为如果你不这样做，就会回到缓慢的时代，你会非常快，但你会不正确，因为你没有正确处理所有可能的名称。这是我为自己设置的一个小陷阱，这意味着我总是必须检查这一点，并在拉取请求模板中询问人们，如果你有一个自定义映射实现，你在哪里处理冲突？

十、GraalVM：JIT 和 AOT 编译器

上面提到了三件大事：并行化、使用 SIMD 和 SWAR 处理所有解析任务，以及自定义哈希映射。此外，还有一些更具体的技巧，以下我会提到其中的几个，给你一些现成的灵感。

现有的一个工具是 Epsilon 垃圾收集器，这是一个非常有趣的垃圾收集器，因为它不收集任何垃圾。这是一个无操作实现。如果是常规的 Java 应用程序，这并不是一个好主意，因为对象会不断分配，如果不执行任何 GC，最终会耗尽堆空间。然而，在这个挑战中，人们意识到，可以通过在处理循环中不进行任何分配来实现这一点。最初在引导程序时会做一些分配，但稍后不会再创建任何对象。只有可以重用的数组，就像可变结构一样，可以更新它们。

这样就不需要任何垃圾收集，也不需要任何 CPU 周期花在垃圾收集上，这意味着可以更快一点。这是一个非常有趣的优化。另一件事是，可以看到这里人们使用了很多 GraalVM。GraalVM 实际上有两个作用。它是一个提前编译器，因此会将 Java 程序编译成原生二进制文件。这有两个优点：首先，它占用更少的内存；其次，它启动速度非常快，因为不必进行类加载和编译等操作，这一切都发生在构建时。如果有这个原生二进制文件，它启动速度很快。

一开始可能认为在启动时节省几百毫秒对处理 13 GB 的文件不会有什么影响，但实际上它确实有影响。AOT 编译器和大多数最快的实现实际上都使用了带有 GraalVM 的 AOT 编译器。也可以使用它来替代 JVM 中的即时编译器。可以将其用作 C2 编译器的替代品。这并不是说应该总是这样做，这取决于特定的工作量和所做的事情。而这个问题非常适合这样做。人们只需使用 GraalVM 作为 JVM 中的 JIT 编译器，就可以获得大约 5% 的改进。推荐尝试一下，因为它基本上是免费的。只需要确保使用的 JVM 或 Java 发行版有 GraalVM 作为 C2 编译器的替代品。

还有其他一些优化手段，例如不安全代码。上图右边的构造很有趣，如果仔细看，这是内部处理循环。有一个 scanner 对象，尝试获取下一个值并处理它们。可以看到，在以顺序方式编写的程序中有三次相同的循环。你会说这三个循环是一个接一个地运行。实际发生的情况是，由于 CPU 有多个执行单元，编译器会发现这些循环之间没有数据依赖关系，因此可以并行化。可以将这些循环同时运行。

为什么是三次循环？这是基于经验的选择。提出这个主意的 Thomas 网友尝试了两次、四次，发现三次循环在那台机器上是最快的。在其他机器上可能会有所不同。

十一、结果

那么你一定很好奇，我们最后能跑多快？

这是初始使用 8 个 CPU 核的排行榜。当转移到本地机器时，尝试保持相同的速度。利用这 8 个核后，处理时间缩短到了 1.5 秒。没想到 Java 能跑得这么快，在 1.5 秒内就能处理 13 GB 的输入，令人印象深刻。

情况变得更好，因为有了一台强大的服务器，拥有 32 个核和 64 个线程，还有超线程。当然，想看看能跑多快？结果处理时间缩短到了 300 毫秒。这简直令人难以置信、印象深刻。

十二、漫长的旅程

人们为此工作了很长时间，挑战持续了整个 1 月。当人们想出某种技巧时，其他人也会很快将其采纳到自己的实现中，这是一段漫长的旅程。

上面的实现来自 Roy Van Rijn，他保存了非常好的日志，展示了随着时间的推移是如何进步的。如果往下看，可以看到他开始有些挣扎，因为做了一些改变，实际上比以前慢了。问题在于他运行在 Arm MacBook 上，这显然与运行的机器有不同的 CPU 和特性。他在本地看到了一些改进，但实际上在评估机器上速度更快。在底部可以看到，他尝试购买一台 Intel MacBook，以便有更好的机会在本地执行某些操作，并且在那台机器上的性能也会更好。

令人惊讶的是，这种情况在 Java 中也会发生，这个层面如此深入，特定的 CPU 甚至具体的代际都会产生影响。

十三、这样做有意义吗？

你应该做这些优化工作吗？这要视情况而定。如果你在开发企业应用程序，大多数时候都在处理数据库 I/O，达到那个级别并试图避免业务代码中的 CPU 周期可能会浪费时间。而如果你要应对类似的挑战，这可能会是一件有趣的事情。我建议的是，例如某个实现比基线快一个数量级，并且它仍然非常易读，没有任何陷阱。这种优化是非常不错的选择，你应该非常清楚是否要这样做。

或者，如果你想加入 GraalVM 团队，也可以尝试一下极限优化。前几天才知道，在比赛中一位名叫 Mary Kitty 的选手被 Oracle 的 GraalVM 编译器团队聘用了。

十四、最后

这场挑战不仅影响了 Java 社区，还影响了其他开发者社区。在 Snowflake 中，他们更是发起了一项「一万亿行挑战」。看到这里，你还会觉得 Java 语言慢吗？