Super Mario Derivations

One of the most surprising aspects of the Nix language is that it is lazy, especially if you have never used a lazy language before. This laziness is what makes much of Nixpkgs possible, and its complexity.

One of the simplest ways to observe the laziness is by understanding that only the attributes you access are evaluated.

$ nix eval --expr 'let pkgs =
   { hello = "hi"; broken = throw "never forced"; };
   in pkgs.hello'
"hi"

The more whackier version of this is you can have endless recursion in an attribute set. Nixpkgs is filled with these bottomless attribute sets:

$ nix eval -f '<nixpkgs>' 'pkgs.hello' --raw
/nix/store/18bbdvag5v2f3d4y37pdbkzvh7s71cw4-hello-2.12.2

$ nix eval -f '<nixpkgs>' 'pkgs.pkgs.pkgs.hello' --raw
/nix/store/18bbdvag5v2f3d4y37pdbkzvh7s71cw4-hello-2.12.2

$ nix eval -f '<nixpkgs>' 'pkgs.python3Packages.pkgs.hello' --raw
/nix/store/18bbdvag5v2f3d4y37pdbkzvh7s71cw4-hello-2.12.2

The same store path every time. pkgs contains itself, and so does every package set inside it. 🤯

If laziness is what lets a recursive attribute set terminate, then the recursion doesn’t have to bottom out at all:

$ nix eval --expr \
    'let countdown = n: { value = n; next = countdown (n + 1); };
     in (countdown 0).next.next.next.value'
3

That attribute set is infinitely deep. Indexing three levels into it costs exactly three levels of evaluation, and the rest of the infinite tree is never built because nobody asked.

So an attribute path is a walk through a lazily-generated tree. Which made me wonder: what if the attribute path were input to something? 🤔

I decided to take that idea and make the attribute path a sequence of button presses in Super Mario Bros. 3. Each node in the tree is a frame of the game, and each child is a button press that produces a new frame. Game states are recursive by nature.

$ nix build '.#level1.rightb.rightb.rightab.rightb'
$ file -L result
result: PNG image data, 256 x 240, 8-bit/color RGB, non-interlaced

.rightb is right + B, which in Super Mario Bros. 3 is “run right”. .rightab is run and jump. The output is the frame you’d be looking at if you’d pressed those buttons in that order, on real hardware, in that game.11The prefix .#level1 is a precanned sequence of button presses that gets you to the start of level 1-1.

Append .play anywhere along the path and you get the whole run stitched into a recording:

The coolest thing though is that every one of those frames is a separate derivation in my store.

The code is at fzakaria/nes-nix. It is generalized and the ROM is a flake input you point wherever you like for any other game.

The flake computes a derivation based on the attribute path such that each press is its own derivation, and it takes the previous press’s savestate as an input. Each derivation never re-emulates its ancestors’ frames.22A screenshot of the frame is also produced, which is used when we want to stitch a video sequence together.

The practical consequence is that the store becomes the emulator’s savestate history:

# 3 derivations, cold
$ nix build '.#game.start4.wait2.right'
# 1 derivation, prefix reused
$ nix build '.#game.start4.wait2.left'
# 1 derivation, all of it reused
$ nix build '.#game.start4.wait2.right.right'

Branching off the middle of a hundred-press run costs one press as does appending to the end of it.

We can look at it the other way. The dependency graph is the input sequence, so we can ask Nix what buttons produced a frame:

$ nix-store --query --tree
     $(nix eval --raw '.#game.start.wait4.start.drvPath')
/nix/store/32n4ni0zg01b9c9v64x67am37rdmmr9y-nes-start.drv
└───/nix/store/j5vy3385pgs9dzw0y7sdrdmn7xnrxgji-nes-wait4.drv
    └───/nix/store/w4zz5aqj5zxqhnialabdc7p3sy80v6dc-nes-start.drv
        └───/nix/store/k9wfz8w5157d0xdwaw1vvhf019dvw5s0-nes-boot.drv

So what is .play actually doing?

Almost nothing. Every frame along the path is already sitting in the store as the output of its own press, so the recording never emulates anything. It is a directory of symlinks to the frames for ffmpeg to process.

$ nix build '.#level1.rightb.rightb.rightab.play'
$ ls -l result/frames | head -4
0000.png -> /nix/store/3p2fxwngh…-nes-boot
.png -> /nix/store/4ha88l0dk…-nes-start
.png -> /nix/store/nh4zfsq6x…-nes-wait4
.png -> /nix/store/ghbgn28f1…-nes-start

How far can we take this input-sequence game input idea?

Nix by default gives out at around 2,400 presses, with:

$ nix eval --raw ".#game.right.right.right…drvPath"
error: stack overflow; max-call-depth exceeded

max-call-depth defaults to 10,000 and evaluating each press costs roughly four nested calls.

It’s a guard against runaway recursion, not a structural limit, and we can raise it to 10 million and get 20,000 presses:

$ ulimit -s unlimited
$ nix eval --raw --option max-call-depth 10000000 \
      ".#game.$(
        python3 -c 'print(".".join(["right"]*20000))')
      .drvPath"
/nix/store/p4nm0a4p4k9bdjqsag1jj0baah9mj6hb-nes-right.drv

20,000 presses, takes roughly fourteen seconds to evaluate on my laptop. The cost is linear in the number of presses, and it is roughly 0.7ms “per press”.

The next bottleneck though is that the kernel gives out at 21,845 presses on my machine. An attribute path is a single argv element, and Linux caps the size of the argument list in total and individual arguments.

The per-argument limit is 131,072 bytes (MAX_ARG_STRLEN), and each press is six bytes long (right.), so 21,845 presses is the maximum that can be passed to nix eval as a single argument.

The escape hatch is to stop passing the run as an argument. and we can feed in the input-sequence as from a file:

$ nix build --impure --expr \
    '(builtins.getFlake (toString ./.))
      .packages.x86_64-linux.game.sequenceFile
        ./runs/world1-1.txt'

This produces the byte-identical derivation to the equivalent attribute path, so a run kept in a file still shares the same store paths.

All of this was to simply evaluate the Nix expression. Now we have to build it. Although Nix is great at building derivations in parallel, the recursion here is tail-recursive and therefore serial.

I benchmarked the build time of a growing list of button presses and the cost is also linear, as we would expect, with the number of presses. The cost per press is roughly 1.27 seconds with substituters enabled and 0.28 seconds with them disabled. The round-trips cost for checking whether the derivation is in the cache costs noticeably more than emulating the frames does.33We can set preferLocalBuild or allowSubstitutes if we want to avoid this cost.

We’re used to the attribute path being a name, simply a coordinate into a catalogue of things that exist. Laziness means it’s really a program: a sequence of steps the evaluator walks, generating whatever it needs as it goes.

Nixpkgs happens to use that machinery to describe software, but nothing about it requires that the tree be a catalogue at all. Coupled with the fact that the store turns out to be a decent persistence layer for reproducible state-machines, makes a our “package manager” reasonable to use for playing Mario. 🍄