collab/1brc
the one billion row challenge
git clone https://git.julia.blue/collab/1brc
398c61b
julia-baseline
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 14upstream-1brc = 15{ stdenv 16, lib 17, writeShellApplication 18, makeWrapper 19, fetchFromGitHub 20, javaPackages 21, graalvmPackages 22} :let 23openjdk = javaPackages . compiler . openjdk25 ; 24in stdenv . mkDerivation ( finalAttrs :{ 25name = "1brc" ; 26version = finalAttrs . src . rev ; 27 28src = fetchFromGitHub { 29owner = "gunnarmorling" ; 30repo = "1brc" ; 31rev = "db064194be375edc02d6dbcd21268ad40f7e2869" ; 32hash = "sha256-SveG6OAFGYNA6IgmTS1r+bUBgVQwamy9lE+mwZr70Wg=" ; 33}; 34 35# generators: 36# - not bothering to pre-compile 37# - using `CreateMeasurements` instead of the faster 38# `CreateMeasurements{2,Fast}` because it is deterministic (enabling 39# us to cache it) 40defaultGenerator = writeShellApplication { 41name = "generator" ; 42runtimeInputs = [ openjdk ]; 43derivationArgs . preCheck = '' 44mkdir -p $ out /misc/ 45cp ${ finalAttrs . src } /src/main/java/dev/morling/onebrc/CreateMeasurements.java $ out /misc 46( cd $ out /misc; patch < ${ ./misc/00-gen-rand-seed.patch } ) 47'' ; 48text = '' 49# $1: output dir, $2: num output rows, $3: random seed 50cd " $ 1 " 51src =" ${ builtins . placeholder "out" } /misc/CreateMeasurements.java " 52java " $ src " " $ 2" " $ 3" 53'' ; 54}; 55manyStationsGenerator = writeShellApplication { 56name = "many-stations-generator" ; 57runtimeInputs = [ openjdk ]; 58derivationArgs . preCheck = '' 59mkdir -p $ out /misc 60cp ${ finalAttrs . src } /src/main/java/dev/morling/onebrc/CreateMeasurements3.java $ out /misc 61cp ${ finalAttrs . src } /data/weather_stations.csv $ out /misc 62( cd $ out /misc; patch < ${ ./misc/01-gen-many-stations-rand-seed.patch } ) 63'' ; 64text = '' 65# $1: output dir, $2: num output rows, $3: random seed 66cd " $ 1 " 67src =" ${ builtins . placeholder "out" } /misc/CreateMeasurements3.java " 68csv=" ${ builtins . placeholder "out" } /misc/weather_stations.csv " 69java " $ src " " $ csv " " $ 2" " $ 3" 70'' ; 71}; 72 73baselineImpl = stdenv . mkDerivation ( this :{ 74name = "1brc-baseline" ; 75inherit ( finalAttrs ) version ; 76dontUnpack = true ; 77 78nativeBuildInputs = [ openjdk makeWrapper ]; 79buildPhase = '' 80src =" ${ finalAttrs . src } /src/main/java/dev/morling/onebrc/CalculateAverage_baseline.java " 81mkdir -p " $ out " 82javac -d " $ out/" " $ src " 83'' ; 84 85installPhase = '' 86mkdir -p " $ out /bin" 87makeWrapper " ${ lib . getExe' openjdk "java" } " " $ out /bin/ $ name " \ 88--add-flag " -Dsun.stdout.encoding=UTF-8 " \ 89--add-flag " -cp " \ 90--add-flag " $ out " \ 91--add-flag " dev.morling.onebrc.CalculateAverage_baseline " 92'' ; 93 94meta . mainProgram = this . name ; 95passthru . commandString = builtins . concatStringsSep " " [ 96" ${ lib . getExe' openjdk "java" } " 97"-Dsun.stdout.encoding=UTF-8" 98"-cp ${ this . finalPackage . outPath } " 99"dev.morling.onebrc.CalculateAverage_baseline" 100]; 101}); 102thomaswueImpl = { arch ? "x86-64-v4" } :stdenv . mkDerivation ( this :{ 103name = "1brc-thomaswue" ; 104inherit ( finalAttrs ) version ; 105dontUnpack = true ; 106 107nativeBuildInputs = [ openjdk graalvmPackages . graalvm-ce ]; 108 109# see: `${finalAttrs.src}/prepare_thomaswue.sh 110graalCompileOpts = [ 111"-O3" 112# "-H:TuneInlinerExploration=1" 113"-march= ${ arch } " 114"--enable-preview" 115"--initialize-at-build-time=dev.morling.onebrc.CalculateAverage_thomaswue\$Scanner" 116"--gc=epsilon" 117"-H:-GenLoopSafepoints" 118]; 119 120buildPhase = '' 121src =" ${ finalAttrs . src } /src/main/java/dev/morling/onebrc/CalculateAverage_thomaswue.java " 122javac -d . " $ src " 123mkdir -p " $ out/bin/" 124native-image $ graalCompileOpts -o " $ out/bin/ $ name " dev.morling.onebrc.CalculateAverage_thomaswue 125'' ; 126 127meta . mainProgram = this . name ; 128passthru . commandString = lib . getExe this . finalPackage ; 129}); 130 131dontUnpack = true ; 132installPhase = '' 133mkdir -p $ out /bin 134ln -s ${ finalAttrs . defaultGenerator } $ out /bin/ 135ln -s ${ finalAttrs . manyStationsGenerator } $ out /bin/ 136'' ; 137}); 138 139materializeInput = name :command :outVar :let 140dirPath = "/tmp/_1br/ ${ name } " ; 141in '' 142if ! [[ -f " ${ dirPath } /measurements.txt" ]]; then 143mkdir -p " ${ dirPath } " 144(cd " ${ dirPath } "; ${ command } ) 145fi 146${ outVar } =" ${ dirPath } " 147'' ; 148in { 149legacyPackages . "1brc" = pkgs . callPackage upstream-1brc {}; 150 151# don't want to put inputs in the nix store (large) so we generate them as 152# needed; results are small and fine to cache 153# - generateInputsCommand: produces `measurements.txt` in cwd 154# - expectedOutput: path to a file containing the expected output 155legacyPackages . data = let 156onebrc = inputs . self . legacyPackages .${ system }. "1brc" ; 157 158sample = name :let 159dir = inputs . self . legacyPackages .${ system }. "1brc" . src . outPath ; 160base = dir + "/src/test/resources/samples/measurements-" ; 161in { 162generateInputCommand = let 163path = base + name + ".txt" ; 164in " ${ lib . getExe' pkgs . coreutils "cp" } ${ path } measurements.txt" ; 165expectedOutput = base + name + ".out" ; 166}; 167 168# generator: executable that takes: `<out dir> <num rows> <seed>` 169generated = generator :seed :rows :rec { 170generateInputCommand = 171" ${ lib . getExe generator } . ${ toString rows } ${ toString seed } " ; 172expectedOutput = let 173name = " ${ generator . name } - ${ toString seed } -rows ${ toString rows } .out" ; 174in pkgs . runCommand name {} '' 175${ generateInputCommand } 176${ lib . getExe onebrc . baselineImpl } > $ out 177'' ; 178}; 179 180genDefault = generated onebrc . defaultGenerator ; 181genManySta = generated onebrc . manyStationsGenerator ; 182in { 183sample-1 = sample "1" ; 184sample-10 = sample "10" ; 185sample-10000-unique-keys = sample "10000-unique-keys" ; 186sample-2 = sample "2" ; 187sample-20 = sample "20" ; 188sample-3 = sample "3" ; 189sample-boundaries = sample "boundaries" ; 190sample-complex-utf8 = sample "complex-utf8" ; 191sample-dot = sample "dot" ; 192sample-rounding = sample "rounding" ; 193sample-short = sample "short" ; 194sample-shortest = sample "shortest" ; 195small = genDefault 0 ( 100 * 1000 ); 196"1br" = genDefault 0 ( 1000 * 1000 * 1000 ); 197"1br-many-stations" = genManySta 0 ( 1000 * 1000 * 1000 ); 198}; 199 200legacyPackages . testRunners = let 201testFunc = name :{ generateInputCommand , expectedOutput } : 202pkgs . writeShellApplication { 203name = "test- ${ name } " ; 204runtimeInputs = [ pkgs . coreutils pkgs . delta ]; 205text = '' 206# $@: command to run the implementation 207set -- " $( realpath " $ 1 " ) " "'' $ {@:2}" 208 209outFile=" $( realpath " $( mktemp ) " ) " 210${ materializeInput name generateInputCommand "inputDir" } 211( cd " $ inputDir "; " $ @" > " $ outFile ") 212 213delta -s \ 214<( sed 's|, |\n|g' < " $ outFile " ) \ 215<( sed 's|, |\n|g' < " ${ expectedOutput } ") 216rm " $ outFile " 217'' ; 218}; 219 220perData = builtins . mapAttrs testFunc inputs . self . legacyPackages .${ system }. data ; 221all = pkgs . writeShellApplication { 222name = "test-all" ; 223text = let 224forTest = name :pkg :'' 225# shellcheck disable=SC2015 226${ lib . getExe pkg } "$@" && echo "PASS: ${ name } " || { 227echo "FAIL: ${ name } "; exit 1 228} 229'' ; 230testCmds = lib . pipe perData [ 231( lib . mapAttrsToList forTest ) 232( builtins . concatStringsSep "\n" ) 233]; 234in '' 235# $@: command to run the implementation 236${ testCmds } 237'' ; 238}; 239in perData // { inherit all ; } // all ; 240 241legacyPackages . benchRunners = let 242benchFunc = name :{ generateInputCommand , ...} : 243pkgs . writeShellApplication { 244name = "bench- ${ name } " ; 245runtimeInputs = [ pkgs . hyperfine ]; 246text = '' 247# $@: command to run the implementation 248# $HYPERFINE_OPTS: extra flags to hyperfine 249set -- " $( realpath " $ 1 " ) " "'' $ { @:2} " 250echo " BENCH: ${ name } " 251 252${ materializeInput name generateInputCommand "inputDir" } 253cd " $ inputDir " 254# shellcheck disable=SC2086 255hyperfine \ 256--shell=none \ 257--time-unit=millisecond \ 258'' $ { HYPERFINE_OPTS-} \ 259" $ *" 260'' ; 261}; 262in builtins . mapAttrs benchFunc inputs . self . legacyPackages .${ system }. data ; 263 264legacyPackages . impls = let 265onebrc = inputs . self . legacyPackages .${ system }. "1brc" ; 266in { 267baseline = onebrc . baselineImpl ; 268"1stAvx10" = onebrc . thomaswueImpl { arch = "x86-64-v4" ; }; 269"1stAvx2" = onebrc . thomaswueImpl { arch = "x86-64-v3" ; }; 270# this; # TODO 271}; 272 273legacyPackages . bench = let 274impls = inputs . self . legacyPackages .${ system }. impls ; 275benchRunners = inputs . self . legacyPackages .${ system }. benchRunners ; 276mkBench = benchRunner :impl :pkgs . writeShellApplication { 277name = " ${ benchRunner . name } - ${ impl . name } " ; 278text = '' 279${ lib . getExe benchRunner } ${ impl . commandString } 280'' ; 281}; 282in lib . pipe impls [ 283( builtins . mapAttrs ( _ :impl :lib . pipe benchRunners [ 284( builtins . mapAttrs ( _ :benchRunner :mkBench benchRunner impl )) 285# lib.recurseIntoAttrs 286])) 287# lib.recurseIntoAttrs 288]; 289 290checks = let 291test-all = inputs . self . legacyPackages .${ system }. testRunners . all ; 292onebrc = inputs . self . legacyPackages .${ system }. "1brc" ; 293mkCheck = name :pkg :{ 294${ name } = pkgs . runCommand " ${ name } -test" {} '' 295${ lib . getExe test-all } ${ pkg . commandString } && touch $ out 296'' ; 297}; 298in ( mkCheck "baseline" onebrc . baselineImpl ) 299// ( mkCheck "thomaswueAvx2" ( onebrc . thomaswueImpl { arch = "x86-64-v3" ; })) 300# TODO: this 301; 302 303# aliases, for convenience: 304apps = let 305mkApp = pkg :{ type = "app" ; program = lib . getExe pkg ; }; 306this = inputs . self . legacyPackages .${ system }; 307in { 308testRunner = mkApp this . testRunners . all ; 309benchRunner = mkApp this . benchRunners . "1br" ; 310benchRunnerSmall = mkApp this . benchRunners . small ; 311benchRunnerManyStations = mkApp this . benchRunners . "1br-many-stations" ; 312 313bench-baseline = mkApp this . bench . baseline . "1br" ; 314bench-1st-avx2 = mkApp this . bench . "1stAvx2" . "1br" ; 315bench-1st-avx10 = mkApp this . bench . "1stAvx10" . "1br" ; 316benchSmall-baseline = mkApp this . bench . baseline . small ; 317benchSmall-1st-avx2 = mkApp this . bench . "1stAvx2" . small ; 318benchSmall-1st-avx10 = mkApp this . bench . "1stAvx10" . small ; 319 320# todo: test, bench (for packages.default) 321}; 322 323# packages.default; # TODO 324 325devShells . default = pkgs . mkShell { 326packages = with pkgs ; let 327this = inputs . self . legacyPackages .${ system }; 328in [ 329hyperfine 330 331this . testRunners . all 332this . benchRunners . small 333this . benchRunners . "1br" 334this . benchRunners . "1br-many-stations" 335this . impls . baseline 336] ++ lib . optionals pkgs . stdenv . isLinux ( with pkgs ; [ 337# linuxKernel.packages.linux_6_12.perf # will vary 338perf 339# todo: perf-tools? 340 341# this.impls."1stAvx10" 342this . impls . "1stAvx2" 343]); 344 345# env. 346}; 347}); 348}