collab/1brc
the one billion row challenge
git clone https://git.julia.blue/collab/1brc
04940aa
main
1{ 2inputs . nixpkgs . url = "github:NixOS/nixpkgs/nixos-unstable" ; 3inputs . flake-utils . url = "github:numtide/flake-utils" ; 4inputs . rust-overlay . url = "github:oxalica/rust-overlay" ; 5 6inputs . rust-overlay . inputs . nixpkgs . follows = "nixpkgs" ; 7 8outputs = inputs :inputs . flake-utils . lib . eachDefaultSystem ( system :let 9pkgs = inputs . nixpkgs . legacyPackages .${ system }. extend ( 10inputs . rust-overlay . overlays . default 11); 12inherit ( inputs . nixpkgs ) lib ; 13 14rust-toolchain = pkgs . rust-bin . fromRustupToolchainFile ./rust-toolchain.toml ; 15 16upstream-1brc = 17{ stdenv 18, lib 19, writeShellApplication 20, makeWrapper 21, fetchFromGitHub 22, javaPackages 23, graalvmPackages 24} :let 25openjdk = javaPackages . compiler . openjdk25 ; 26in stdenv . mkDerivation ( finalAttrs :{ 27name = "1brc" ; 28version = finalAttrs . src . rev ; 29 30src = fetchFromGitHub { 31owner = "gunnarmorling" ; 32repo = "1brc" ; 33rev = "db064194be375edc02d6dbcd21268ad40f7e2869" ; 34hash = "sha256-SveG6OAFGYNA6IgmTS1r+bUBgVQwamy9lE+mwZr70Wg=" ; 35}; 36 37# generators: 38# - not bothering to pre-compile 39# - using `CreateMeasurements` instead of the faster 40# `CreateMeasurements{2,Fast}` because it is deterministic (enabling 41# us to cache it) 42defaultGenerator = writeShellApplication { 43name = "generator" ; 44runtimeInputs = [ openjdk ]; 45derivationArgs . preCheck = '' 46mkdir -p $ out /misc/ 47cp ${ finalAttrs . src } /src/main/java/dev/morling/onebrc/CreateMeasurements.java $ out /misc 48( cd $ out /misc; patch < ${ ./misc/00-gen-rand-seed.patch } ) 49'' ; 50text = '' 51# $1: output dir, $2: num output rows, $3: random seed 52cd " $ 1 " 53src =" ${ builtins . placeholder "out" } /misc/CreateMeasurements.java " 54java " $ src " " $ 2" " $ 3" 55'' ; 56}; 57manyStationsGenerator = writeShellApplication { 58name = "many-stations-generator" ; 59runtimeInputs = [ openjdk ]; 60derivationArgs . preCheck = '' 61mkdir -p $ out /misc 62cp ${ finalAttrs . src } /src/main/java/dev/morling/onebrc/CreateMeasurements3.java $ out /misc 63cp ${ finalAttrs . src } /data/weather_stations.csv $ out /misc 64( cd $ out /misc; patch < ${ ./misc/01-gen-many-stations-rand-seed.patch } ) 65'' ; 66text = '' 67# $1: output dir, $2: num output rows, $3: random seed 68cd " $ 1 " 69src =" ${ builtins . placeholder "out" } /misc/CreateMeasurements3.java " 70csv=" ${ builtins . placeholder "out" } /misc/weather_stations.csv " 71java " $ src " " $ csv " " $ 2" " $ 3" 72'' ; 73}; 74 75baselineImpl = stdenv . mkDerivation ( this :{ 76pname = "1brc-baseline" ; 77inherit ( finalAttrs ) version ; 78dontUnpack = true ; 79 80nativeBuildInputs = [ openjdk makeWrapper ]; 81buildPhase = '' 82src =" ${ finalAttrs . src } /src/main/java/dev/morling/onebrc/CalculateAverage_baseline.java " 83mkdir -p " $ out " 84javac -d " $ out/" " $ src " 85'' ; 86 87installPhase = '' 88mkdir -p " $ out /bin" 89makeWrapper " ${ lib . getExe' openjdk "java" } " " $ out /bin/ $ pname " \ 90--add-flag " -Dsun.stdout.encoding=UTF-8 " \ 91--add-flag " -cp " \ 92--add-flag " $ out " \ 93--add-flag " dev.morling.onebrc.CalculateAverage_baseline " 94'' ; 95 96meta . mainProgram = this . pname ; 97passthru . commandString = builtins . concatStringsSep " " [ 98" ${ lib . getExe' openjdk "java" } " 99"-Dsun.stdout.encoding=UTF-8" 100"-cp ${ this . finalPackage . outPath } " 101"dev.morling.onebrc.CalculateAverage_baseline" 102]; 103}); 104thomaswueImpl = { 105arch ? "x86-64-v4" , extraAttrs ? {} 106} :stdenv . mkDerivation ( this :{ 107pname = "1brc-thomaswue- ${ arch } " ; 108inherit ( finalAttrs ) version ; 109dontUnpack = true ; 110 111nativeBuildInputs = [ openjdk graalvmPackages . graalvm-ce ]; 112 113# see: `${finalAttrs.src}/prepare_thomaswue.sh 114graalCompileOpts = [ 115"-O3" 116# "-H:TuneInlinerExploration=1" 117"-march= ${ arch } " 118"--enable-preview" 119"--initialize-at-build-time=dev.morling.onebrc.CalculateAverage_thomaswue\$Scanner" 120"--gc=epsilon" 121"-H:-GenLoopSafepoints" 122"-H:-CheckToolchain" 123]; 124 125buildPhase = '' 126src =" ${ finalAttrs . src } /src/main/java/dev/morling/onebrc/CalculateAverage_thomaswue.java " 127javac -d . " $ src " 128mkdir -p " $ out/bin/" 129native-image $ graalCompileOpts -o " $ out/bin/ $ pname " dev.morling.onebrc.CalculateAverage_thomaswue 130'' ; 131 132meta . mainProgram = this . pname ; 133passthru . commandString = lib . getExe this . finalPackage ; 134} // extraAttrs ); 135 136dontUnpack = true ; 137installPhase = '' 138mkdir -p $ out /bin 139ln -s ${ finalAttrs . defaultGenerator } $ out /bin/ 140ln -s ${ finalAttrs . manyStationsGenerator } $ out /bin/ 141'' ; 142}); 143 144materializeInput = name :command :outVar :'' 145_dirPath="''${ONEBRC_TEST_DIR-"/tmp/_1br"}/ ${ name } " 146if ! [[ -f "''${_dirPath}/measurements.txt" ]]; then 147mkdir -p "''${_dirPath}" 148(cd "''${_dirPath}"; ${ command } ) 149fi 150${ outVar } ="''${_dirPath}" 151'' ; 152 153plat = pkgs . stdenv . hostPlatform ; 154platformsFor1st = { # name => { arch: graal target arch, extraAttrs: {} } 155Native = { 156arch = "native" ; 157# need to be careful not to upload to substituters... 158extraAttrs = { 159allowSubstitutes = false ; 160preferLocalBuild = true ; 161}; 162}; 163} // lib . optionalAttrs plat . isx86_64 { 164Avx2 . arch = "x86-64-v3" ; 165Avx10 . arch = "x86-64-v4" ; 166} // lib . optionalAttrs plat . isAarch64 { 167# all: FP + ASIMD + EVTSTRM, + AES + PMULL + SHA1 + SHA2 + CRC32 + LSE + DCPOP + SHA3 + SHA512 + SVE + PACA + SVEBITPERM + SVE2 + A53MAC 168# armv8-a: FP + ASIMD 169# armv8.1-a: FP + ASIMD + + CRC32 + LSE 170# m1: FP + ASIMD + AES + PMULL + SHA1 + SHA2 + CRC32 + LSE + SHA3 + SHA512 171# m4: FP + ASIMD + AES + PMULL + SHA1 + SHA2 + CRC32 + LSE + SHA3 + SHA512 172# 173# unfortunately, can only enable `aes`, `lse`, `fp`, `simd` via feature modifiers... 174ASIMD . arch = "armv8.1-a+aes" ; 175}; 176in { 177legacyPackages . "1brc" = pkgs . callPackage upstream-1brc {}; 178 179# don't want to put inputs in the nix store (large) so we generate them as 180# needed; results are small and fine to cache 181# - generateInputsCommand: produces `measurements.txt` in cwd 182# - expectedOutput: path to a file containing the expected output 183legacyPackages . data = let 184onebrc = inputs . self . legacyPackages .${ system }. "1brc" ; 185 186sample = name :let 187dir = inputs . self . legacyPackages .${ system }. "1brc" . src . outPath ; 188base = dir + "/src/test/resources/samples/measurements-" ; 189in { 190generateInputCommand = let 191path = base + name + ".txt" ; 192in " ${ lib . getExe' pkgs . coreutils "cp" } ${ path } measurements.txt" ; 193expectedOutput = base + name + ".out" ; 194}; 195 196# generator: executable that takes: `<out dir> <num rows> <seed>` 197generated = generator :seed :rows :rec { 198generateInputCommand = 199" ${ lib . getExe generator } . ${ toString rows } ${ toString seed } " ; 200expectedOutput = let 201name = " ${ generator . name } - ${ toString seed } -rows ${ toString rows } .out" ; 202in pkgs . runCommand name {} '' 203${ generateInputCommand } 204${ lib . getExe onebrc . baselineImpl } > $ out 205'' ; 206}; 207 208genDefault = generated onebrc . defaultGenerator ; 209genManySta = generated onebrc . manyStationsGenerator ; 210in { 211sample-1 = sample "1" ; 212sample-10 = sample "10" ; 213sample-10000-unique-keys = sample "10000-unique-keys" ; 214sample-2 = sample "2" ; 215sample-20 = sample "20" ; 216sample-3 = sample "3" ; 217sample-boundaries = sample "boundaries" ; 218sample-complex-utf8 = sample "complex-utf8" ; 219sample-dot = sample "dot" ; 220sample-rounding = sample "rounding" ; 221sample-short = sample "short" ; 222sample-shortest = sample "shortest" ; 223small = genDefault 0 ( 100 * 1000 ); 224"1br" = genDefault 0 ( 1000 * 1000 * 1000 ); 225"1br-many-stations" = genManySta 0 ( 1000 * 1000 * 1000 ); 226}; 227 228legacyPackages . testRunners = let 229testFunc = name :{ generateInputCommand , expectedOutput } : 230pkgs . writeShellApplication { 231name = "test- ${ name } " ; 232runtimeInputs = [ pkgs . coreutils pkgs . delta ]; 233text = '' 234# $@: command to run the implementation 235set -- " $( realpath " $ 1 " ) " "'' $ {@:2}" 236 237outFile=" $( realpath " $( mktemp ) " ) " 238${ materializeInput name generateInputCommand "inputDir" } 239( cd " $ inputDir "; " $ @" > " $ outFile ") 240 241delta -s \ 242<( sed 's|, |\n|g' < " $ outFile " ) \ 243<( sed 's|, |\n|g' < " ${ expectedOutput } ") 244rm " $ outFile " 245'' ; 246}; 247 248perData = builtins . mapAttrs testFunc inputs . self . legacyPackages .${ system }. data ; 249all = pkgs . writeShellApplication { 250name = "test-all" ; 251text = let 252forTest = name :pkg :'' 253# shellcheck disable=SC2015 254${ lib . getExe pkg } "$@" && echo "PASS: ${ name } " || { 255echo "FAIL: ${ name } "; exit 1 256} 257'' ; 258testCmds = lib . pipe perData [ 259( lib . mapAttrsToList forTest ) 260( builtins . concatStringsSep "\n" ) 261]; 262in '' 263# $@: command to run the implementation 264${ testCmds } 265'' ; 266}; 267in all // perData // { inherit all ; }; 268 269legacyPackages . benchRunners = let 270benchFunc = name :{ generateInputCommand , ...} : 271pkgs . writeShellApplication { 272name = "bench- ${ name } " ; 273runtimeInputs = [ pkgs . hyperfine ]; 274text = '' 275# $@: command to run the implementation 276# $HYPERFINE_OPTS: extra flags to hyperfine 277set -- " $( realpath " $ 1 " ) " "'' $ { @:2} " 278echo " BENCH: ${ name } " 279 280${ materializeInput name generateInputCommand "inputDir" } 281cd " $ inputDir " 282# shellcheck disable=SC2086 283hyperfine \ 284--shell=none \ 285--time-unit=millisecond \ 286'' $ { HYPERFINE_OPTS-} \ 287" $ *" 288'' ; 289}; 290in builtins . mapAttrs benchFunc inputs . self . legacyPackages .${ system }. data ; 291 292legacyPackages . impls = let 293onebrc = inputs . self . legacyPackages .${ system }. "1brc" ; 294in { 295baseline = onebrc . baselineImpl ; 296# this; # TODO 297} // lib . mapAttrs' ( name :attrs :{ 298name = "1st ${ name } " ; 299value = onebrc . thomaswueImpl attrs ; 300}) platformsFor1st ; 301 302legacyPackages . bench = let 303impls = inputs . self . legacyPackages .${ system }. impls ; 304benchRunners = inputs . self . legacyPackages .${ system }. benchRunners ; 305mkBench = benchRunner :impl :pkgs . writeShellApplication { 306name = " ${ benchRunner . name } - ${ impl . pname or impl . name } " ; 307text = '' 308${ lib . getExe benchRunner } ${ impl . commandString } 309'' ; 310}; 311in lib . pipe impls [ 312( builtins . mapAttrs ( _ :impl :lib . pipe benchRunners [ 313( builtins . mapAttrs ( _ :benchRunner :mkBench benchRunner impl )) 314# lib.recurseIntoAttrs 315])) 316# lib.recurseIntoAttrs 317]; 318 319checks = let 320impls = inputs . self . legacyPackages .${ system }. impls ; 321test-all = inputs . self . legacyPackages .${ system }. testRunners . all ; 322onebrc = inputs . self . legacyPackages .${ system }. "1brc" ; 323mkCheck = name :pkg :pkgs . runCommand " ${ name } -test" {} '' 324export ONEBRC_TEST_DIR = $( realpath ./test-data) 325${ lib . getExe test-all } ${ pkg . commandString } && touch $ out 326'' ; 327 328in lib . mapAttrs' ( name' :impl :rec { 329name = builtins . replaceStrings [ "1st" ] [ "thomaswue" ] name' ; 330value = mkCheck name impl ; 331}) 332impls 333; 334 335# aliases, for convenience: 336apps = let 337mkApp = pkg :{ type = "app" ; program = lib . getExe pkg ; }; 338this = inputs . self . legacyPackages .${ system }; 339in { 340testRunner = mkApp this . testRunners . all ; 341benchRunner = mkApp this . benchRunners . "1br" ; 342benchRunnerSmall = mkApp this . benchRunners . small ; 343benchRunnerManyStations = mkApp this . benchRunners . "1br-many-stations" ; 344 345bench-baseline = mkApp this . bench . baseline . "1br" ; 346benchSmall-baseline = mkApp this . bench . baseline . small ; 347 348# todo: test, bench (for packages.default) 349} 350// lib . mapAttrs' ( name' :_ :{ 351name = "bench-1st- ${ name' } " ; 352value = mkApp this . bench . "1st ${ name' } " . "1br" ; 353}) platformsFor1st 354// lib . mapAttrs' ( name' :_ :{ 355name = "benchSmall-1st- ${ name' } " ; 356value = mkApp this . bench . "1st ${ name' } " . small ; 357}) platformsFor1st 358; 359 360# packages.default; # TODO 361 362devShells . default = pkgs . mkShell { 363packages = with pkgs ; let 364this = inputs . self . legacyPackages .${ system }; 365in [ 366rust-toolchain 367hwloc pkg-config 368 369hyperfine 370vmtouch 371# todo: lowcharts from julia's config (w/necessary overrides) 372 373this . testRunners . all 374this . benchRunners . small 375this . benchRunners . "1br" 376this . benchRunners . "1br-many-stations" 377python3 378cargo-pgo 379llvm 380] ++ lib . optionals plat . isLinux [ 381numactl 382 383# linuxKernel.packages.linux_6_12.perf # will vary 384perf 385# todo: perf-tools? 386ocamlPackages . magic-trace # needs `legacyPackages.x86_64-linux.linuxPackages_5_15.perf` from nixos-24.11 387# MAGIC_TRACE_FZF_DEMANGLE_SYMBOLS 388# MAGIC_TRACE_PERF_PATH 389# MAGIC_TRACE_PERF_NO_KCORE — to fix kernel tracing 390 391# todo: https://github.com/michoecho/perf2perfetto 392] ++ builtins . attrValues this . impls ; 393}; 394}); 395}