十亿行挑战赛（1BRC）总结

背景与目标

2024年1月1日，Decodable的高级软件工程师Gunnar Morling向Java社区发起了“十亿行挑战赛”（1BRC）。该挑战赛将持续到1月底，目标是找到能够在最短时间内处理十亿行数据的Java代码。目前，最快的算法已经能够在1.7秒内完成处理。

挑战规则

挑战规则简单明了：只能使用任何Java发行版中的SDK功能，禁止使用外部库或数据存储。这使得参与者必须充分利用Java的核心功能来实现高效的数据处理。

挑战内容

挑战的核心任务是从一个包含十亿条温度测量值的文本文件中解析数据，并计算每个气象站的最低、最高和平均温度。Morling希望通过这个挑战探索高性能编程技术、新API（如向量API）以及不同Java发行版的能力，展示Java的速度和性能。

参与方式

参与者可以从GitHub上克隆代码库，阅读README文件，并尝试实现自己的解决方案。Morling鼓励大家学习他人的代码，强调挑战的最终目的是学习和提升。

解决方案与技术创新

在挑战过程中，参与者提出了许多创新的解决方案，其中包括：

1. Eliot Barlas的解决方案：

   • 将文件分成与处理器数量相等的分区，每个分区在单独的线程上计算气象站的统计数据。
   • 使用MappedByteBuffer映射分区数据，并通过ByteBuffer逐字节读取数据。
   • 使用sun.misc.Unsafe存储气象站名称。

2. Roy van Rijn的解决方案：

   • 从使用标准SDK API（如BufferedInputStream和HashMap）开始，逐步演进到使用Unsafe直接访问内存。
   • 通过并行化、无分支代码和SWAR（寄存器内的SIMD）技术优化性能。
   • 实现了一个基于线性探针的简单哈希表用于数据存储。

3. Thomas Wuerthinger的解决方案：

   • 将工作负载划分为目标处理器上的核心数量，实现并行化。
   • 使用Java的内存映射功能直接访问输入文件。
   • 在数据解析的核心循环中采用无分支代码技术，通过复杂的算术和位操作提高性能。

进一步优化的可能性

参与者们认为，进一步优化取决于目标硬件的特点，特别是内存带宽、计算带宽和分支预测的权衡。Barlas表示，他尚未成功使用Project Panama的向量API实现加速，但希望未来能通过其他类型的向量或结合MemorySegment接口进行优化。

挑战赛的成果与影响

挑战赛取得了巨大成功，吸引了大量开发者参与，包括一些知名开发者。Morling表示，Java生态系统和社区比以往任何时候都更加繁荣，参与者通过编码和阅读代码都学到了很多。社区的帮助使得挑战赛得以蓬勃发展。

虽然目前领先的解决方案大多基于GraalVM，但也有使用OpenJDK、Amazon Corretto和Eclipse Temurin的提交。Morling指出，GraalVM非常适合这个任务，能够免费提供额外的性能提升。

挑战赛的扩展

挑战赛不仅限于Java生态系统，还有使用Rust、Go、C++、SQL和Shell编写的解决方案。在Java生态系统中，Thomas Wuerthinger、Quan Anh Mai和Alfonso Peterssen共同获得了金牌，Artsiom Korzun和Jaromir Hamala分别获得银牌和铜牌。

Morling对社区和Decodable提供的评估机器表示感谢，并认为此次挑战赛的成功超出了他的预期。