# One Billion Row Challenge See [here](https://github.com/gunnarmorling/1brc). --- ## results > On an [E-2378G](https://www.intel.com/content/www/us/en/products/sku/212262/intel-xeon-e2378g-processor-16m-cache-2-80-ghz/specifications.html) w/o SMT w/turbo. | name | details | result (ms) | result: 10k stations (ms) | |:----:|:-------:|:-----------:|:--------------------------:| | [upstream baseline](https://github.com/gunnarmorling/1brc/blob/db064194be375edc02d6dbcd21268ad40f7e2869/src/main/java/dev/morling/onebrc/CalculateAverage_baseline.java) | `nix run .#bench.baseline.1br` | 135835 ± 1866 | 169128 ± 1378 | | [upstream #1](https://github.com/gunnarmorling/1brc/blob/db064194be375edc02d6dbcd21268ad40f7e2869/src/main/java/dev/morling/onebrc/CalculateAverage_thomaswue.java) | `nix run .#bench.1stAvx10.1br` | 1583 ± 18 | 5773 ± 143 | | [baseline](#baseline) | [`checkpoint/01-baseline`](https://github.com/rrbutani/1brc/tree/checkpoint/01-baseline) | 58583 ± 975 | 79712 ± 318 | ## how to run? runnables: - `nix run .#bench..` + benchmarks a particular implemetnation on a particular input + i.e. `nix run .#bench.baseline.small` - `nix run .#testRunners. -- ` + tests that the implementation's outputs match reference outputs, for a particular input - `nix run .#testRunners.all -- ` + test an implementation on _all_ inputs + also accessible as `nix run .#testRunners` - `nix run .#benchRunners. -- ` + benchmarks (`hyperfine`) the implementation when run on a particular input - `nix run .#impls.` + run a particular implementation + you probably do not want to do this directly (impls expect `measurements.txt` in cwd) * using `.#testRunner`/`.#benchRunner` or `.#bench..` will handle this for you notable impls: - `baseline`: baseline Java implementation from upstream - `1stNative`: 1st place Java implementation, compiled (graalvm) for the current CPU (build time) - `1stAvx2`: ^ but compiled for `x86_64-v3` - `1stAvx10`: ^ but compiled for `x86_64-v4` (AVX512) - `1stASIMD`: ^ but compiled for `armv8.1-a` (ASIMD, no SVE/SVE2) - `this-avx10`: - `this-avx2`: notable inputs: - `1br`: default billion row input - `1br-many-stations`: billion row input with 10K stations - `small`: 100K row input ## details ### baseline ### mem bandwidth testing timings: 0. no-op: `460.9 µs ± 37.6 µs` 1. mmap: - 1 thread: `597.8 µs ± 52.9 µs` - 8 threads: `762.0 µs ± 121.9 µs` 2. read: 3. read avx512: mmap stuff, linux: - FilePmdMapped - page cache huge pages? - look at `/proc//smaps` - https://news.ycombinator.com/item?id=35457499 + `CONFIG_READ_ONLY_THP_FOR_FS` - https://lwn.net/Articles/718102/ + huge pages for filesystems - alternatively: hugetlbfs + https://lwn.net/Articles/374424/ + https://stackoverflow.com/questions/10343124/how-to-use-linux-hugetlbfs-for-shared-memory-maps-of-files + https://stackoverflow.com/a/64914391 + https://www.kernel.org/doc/Documentation/vm/hugetlbpage.txt * `default_hugepagesz=1G hugepages=32` - `i7-10610U` (kernel `6.12.59` w/`CONFIG_READ_ONLY_THP_FOR_FS`) measurements: + 1 thread: * no hugetlbfs (4K pages) mmap: 1326ms (210583 page faults) * 2MB hugetlbfs mmap: 760ms (6656 page faults) * 1GB hugetlbfs mmap: 760ms (89 page faults) + 8 threads: * no hugetlbfs (4K pages) mmap: 786ms * 2MB hugetlbfs mmap: 663.5ms * file I/O (256K buf size): 641ms - `2x E5-2699 v4` (kernel `6.5.0`) measurements: + mem b/w: * theoretical: 2 socket, 4 channel (per socket) DDR4, 2133 MT/s -> 136 GB/s * measured: 120 GB/s + 20 threads: * commands: ```bash file=/tmp/_1br/1br/measurements.txt # `/dev/shm/measurements.txt` performs worse (??) NUM_THREADS=20 hyperfine \ "$bin $file" \ "ONEMMAP=1 $bin $file" \ "TLB_2MB=1 $bin /dev/hugepages/measurements.txt" \ "TLB_1GB=1 $bin /dev/huge-1gb/measurements.txt" \ "DONTMAP=1 $bin $file" vmtouch -e "$file" # NUM_THREADS=20 NUMA=1 hyperfine \ "$bin $file" \ "ONEMMAP=1 $bin $file" \ "TLB_2MB=1 $bin /dev/hugepages/measurements3.txt" \ "TLB_1GB=1 $bin /dev/huge-1gb/measurements3.txt" \ "DONTMAP=1 $bin $file" ``` * no hugetlbfs (4K pages) mmap: 708ms * no hugetlbfs (4K pages) mmap (shared across threads): 719ms * 2MB hugetlbfs mmap: 333ms * 1GB hugetlbfs mmap: 332ms * file I/O (256K buf size): 358ms * NUMA aware: - no hugetlbfs (4K pages) mmap: 760ms (??) - no hugetlbfs (4K pages) mmap (shared across threads): 743ms (??) - 2MB hugetlbfs mmap: 208ms (!) - 1GB hugetlbfs mmap: 214ms (!) - file I/O (256K buf size): 267ms (!) + 88 threads: * (same as above but with all threads on machine) * no hugetlbfs (4K pages) mmap: 673ms * no hugetlbfs (4K pages) mmap (shared across threads): 684ms * 2MB hugetlbfs mmap: 360ms * 1GB hugetlbfs mmap: 350ms * file I/O (256K buf size): 363ms * NUMA aware: - no hugetlbfs (4K pages) mmap: 559ms (!) - no hugetlbfs (4K pages) mmap (shared across threads): 563ms (!) - 2MB hugetlbfs mmap: 202ms (!) - 1GB hugetlbfs mmap: 205ms (!) - file I/O (256K buf size): 214ms (!) + 20 threads, 10x repeat: * (same as `20 threads` above but with `REPEAT=10` and no `--min-runs`) * no hugetlbfs (4K pages) mmap: 2900ms - `(2900 - 708)/9` -> 244ms per read (after first) * no hugetlbfs (4K pages) mmap (shared across threads): 2900ms - `(2900 - 719)/9` -> 242ms per read (after first) * 2MB hugetlbfs mmap: 2591ms - `(2591 - 333)/9` -> 251ms per read (after first) * 1GB hugetlbfs mmap: 2599ms - `(2599 - 332)/9` -> 252ms per read (after first) * file I/O (256K buf size): 2908ms - `(2908 - 358)/9` -> 283ms per read (after first) + 20 threads, 100x repeat: * (same as `20 threads` above but with `REPEAT=100` and no `--min-runs` or `--warmup`) * no hugetlbfs (4K pages) mmap: 22871ms - `(22871 - 708)/99` -> 224ms per read (after first) * no hugetlbfs (4K pages) mmap (shared across threads): 22834ms - `(22834 - 719)/99` -> 223ms per read (after first) * 2MB hugetlbfs mmap: 24256ms - `(24256 - 333)/99` -> 242ms per read (after first) * 1GB hugetlbfs mmap: 24643ms - `(24643 - 332)/99` -> 246ms per read (after first) * file I/O (256K buf size): 27503ms - `(27503 - 358)/99` -> 274ms per read (after first) * NUMA aware: * no hugetlbfs (4K pages) mmap: 12316ms - `(12316 - 760)/99` -> 117ms per read (after first) * no hugetlbfs (4K pages) mmap (shared across threads): 12125ms - `(12125 - 743)/99` -> 115ms per read (after first) * 2MB hugetlbfs mmap: 17033ms - `(17033 - 208)/99` -> 170ms per read (after first) * 1GB hugetlbfs mmap: 17623ms - `(17623 - 214)/99` -> 176ms per read (after first) * file I/O (256K buf size): 20820ms - `(20820 - 267)/99` -> 208ms per read (after first) + re: the memory b/w we're seeing * input file is about 14GB, at ~225ms per read (when not accounting for NUMA) that's ~62 GB/s * with NUMA-awareness (pinning threads, taking care to populate page cache and hugetlbfs this way) we see ~115ms for reads meaning ~118GB/s – a match for the measured memory b/w (`mlc`)! * there is some weirdness in the NUMA results though: - in the 100x repeat, hugetlbfs doesn't see the same speedup from NUMA awareness... I'm not totally clear on how hugepages are allocated; it may be the case that despite the NUMA "awareness" in `f2htlbfs`, pages (allocated when bumping `/sys/kernel/mm/hugepages/hugepages-*/nr_hugepages`?) are allocated such that there's cross-domain memory traffic - not entirely sure what's going on w/file I/O w/NUMA-awareness and why it's not saturating memory b/w.. - `5950X` (kernel: `6.12.61`) + mem b/w: * theoretical: 2 channel DDR4, 3200 MT/s -> 51.2 GB/s * measured: 40.2 GB/s + 32 threads: * `hyperfine "$bin /dev/shm/measurements.txt" "ONEMMAP=1 $bin /dev/shm/measurements.txt" "TLB_2MB=1 $bin /dev/hugepages/measurements.txt" "DONTMAP=1 BUF_SIZE=65536 $bin /dev/shm/measurements.txt" "DONTMAP=1 BUF_SIZE=262144 $bin /dev/shm/measurements.txt" --warmup 3` * no hugetlbfs (4K pages) mmap: 611ms * no hugetlbfs (4K pages) mmap (shared across threads): 632ms * 2MB hugetlbfs mmap: 344ms * file I/O (4K buf size): 387ms * file I/O (8K buf size): 384ms * file I/O (16K buf size): 388ms * file I/O (32K buf size): 392ms * file I/O (65K buf size): 396ms * file I/O (256K buf size): 413ms + 32 threads, 100x repeat: * (same as above but with `REPEAT=100` and `--min-runs 3` and no `--warmup`) * no hugetlbfs (4K pages) mmap: 34818ms - `(34818 - 611)/99` -> 346ms per read (after first) * no hugetlbfs (4K pages) mmap (shared across threads): 34696ms - `(34696 - 632)/99` -> 344ms per read (after first) * 2MB hugetlbfs mmap: 34255ms - `(34255 - 344)/99` -> 343ms per read (after first) * file I/O (4K buf size): 36144ms - `(36144 - 387)/99` -> 361ms per read (after first) * file I/O (8K buf size): 36342ms - `(36342 - 384)/99` -> 363ms per read (after first) + note: `(1000ms / 345ms) * 13795366173 bytes` comes out to 39.871 GB/s, matching the measured memory bandwidth for the system - _verdict_: - after all the page faults have happened, regular page-sized `mmap`'d memory is the fastest - hugeTLB `mmap`'d pages are sometimes a bit slower? not sure why though... + caution: may be specific to `E5-2699 v4`, may be a NUMA side-effect, etc - file I/O is slower (extra syscall) but not by much... + as seen above for one shot file reads, its overhead is less than page fault/PTE setup (when using regular sized pages) + even when using huge TLB pages its pretty close.. todo, comparison knobs: - madv Sequential hint or not - no preread or manual preread or madv LinuxPopulateRead - thp or not darwin mmap: - note: [no darwin "superpage" support on apple silicon](https://gist.github.com/pankkor/8e6b87f914f5a6697469af85fbbbf1bf#macos-super-pages) - see [guidance on `mmap`](https://developer.apple.com/library/archive/documentation/FileManagement/Conceptual/FileSystemAdvancedPT/MappingFilesIntoMemory/MappingFilesIntoMemory.html#//apple_ref/doc/uid/TP40010765-CH2-SW1) + should try just reading the file in chunks instead of `mmap`-ing - findings: + using one `mmap` (shared across threads) is faster than using one per thread * on Linux its about equivalent, separate mmap per thread is a bit faster + just reading the file (no mmap) is significantly faster! * this is true on Linux as well, actually (though its less dramatic) * page fault overhead is brutal I guess? reading the file data multiple times tips things in `mmap`s favor again (but on my M1 this is only true once you get up to >=8 reads of the file!) - (todo: get m1 numbers for each iteration to compare first and steady state numbers for mmap read vs file read) notes: - perf events to assess cross-NUMA domain accesses: ``` mem_load_uops_l3_miss_retired.local_dram mem_load_uops_l3_miss_retired.remote_dram mem_load_uops_l3_miss_retired.remote_fwd mem_load_uops_l3_miss_retired.remote_hitm ``` ##### linux page fault exploration three profiles: 1. `250mb.2r.no-preload.ftf.gz` + `NUM_THREADS=1 REPEAT=2` 2. `250mb.2r.manual-preread.ftf.gz` + `NUM_THREADS=1 REPEAT=2 PREREAD=1` + (has a background thread go and access each page) 3. `250mb.2r.madv-pop.ftf.gz` + `NUM_THREADS=1 REPEAT=2 PREPOP=1` + (uses madvise populate_read to eagerly load in all the pages) observations: - the number of separate `asm_exc_page_fault` calls in the profile matches the number of minor faults we see in `perf stat`! + for `madv-pop` we don't see separate `asm_exc_page_fault` but we do see the `handle_mm_fault` calls that correspond (under `do_madvise`) - comparing where the `handle_mm_fault` calls are across the profiles is (imo) instructive: 1. spread exclusively throughout the 1st execution of `process` 2. a few in the start of the 1st execution of `process`, the vast majority grouped together in the background thread 3. all under the `madvise` syscall, before `process` runs - comparing how long it takes the first `process` invocation vs the 2nd follows one's expectations: 1. 158.844ms vs. 90.881ms 2. 117.508ms vs. 108.613ms 3. 105.613ms vs. 112.253ms - comparing page fault "overhead": 1. comparing 1st run vs 2nd run timings above (158ms - 90ms) yields ~68ms 2. manual pre-read (naive, manually reading pages) took 75.396ms 3. `madvise` (foreground) took 65.954ms compare pre-read/pre-populate/no pre: ```shell bin=/home/rahul/.target/release/onebrc inp=/dev/shm/measurements.txt hyperfine -P N 1 $(nproc) --export-json page_fault.bench.json \ "NUM_THREADS={N} $bin $inp" \ "NUM_THREADS={N} PREREAD=1 $bin $inp" \ "NUM_THREADS={N} PREPOP=1 $bin $inp" \ "NUM_THREADS={N} BACKPOP=1 $bin $inp" ``` compare runtimes for multiple repetitions: ```shell bin=/home/rahul/.target/release/onebrc inp=/dev/shm/measurements.txt hyperfine -P R 1 5 --export-json repeat.bench.json \ "NUM_THREADS=1 REPEAT={R} $bin $inp" ``` #### `io_uring` links: - Jens Axboe's original [`io_uring` talk](https://www.youtube.com/watch?v=-5T4Cjw46ys) - https://unixism.net/loti/ - https://blog.cloudflare.com/missing-manuals-io_uring-worker-pool/ - https://kernel.dk/io_uring.pdf ### hash table can "cheat" (use a priori knowledge of the actual station names in the input to go faster) so long as we don't sacrifice correctness (for inputs that have other stations names we should still give the right answer, even if it comes at extreme performance cost) 413 unique stations names in the actual input (~9 bits worth) > [!NOTE] > (Julia) > Using the [phf](https://docs.rs/phf) crate (attempted in 65c05cd) performs worse than > our custom hash function, even with the naive implementation. It ran around 15% slower > on both HAL and GLaDOS. links: - http://www.0x80.pl/notesen/2023-04-30-lookup-in-strings.html ### SIMD entry processing similar idea as above; imo we're allowed to tailor to patterns in the actual input so long as we're still correct (but slow) for other inputs with newlines, distribution of entry lengths in the actual input: ``` 8 296680 9 13368845 10 56549519 11 126363662 12 200403848 13 157218545 14 130256624 15 100182128 16 61784198 17 58822394 18 37971047 19 19794500 20 11156550 21 4870157 22 11128531 23 3317775 24 1639407 25 35715 29 888692 30 1246628 31 559663 32 2142634 33 2258 ``` [analysis](misc/entry-size-analysis.py) of how many entries can fit into a given vector width: ``` : - 16 0: 180641947 - 16.30481090308443 1: 843762726 - 12.85910339917054 2: 78 - 16.0 32 0: 2258 - 33.0 1: 75066439 - 18.90311886247861 2: 455687003 - 26.846872602157582 3: 4519099 - 31.539677267526116 64 1: 1 - 32.0 2: 426053 - 46.05559636946577 3: 18677350 - 51.90815774186381 4: 167686146 - 56.34797425662106 5: 54414955 - 61.64345858597145 6: 49414 - 63.474379730440766 ``` I'm going to assume AVX2+ (sorry arm NEON processors); 32 bytes per vector means we can handle all but `2258` entries using the "fast" path (vectorized) - i'm comfortable selling this case out; we can have 2258 branch mispredicts and be okay I think for AVX512 (64 byte vectors) we never need to fall back links: - https://mcyoung.xyz/2023/11/27/simd-base64/ - https://branchfree.org/2019/03/06/code-fragment-finding-quote-pairs-with-carry-less-multiply-pclmulqdq/ - https://www.officedaytime.com/simd512e/ + https://www.officedaytime.com/tips/simd.html - http://users.atw.hu/instlatx64/ - https://github.com/WojciechMula/man-intrinsics (todo: package) experiments: - find character index w/`std::simd` (x86 & arm): [godbolt](https://rust.godbolt.org/z/3TdefvWaP) --- file I/O execution strategies: - mmap: + one vs. per thread + manual preread vs madvise prepop vs none + (linux only) hugepages: thp vs hugetlbfs 2MB vs hugetlbfs 1GB vs none - regular file I/O: + buffer size: 4K, 16K, 65K, 256K (sweet spot?), 1M, 4M - io_uring (linux only) --- impls: - baseline - u16 instead of f32 - "branchless" parse instead of regular - hash function change? - mmap - threading - (experiment) avx512 read max roofline test - ... opts to try/things to look into: - file read opts: + huge pages (probably not helpful?) + NUMA-aware page cache set up? * duplicating pages across NUMA domains? (see: [replicated cache](https://lwn.net/Articles/223056/) in older kernels?) + io_uring? + unmap memory maps in background while reducing? - tree reduce (very minor) todo: linux vm on m1 mac