← back

collab/1brc

the one billion row challenge

git clone https://git.julia.blue/collab/1brc

Rahul Butaniexp/file-io: `io_uring` mem b/w experiment9e4db4f

back-to-mmap
2 folders8 files

files

misc/
src/
.envrc10 B
.gitignore43 B
Cargo.lock6.9 KiB
Cargo.toml462 B
README.md17.6 KiB
flake.lock2.0 KiB
flake.nix14.1 KiB
rust-toolchain.toml158 B

One Billion Row Challenge

See here.


results

On an E-2378G w/o SMT w/turbo.

namedetailsresult (ms)result: 10k stations (ms)
upstream baselinenix run .#bench.baseline.1br135835 ± 1866169128 ± 1378
upstream #1nix run .#bench.1stAvx10.1br1583 ± 185773 ± 143
baselinecheckpoint/01-baseline58583 ± 97579712 ± 318

how to run?

runnables:

notable impls:

notable inputs:

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:

todo, comparison knobs:

darwin mmap:

notes:

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:

<!-- TODO: distribution of `handle_mm_fault` timings; aggregate timings --> <!-- todo: graphs, graph script --> <!-- todo: switch to issuing the madvise in the background instead of manually hitting pages -->

compare pre-read/pre-populate/no pre:

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:

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:

<!-- tons of wrong information in this thread: https://news.ycombinator.com/item?id=45132710 -->

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:

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)

for AVX512 (64 byte vectors) we never need to fall back

links:

experiments:


file I/O execution strategies:


impls:

opts to try/things to look into:

todo: linux vm on m1 mac