Skip to content
vifair22Public

About

No description, website, or topics provided.

Resources

Stars

0 stars

Watchers

0 watching

Forks

Latest commit

 

History

18 Commits

Folders and files

Repository files navigation

1brc - High-Performance C Solution

C17 implementation of the 1 Billion Row Challenge for x86-64 Linux. Parses a newline-delimited city;temperature file with AVX2, branchless temperature decoding, and per-thread hash tables merged at the end.

Performance

System CPU SIMD Cores/Threads File Size Parse Time Throughput
Linux Ryzen 9 5900XT AVX2 16/32 13.8 GB ~322 ms ~42.8 GB/s

Parse time excludes I/O; the file is mapped and prefaulted before the timer starts. Median of 5 warm runs on an idle machine (318/321/322/322/323 ms). Warm starts map the file in tens of milliseconds, so total wall time is ~330 ms start to exit, output included.

Measurement conditions:

  • Boost clocks sag 5-10% as the package heats. Back-to-back 32-thread runs drift upward; compare variants with interleaved A/B runs or, for anything under ~5%, with cycles per row from micro (below).
  • The DRAM read ceiling, measured by a probe that maps the same file the same way and streams it with pure AVX2 loads, is 43.8-44.4 GB/s at 32 threads and 45.5 GB/s at 16. The difference is SMT contention, not stream count: 32 threads over 16 shared regions, or over one clustered region, also measure ~44. The 32-thread floor for this file is therefore ~313 ms; the parse runs within ~3% of it.
  • Because the 32-thread run sits at the memory ceiling, single-thread compute wins convert to wall clock at a discount. The BZHI key change removed 7.7% of 8-thread cycles and ~4% of 32-thread wall time. Thread scaling: 1.92-1.94x per doubling from 2 to 8 threads, 1.24x from 16 to 32.

Building

Requires GCC or Clang on x86-64 Linux with AVX2, BMI1, and BMI2 (Haswell+, Zen 1+).

BUILD_TYPE=release ./build.sh    # -O3 -march=native
BUILD_TYPE=dev ./build.sh        # -O0 -g
CC=clang BUILD_TYPE=release ./build.sh

Running

Place the input at data/data.txt and run from the repo root:

./build/release/1brc              # per-city stats + timings
./build/release/1brc --challenge  # official output format only

Default output: per-city min, max, mean, and count, plus I/O and parse timings. --challenge prints the official challenge format ({Name=min/mean/max, ...}, names in byte order, one decimal, mean rounded through double arithmetic to match the reference implementation) on stdout and moves diagnostics to stderr.

Output verification

./check.sh                        # or: ./check.sh path/to/1brc

Runs the binary in --challenge mode against each input with a golden file under tests/ and byte-compares. Goldens are cross-validated against lehuyduc/1brc-simd, which matches the official reference implementation. tests/golden_data.txt pairs with the local 13.8 GB data/data.txt and is skipped when that file is absent. Exit 0 on pass, 1 on any mismatch.

Input Format

CityName;12.3
OtherCity;-5.7

One record per line, ;-separated, temperature in [-][d]d.d form (exactly one fractional digit). The file must end with a newline.

Benchmarking

Two tools with different resolutions:

  • bench measures whole-process wall clock. Noise floor on this machine is +/-5%.
  • micro compiles the identical hot path from parse.h, runs it single-threaded and pinned over a synthetic buffer, and reports cycles per row from the PMU. Cycle counts are frequency-invariant, so thermal drift does not affect them; resolution is ~0.1%.

Use micro to decide whether a change helps; confirm on bench. A rejection measured below the instrument's noise floor is not a result: one optimization in the history below (the newline-mask line advance, worth 7% of single-thread cycles) was first recorded as neutral from wall-clock A/B, and that wrong verdict also locked in a wrong NSTREAMS tuning. The two together cost ~15%.

./build/release/bench ./build/release/1brc
./build/release/micro                        # working-set sweep
./build/release/micro --sizes 16k,64m
./build/release/micro --slots 32768          # load-factor sweep
CFLAGS_EXTRA=-DNSTREAMS=2 ./build.sh         # compile-time parameters

micro working-set sweep (single thread, pinned):

Working set Fits in cycles/row instr/row IPC bmiss/row
16 KB L1D 24.4 81.5 3.34 0.020
256 KB L2 24.6 81.7 3.32 0.034
4 MB L3 24.9 81.8 3.28 0.044
64 MB DRAM 25.0 81.8 3.27 0.047

The memory hierarchy is worth ~0.6 cycles per row single-threaded: L1 residency is under 3% faster than streaming from DRAM, so single-thread cost is compute and dependency structure, not memory. Demand L2 misses on the real run are 1.8M for 10^9 rows; the hardware prefetcher covers the input.

Caveats: small working sets let the branch predictor memorize the row sequence (0.020 bmiss/row at 16 KB vs 0.047 in production), so judge branch behavior at DRAM-sized sets. The spread column is the validity check; above a few percent, the run was disturbed and is not comparable.

Optimization history

Each row was measured against the previous state on the same machine. Rows through the SIMD key build used wall-clock A/B; later rows used cycles per row from micro.

Change Parse time Note
Baseline (newline scan + back-probe for ;, 64-byte entries, hash-only equality) 837 ms merged 3 city pairs (hash collision, see Architecture.md)
Arithmetic line advance (no newline scan) 832 ms latency-bound, not instruction-bound
3 interleaved line streams per worker 792 ms breaks the serial per-line chain
Byte-exact keys stored inline in the entry 780 ms fixes the collision bug
One-multiply hash (was 3 multiplies + 6 shifts) ~-14%
Dot-position temperature parse (tzcnt + one multiply) ~-8%
Key = first 16 bytes (no length-dependent load address) ~-24% removes an address-dependent load from the chain
32-byte hot entries + cold side metadata 479 ms halves bytes touched per probe
mmap + MADV_COLLAPSE + MADV_POPULATE_READ 479 ms parse unchanged; warm-start load 2.8 s -> 30 ms
SIMD key build (sliding-mask AND in XMM) 436 ms ~1%
Packed min/max: -max stored beside min, one PMINSW updates both 406 ms -6.4% cycles
Forced unroll of the stream loop (cursors in registers) 406 ms -2% single-threaded
Line advance from the newline mask, not the parsed value shape ~390 ms -7% single-threaded
NSTREAMS 4 -> 1 (the shortened chain inverted the tuning) 385 ms -8% cycles at 32 threads
Table 8192 -> 32768 slots ~375 ms -2.3% cycles; also required for 10,000 stations
Masked key halves via BZHI in scalar registers ~340 ms -6.5% cycles 1T, -7.7% 8T; hash values unchanged
Dynamic chunked work distribution (atomic cursor, 8 MB chunks) ~322 ms removes the straggler tail; run spread 15 ms -> 5 ms

Perf counters, baseline vs current (whole run): instructions 115G -> 81G, cycles 52G -> 41G, branch misses 810M -> 48M.

Rejected changes

Measured and rejected; recorded to prevent retries.

Attempt Result Cause
clang 22 ~8% slower than gcc
gcc PGO -1.4% (cycle harness) reorders the hand-tuned loop
Software prefetch of input neutral hardware prefetcher already covers it
Probe software pipelining (one-iteration prefetch) neutral OoO already covers the probe load
16 workers, no SMT ~12% worse workload is latency-bound
Batched separator scan (64-byte window, k-th ; to k-th line) 0 to -3% records-per-window loop exit is unpredictable; mispredicts 76M -> 204M
Merged delimiter movemask (one VPMOVMSKB + tzcnt/BLSR/tzcnt) +1.5 cyc/row BLSR + second tzcnt land on the line-advance chain
Paired two-line iterations (one 64-byte scan, fixed cadence of 2) +1.1 cyc/row mask combine and shift sit on the carried chain; the movemask removed was already hidden by OoO
SWAR semicolon find (drop the ; movemask) +5 cyc/row +22 instructions from lost load CSE across the fallback
Oversubscription (64/128 ranges on 32 threads) worse context switches and cache dilution exceed the balancing gain
-march=x86-64-v3 -3.8% on current code won by +2.8% on the pre-BZHI code; scheduling interacts with loop shape, re-measure after structural changes

The three structural rewrites (merged movemask, paired iterations, SWAR) bracket the current loop as a local optimum: lengthening the carried chain costs ~1:1 in cycles, and shortening latency elsewhere returns nothing because the out-of-order engine already covers it. Instruction count does not predict either direction.

Two operational notes from the SWAR attempt: a ternary select on "name shorter than 7 bytes" compiles to a branch that mispredicts 0.54 times per row, and this is invisible at a 16 KB working set because the predictor memorizes the benchmark's row sequence.

Thread pinning (-DPIN_THREADS) is worth ~1% and remains opt-in.

Key design points

  • One 32-byte load per line, two delimiters. The load at the line start is compared against ; and \n; the newline mask supplies the line length, so the loop-carried chain is load, compare, movemask, tzcnt, add. Deriving the advance from the parsed value shape is fewer instructions but puts the temperature parse on the carried chain (-7%).
  • Single line stream per worker (NSTREAMS=1). Interleaved streams were worth ~20% when the per-line chain was long; with the short chain they are a net loss. The knob is kept because the optimum is a function of the chain shape. Re-swept after the BZHI change: 1 stream 25.1 cycles/row, 2 streams 26.3.
  • Branchless temperature parse. tzcnt(~word & 0x10101000) locates the dot (digits have bit 4 set, . does not); one multiply gathers hundreds/tens/units. Derivation in Architecture.md.
  • First-16-bytes key with embedded terminator. The key is the first 16 bytes of name;, zero-padded. A name cannot contain ;, so the key is exact identity for names up to 15 bytes; longer names take a cold tail compare. Both 8-byte key halves load at addresses known at line start; BZHI masks them in scalar registers, so only BZHI + ADD + IMUL separate the name length from the table index.
  • One-multiply hash: (key_a + key_b) * 0x9e3779b185ebca87 >> 29. Equality is decided by key bytes, never the hash.
  • 32-byte hot entries, cold side metadata. Two entries per cache line; name pointer/length in a parallel array touched only on insert, long-name probes, and merge.
  • One read-modify-write per row. The maximum is stored negated beside the minimum, so one PMINSW updates both extremes, and sum, count, and minmax update as a single aligned 16-byte load/PADDQ/PMINSW/blend/store.
  • Zero-copy input. The file is mapped read-only. MADV_COLLAPSE rewrites the page cache into large folios (one-time cost, persists across runs); MADV_POPULATE_READ prefaults so the timed phase takes no faults. The last few lines are re-parsed from a padded heap copy because SIMD reads overrun up to 32 bytes and mappings have no padding after EOF.
  • Dynamic work distribution. Workers pull 8 MB line-aligned chunks from a shared atomic cursor. Static equal ranges leave a straggler tail (cores do not run at equal speed; perf showed ~28 of 32 CPUs utilized). Chunk size is flat across 4-16 MB.
  • SMT on (one worker per logical CPU): ~12% faster than one per core.

Robustness

  • Hash collisions. The baseline compared hash+length only; three real city pairs collided and were silently merged. Equality now compares key bytes. Analysis in Architecture.md.
  • Table overflow. The probe loop terminates only if an empty slot exists. 32768 slots hold the challenge maximum of 10,000 stations at 30% load; a guard on the insert path refuses the insert that would fill the table, so oversized inputs exit non-zero with a diagnostic instead of spinning. Guard cost: 52,940 instructions per 78.8 G (0.00007%), once per distinct station rather than once per row. The aggregate table carries the same guard, since the union of worker keys can exceed any single worker's count. Verified with a 1024-slot build against a 9000-station file.

Comparison with other implementations

Same machine, same 13.8 GB / 413-station file, warm page cache, total wall clock per process, 5 interleaved rounds after an untimed warm-up. Each project built per its own documentation; austindonisan and lehuyduc run with 32 threads as their docs prescribe on SMT machines. Both were tuned for the official 8-core evaluation server.

Implementation Language Min Mean
this repo C 0.32 s 0.33 s
lehuyduc/1brc-simd C++ 0.35 s 0.38 s
austindonisan/1brc C 0.49 s 0.51 s
dannyvankooten/1brc C 0.74 s 0.76 s

Round-by-round against lehuyduc (fastest known native solution):

Round 1 2 3 4 5 min mean
this repo 0.33 0.32 0.34 0.33 0.33 0.32 0.33
lehuyduc 0.36 0.40 0.42 0.35 0.37 0.35 0.38

At the start of the optimization history this repo measured 433 ms minimum against lehuyduc's 397. The compute difference at 8 threads (below the memory ceiling): 24.9 G cycles vs 28.8 G for the same billion rows, IPC 3.28 vs 2.46. lehuyduc's batched scan retires 13% fewer instructions but stalls more.

Repository Layout

1brc.c          - I/O, threading, merge, output
parse.h         - Hot path, shared by 1brc.c and micro.c
bench.c         - Whole-process wall-clock benchmark
micro.c         - Cycle-accurate microbenchmark of the hot loop
build.sh        - Build script
check.sh        - Output verification against tests/ goldens
Architecture.md - Pipeline, hot-loop dataflow, probe design, derivations
data/           - Input files (data.txt, data_small.txt)
tests/          - Golden outputs for check.sh

parse.h exists so micro compiles the identical inlined code the real program runs; a hot path measured in a different translation unit has different inlining and register allocation and is a different program.

About

No description, website, or topics provided.

Resources

Stars

0 stars

Watchers

0 watching

Forks

Releases

Packages

Contributors

Languages