collab/1brc
the one billion row challenge
git clone https://git.julia.blue/collab/1brc
9e4db4f
back-to-mmap
files
| misc/ | |
| src/ | |
| .envrc | 10 B |
| .gitignore | 43 B |
| Cargo.lock | 6.9 KiB |
| Cargo.toml | 462 B |
| README.md | 17.6 KiB |
| flake.lock | 2.0 KiB |
| flake.nix | 14.1 KiB |
| rust-toolchain.toml | 158 B |
One Billion Row Challenge
See here.
results
On an E-2378G w/o SMT w/turbo.
| name | details | result (ms) | result: 10k stations (ms) |
|---|---|---|---|
| upstream baseline | nix run .#bench.baseline.1br | 135835 ± 1866 | 169128 ± 1378 |
| upstream #1 | nix run .#bench.1stAvx10.1br | 1583 ± 18 | 5773 ± 143 |
| baseline | checkpoint/01-baseline | 58583 ± 975 | 79712 ± 318 |
how to run?
runnables:
nix run .#bench.<impl name>.<input name>- benchmarks a particular implemetnation on a particular input
- i.e.
nix run .#bench.baseline.small
nix run .#testRunners.<input name> -- <args to run an implementation>- tests that the implementation's outputs match reference outputs, for a particular input
nix run .#testRunners.all -- <args to run an implementation>- test an implementation on all inputs
- also accessible as
nix run .#testRunners
nix run .#benchRunners.<input name> -- <args to run an implementation>- benchmarks (
hyperfine) the implementation when run on a particular input
- benchmarks (
nix run .#impls.<impl name>- run a particular implementation
- you probably do not want to do this directly (impls expect
measurements.txtin cwd)- using
.#testRunner/.#benchRunneror.#bench.<impl name>.<input name>will handle this for you
- using
notable impls:
baseline: baseline Java implementation from upstream1stNative: 1st place Java implementation, compiled (graalvm) for the current CPU (build time)1stAvx2: ^ but compiled forx86_64-v31stAvx10: ^ but compiled forx86_64-v4(AVX512)1stASIMD: ^ but compiled forarmv8.1-a(ASIMD, no SVE/SVE2)this-avx10:this-avx2:
notable inputs:
1br: default billion row input1br-many-stations: billion row input with 10K stationssmall: 100K row input
details
baseline
mem bandwidth testing
timings:
0. no-op: 460.9 µs ± 37.6 µs
- mmap:
- 1 thread:
597.8 µs ± 52.9 µs- 8 threads:762.0 µs ± 121.9 µs - read:
- read avx512:
mmap stuff, linux:
-
FilePmdMapped
-
page cache huge pages?
-
look at
/proc/<pid>/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(kernel6.12.59w/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
- 1 thread:
-
2x E5-2699 v4(kernel6.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:
file =/tmp/_1br/1br/measurements.txt# `/dev/shm/measurements.txt` performs worse (??) NUM_THREADS =20hyperfine \" $ 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 " # <warmup> NUM_THREADS =20NUMA =1hyperfine \" $ 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 (!)
- commands:
- 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 threadsabove but withREPEAT=10and 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)
- (same as
- 20 threads, 100x repeat:
- (same as
20 threadsabove but withREPEAT=100and no--min-runsor--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)
- no hugetlbfs (4K pages) mmap: 12316ms
- (same as
- 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..
- 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
- mem 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=100and--min-runs 3and 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)
- (same as above but with
- note:
(1000ms / 345ms) * 13795366173 bytescomes out to 39.871 GB/s, matching the measured memory bandwidth for the system
- mem b/w:
-
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
- caution: may be specific to
- 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..
- after all the page faults have happened, regular page-sized
todo, comparison knobs:
- madv Sequential hint or not
- no preread or manual preread or madv LinuxPopulateRead
- thp or not
darwin mmap:
-
see guidance on
mmap- should try just reading the file in chunks instead of
mmap-ing
- should try just reading the file in chunks instead of
-
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
mmaps 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)
- using one
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:
250mb.2r.no-preload.ftf.gz+NUM_THREADS=1 REPEAT=2250mb.2r.manual-preread.ftf.gz+NUM_THREADS=1 REPEAT=2 PREREAD=1+ (has a background thread go and access each page)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_faultcalls in the profile matches the number of minor faults we see inperf stat!- for
madv-popwe don't see separateasm_exc_page_faultbut we do see thehandle_mm_faultcalls that correspond (underdo_madvise)
- for
- comparing where the
handle_mm_faultcalls are across the profiles is (imo) instructive:- spread exclusively throughout the 1st execution of
process - a few in the start of the 1st execution of
process, the vast majority grouped together in the background thread - all under the
madvisesyscall, beforeprocessruns
- spread exclusively throughout the 1st execution of
- comparing how long it takes the first
processinvocation vs the 2nd follows one's expectations:- 158.844ms vs. 90.881ms
- 117.508ms vs. 108.613ms
- 105.613ms vs. 112.253ms
- comparing page fault "overhead":
- comparing 1st run vs 2nd run timings above (158ms - 90ms) yields ~68ms
- manual pre-read (naive, manually reading pages) took 75.396ms
madvise(foreground) took 65.954ms
compare pre-read/pre-populate/no pre:
bin =/home/rahul/.target/release/onebrcinp =/dev/shm/measurements.txthyperfine -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:
bin =/home/rahul/.target/release/onebrcinp =/dev/shm/measurements.txthyperfine -P R 1 5--export-json repeat.bench.json \"NUM_THREADS=1 REPEAT={R} $ bin $ inp "
io_uring
links:
- Jens Axboe's original
io_uringtalk - 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 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 of how many entries can fit into a given vector width:
<vector width in bytes>
<num entries that can fit in width>: <count>
- <avg number of bytes>
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
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 in older kernels?)
- io_uring?
- unmap memory maps in background while reducing?
- tree reduce (very minor)
todo: linux vm on m1 mac