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. The more whackier version of this is you can have endless recursion in an attribute set. Nixpkgs is filled with these bottomless attribute sets: The same store path every time. 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 : 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. is right + B, which in Super Mario Bros. 3 is “run right”. 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. 1 Append 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. 2 The practical consequence is that the store becomes the emulator’s savestate history: 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: So what is 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 to process. How far can we take this input-sequence game input idea? Nix by default gives out at around 2,400 presses, with: 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: 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 element, and Linux caps the size of the argument list in total and individual arguments. The per-argument limit is 131,072 bytes ( ), and each press is six bytes long ( ), so 21,845 presses is the maximum that can be passed to 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: 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. 3 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. 🍄 The prefix is a precanned sequence of button presses that gets you to the start of level 1-1. ↩ A screenshot of the frame is also produced, which is used when we want to stitch a video sequence together. ↩ We can set or if we want to avoid this cost. ↩ The prefix is a precanned sequence of button presses that gets you to the start of level 1-1. ↩ A screenshot of the frame is also produced, which is used when we want to stitch a video sequence together. ↩ We can set or if we want to avoid this cost. ↩
Programming
Open Source
C++
DevOps
Shell
C
Java
Backend
Performance
Web
AI
CSS
Linux
Security
JavaScript
Writing
Culture
Business
Python
JSON
Rust
Sql