collab/1brc

the one billion row challenge

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

Rahul Butaniexp/file-io: NUMA, pt. 204940aa

main
14.1 KiB395 linesraw
1{
2  inputs.nixpkgs.url = "github:NixOS/nixpkgs/nixos-unstable";
3  inputs.flake-utils.url = "github:numtide/flake-utils";
4  inputs.rust-overlay.url = "github:oxalica/rust-overlay";
5
6  inputs.rust-overlay.inputs.nixpkgs.follows = "nixpkgs";
7
8  outputs = inputs: inputs.flake-utils.lib.eachDefaultSystem (system: let
9    pkgs = inputs.nixpkgs.legacyPackages.${system}.extend (
10      inputs.rust-overlay.overlays.default
11    );
12    inherit (inputs.nixpkgs) lib;
13
14    rust-toolchain = pkgs.rust-bin.fromRustupToolchainFile ./rust-toolchain.toml;
15
16    upstream-1brc =
17      { stdenv
18      , lib
19      , writeShellApplication
20      , makeWrapper
21      , fetchFromGitHub
22      , javaPackages
23      , graalvmPackages
24      }: let
25        openjdk = javaPackages.compiler.openjdk25;
26      in stdenv.mkDerivation (finalAttrs: {
27        name = "1brc";
28        version = finalAttrs.src.rev;
29
30        src = fetchFromGitHub {
31          owner = "gunnarmorling";
32          repo = "1brc";
33          rev = "db064194be375edc02d6dbcd21268ad40f7e2869";
34          hash = "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)
42        defaultGenerator = writeShellApplication {
43          name = "generator";
44          runtimeInputs = [ openjdk ];
45          derivationArgs.preCheck = ''
46            mkdir -p $out/misc/
47            cp ${finalAttrs.src}/src/main/java/dev/morling/onebrc/CreateMeasurements.java $out/misc
48            (cd $out/misc; patch < ${./misc/00-gen-rand-seed.patch})
49          '';
50          text = ''
51            # $1: output dir, $2: num output rows, $3: random seed
52            cd "$1"
53            src="${builtins.placeholder "out"}/misc/CreateMeasurements.java"
54            java "$src" "$2" "$3"
55          '';
56        };
57        manyStationsGenerator = writeShellApplication {
58          name = "many-stations-generator";
59          runtimeInputs = [ openjdk ];
60          derivationArgs.preCheck = ''
61            mkdir -p $out/misc
62            cp ${finalAttrs.src}/src/main/java/dev/morling/onebrc/CreateMeasurements3.java $out/misc
63            cp ${finalAttrs.src}/data/weather_stations.csv $out/misc
64            (cd $out/misc; patch < ${./misc/01-gen-many-stations-rand-seed.patch})
65          '';
66          text = ''
67            # $1: output dir, $2: num output rows, $3: random seed
68            cd "$1"
69            src="${builtins.placeholder "out"}/misc/CreateMeasurements3.java"
70            csv="${builtins.placeholder "out"}/misc/weather_stations.csv"
71            java "$src" "$csv" "$2" "$3"
72          '';
73        };
74
75        baselineImpl = stdenv.mkDerivation (this: {
76          pname = "1brc-baseline";
77          inherit (finalAttrs) version;
78          dontUnpack = true;
79
80          nativeBuildInputs = [ openjdk makeWrapper ];
81          buildPhase = ''
82            src="${finalAttrs.src}/src/main/java/dev/morling/onebrc/CalculateAverage_baseline.java"
83            mkdir -p "$out"
84            javac -d "$out/" "$src"
85          '';
86
87          installPhase = ''
88            mkdir -p "$out/bin"
89            makeWrapper "${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
96          meta.mainProgram = this.pname;
97          passthru.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        });
104        thomaswueImpl = {
105          arch ? "x86-64-v4", extraAttrs ? {}
106        }: stdenv.mkDerivation (this: {
107          pname = "1brc-thomaswue-${arch}";
108          inherit (finalAttrs) version;
109          dontUnpack = true;
110
111          nativeBuildInputs = [ openjdk graalvmPackages.graalvm-ce ];
112
113          # see: `${finalAttrs.src}/prepare_thomaswue.sh
114          graalCompileOpts = [
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
125          buildPhase = ''
126            src="${finalAttrs.src}/src/main/java/dev/morling/onebrc/CalculateAverage_thomaswue.java"
127            javac -d . "$src"
128            mkdir -p "$out/bin/"
129            native-image $graalCompileOpts -o "$out/bin/$pname" dev.morling.onebrc.CalculateAverage_thomaswue
130          '';
131
132          meta.mainProgram = this.pname;
133          passthru.commandString = lib.getExe this.finalPackage;
134        } // extraAttrs);
135
136        dontUnpack = true;
137        installPhase = ''
138          mkdir -p $out/bin
139          ln -s ${finalAttrs.defaultGenerator} $out/bin/
140          ln -s ${finalAttrs.manyStationsGenerator} $out/bin/
141        '';
142      });
143
144    materializeInput = name: command: outVar: ''
145      _dirPath="''${ONEBRC_TEST_DIR-"/tmp/_1br"}/${name}"
146      if ! [[ -f "''${_dirPath}/measurements.txt" ]]; then
147        mkdir -p "''${_dirPath}"
148        (cd "''${_dirPath}"; ${command})
149      fi
150      ${outVar}="''${_dirPath}"
151    '';
152
153    plat = pkgs.stdenv.hostPlatform;
154    platformsFor1st = { # name => { arch: graal target arch, extraAttrs: {} }
155      Native = {
156        arch = "native";
157        # need to be careful not to upload to substituters...
158        extraAttrs = {
159          allowSubstitutes = false;
160          preferLocalBuild = true;
161        };
162      };
163    } // lib.optionalAttrs plat.isx86_64 {
164      Avx2.arch = "x86-64-v3";
165      Avx10.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...
174      ASIMD.arch = "armv8.1-a+aes";
175    };
176  in {
177    legacyPackages."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
183    legacyPackages.data = let
184      onebrc = inputs.self.legacyPackages.${system}."1brc";
185
186      sample = name: let
187        dir = inputs.self.legacyPackages.${system}."1brc".src.outPath;
188        base = dir + "/src/test/resources/samples/measurements-";
189      in {
190        generateInputCommand = let
191          path = base + name + ".txt";
192        in "${lib.getExe' pkgs.coreutils "cp"} ${path} measurements.txt";
193        expectedOutput = base + name + ".out";
194      };
195
196      # generator: executable that takes: `<out dir> <num rows> <seed>`
197      generated = generator: seed: rows: rec {
198        generateInputCommand =
199          "${lib.getExe generator} . ${toString rows} ${toString seed}";
200        expectedOutput = let
201          name = "${generator.name}-${toString seed}-rows${toString rows}.out";
202        in pkgs.runCommand name {} ''
203          ${generateInputCommand}
204          ${lib.getExe onebrc.baselineImpl} > $out
205        '';
206      };
207
208      genDefault = generated onebrc.defaultGenerator;
209      genManySta = generated onebrc.manyStationsGenerator;
210    in {
211      sample-1                 = sample "1";
212      sample-10                = sample "10";
213      sample-10000-unique-keys = sample "10000-unique-keys";
214      sample-2                 = sample "2";
215      sample-20                = sample "20";
216      sample-3                 = sample "3";
217      sample-boundaries        = sample "boundaries";
218      sample-complex-utf8      = sample "complex-utf8";
219      sample-dot               = sample "dot";
220      sample-rounding          = sample "rounding";
221      sample-short             = sample "short";
222      sample-shortest          = sample "shortest";
223      small                    = genDefault 0 (100 * 1000);
224      "1br"                    = genDefault 0 (1000 * 1000 * 1000);
225      "1br-many-stations"      = genManySta 0 (1000 * 1000 * 1000);
226    };
227
228    legacyPackages.testRunners = let
229      testFunc = name: { generateInputCommand, expectedOutput }:
230        pkgs.writeShellApplication {
231          name = "test-${name}";
232          runtimeInputs = [ pkgs.coreutils pkgs.delta ];
233          text = ''
234            # $@: command to run the implementation
235            set -- "$(realpath "$1")" "''${@:2}"
236
237            outFile="$(realpath "$(mktemp)")"
238            ${materializeInput name generateInputCommand "inputDir"}
239            (cd "$inputDir"; "$@" > "$outFile")
240
241            delta -s \
242              <(sed 's|, |\n|g' < "$outFile") \
243              <(sed 's|, |\n|g' < "${expectedOutput}")
244            rm "$outFile"
245          '';
246        };
247
248      perData = builtins.mapAttrs testFunc inputs.self.legacyPackages.${system}.data;
249      all = pkgs.writeShellApplication {
250        name = "test-all";
251        text = let
252          forTest = name: pkg: ''
253            # shellcheck disable=SC2015
254            ${lib.getExe pkg} "$@" && echo "PASS: ${name}" || {
255              echo "FAIL: ${name}"; exit 1
256            }
257          '';
258          testCmds = lib.pipe perData [
259            (lib.mapAttrsToList forTest)
260            (builtins.concatStringsSep "\n")
261          ];
262        in ''
263          # $@: command to run the implementation
264          ${testCmds}
265        '';
266      };
267    in  all // perData // { inherit all; };
268
269    legacyPackages.benchRunners = let
270      benchFunc = name: { generateInputCommand, ... }:
271        pkgs.writeShellApplication {
272          name = "bench-${name}";
273          runtimeInputs = [ pkgs.hyperfine ];
274          text = ''
275            # $@: command to run the implementation
276            # $HYPERFINE_OPTS: extra flags to hyperfine
277            set -- "$(realpath "$1")" "''${@:2}"
278            echo "BENCH: ${name}"
279
280            ${materializeInput name generateInputCommand "inputDir"}
281            cd "$inputDir"
282            # shellcheck disable=SC2086
283            hyperfine \
284              --shell=none \
285              --time-unit=millisecond \
286              ''${HYPERFINE_OPTS-} \
287              "$*"
288          '';
289        };
290    in builtins.mapAttrs benchFunc inputs.self.legacyPackages.${system}.data;
291
292    legacyPackages.impls = let
293      onebrc = inputs.self.legacyPackages.${system}."1brc";
294    in {
295      baseline = onebrc.baselineImpl;
296      # this; # TODO
297    } // lib.mapAttrs' (name: attrs: {
298      name = "1st${name}";
299      value = onebrc.thomaswueImpl attrs;
300    }) platformsFor1st;
301
302    legacyPackages.bench = let
303      impls = inputs.self.legacyPackages.${system}.impls;
304      benchRunners = inputs.self.legacyPackages.${system}.benchRunners;
305      mkBench = benchRunner: impl: pkgs.writeShellApplication {
306        name = "${benchRunner.name}-${impl.pname or impl.name}";
307        text = ''
308          ${lib.getExe benchRunner} ${impl.commandString}
309        '';
310      };
311    in 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
319    checks = let
320      impls = inputs.self.legacyPackages.${system}.impls;
321      test-all = inputs.self.legacyPackages.${system}.testRunners.all;
322      onebrc = inputs.self.legacyPackages.${system}."1brc";
323      mkCheck = name: pkg: pkgs.runCommand "${name}-test" {} ''
324        export ONEBRC_TEST_DIR=$(realpath ./test-data)
325        ${lib.getExe test-all} ${pkg.commandString} && touch $out
326      '';
327
328    in lib.mapAttrs' (name': impl: rec {
329        name = builtins.replaceStrings ["1st"] ["thomaswue"] name';
330        value = mkCheck name impl;
331      })
332      impls
333    ;
334
335    # aliases, for convenience:
336    apps = let
337      mkApp = pkg: { type = "app"; program = lib.getExe pkg; };
338      this = inputs.self.legacyPackages.${system};
339    in {
340      testRunner = mkApp this.testRunners.all;
341      benchRunner = mkApp this.benchRunners."1br";
342      benchRunnerSmall = mkApp this.benchRunners.small;
343      benchRunnerManyStations = mkApp this.benchRunners."1br-many-stations";
344
345      bench-baseline = mkApp this.bench.baseline."1br";
346      benchSmall-baseline = mkApp this.bench.baseline.small;
347
348      # todo: test, bench (for packages.default)
349    }
350    // lib.mapAttrs' (name': _: {
351      name = "bench-1st-${name'}";
352      value = mkApp this.bench."1st${name'}"."1br";
353    }) platformsFor1st
354    // lib.mapAttrs' (name': _: {
355      name = "benchSmall-1st-${name'}";
356      value = mkApp this.bench."1st${name'}".small;
357    }) platformsFor1st
358    ;
359
360    # packages.default; # TODO
361
362    devShells.default = pkgs.mkShell {
363      packages = with pkgs; let
364        this = inputs.self.legacyPackages.${system};
365      in [
366        rust-toolchain
367        hwloc pkg-config
368
369        hyperfine
370        vmtouch
371        # todo: lowcharts from julia's config (w/necessary overrides)
372
373        this.testRunners.all
374        this.benchRunners.small
375        this.benchRunners."1br"
376        this.benchRunners."1br-many-stations"
377        python3
378        cargo-pgo
379        llvm
380      ] ++ lib.optionals plat.isLinux [
381        numactl
382
383        # linuxKernel.packages.linux_6_12.perf # will vary
384        perf
385        # todo: perf-tools?
386        ocamlPackages.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}