几周前，我看到了 十亿行挑战，完全被它吸引住了，于是就用 Go 去解题了。

我来得有点晚，原版比赛在一月份就已经结束了，而且是用 Java 做的。我对 Java 本身兴趣不大，但已经有一段时间一直在关注如何优化 Go 代码了。

这个挑战本身特别简单：处理一个包含气象站名称和温度的文本文件，为每个气象站输出最低、平均和最高温度。还有一些让题目更简单的其他限制条件，不过其中和 Java 相关的我都忽略了。

输入示例中的几行是这样的：

Hamburg;12.0
Bulawayo;8.9
Palembang;38.8
St. John's;15.2
Cracow;12.6
...

唯一的难点在于：输入文件有十亿行，大约 13GB 的数据。我之前就已经发现，磁盘 I/O 早已不是瓶颈——在这种程序里，真正拖慢速度的通常是内存分配和解析。

本文将介绍我用 Go 写的九个方案，每一个都比前一个更快。第一个是简单、符合惯用写法的方案，在我的机器上跑了 1 分 45 秒，而最后一个只需要 3.4 秒。行文过程中，我会展示我是如何用 Go 的性能分析工具来定位耗时所在的。

更新：一位朋友指出我最初的自定义哈希表有个 bug：我把哈希表数组大小设成了 100,000，它不是 2 的幂，却又用 hash & (len(items)-1) 来计算哈希下标。结果哈希表远比应有的更空，冲突也多得多。我已经更新了代码和数据——耗时从 3.9 秒降到了 3.4 秒。

九个方案按从慢到快的顺序如下：

• r1：简单、符合惯用写法
• r2：值为指针的 map
• r3：手写解析温度
• r4：定点整数
• r5：去掉 bytes.Cut
• r6：去掉 bufio.Scanner
• r7：自定义哈希表
• r8：并行化 r1
• r9：并行化 r7

我希望每个方案都是仅使用标准库的可移植 Go 代码：不用汇编，不用unsafe，也不用内存映射文件。而 3.4 秒，也就是 3.8GB/s 的速度，对我来说已经足够快了。作为对比，最快的、经过重度优化的 Java 方案在我的机器上跑进了 1 秒以内——已经很不错了！

市面上已经有好几个其他的 Go 解法，至少还有一篇不错的总结文章。我的方案比其中一些要快，但比最快的那个稍慢。不过在写自己的方案之前，我一个都没看过——我希望自己的解法是独立完成的。

如果你只关心数据，可以直接跳到结果表格。

基线

下面是几项基线测试，先给大家一个直观感受。首先，仅仅用 cat 读取 13GB 数据需要多久：

$ time cat measurements.txt >/dev/null
0m1.052s

注意这是五次取最好成绩的结果，所以文件是允许被缓存的。Linux 是否会把整整 13GB 都留在磁盘缓存里我也不确定，不过第一次跑花了将近 6 秒，想来应该是缓存住了。

作为对比，对文件做点实际处理就要慢得多：wc 就花了将近一分钟：

$ time wc measurements.txt 
 1000000000  1179173106 13795293380 measurements.txt
0m55.710s

如果要为这个实际问题写个简单的解法，我大概会先用 AWK。这个解法用的是 Gawk，因为用它的asorti 函数来给输出排序更方便。我用了 -b 选项来开启“按字节处理字符”模式，这样会快一点：

$ time gawk -b -f 1brc.awk measurements.txt >measurements.out
7m35.567s

我相信哪怕用一个简单的 Go 方案也能轻松打败 7 分钟，那就从这里开始吧。

我会先优化单核顺序执行的版本（方案 1-7），然后再做并行化（方案 8 和 9）。所有结果都是在 Go 1.21.5、搭载高速 SSD 和 32GB 内存的 linux/amd64 笔记本上测得的。

我的很多方案，以及大多数最快的方案，都假设输入是合法的。例如，温度恰好有一位小数。如果输入不合法，有几个方案会直接 panic，或者产生错误的结果。

方案 1：简单、符合惯用写法的 Go

我希望第一个版本是用 Go 标准库工具写的简单、直白的代码：用bufio.Scanner逐行读取，用strings.Cut按 ';' 分割，用strconv.ParseFloat解析温度，再用普通的 Go map 来汇总结果。

我会把第一个方案的代码完整贴出来（之后的方案就只展示关键部分）：

func r1(inputPath string, output io.Writer) error {
    type stats struct {
        min, max, sum float64
        count         int64
    }

    f, err := os.Open(inputPath)
    if err != nil {
        return err
    }
    defer f.Close()

    stationStats := make(map[string]stats)

    scanner := bufio.NewScanner(f)
    for scanner.Scan() {
        line := scanner.Text()
        station, tempStr, hasSemi := strings.Cut(line, ";")
        if !hasSemi {
            continue
        }

        temp, err := strconv.ParseFloat(tempStr, 64)
        if err != nil {
            return err
        }

        s, ok := stationStats[station]
        if !ok {
            s.min = temp
            s.max = temp
            s.sum = temp
            s.count = 1
        } else {
            s.min = min(s.min, temp)
            s.max = max(s.max, temp)
            s.sum += temp
            s.count++
        }
        stationStats[station] = s
    }

    stations := make([]string, 0, len(stationStats))
    for station := range stationStats {
        stations = append(stations, station)
    }
    sort.Strings(stations)

    fmt.Fprint(output, "{")
    for i, station := range stations {
        if i > 0 {
            fmt.Fprint(output, ", ")
        }
        s := stationStats[station]
        mean := s.sum / float64(s.count)
        fmt.Fprintf(output, "%s=%.1f/%.1f/%.1f", station, s.min, mean, s.max)
    }
    fmt.Fprint(output, "}\n")
    return nil
}

这个基础方案处理十亿行用了 1 分 45 秒。相比 AWK 方案的 7 分钟，已经有了明显的提升。

方案 2：值为指针的 map

在写统计词频程序时我就发现，我们做的哈希计算比必要的多得多。每一行，我们都会对字符串哈希两次：一次是从 map 中取值时，一次是更新 map 时。

为了避免这种情况，我们可以用 map[string]*stats（值为指针）并直接更新指针指向的结构体，而不是用 map[string]stats 去更新哈希表本身。

不过，我想先用 Go 的性能分析工具确认一下。给 Go 程序加上 CPU 分析只需要几行代码。

$ ./go-1brc -cpuprofile=cpu.prof -revision=1 measurements-10000000.txt >measurements-10000000.out
Processed 131.6MB in 965.888929ms
$ go tool pprof -http=: cpu.prof
...

这些命令生成了方案 1 在一个缩减到 1000 万行的输入文件上的分析报告：

map 操作占了整整 30% 的时间：赋值占 12.24%，查询占 17.35%。如果改用指针值，我们应该能省掉大部分 map 赋值的耗时。

顺带一提，这张分析图也告诉我们其余时间都花在了哪里：

• 用 Scanner.Scan 扫描行
• 用 strings.Cut 查找 ';'
• 用 strconv.ParseFloat 解析温度
• 调用 Scanner.Text，它会为每一行分配一个字符串

不管怎样，我的第二个方案只是对 map 操作做了一点小调整：

stationStats := make(map[string]*stats)
scanner := bufio.NewScanner(f)
for scanner.Scan() {
    // ...
    s := stationStats[station]
    if s == nil {
        stationStats[station] = &stats{
            min:   temp,
            max:   temp,
            sum:   temp,
            count: 1,
        }
    } else {
        s.min = min(s.min, temp)
        s.max = max(s.max, temp)
        s.sum += temp
        s.count++
    }
}

在常见情况下——气象站已经存在于 map 中时，我们现在只做一次 map 操作，s := stationStats[station]，这样对气象站名称的哈希和哈希表访问就只需要做一次。如果它已经在 map 里——在十亿行数据中这是绝大多数情况——我们就直接更新已有的指针指向的结构体。

提升不算巨大，但也聊胜于无：在 map 中使用指针值让耗时从 1 分 45 秒降到了 1 分 31 秒。

方案 3：去掉 strconv.ParseFloat

我的第三个方案开始有点硬核了：不再用 strconv.ParseFloat，而是用手写代码来解析温度。标准库函数要处理大量我们根本不需要的边界情况，而我们的输入温度格式很简单：1.2 或 34.5 这样的 2 到 3 个字符（有些前面带负号）。

而且，strconv.ParseFloat 需要的是 string 参数，现在既然不再调用它，我们就可以直接使用 Scanner.Bytes 返回的字节切片，而不用通过 Scanner.Text 分配并拷贝一个字符串了。

现在我们这样解析温度：

negative := false
index := 0
if tempBytes[index] == '-' {
    index++
    negative = true
}
temp := float64(tempBytes[index] - '0') // parse first digit
index++
if tempBytes[index] != '.' {
    temp = temp*10 + float64(tempBytes[index]-'0') // parse optional second digit
    index++
}
index++ // skip '.'
temp += float64(tempBytes[index]-'0') / 10 // parse decimal digit
if negative {
    temp = -temp
}

代码不算漂亮，但也算不上什么高深技术。这一步让耗时从 1 分 31 秒降到了 1 分钟以内：55.8 秒。

方案 4：定点整数

在很久以前，浮点指令比整数指令要慢得多。如今，浮点只比整数慢一点点，但如果能避免，还是值得一试的。

对于这个问题，每个温度都只有一位小数，所以很容易用定点整数来表示。比如，我们可以把 34.5 表示成整数 345。然后在最后打印结果之前，再把它们转回浮点数。

所以我的第四个方案基本上和方案 3 一样，只是 stats 结构体的字段改成了这样：

type stats struct {
    min, max, count int32
    sum             int64
}

然后，打印结果时需要除以 10：

mean := float64(s.sum) / float64(s.count) / 10
fmt.Fprintf(output, "%s=%.1f/%.1f/%.1f",
    station, float64(s.min)/10, mean, float64(s.max)/10)

我对最低和最高温度用了 32 位整数，因为最高大概也就 500 左右（也就是 50 摄氏度）。也可以用 int16，但根据以往经验，现代 64 位 CPU 处理 16 位整数时会比处理 32 位稍慢一些。我刚刚测试时似乎没有测出可感知的差异，但还是选择了 32 位。

改用整数让耗时从 55.8 秒降到了 51.0 秒，算是个小小的胜利。

方案 5：去掉 bytes.Cut

为了做方案 5，我又录了一份性能分析（针对方案 4）：

好吧，现在越来越难了。map 操作占了大头，要换成自定义哈希表会有点棘手，去掉 bufio.Scanner 也是。先拖延一下，把 bytes.Cut 去掉再说。

我想到一个省时的简单办法。看看这样一行，比如：

New Orleans;11.7

从末尾开始解析温度并在那里找到 ';'，要比从头扫描整个气象站名称去找 ';' 更快。下面这段不太好看的代码就是这么做的：

end := len(line)
tenths := int32(line[end-1] - '0')
ones := int32(line[end-3] - '0') // line[end-2] is '.'
var temp int32
var semicolon int
if line[end-4] == ';' {          // positive N.N temperature
    temp = ones*10 + tenths
    semicolon = end - 4
} else if line[end-4] == '-' {   // negative -N.N temperature
    temp = -(ones*10 + tenths)
    semicolon = end - 5
} else {
    tens := int32(line[end-4] - '0')
    if line[end-5] == ';' {      // positive NN.N temperature
        temp = tens*100 + ones*10 + tenths
        semicolon = end - 5
    } else {                     // negative -NN.N temperature
        temp = -(tens*100 + ones*10 + tenths)
        semicolon = end - 6
    }
}
station := line[:semicolon]

去掉 bytes.Cut 让耗时从 51.0 秒降到了 46.0 秒，又是一个小胜利。

方案 6：去掉 bufio.Scanner

现在我们要尝试去掉 bufio.Scanner。想一想，为了找到每一行的末尾，scanner 必须遍历所有字节去找换行符。之后我们又要再次处理其中很多字节来解析温度和查找 ';'。所以我们试着把这些步骤合并起来，把 bufio.Scanner 彻底抛弃掉。

在方案 6中，我们分配一个 1MB 的缓冲区来分块大批量读取文件，在每个块中寻找最后一个换行符，以确保不会把一行从中间切断，然后再逐块处理。代码大概是这样：

buf := make([]byte, 1024*1024)
readStart := 0
for {
    n, err := f.Read(buf[readStart:])
    if err != nil && err != io.EOF {
        return err
    }
    if readStart+n == 0 {
        break
    }
    chunk := buf[:readStart+n]

    newline := bytes.LastIndexByte(chunk, '\n')
    if newline < 0 {
        break
    }
    remaining := chunk[newline+1:]
    chunk = chunk[:newline+1]

    for {
        station, after, hasSemi := bytes.Cut(chunk, []byte(";"))
        // ... from here, same temperature processing as r4 ...

去掉 bufio.Scanner、改用自己的扫描逻辑让耗时从 46.0 秒降到了 41.3 秒。又是一个小胜利，但有总比没有好。

方案 7：自定义哈希表

方案 7才是真正动真格的地方。我们要实现一个自定义哈希表来替代 Go 的 map。这样做有两个好处：

1. 我们可以在查找 ';' 的同时对气象站名称做哈希，避免对字节处理两遍。
2. 我们可以在哈希表中把每个键存为字节切片，从而避免把每个键都转换成 string（那会为每一行都分配内存并拷贝）。

我曾写过如何在 C 中实现哈希表，也曾在 Go 中实现过一个自定义的“counter”哈希表，这次的实现就是从那里搬过来的。

这是一个简单的实现，使用了 FNV-1a 哈希算法和线性探测：如果发生冲突，就使用下一个空槽。

为了简化，我直接预分配了大量哈希桶（我用了 131,072，是 2 的幂），这样就不用写扩容逻辑了。如果表超过一半被占满，我的代码会直接 panic。我测得哈希冲突率大约只有 0.2%。

这次的代码要多得多——包括哈希表的初始化、哈希计算本身，以及表的探测和插入：

// The hash table structure:
type item struct {
    key  []byte
    stat *stats
}
const numBuckets = 1 << 17        // number of hash buckets (power of 2)
items := make([]item, numBuckets) // hash buckets, linearly probed
size := 0                         // number of active items in items slice

buf := make([]byte, 1024*1024)
readStart := 0
for {
    // ... same chunking as r6 ...

    for {
        const (
            // FNV-1 64-bit constants from hash/fnv.
            offset64 = 14695981039346656037
            prime64  = 1099511628211
        )

        // Hash the station name and look for ';'.
        var station, after []byte
        hash := uint64(offset64)
        i := 0
        for ; i < len(chunk); i++ {
            c := chunk[i]
            if c == ';' {
                station = chunk[:i]
                after = chunk[i+1:]
                break
            }
            hash ^= uint64(c) // FNV-1a is XOR then *
            hash *= prime64
        }
        if i == len(chunk) {
            break
        }

        // ... same temperature parsing as r6 ...

        // Go to correct bucket in hash table.
        hashIndex := int(hash & uint64(numBuckets-1))
        for {
            if items[hashIndex].key == nil {
                // Found empty slot, add new item (copying key).
                key := make([]byte, len(station))
                copy(key, station)
                items[hashIndex] = item{
                    key: key,
                    stat: &stats{
                        min:   temp,
                        max:   temp,
                        sum:   int64(temp),
                        count: 1,
                    },
                }
                size++
                if size > numBuckets/2 {
                    panic("too many items in hash table")
                }
                break
            }
            if bytes.Equal(items[hashIndex].key, station) {
                // Found matching slot, add to existing stats.
                s := items[hashIndex].stat
                s.min = min(s.min, temp)
                s.max = max(s.max, temp)
                s.sum += int64(temp)
                s.count++
                break
            }
            // Slot already holds another key, try next slot (linear probe).
            hashIndex++
            if hashIndex >= numBuckets {
                hashIndex = 0
            }
        }
    }

    readStart = copy(buf, remaining)
}

这么多代码的回报也很可观：自定义哈希表让耗时从 41.3 秒一下子降到了 22.1 秒。

方案 8：并行处理分块

在方案 8中，我想加入并行处理。不过，我打算回到第一个方案那种简单、符合惯用写法的代码——它用了 bufio.Scanner 和 strconv.ParseFloat——来做并行化。这样我们就能看出到底是优化更有效还是并行化更有效——而在方案 9 中，我们会两者兼施。

像这样一个MapReduce问题，并行化起来很直接：把文件切成大小相近的块（每个 CPU 核心一块），启动一个线程（在 Go 中就是 goroutine）来处理每一块，最后再把结果合并起来。

大致逻辑如下：

// Determine non-overlapping parts for file split (each part has offset and size).
parts, err := splitFile(inputPath, maxGoroutines)
if err != nil {
    return err
}

// Start a goroutine to process each part, returning results on a channel.
resultsCh := make(chan map[string]r8Stats)
for _, part := range parts {
    go r8ProcessPart(inputPath, part.offset, part.size, resultsCh)
}

// Wait for the results to come back in and aggregate them.
totals := make(map[string]r8Stats)
for i := 0; i < len(parts); i++ {
    result := <-resultsCh
    for station, s := range result {
        ts, ok := totals[station]
        if !ok {
            totals[station] = r8Stats{
                min:   s.min,
                max:   s.max,
                sum:   s.sum,
                count: s.count,
            }
            continue
        }
        ts.min = min(ts.min, s.min)
        ts.max = max(ts.max, s.max)
        ts.sum += s.sum
        ts.count += s.count
        totals[station] = ts
    }
}

splitFile 函数有点繁琐，这里就不贴了。它会查看文件大小，按我们想要的份数进行划分，然后 seek 到每一部分的边界，往结束位置前读取 100 字节并寻找最后一个换行符，以确保每一部分都以完整的一行结束。

r8ProcessPart 函数基本上和 r1 方案一样，只是它一开始会 seek 到所属分片的偏移位置，并通过io.LimitedReader把读取长度限制在分片大小内。处理完成后，它会把自己的统计 map 通过 channel 发回去：

func r8ProcessPart(inputPath string, fileOffset, fileSize int64,
                   resultsCh chan map[string]r8Stats) {
    file, err := os.Open(inputPath)
    if err != nil {
        panic(err)
    }
    defer file.Close()
    _, err = file.Seek(fileOffset, io.SeekStart)
    if err != nil {
        panic(err)
    }
    f := io.LimitedReader{R: file, N: fileSize}

    stationStats := make(map[string]r8Stats)

    scanner := bufio.NewScanner(&f)
    for scanner.Scan() {
        // ... same processing as r1 ...
    }

    resultsCh <- stationStats
}

并行处理输入文件相比 r1 带来了巨大的提升，耗时从 1 分 45 秒降到了 22.6 秒。作为对比，之前“优化但不并行”的版本——方案 7——用了 22.1 秒。所以在这个例子中，优化比并行化还要快一点点，不过两者恰好非常接近。

方案 9：所有优化加上并行化

对于方案 9，也就是最后一次尝试，我们将把从 r1 到 r7 的所有优化与 r8 中的并行化简单地结合起来。

我沿用了 r8 中的 splitFile 函数，其余代码则直接从 r7 复制过来，所以这里没有什么新东西可展示。除了结果……这个最终版本把耗时从 22.6 秒进一步砍到了 3.4 秒，提升巨大。

有意思的是，由于所有真正的处理现在都集中在一个大函数 r9ProcessPart 中，性能分析图已经没那么有用了。现在它看起来是这样：

可以看到，82% 的时间都花在 r9ProcessPart 上，bytes.Equal 占 13%，剩下的 5% 是文件读取。

如果想进一步分析，就不能只停留在图表视图的函数层面，而需要深入到源码视图。下面是内层循环的情况：

我觉得这份报告让人困惑。为什么 if items[hashIndex].key == nil 显示耗时 5.01 秒，而对 bytes.Equal 的调用却只显示 390 毫秒？按理说一次切片查找应该比一次函数调用便宜得多才对？如果你是 Go 性能专家，能帮我解读一下，我洗耳恭听！

不管怎样，我相信肯定还有更疯狂的优化可以做，但我决定就到此为止了。以 3.4 秒处理十亿行，也就是每秒 2.9 亿行的速度，对我来说已经足够好了。

结果汇总

下面是将我所有的 Go 方案汇总在一处的表格，此外还有最快的 Go* 方案和最快的 Java 方案。每个结果都是在同一个十亿行输入上运行五次取最好成绩的时间。

2025 年 12 月更新：François Pons 创建了一个Go 版本，看起来比 AY 版本还要快一些，至少在 Go 1.25 上是如此。除其他优化外，它使用 sync/atomic 来最大限度地减少 map 开销并避免“归约”步骤。

我的成绩和Alexander Yastrebov 的 Go 版本在同一量级。他的方案看起来和我很像：把文件分块、使用自定义哈希表（他甚至也用了 FNV 哈希）、并把温度当作整数来解析。不过，他用了内存映射文件，而出于可移植性的考虑我把它排除了——我想这就是他的方案稍快一点的原因。

Thomas Wuerthinger（以及其他贡献者）为原始挑战创作了 Java 的最快整体解法。在我的机器上，他的方案跑进了 1 秒以内，几乎比我的 Go 版本快 4 倍。除了并行处理和内存映射文件，看起来他还用了循环展开、无分支解析代码以及其他底层技巧。

Thomas 似乎是 GraalVM 的创始人以及重要贡献者，GraalVM 是一个支持预先编译的、更快的 Java 虚拟机。所以他无疑是该领域的专家。干得漂亮，Thomas 和他的团队！

最后的感想

这有意义吗？

对于大多数日常编程任务来说，简单、符合惯用写法的代码通常是最好的起点。如果你只是需要计算一次十亿条温度数据的统计结果，1 分 45 秒大概也够用了。

但如果你在构建一条数据处理流水线，能够让代码快 4 倍，甚至 29 倍，不仅能让用户更满意，还能省下大量计算成本——如果系统负载很高，你的计算成本可能就只有原来的 1/4 甚至 1/29！

或者，如果你在构建像 GraalVM 这样的运行时，或是像我的 GoAWK 这样的解释器，这种级别的性能就真的很重要：如果你让解释器变快了，你所有用户的程序也会随之快上那么多。

再说了，能写出把机器性能压榨到极致的代码，本身就很有趣。