collab/1brc

the one billion row challenge

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

Julia RyanGet working on macos398c61b

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