十亿行挑战显示 Java 可以在两秒钟内处理十亿行的文件

2024 年的第一天，Decodable 高级软件工程师 Gunnar Morling 向 Java 社区发起了 十亿行挑战（1BRC）。这项挑战将持续到 1 月底，目标是找到在最快时间内处理 10 亿行的 Java 代码。到目前为止，最快的算法可以在 2.5 秒内完成处理。

挑战的规则很简单：只能使用 SDK 特性，可以是任何 Java 发行版。因此，解决方案中不能借助外部库或数据存储。为了更好地了解这一挑战，InfoQ 联系了 Morling、GoTo 首席软件工程师 Eliot Barlas、OpenValue Rotterdam 总监 Roy van Rijn 以及 Oracle 软件开发副总裁兼 GraalVM 创始人 Thomas Wuerthinger。

InfoQ：这是一项令人兴奋的挑战。您能描述一下吗？其背后的动机是什么？

Morling：1BRC 是一项编码挑战，它的任务看似简单：解析文本文件中的温度测量值，并确定每个气象站的最小、最大和平均温度。需要注意的是：该文件有 10 亿个条目！

我想创造一个机会来探索高性能编程技术、新引入的 API（比如 Vector API——它利用了 CPU SIMD 指令）、不同 Java 发行版的特性，以及任何能证明 Java 已经变得非常快的东西。

InfoQ：如何参与这项挑战？

Morling： 可以先看下README文件，并克隆存储库。尝试实现自己的解决方案，并看看其他人做了什么尝试——归根结底是为了学习。

InfoQ：您在解决方案中有看到什么出人意料的东西吗？

Morling： 有人采用了黑客的做法：许多解决方案针对特定的键集合（即天气预报站名称）做了优化。这对于这个特定的数据集是有效的。在社区的帮助下，我们澄清了挑战的目的。

有许多解决方案很有趣：使用 SIMD 和新特性 Java 原生内存 API（这是我希望看到的），以及高度优化的解析函数，包括 SWAR（寄存器内 SIMD），这是我没有预料到的。到目前为止，致力于实现最快算法的人们已经深入到原生优化领域，计算 CPU 指令，评估分支预测错误等。

InfoQ：请描述下您的解决方案。有什么技术是您想要尝试的吗？

Eliot Barlas：我的解决方案是按照可用处理器的数量拆分文件。对于每一个部分，都有一个任务在单独的线程上计算每个气象站的统计信息。当这些任务完成后，最终结果将汇总到最终的统计数据表中。

对每一部分中的数据做内存映射，并通过可以覆盖整个分区字节范围的MappedByteBuffer进行访问。任务会使用ByteBuffer遍历分区中的数据，每次一个 byte 或 int。我还使用sun.misc.Unsafe将气象站名称提取并存储为整数序列。

Roy van Rijn： 我的解决方案是一种渐进式的解决方案。一开始，它使用 SDK 提供的普通数据结构和 API（如BufferedInputStream或HashMap）。逐步地，它演变成使用 Unsafe 来直接访问内存。并行性、无分支代码和实现 SWAR（SIMD 作为寄存器）使我的解决方案成为迄今为止最主要的竞争者之一。对于存储，我自己实现了一个“非常简单”的 hashmap，其底层是基于线性探查概念的数组。

Thomas Wuerthinger： 该解决方案的第一部分将工作负载按照目标处理器的可用核数进行划分，以便可以并行处理。它使用 Java 的特性对输入文件做内存映射，从而实现最有效的直接内存访问。解析数据的最内层循环所采用的技术设法避免了分支代码，代之以一些复杂的算术和位操作。对于这个特定的问题，由于输入的随机性，处理器经常会做出错误的分支预测，因此避免分支是最大化性能的关键。

InfoQ：您的解决方案还有可能进一步改进吗？

Barlas： 我一直在关注 Panama 项目，但 1BRC 提供了一个以应用方式探索外部内存能力的机会。[…] 我还未能成功地利用 Panama 项目的 Vector API 实现加速。例如，开始时，我尝试使用 ByteVector API 来快速比较气象站名称。我想使用其他类型的向量或结合 MemorySegment 接口重新实现这个过程。

Wuerthinger： 现在可能的改进在很大程度上取决于目标硬件。具体来说，可以在内存带宽、计算带宽和分支预测依赖方面进行权衡。

Roy van Rijn： 从大的方面来讲，方法是类似的。我目前正在尝试探索的概念是“机械同情（mechanical sympathy）”，我希望改进需要执行的指令，让它们以一种最适合测试机器的方式执行。

InfoQ：您怎么看新年伊始的这项有趣的挑战？

Morling： 可以肯定的是，Java 及其生态系统和社区比以往任何时候都更加繁荣！看到这么多人参加挑战，包括一些非常知名的开发者，真是令人鼓舞。每个人都在学习：要么通过编码，要么通过阅读代码。能有这么多人参加这项挑战，实在是离不开社区的帮助。

这一挑战受到了程序员社区的热烈欢迎，Morling 说，“这一切都远远超出了我的预期。”尽管领跑者似乎是在 GraalVM 上运行的解决方案，但也有提交使用了 OpenJDK 构建、Amazon Corretto 或 Eclipse Temurin。Morling 进一步评论说：“Graal 非常适合眼下这项任务，可以额外提供几个百分点的性能提升。”

这个挑战已经不限于 Java 生态系统，已经有使用 Rust、Go、C++ 甚至 SQL 和 Shell 编写的解决方案。

Morling 感谢了社区和 Decodable——他们提供了评估用的机器。

原文链接：

https://www.infoq.com/news/2024/01/1brc-fast-java-processing/

欢迎加入 InfoQ 读者技术交流群，与志同道合的朋友一起探讨知识，交流经验。