幾週前我看到了 One Billion Row Challenge，完全被它迷住了，於是就用 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 的 profiler 來觀察時間都花在哪裡。

更新：有朋友指出我原本自製的雜湊表有個 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，也不用 memory-mapped files。而 3.4 秒，也就是 3.8GB/s，對我來說已經夠快了。作為對比，經過高度優化的最快 Java 解法在我的電腦上跑不到一秒——相當不錯！

外面已經有好幾個其他的 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）。所有結果都是在搭載快速 SSD 與 32GB 記憶體的 linux/amd64 筆電上，使用 Go 1.21.5 測得的。

我的許多解法，以及大多數最快的解法，都假設輸入是合法的。例如，假設氣溫恰好有一位小數。如果輸入不合法，有幾個解法會造成執行時 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

在做 count-words 程式時我就學到，我們做了比實際需要多得多的雜湊運算。每一行，我們都會對字串雜湊兩次：一次是從 map 取值時，一次是更新 map 時。

要避免這一點，我們可以用 map[string]*stats（指標值）並直接更新指標指向的結構，而不是用 map[string]stats 然後去更新雜湊表本身。

不過，我想先用 Go 的 profiler 來確認這一點。在 Go 程式中加入 CPU profiling 只需要幾行程式碼。

$ ./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 的效能分析，測試資料是縮減到一千萬行的輸入檔：

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 秒降到一分鐘以內：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 中，我們兩者都會做。

要平行化這種 map-reduce 問題其實很直觀：把檔案切成大小相近的區塊（每個 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 的開銷並避免「reduce」步驟。

我的成績與 Alexander Yastrebov 的 Go 版本在同一個區間。他的解法看起來和我的很像：把檔案切成區塊、使用自製雜湊表（他甚至也用了 FNV 雜湊），並將氣溫解析為整數。不過，他使用了 memory-mapped files，而我基於可攜性的理由排除了這個做法——我想這就是他的版本稍微快一點的原因。

Thomas Wuerthinger（並歸功於其他人）打造了最快的整體解法，用的是 Java。他的解法在我的電腦上跑不到一秒，幾乎比我的 Go 版本快了 4 倍。除了平行處理與 memory-mapped files 之外，看起來他還使用了展開迴圈、無分支的解析程式碼，以及其他低階技巧。

看起來 Thomas 是 GraalVM 的創辦人兼主要貢獻者，GraalVM 是一個具備 ahead-of-time 編譯、更快的 Java 虛擬機器。所以他在這個領域絕對是專家。做得太好了，Thomas 及其團隊！

結語

這一切有意義嗎？

對於大多數日常的程式設計任務來說，簡單且符合慣例的程式碼通常是最好的起點。如果你只是要計算十億筆氣溫的統計數據，而且只需要算一次，1 分 45 秒大概就夠好了。

但如果你正在打造資料處理管線，如果能讓程式碼快 4 倍，甚至快 29 倍，你不僅能讓使用者更滿意，還能省下大量運算成本——如果系統負載充足，你的運算成本可能只剩原來的 1/4 或 1/29！

或者，如果你正在打造像 GraalVM 這樣的執行環境，或像我的 GoAWK 這樣的直譯器，這種層級的效能就真的很重要：如果你讓直譯器變快，所有使用者的程式也會跟著快上許多。

更何況，能寫出把機器效能榨到極限的程式碼，本身就很有趣。