How to Process One Billion CSV Rows in Go: 9 Optimized Solutions

Problem Overview

The One Billion Row Challenge (1BRC) requires reading a 13 GB text file with one billion temperature measurements and computing the minimum, average, and maximum temperature for each weather station. Ben Hoyt solved the challenge in Go using only the standard library, producing nine progressively faster solutions.

Baseline Measurements

Raw I/O cost:

$ time cat measurements.txt > /dev/null
1.05 s (cached)

Word count: <code>$ time wc measurements.txt 55.7 s</code> Simple AWK solution: <code>$ time gawk -b -f 1brc.awk measurements.txt 7 min 35 s</code> Solution 1 – Simple Scanner Uses bufio.Scanner to read lines, strings.Cut to split on ‘;’, strconv.ParseFloat for conversion, and a plain map[string]stats to aggregate. Runtime ≈ 1 min 45 s. <code>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, ok := strings.Cut(line, ";") if !ok { continue } temp, err := strconv.ParseFloat(tempStr, 64) if err != nil { return err } s := stationStats[station] if s.count == 0 { s.min, s.max, s.sum, s.count = temp, temp, temp, 1 } else { if temp < s.min { s.min = temp } if temp > s.max { s.max = temp } s.sum += temp; s.count++ } stationStats[station] = s } // output sorted results … return nil }</code> Solution 2 – Map with Pointer Values Change the map to map[string]*stats to avoid copying structs on each lookup. Runtime drops to ≈ 1 min 31 s. <code>stationStats := make(map[string]*stats) // … s := stationStats[station] if s == nil { stationStats[station] = &stats{min:temp, max:temp, sum:temp, count:1} } else { … }</code> Solution 3 – Hand‑written Float Parser Replace strconv.ParseFloat with a custom byte‑level parser that handles the fixed format [-]N.N . This removes string allocations and reduces runtime to 55.8 s. <code>negative := false i := 0 if tempBytes[i] == '-' { negative = true; i++ } temp := float64(tempBytes[i]-'0') i++ if tempBytes[i] != '.' { temp = temp*10 + float64(tempBytes[i]-'0'); i++ } i++ // skip '.' temp += float64(tempBytes[i]-'0') / 10 if negative { temp = -temp }</code> Solution 4 – Fixed‑Point Integers Store temperatures as tenths of degrees in 32‑bit integers, converting back to float only for output. Runtime improves to 51.0 s. <code>type stats struct { min, max, count int32; sum int64 } // parsing produces an int32 value "temp" // output: mean := float64(s.sum)/float64(s.count)/10 // fmt.Fprintf(..., "%s=%.1f/%.1f/%.1f", station, float64(s.min)/10, mean, float64(s.max)/10)</code> Solution 5 – Remove bytes.Cut Parse the line from the end to locate the semicolon, avoiding the overhead of bytes.Cut . Runtime ≈ 46.0 s. <code>end := len(line) // extract temperature digits from the end, handle optional sign and two‑digit integer part // then station := line[:semicolon] </code> Solution 6 – Manual Chunk Scanning Read the file in 1 MiB chunks, locate the last newline in each chunk, and process the chunk byte‑wise, eliminating bufio.Scanner . Runtime ≈ 41.3 s. <code>buf := make([]byte, 1024*1024) for { n, err := f.Read(buf) if err != nil && err != io.EOF { return err } if n == 0 { break } chunk := buf[:n] newline := bytes.LastIndexByte(chunk, '\n') // process chunk[:newline+1] and keep remaining bytes for next iteration } </code> Solution 7 – Custom Linear‑Probing Hash Table Implement a hand‑rolled hash table with 100 000 pre‑allocated buckets, using FNV‑1a 64‑bit hashing and linear probing. Keys are stored as byte slices to avoid string allocations. Runtime drops dramatically to 25.8 s. <code>type item struct { key []byte; stat *stats } items := make([]item, 100000) // FNV‑1a constants const offset64 = 14695981039346656037 const prime64 = 1099511628211 // hashing loop extracts station name until ';', updates hash, then probes table </code> Solution 8 – Parallel Chunk Processing Split the file into equal‑size parts (one per CPU core), launch a goroutine for each part, and merge the partial maps. This parallel map‑reduce reduces runtime to 24.3 s. <code>parts, _ := splitFile(inputPath, maxGoroutines) resultsCh := make(chan map[string]r8Stats) for _, p := range parts { go r8ProcessPart(inputPath, p.offset, p.size, resultsCh) } // aggregate results from channel </code> Solution 9 – Combined Optimizations + Parallelism Integrate all previous optimizations (pointer map, custom parser, fixed‑point integers, custom hash table) with the parallel processing framework. Final runtime ≈ 3.99 s, processing about 2.5 × 10⁸ rows per second. Key Takeaways Small changes such as using pointer values in maps or hand‑written parsers yield measurable speedups. Custom data structures (e.g., a linear‑probing hash table) can outperform built‑in maps when allocation patterns dominate. Parallelism provides the largest boost, especially when combined with low‑overhead per‑thread code. Even a straightforward solution (≈ 1 min 45 s) may be sufficient for occasional runs, but deep optimization can reduce runtime by an order of magnitude and lower compute cost.