数週間前にOne Billion Row Challengeを見かけて、すっかりnerd-snipedされてしまったので、Goで解いてみることにした。

もともとのコンテストは1月に開催されたので、完全に乗り遅れての参加になる。しかも元はJavaでの企画だった。Java自体にはそれほど興味はないのだが、最適化やGoコードには以前から興味を持っていた。

このチャレンジ自体はいたってシンプルだ。気象観測所の名前と気温が書かれたテキストファイルを処理し、観測所ごとに最小値、平均値、最大値を出力するだけだ。よりシンプルにするための他の制約もいくつかあるが、Java固有のものは無視した。

入力例の数行は次のとおりだ。

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

唯一の難点は、入力ファイルが10億行あることだ。データ量にして約13GBになる。以前に検証したとおり、ディスクI/Oはもはやボトルネックではない――この種のプログラムで速度を落とすのは、たいていメモリ確保とパース処理だ。

この記事では、私がGoで書いた9つの解法を、それぞれ前のものより高速化していった過程とともに紹介する。最初のシンプルでイディオマティックな解法は私のマシンで1分45秒かかるが、最後のものは3.4秒で実行できる。その過程で、Goのプロファイラを使ってどこで時間がかかっているかを確認した方法も示していく。

追記：友人から、当初の自作ハッシュテーブルにバグがあると指摘された。ハッシュテーブルの配列サイズを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の解法が公開されており、少なくとも1つは素晴らしい解説記事もある。私のものは一部の解法より速いが、最速のものよりはわずかに遅い。ただし、これらを書く前に他の解法は一切見ていない。自分の解法は独立して作りたかったからだ。

数値だけ知りたい場合は、結果一覧の表までスキップしてほしい。

ベースライン

まずは前提としていくつかベースラインを測っておこう。最初に、13GBのデータを単に読み込むのにどれくらいかかるか、catを使って測ってみる。

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

なお、これは5回計測したうちのベストタイムで、ファイルがキャッシュされることを前提にしている。Linuxが13GBすべてをディスクキャッシュに保持してくれるかはわからないが、おそらく保持されているのだろう。初回は6秒近くかかっていたからだ。

比較のために、ファイルに対して実際に何か処理をするとかなり遅くなる。wcは1分近くかかる。

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

実際の問題に対するシンプルな解法としては、まずはAWKから始めるだろう。この解法はGawkを使っている。出力のソートがそのasorti関数で簡単にできるからだ。より高速になるよう、「characters as bytes」モードになる-bオプションを使っている。

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

シンプルなGoの解法でも7分は超えられるはずだ。そこから始めよう。

まずは逐次的でシングルコアのバージョン（解法1〜7）を最適化し、その後で並列化（解法8と9）する。すべての結果は、高速なSSDと32GBのRAMを搭載したlinux/amd64のラップトップで、Go 1.21.5を使って計測したものだ。

私の解法の多く、そして最速の解法のほとんどは、入力が妥当であることを前提にしている。たとえば、気温が小数点以下1桁ちょうどであるといったことだ。入力が不正な場合、私の解法のいくつかはランタイムパニックを起こすか、不正な出力を生成する。

解法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
}

この基本的な解法で10億行を処理するのに1分45秒かかる。AWKの解法の7分からは明確な改善だ。

解法2：ポインタを値に持つmap

count-wordsプログラムを作ったときに、必要以上にハッシュ計算をしていることを学んだ。1行ごとに文字列を2回ハッシュしている。mapから値を取得しようとするときに1回、mapを更新するときにもう1回だ。

ただ、まずは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
...

これらのコマンドで、1000万行に縮小した入力ファイルで実行した解法1の次のプロファイルが得られた。

map操作だけで全体の30%を占めている。代入が12.24%、参照が17.35%だ。ポインタを値に使えば、mapへの代入にかかる時間のほとんどをなくせるはずだ。

余談だが、このプロファイル画像からは残りの時間がどこで費やされているかもわかる。

• Scanner.Scanでの行のスキャン
• strings.Cutでの';'の探索
• strconv.ParseFloatでの気温のパース
• Scanner.Textの呼び出し。行の文字列を確保（アロケート）する

いずれにせよ、私の2つ目の解法は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]の1回だけで済む。つまり観測所名のハッシュ計算とハッシュテーブルへのアクセスが1回で済むということだ。すでにmapにある場合――10億行ではこれが大半だが――既存のポインタ先の構造体を更新するだけだ。

劇的な効果ではないが、効果はある。mapでポインタを値に使うことで、実行時間は1分45秒から1分31秒に短縮された。

解法3：strconv.ParseFloatを避ける

私の3つ目の解法からは少しハードコアになる。strconv.ParseFloatの代わりに自作コードで気温をパースするのだ。標準ライブラリの関数は、私たちの入力にあるようなシンプルな気温には不要な、大量のエッジケースに対応している。たとえば1.2や34.5といった2桁か3桁の形式（一部は先頭にマイナス符号が付く）だ。

また、strconv.ParseFloatはstring型の引数を取るが、これを呼び出さなくなったことで、Scanner.Textで文字列を確保してコピーする代わりに、Scanner.Bytesから得られるバイトスライスを直接使えるようになる。

気温のパースは次のように行う。

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：固定小数点整数

昔は、浮動小数点命令は整数命令よりはるかに遅かった。最近は少し遅い程度だが、避けられるなら避ける価値はあるだろう。

この問題では、各気温は小数点以下1桁なので、固定小数点の整数で表すのは簡単だ。たとえば34.5は整数の345として表せる。そして最後に結果を出力する直前で、再び浮動小数点数に戻す。

そこで私の4つ目の解法は基本的に解法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を取り除いてみよう。考えてみれば、各行の末尾を見つけるためにスキャナは改行文字を探してすべてのバイトを走査しなければならない。その後、気温のパースや';'の探索のために、多くのバイトを再び処理することになる。そこでこれらのステップを統合して、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の代わりに自作のハッシュテーブルを実装する。これには2つの利点がある。

1. ';'を探しながら観測所名をハッシュできるため、バイトを二重に処理するのを避けられる。
2. 各キーをハッシュテーブルにバイトスライスとして格納できるため、各キーをstringに変換する必要がなくなる（行ごとに確保とコピーが発生する）。

私はCでハッシュテーブルを実装する方法について書いたこともあるが、Goでも自作の「counter」ハッシュテーブルを実装したことがあり、今回の実装はそこから持ってきたものだ。

これはFNV-1aハッシュアルゴリズムと線形探索（リニアプロービング）を使ったシンプルな実装だ。衝突が起きたら次の空きスロットを使う。

簡略化のため、テーブルのリサイズロジックを書かなくて済むように、大量のハッシュバケットを事前に確保した（2の累乗である131,072個を使った）。テーブルが半分を超えて埋まるとコードはパニックする。計測したところ、ハッシュ衝突は約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問題を並列化するのは straightforward だ。ファイルをほぼ同じサイズのチャンクに分割し（CPUコアごとに1つ）、各チャンクを処理するスレッド（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関数は少し冗長なのでここでは省略する。ファイルサイズを見て、それを分割したい数で割り、それぞれの区切りにシークして、末尾の100バイト手前から読み込み、最後の改行を探すことで各パートが完全な行で終わるようにしている。

r8ProcessPart関数は基本的にr1の解法と同じだが、まずパートのオフセットまでシークし、長さをパートのサイズに制限するところから始まる（io.LimitedReaderを使用）。完了したら、自身の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
}

入力ファイルを並列に処理することで、r1からは大幅な改善となり、実行時間は1分45秒から22.6秒に短縮された。比較のために、前の「最適化済みだが非並列」のバージョンである解法7は22.1秒かかっていた。つまり今回のケースでは、最適化の方が並列化よりわずかに速いが、偶然にも両者は非常に近い結果になった。

解法9：すべての最適化と並列化

解法9では、最後の挑戦として、r1からr7までのこれまでのすべての最適化と、r8で行った並列化を単純に組み合わせる。

r8と同じsplitFile関数を使い、残りのコードはr7からそのままコピーしたので、ここで示す新しいことは特にない。結果を除いては……この最終バージョンで実行時間は22.6秒から3.4秒へと大幅に短縮された。

興味深いことに、実際の処理がすべて1つの大きな関数r9ProcessPartに集約されたため、プロファイルグラフはもはやそれほど役に立たない。現在の見た目は次のとおりだ。

見ての通り、82%の時間がr9ProcessPartで費やされており、bytes.Equalが13%、残りの5%がファイル読み込みに使われている。

さらにプロファイルするなら、グラフビューが提供する関数レベルよりも深く潜り、ソースビューを使う必要がある。内側のループは次のとおりだ。

このレポートは私には混乱を招く。なぜif items[hashIndex].key == nilが5.01秒もかかっていると表示されるのに、bytes.Equalの呼び出しはわずか390msなのだろう。スライスの参照の方が関数呼び出しよりはるかに安いはずだ。もしGoのパフォーマンスに詳しい方で、この解釈を手伝っていただけるなら、ぜひ聞かせてほしい！

いずれにせよ、もっとクレイジーな最適化もできるのだろうが、ここで区切ることにした。10億行を3.4秒で処理する、つまり毎秒2億9千万行という速度で私には十分だった。

結果一覧

以下は、私のすべてのGo解法に加え、最速のGo*と最速のJava解法をまとめた表だ。各結果は、同じ10億行の入力に対して解法を実行した5回中のベストタイムだ。

追記（2025年12月）：François Pons氏がGoバージョンを作成した。少なくともGo 1.25ではAY版よりやや高速に見える。とりわけ、sync/atomicを使ってmapのオーバーヘッドを最小化し、「reduce」ステップを回避している。

私の結果はAlexander Yastrebov氏のGoバージョンとほぼ同じ水準だ。彼の解法は私のものと似ている。ファイルをチャンクに分割し、自作ハッシュテーブルを使い（彼もFNVハッシュを使っている）、気温を整数としてパースする。ただし彼はメモリマップドファイルを使っており、私は移植性の理由で除外していた。おそらくそれが彼の方が少し速い理由だろう。

Thomas Wuerthinger氏（他の方々への謝辞あり）は、オリジナルのチャレンジに対するJavaでの全体最速の解法を作った。私のマシンでは1秒未満で動作し、私のGoバージョンのほぼ4倍の速さだ。並列処理やメモリマップドファイルに加え、ループの展開、分岐なしのパースコード、その他の低レベルなトリックを使っているようだ。

Thomas氏は、事前コンパイルを備えた高速なJava仮想マシンであるGraalVMの創設者であり、主要なコントリビューターのようだ。まさにその分野のエキスパートだ。素晴らしい仕事だ、Thomas氏とチームのみなさん！

最後に

これは果たして意味があるのだろうか？

日々のプログラミング作業の大部分では、シンプルでイディオマティックなコードから始めるのが通常は最善だ。10億件の気温について統計を計算するにしても、答えが一度だけ必要なら、1分45秒でもおそらく十分だろう。

しかしデータ処理パイプラインを構築しているなら、コードを4倍、あるいは29倍にも高速化できれば、ユーザーを喜ばせるだけでなく、計算コストも大幅に節約できる。システムが高負荷で稼働しているなら、計算コストは元の1/4や1/29になる可能性もあるのだ！

あるいはGraalVMのようなランタイムや、私のGoAWKのようなインタプリタを構築しているなら、このレベルのパフォーマンスは本当に重要になる。インタプリタを高速化すれば、ユーザーのすべてのプログラムがその分速くなるのだから。

それに、マシンの性能を最大限に引き出すコードを書くのは、単純に楽しいのだ。