阿超 > 1brc

1brc

2025-12-24

java

辛勤的蜜蜂永远没有时间的悲哀。——布莱克

1️⃣🐝🏎️ One Billion Row Challenge（1BRC）：用 Java 把 10 亿行跑到飞起的那一次

如果你还记得第一次用 Java 处理海量数据的震撼，那么 1BRC 一定会让你再次血液加速。它的仓库描述这么写：“The One Billion Row Challenge — A fun exploration of how quickly 1B rows from a text file can be aggregated with Java”。这不是一个普通的练习题，而是一场关于现代 Java 极限性能的集体冒险：把一个包含 10 亿行的文本文件在最短时间里按站点聚合，输出每个站点的最小值、平均值和最大值。

状态提示（摘自 README）：挑战在 2024-01-31 UTC 截止，最终榜单已发布；评测由作者在统一环境下完成，目的在于学习与乐趣，而非严苛的微基准科考。

题目长什么样？

数据是气象站的温度观测，每行一个记录，格式为：

1
<string: station name>;<double: measurement>

其中温度值固定一位小数。举个例子（摘自 README）：

1
2
3
4
5
6
7
8
9
10
Hamburg;12.0
Bulawayo;8.9
Palembang;38.8
St. John's;15.2
Cracow;12.6
Bridgetown;26.9
Istanbul;6.2
Roseau;34.4
Conakry;31.2
Istanbul;23.0

你的任务：用 Java 写一个程序，读取文件后按站点名称排序，输出每个站点的最小值、平均值、最大值，格式如下（站点按字母序；数值保留一位小数并按 IEEE 754 的 roundTowardPositive 规则取整）：

1
{Abha=-23.0/18.0/59.2, Abidjan=-16.2/26.0/67.3, ...}

怎么跑起来？（来自 README）

准备好 Java 21，克隆项目后按照脚本运行：

1
2
3
4
5
6
7
8
# 1. 构建
./mvnw clean verify

# 2. 生成 10 亿行数据（约 12 GB！注意磁盘空间）
./create_measurements.sh 1000000000

# 3. 运行基线（baseline）实现
./calculate_average_baseline.sh

项目提供了两个程序：

  • CreateMeasurements：生成随机数据文件 measurements.txt
  • CalculateAverage：计算每个站点的 min/mean/max（基线实现采用 Java Streams，评测环境约 2 分钟）

之后，你就可以在这个基线的基础上尽情优化：并行化、(孵化中的) Vector API、把文件分段内存映射并并发处理、AppCDS、GraalVM、CRaC 等等，只要遵守规则即可。

规则与限制（摘录）

  • 使用 Java（JDK 21），不能依赖外部库，提交需是单个源文件
  • 计算必须在应用“运行时”完成，不能在构建时预处理后把结果固化
  • 站点名：UTF-8 字符串，长度 1–100 字节，不含 ; 和 \n
  • 温度值：-99.9 到 99.9（含），始终一位小数
  • 站点上限：10,000 个唯一名称
  • 文件行尾统一为 \n
  • 输出取整规则：IEEE 754 的 “roundTowardPositive”（向正方向取整）

评测环境也透明公开：统一机器（Hetzner AX161，AMD EPYC 7502P，128 GB RAM），从 RAM 磁盘读取，使用 8 核，hyperfine 测量端到端时间、五次跑取中位（去掉最快/最慢），流程脚本在仓库中可查。

这场“狂欢”有什么意义？

1BRC 的初衷很纯粹：学习、分享、享受优化的乐趣。作者 Gunnar Morling 将其描述为一场“现代 Java 能做到哪儿”的探索。你会在榜单里看到 GraalVM、向量化、零拷贝、字节级解析、GC 参数调优、编译策略选择……各种方案在严格统一的赛道上交锋。结果不止令人惊艳，更有趣的是每个实现背后“如何想到、为何有效”。

仓库的 Discussions 里还有 “Show & Tell”，聚集了其他语言（C、Go、DuckDB、R、.NET、Pinot 等）的实践对照，一次性补足你的性能视野。

代码案例：从“可读”到“可快”

下面给两段示例代码，第一段是“可读”的基线风格，第二段演示如何在输出取整上符合 roundTowardPositive（向正方向取整，Java 用 RoundingMode.CEILING）。它们用于说明思路，非仓库中的提交。

1) 基线思路：用 Streams 聚合

目标：读入 station;temp，用 Map<String, Stats> 累积 min/max/sum/count，最后排序输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
import java.io.IOException;
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.nio.file.Files;
import java.nio.file.Path;
import java.util.*;
import java.util.stream.Stream;

public class CalculateAverage_example {
    static class Stats {
        double min = Double.POSITIVE_INFINITY;
        double max = Double.NEGATIVE_INFINITY;
        double sum = 0.0;
        long count = 0L;
        void add(double x) {
            if (x < min) min = x;
            if (x > max) max = x;
            sum += x;
            count++;
        }
        double mean() { return sum / count; }
    }

    static String roundTowardPositive(double v) {
        // 一位小数，向正方向取整（IEEE 754 roundTowardPositive）
        // Java BigDecimal 的 CEILING 即向正无穷方向
        return BigDecimal.valueOf(v).setScale(1, RoundingMode.CEILING).toPlainString();
    }

    public static void main(String[] args) throws IOException {
        Path file = Path.of(args.length > 0 ? args[0] : "measurements.txt");

        Map<String, Stats> map = new HashMap<>(4096); // 初始容量按站点数估

        try (Stream<String> lines = Files.lines(file)) {
            lines.forEach(line -> {
                int sep = line.indexOf(';');
                if (sep <= 0) return; // 简单健壮性保护
                String station = line.substring(0, sep);
                double temp = Double.parseDouble(line.substring(sep + 1));
                map.computeIfAbsent(station, k -> new Stats()).add(temp);
            });
        }

        // 按字母序输出，格式为 {name=min/mean/max, ...}
        StringBuilder sb = new StringBuilder();
        sb.append('{');
        map.entrySet().stream()
            .sorted(Map.Entry.comparingByKey())
            .forEachOrdered(e -> {
                Stats s = e.getValue();
                sb.append(e.getKey()).append('=')
                  .append(roundTowardPositive(s.min)).append('/')
                  .append(roundTowardPositive(s.mean())).append('/')
                  .append(roundTowardPositive(s.max)).append(", ");
            });

        if (sb.length() > 1) {
            sb.setLength(sb.length() - 2); // 去掉最后的逗号空格
        }
        sb.append('}');
        System.out.println(sb);
    }
}

这段代码的优点是清晰直接；缺点也明显：逐行解析、字符串拆分和 Double.parseDouble() 都有开销。要跑到“飞起”，你需要：

  • 减少对象分配（如复用缓冲区）
  • 避免高频字符串创建（对字节数组做就地解析）
  • 手写更高效的小数解析（避免 Double.parseDouble() 的通用成本）
  • 并行化（但要注意分片边界与聚合开销）
  • 利用 NIO 的 FileChannel#map() 对文件分段内存映射并并发扫描
  • 在合适场景尝试孵化的 Vector API 做 SIMD 优化（比如快速定位分隔符）
  • 在启动与 JIT 层面做功：AppCDS、GraalVM 原生镜像、CRaC 快速启动等

2) 向正方向取整的正确打开方式

根据 README 的规则，输出需要使用 IEEE 754 的 roundTowardPositive。用 Java 的 BigDecimal 可以稳妥实现：

1
2
3
4
5
6
7
8
9
10
11
12
import java.math.BigDecimal;
import java.math.RoundingMode;

public class RoundingDemo {
    static String roundTowardPositive(double v) {
        return BigDecimal.valueOf(v).setScale(1, RoundingMode.CEILING).toPlainString();
    }
    public static void main(String[] args) {
        System.out.println(roundTowardPositive(12.01));   // 12.1
        System.out.println(roundTowardPositive(-12.01));  // -12.0  （向正方向，即靠近 0）
    }
}

注意：RoundingMode.CEILING 是“向正无穷方向”，对负数会向 0 方向靠近，正好符合题目要求。

优化方向灵感（来自 README 的允许范围）

  • 并发：多核读取与计算；注意切片边界上的记录完整性
  • 字节级解析：直接在 byte[] 上找分号与行尾，减少字符串中间态
  • 内存映射：FileChannel#map() 把文件映射到内存，分片并发扫描
  • 向量化：尝试孵化中的 Vector API 做批量扫描（如查找 ; 或 \n）
  • 启动/编译优化：AppCDS、GraalVM、CRaC，缩短启动并提升稳态性能
  • I/O：评测跑在 RAM 磁盘，I/O 开销不是瓶颈，重点在 CPU 与解析逻辑

仓库还贴心地给了火焰图的建议：如果装了 jbang，可以用 async-profiler 的 ap-loader 快速生成 flamegraph，一眼看出热点：

1
2
3
4
5
6
jbang --javaagent=ap-loader@jvm-profiling-tools/ap-loader=start,event=cpu,file=profile.html \
  -m dev.morling.onebrc.CalculateAverage_yourname target/average-1.0.0-SNAPSHOT.jar

# 或直接分析 .java 文件
jbang --javaagent=ap-loader@jvm-profiling-tools/ap-loader=start,event=cpu,file=profile.html \
  src/main/java/dev/morling/onebrc/CalculateAverage_yourname

如何参与这场挑战？（流程摘录）

  • Fork 仓库
  • 复制基线实现，改名为你自己的类（如 CalculateAverage_<your_GH_user>.java），并调整配套脚本
  • 所有实现必须单文件、无外部依赖，并通过测试套件（/test.sh <your_GH_user>）
  • 提交 PR 时附上本机跑分与硬件信息（官方成绩由统一评测环境产生）

详情请从 README 的 “Entering the Challenge” 章节获取最新信息。

评测说明与榜单

作者用统一脚本在同一台机器上跑选手提交，端到端计时，每个提交跑五遍取中位（去掉最慢/最快）。榜单与不同配置的“Bonus Results”（如 32 核、10K 站点集）都在 README 中公开，且不断记录演进。记住：核心目的是学习与快乐，不必拘泥于名次的微小差异。

跨生态的“对照组”

虽然正式挑战仅限 Java，但 Discussions 的 “Show & Tell” 集结了许多有趣的跨语言实践：C、Go、DuckDB、Racket、.NET、Pinot、Snowflake、ClickHouse、QuestDB 等。这就像一次性能“拼图”，让你在不同技术栈里对比同一问题的路径与哲学。

许可证与社区准则

  • License：Apache 2.0
  • Code of Conduct：Be excellent to each other! 学习和乐趣优先。

最后的彩蛋：这为什么会“那么爽”？

1BRC 的爆点在于把“真实的工程挑战”压缩成一个“可对比、可复现、可玩的”赛题。它要求你在严格的输入与输出规则下，调动 Java 的当代武库：JIT/AOT、GC、内存、并发、SIMD、I/O 模型……并最终把复杂性收敛为一种“可读的速度”。

如果你已经跃跃欲试：

  • 先跑一遍基线，理解端到端瓶颈在哪里
  • 用火焰图确认热点，再针对性重写解析与聚合
  • 按规则尝试 GraalVM 或 Vector API 等加速手段
  • 不断复跑与对比，记录每一步优化的收益

当你把 10 亿行跑得越来越快时，你会发现——这不仅是 Java 的胜利，也是你对“性能与工程”的一次深刻理解。

— 参考与原始信息：