2024 年開年，Java “十億行挑戰(zhàn)”（1BRC）火爆外網(wǎng)。該挑戰(zhàn)賽要求開發(fā)者編寫一個(gè) Java 程序，從一個(gè)包含十億行信息的文本文件中檢索溫度測量值，并計(jì)算每個(gè)氣象站的最小、平均值和最高溫度?！笆畠|行挑戰(zhàn)”的目標(biāo)是為這項(xiàng)任務(wù)創(chuàng)建最快的實(shí)現(xiàn)，同時(shí)探索現(xiàn)代 Java 的優(yōu)勢。

這項(xiàng)挑戰(zhàn)聽起來很簡單。但十億行代碼實(shí)際是一項(xiàng)龐大的工程，如果以每個(gè)數(shù)字 3 秒的速度數(shù)到 10 億，大約需要 95.1 年！因此該挑戰(zhàn)最大的難度在于，處理文件以在盡可能短的時(shí)間內(nèi)打印輸出：

該挑戰(zhàn)很快在 Hacker News、lobste.rs、Reddit 等社區(qū)掀起熱烈討論，不少開發(fā)者采用 Rust、Go、C 等其他編程語言甚至是數(shù)據(jù)庫參與挑戰(zhàn)。

日前，從業(yè) 20 年的軟件工程師 Ben Hoyt 用 Go 語言參與該挑戰(zhàn)，他一共想出了 9 種解決方案，完成 10 億行數(shù)據(jù)處理的時(shí)間最快只需 4 秒，最慢需要 1 分 45 秒。Ben Hoyt 還給自己提了點(diǎn)限制條件：每種方法都僅使用 Go 標(biāo)準(zhǔn)庫以保證可移植性，不涉及程序集、不涉及 unsafe、不涉及內(nèi)存映射文件。跟其他作者的發(fā)現(xiàn)相比，Ben Hoyt 的解決方案不是最慢的、但也沒能占據(jù)榜首。不過最重要的是，他的解跟其他參賽者的思路都不一樣，這種獨(dú)立性可能更具價(jià)值。

以下是 Ben Hoyt 用 Go 語言編寫的九種解決方案，每個(gè)方案都比前一個(gè)速度更快，概要如下：

• 方案一：簡單且常見
• 方案二：帶指針值的 map
• 方案三：手動解析溫度
• 方案四：定點(diǎn)整數(shù)
• 方案五：去掉 bytes.Cut
• 方案六：去掉 bufio.Scanner
• 方案七：自定義哈希表
• 方案八：并行化方案一
• 方案九：并行化方案七

基線性能

首先通過幾條基線建立對這個(gè)任務(wù)的初步認(rèn)識，看看使用 cat 讀取 13 GB 的數(shù)據(jù)需要多長時(shí)間：

$ time cat measurements.txt >/dev/null0m1.052s

這里 Ben Hoyt 一共測試了五次，所以實(shí)際上文件是被緩存過的?？雌饋?Linux 是允許把完整的 13 GB 數(shù)據(jù)都保留在磁盤緩存中，因?yàn)榈谝淮尾僮骰私咏?6 秒時(shí)間，之后速度開始直線上升。

相比之下，對文件實(shí)際執(zhí)行某些操作則要慢得多，wc 幾乎需要整整一分鐘：

$ time wc measurements.txt 1000000000 1179173106 13795293380 measurements.txt0m55.710s

要快速為這個(gè)問題找個(gè)簡單的方案，Ben Hoyt 可能會先從 AWK 開始。這種方法使用 Gawk，因?yàn)槠渲械?asorti 函數(shù)可以輕松對輸出進(jìn)行排序。Ben Hoyt 還加上了 -b 選項(xiàng)來使用“將字符當(dāng)作字節(jié)”模式，這樣能讓速度更快一些：

$ time gawk -b -f 1brc.awk measurements.txt >measurements.out7m35.567s

事實(shí)證明哪怕是最簡單粗暴的 Go 方法，也能在 7 分鐘左右搞定問題。下面就以此為基礎(chǔ)摸索答案序列。

Ben Hoyt 首先優(yōu)化出按序單核版本（方案 1 到 7），之后再對其做并行化調(diào)整（方案 8 和 9）。得到的所有結(jié)果都是在配備高速 SSD 驅(qū)動器和 32 GB 內(nèi)存的 linux/amd64 筆記本電腦上，配合 Go 1.21.5 版本得到的。

Ben Hoyt 的許多方案和其他參與者給出的大部分最快方案，都會假設(shè)有效輸入。例如溫度數(shù)值只保留一位小數(shù)。如果輸入無效，那么這幾種方案可能會引發(fā)運(yùn)行時(shí)故障或產(chǎn)生錯誤輸出。

方案一：簡單且常見的 Go 代碼

作為第一種方案，Ben Hoyt 的要求就是簡單且直接，只使用 Go 標(biāo)準(zhǔn)庫中的工具：bufio.Scanner 負(fù)責(zé)讀取數(shù)據(jù)行，strings.Cut 通過“；”進(jìn)行分隔，strconv.ParseFloat 用于解析溫度，再加上普通的 Go map 來累積結(jié)果。

在方案一中，Ben Hoyt 完整列出首種方案的所有代碼，對于之后的方案就只給出比較有趣的部分：

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 秒內(nèi)完成 10 億行數(shù)據(jù)的處理。相較于 AWK 方案的 7 分鐘，這明顯是有了質(zhì)的飛躍。

方案二：帶指針值的 map

Ben Hoyt 之前開發(fā)過一款單詞計(jì)數(shù)程序，當(dāng)時(shí)就發(fā)現(xiàn)實(shí)際執(zhí)行的哈希處理比理論需要的數(shù)量要多得多。對于每一行，我們都會對字符串執(zhí)行兩次哈希處理：第一次用于從 map 中獲取值，第二次則是更新該 map。

為了避免這種情況，我們可以使用 map[string]*stats（指針值）并更新指向的 struct，而不再使用 map[string]stats 并更新哈希表本體。

這里，Ben Hoyt 首先想到用 Go 分析器來做確認(rèn)。只需幾行代碼，即可將 CPU 分析添加到 Go 程序當(dāng)中。

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

通過在精簡后的 1000 萬行輸入文件上運(yùn)行，這些命令為方案一生成了以下概覽：

Map 操作占用了整整 30% 的時(shí)間：其中 12.24% 用于分配，17.35% 用于查找。所以只要使用指針值，我們應(yīng)該就能消除大部分 map 分配時(shí)間。

順帶一提，這張概覽圖還顯示出其余時(shí)間的具體用途：

• 通過 Scanner.Scan 掃描各行
• 通過 strings.Cut 找到“；”
• 通過 strconv.ParseFloat 解析溫度
• 調(diào)用 Scanner.Text 為該行分配一個(gè)字符串

總的來說，方案二其實(shí)就是對 map 操作做一點(diǎn)小小調(diào)整：

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 中存在氣象站的常見情況下，我們現(xiàn)在只須執(zhí)行一次 map 操作 s := stationStats[station]，也就是說對氣象站名稱進(jìn)行哈希處理并訪問哈希表的過程只需執(zhí)行一次。即在氣象站已存在于 map 內(nèi)的情況（在 10 億行數(shù)據(jù)中占多數(shù)比例），我們會更新現(xiàn)有指向 struct。

雖然這對性能的提升不是太大，但也有一定效果：在 map 中使用指針值，可以將整個(gè)處理時(shí)間由 1 分 45 秒縮短至 1 分 31 秒。

方案三：去掉 strconv.ParseFloat

第三種方案相對比較硬核：用自定義代碼來取代 strconv.ParseFloat 進(jìn)行溫度解析。標(biāo)準(zhǔn)庫函數(shù)會處理大量我們并不需要支持的極端溫度輸入情況，畢竟實(shí)際數(shù)據(jù)格式就是 1.2 或 34.5 這類 2 到 3 位數(shù)字（有些前面再多個(gè)負(fù)號）。

另外，strconv.ParseFloat 會接受一條字符串參數(shù)?，F(xiàn)在我們不需要調(diào)用該參數(shù)，因此可以直接從 Scanner.Bytes 使用字節(jié)切片，而非借助 Scanner.Text 進(jìn)行字符串的分配和復(fù)制。

方法如下：

negative := falseindex := 0if tempBytes[index] == '-' { index negative = true}temp := float64(tempBytes[index] - '0') // parse first digitindex 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 digitif negative { temp = -temp}

不太直觀，但也不至于特別難理解。方案三的處理時(shí)長從 1 分 31 秒成功縮短到了 1 分鐘以內(nèi)：55.8 秒。

方案四：定點(diǎn)整數(shù)

曾幾何時(shí)，浮點(diǎn)指令的執(zhí)行速度要比整數(shù)指令慢得多?，F(xiàn)如今速度差距仍然存在，只是沒那么夸張。但如果可以，把浮點(diǎn)轉(zhuǎn)換成整數(shù)還是會提高性能。

對于這個(gè)問題，每項(xiàng)溫度都有一個(gè)小數(shù)位，因此可以輕松用定點(diǎn)整數(shù)進(jìn)行表示。例如，我們可以將 34.5 表示為整數(shù) 345，然后在最終輸出結(jié)果之前再將其轉(zhuǎn)換回浮點(diǎn)數(shù)。

所以方案四跟方案三基本相同，只是將 stats struct 字段調(diào)整如下：

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

之后在輸出結(jié)果時(shí)，再將數(shù)字除以 10：

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

這里 Ben Hoyt 用 32 位整數(shù)表示最低和最高溫度，因?yàn)樽罡邷囟群芸赡苓_(dá)到約 500（即 50 攝氏度）。也可以使用 int16，但從過往的開發(fā)經(jīng)驗(yàn)來看，現(xiàn)代 64 位 CPU 在處理 16 位整數(shù)時(shí)速度要比 32 位整數(shù)更慢。在具體測試中，二者似乎沒有什么可感知的差異，但 Ben Hoyt 還是優(yōu)先選擇了 32 位。

使用整數(shù)之后，運(yùn)行時(shí)間從 55.8 秒縮短到了 51.0 秒，效果也算顯著。

方案五：去掉 bytes.Cut

為了推衍出方案五，Ben Hoyt 先為方案四生成了一份概覽圖：

看來繼續(xù)優(yōu)化是越來越困難了。很明顯，map 操作在其中占主導(dǎo)地位，轉(zhuǎn)為自定義哈希表和去掉 bufio.Scanner 也非易事。所以這里我們先試著去掉 bytes.Cut。

Ben Hoyt 想到一個(gè)簡單的辦法來節(jié)約時(shí)間。以原始文件中的一行數(shù)據(jù)為例：

New Orleans;11.7

直接從后往前查找“；”來解析溫度，其速度會比直接掃描完整氣象站名稱來查找“；”更快。下面這段不怎么優(yōu)雅的代碼就是干這個(gè)的：

end := len(line)tenths := int32(line[end-1] - '0')ones := int32(line[end-3] - '0') // line[end-2] is '.'var temp int32var semicolon intif 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 之后，運(yùn)行時(shí)間從 51.0 秒縮短到了 46.0 秒，又是一場小小的勝利。

方案六：去掉 bufio.Scanner

現(xiàn)在要嘗試去掉 bufio.Scanner 了?？梢韵氲?，要想查找每行的末尾，掃描器必須查看所有字節(jié)并尋找換行符。接下來，就是處理大量字節(jié)來解析溫度并找到“；”。因此，我們可以嘗試把這些步驟整合起來，避免使用 bufio.Scanner。

在方案六中，我們分配了一個(gè) 1 MB 的緩沖區(qū)來讀取大塊文件，查找塊中的最后一個(gè)換行符來確保不會把單行截?cái)?，之后再處理這些單個(gè)塊。具體代碼如下：

buf := make([]byte, 1024*1024)readStart := 0for { 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 并進(jìn)行自主掃描之后，處理時(shí)間從 46.0 秒縮短到了 41.3 秒。效果不算太好，但至少感知得到。

方案七：自定義哈希表

方案七是這次探索中的真正核心。我們會自行建立一個(gè)自定義哈希表，而不再使用 Go map。這樣做有兩大優(yōu)點(diǎn)：

1. 我們可以在查找“；”時(shí)對氣象站名稱進(jìn)行哈希處理，從而避免對字節(jié)的二次處理。
2. 我們可以將哈希表中的每個(gè)鍵存儲為字節(jié)切片，從而避免將各個(gè)鍵轉(zhuǎn)換為 string（將在每一行上分配和復(fù)制）。

在 Go 中自定義哈希表并不復(fù)雜，只需使用帶有線性探測的 FNV-1a 哈希算法即可。如果發(fā)生沖突，則使用下一空槽。

為了簡單起見，Ben Hoyt 預(yù)先分配了大量哈希桶（這里共用到 10 萬個(gè)）以避免編寫邏輯來調(diào)整表的大小。但如果表的占用比例超過了一半，代碼還是會出問題。通過測試，Ben Hoyt 發(fā)現(xiàn)引發(fā)哈希沖突的幾率大概是 2%。

為了解決這次的問題，Ben Hoyt 還添加了一堆新代碼，包括哈希表設(shè)置、哈希本體以及表探測與插入：

// The hash table structure:type item struct { key []byte stat *stats}items := make([]item, 100000) // hash buckets, linearly probedsize := 0 // number of active items in items slicebuf := make([]byte, 1024*1024)readStart := 0for { // ... 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(len(items)-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 > len(items)/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 >= len(items) { hashIndex = 0 } } } readStart = copy(buf, remaining)}

這部分代碼帶來了巨大回報(bào)：自定義哈希表將處理時(shí)長從 41.3 秒縮短到了 25.8 秒。

方案八：并行處理各塊

在方案八中，Ben Hoyt 想引入一些并行性。但為了控制變量，他打算繼續(xù)沿用方案 1 的代碼，畢竟更簡單且常見。方案一中保留了 bufio.Scanner 和 strconv.ParseFloat，這里姑且直接將其并行化。在并行化成功之后，Ben Hoyt 再嘗試引入之后幾種方案的優(yōu)化手段，雙管齊下的結(jié)果就是最終的方案九。

對這類 Map-Reduce 問題進(jìn)行并行化并不困難：把文件拆分成大小相似的多個(gè)塊（每個(gè) CPU 核心對應(yīng)一個(gè)塊）、啟動一個(gè)線程（在 Go 中叫作 goroutine）來處理各個(gè)塊，最后把結(jié)果合并起來即可。

所以總體來看，代碼表示如下所示：

// 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 函數(shù)有點(diǎn)繁瑣，所以這里沒有使用。它負(fù)責(zé)查看文件的大小，除以我們指定的拆分塊數(shù)，然后查找每一塊，在末尾讀取 100 個(gè)字節(jié)并查找最后一個(gè)換行符，借此確保每個(gè)塊在結(jié)尾都保留了整行（未將原始數(shù)據(jù)行截?cái)啵?/span>

r8ProcessPart 函數(shù)與方案 1 基本相同，但它會首先查找各個(gè)塊的偏移并將長度限制為塊大小之內(nèi)（使用 io.LimitedReader）。完成后，它會發(fā)回自己的 stats map：

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}

相較于方案一，并行處理的性能表現(xiàn)出巨大優(yōu)勢，成功將時(shí)間從 1 分 45 秒縮短到了 24.3 秒。相比之下，之前的“優(yōu)化但非并行”版本（即方案七）需要耗費(fèi) 25.8 秒。也就是說并行化比優(yōu)化的性能增強(qiáng)效果更好，而且也簡單得多。

方案九：優(yōu)化加并行

在方案九，也就是最終答案中，我們簡單將之前從方案一到七的所有優(yōu)化方法，跟方案八中的并行化結(jié)合起來。

這里 Ben Hoyt 使用了方案八中的 splitFile 函數(shù)，其余代碼則直接從方案七處復(fù)制而來，所以這里就不再贅述了。從結(jié)果來看，最終方案將處理時(shí)長從 24.3 秒進(jìn)一步縮短到 3.99 秒。

有趣的是，由于所有實(shí)際處理現(xiàn)在都在單一大函數(shù) r9ProcessPart 中進(jìn)行，因此概覽圖就沒什么用了。整個(gè)過程如下所示：

如大家所見，有 82% 的時(shí)間都花在了 r9ProcessPart 上，其中 bytes.Equal 占用了 13%，文件讀取則占用了余下的 5%。

如果想要進(jìn)一步分析，我們就得進(jìn)一步下探到源視圖的層次。下面來看內(nèi)部循環(huán)：

但這份報(bào)告還是有讓人迷惑的地方。為什么 if items[hashIndex].key == nil 顯示消費(fèi)了 5.01 秒，但調(diào)用 bytes.Equal 則只用了 390 毫秒？難道說切片查找就是要比函數(shù)調(diào)用快得多？Ben Hoyt 自己也不太理解，歡迎各位 Go 性能大神在評論區(qū)中答疑解惑。

總而言之，這里肯定還有更大的性能優(yōu)化空間，但 4 秒之內(nèi)處理 10 億行數(shù)據(jù)，也就是每秒 2.5 億行，這對不少開發(fā)者來說已經(jīng)相當(dāng)夠用了。

寫在最后

也許有人會問，折騰這些有意義嗎？

對于大多數(shù)日常編程任務(wù)，使用最簡單、最常見的代碼往往才是王道。哪怕是面對超過 10 億行的溫度統(tǒng)計(jì)數(shù)據(jù)，如果只需要獲得一次答案，那么 1 分 45 秒也絕非不可接受。

但如果我們正在構(gòu)建數(shù)據(jù)處理管線，并且用以上種種方法把代碼執(zhí)行速度提高了 4 倍、甚至是 26 倍，那么不僅用戶體驗(yàn)會更好，也能節(jié)約下大量計(jì)算成本。換言之，系統(tǒng)負(fù)載水平更低，且計(jì)算成本很可能只是原先的 1/4 甚至 1/26！

或者，如果大家正在構(gòu)建像 GraalVM 這樣的運(yùn)行時(shí)，或者像 Ben Hoyt 的 GoAWK 這種解釋器，那這樣的性能差異將極為重要：解釋器的速度越快，一切用戶程序的運(yùn)行速度都將同步提升。

哪怕退一萬步，單純嘗試讓代碼充分發(fā)揮機(jī)器性能本身也是種既有益、也有趣的嘗試，不是嗎？

參考鏈接：

https://benhoyt.com/writings/go-1brc/

https://www.morling.dev/blog/one-billion-row-challenge/