Super Mario Derivaties

Een van de eenvoudigste manieren om deze luie aard te observeren, is door te begrijpen dat alleen de attributen die je daadwerkelijk aanroept, worden geëvalueerd.

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

Een extremere versie hiervan is dat je oneindige recursie in een attribute set kunt hebben. Nixpkgs zit vol met dit soort bodemloze 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

Elke keer hetzelfde store-pad. pkgs bevat zichzelf, en dat geldt voor elke package set daarbinnen.

Als laziness ervoor zorgt dat een recursieve attribute set kan termineren, dan hoeft de recursie helemaal niet te stoppen bij een basisgeval:

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

Die attribute set is oneindig diep. Het indexeren van drie niveaus kost precies drie niveaus aan evaluatie; de rest van de oneindige boom wordt nooit gebouwd omdat daar niet om gevraagd is.

Van attribuutpaden naar knopcombinaties

Een attribuutpad is in feite een wandeling door een lui gegenereerde boom. Dit riep bij mij de vraag op: wat als het attribuutpad de input zou zijn voor iets anders?

Ik besloot van dit idee een reeks knopdrukken in Super Mario Bros. 3 te maken. Elke node in de boom is een frame van het spel, en elk kind is een knopdruk die een nieuw frame produceert. Gamestates zijn van nature recursief.

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

Hierbij is .rightb een combinatie van rechts + B, wat in Super Mario Bros. 3 "naar rechts rennen" betekent. .rightab is rennen en springen. De output is het frame dat je zou zien als je deze knoppen in die volgorde zou indrukken op echte hardware in dat spel. Het prefix .#level1 is een vooraf gedefinieerde reeks knopdrukken die je naar het begin van level 1-1 brengt.

Door overal in het pad .play toe te voegen, krijg je de volledige run samengevoegd in een opname.

De Nix store als geschiedenis van gamestates

Het interessantste is dat elk van deze frames een aparte derivatie is in mijn store. De code is te vinden op fzakaria/nes-nix. Het is gegeneraliseerd en de ROM is een flake input die je naar elk gewenst spel kunt wijzen.

De flake berekent een derivatie op basis van het attribuutpad, waarbij elke knopdruk zijn eigen derivatie is en de savestate van de vorige druk als input gebruikt. Elke derivatie emuleert nooit opnieuw de frames van zijn voorgangers. Er wordt ook een screenshot van het frame gegenereerd, die wordt gebruikt wanneer we een videosequentie willen samenvoegen.

Voorbeeld van de derivatie-structuur:

  • trunk1 → level1 → 2y1qjbk7…-nes-wait16
  • trunk2 → .rightb → gdbgfpdk…-nes-rightb (van trunk1 naar trunk2)
  • run → .rightb → kpjlw529…-nes-rightb (van trunk2 naar run)
  • jump → .rightab → iv6asl0i…-nes-rightab (van trunk2 naar jump)
  • a → .a → q02kp71k…-nes-a (van run naar a)
  • righta → .righta → nb87m9ss…-nes-righta (van run naar righta)

Het praktische gevolg is dat de store de savestate-geschiedenis van de emulator wordt:

# 3 derivaties, koud
$ nix build '.#game.start4.wait2.right'

# 1 derivatie, prefix hergebruikt
$ nix build '.#game.start4.wait2.left'

# 1 derivatie, alles hergebruikt
$ nix build '.#game.start4.wait2.right.right'

Het aftakken vanuit het midden van een run van honderd knopdrukken kost slechts één knopdruk, net als het toevoegen van een druk aan het einde.

We kunnen het ook andersom bekijken: de dependency graph is de inputsequentie. We kunnen Nix dus vragen welke knoppen een specifiek frame hebben geproduceerd:

$ 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

Wat doet .play precies?

Vrijwel niets. Elk frame langs het pad bevindt zich al in de store als de output van zijn eigen knopdruk, dus de opname emuleert nooit iets opnieuw. Het is een directory met symlinks naar de frames die door ffmpeg kunnen worden verwerkt.

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

Technische limieten

Hoe ver kunnen we gaan met dit idee van inputsequenties?

Standaard geeft Nix bij ongeveer 2.400 knopdrukken een foutmelding:

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

De max-call-depth staat standaard op 10.000 en het evalueren van elke knopdruk kost ongeveer vier geneste aanroepen. Dit is een beveiliging tegen ongecontroleerde recursie, geen structurele limiet. Door deze waarde te verhogen naar 10 miljoen, kunnen we 20.000 knopdrukken bereiken:

$ 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

Dit kost op mijn laptop ongeveer veertien seconden om te evalueren. De kosten zijn lineair aan het aantal knopdrukken, ongeveer 0,7 ms per druk.

De volgende bottleneck is de kernel, die op mijn machine stopt bij 21.845 knopdrukken. Een attribuutpad is één enkel argv-element, en Linux beperkt de totale grootte van de argumentenlijst en individuele argumenten. De limiet per argument is 131.072 bytes (MAXARGSTRLEN). Aangezien elke knopdruk zes bytes lang is (right.), is 21.845 het maximum dat als één argument aan nix eval kan worden doorgegeven.

De oplossing is om de run niet langer als argument door te geven, maar de inputsequentie vanuit een bestand in te lezen:

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

Dit produceert een byte-identieke derivatie als het equivalente attribuutpad, waardoor een run in een bestand nog steeds dezelfde store-paden deelt.

Bouwtijden en prestaties

Hoewel Nix uitblinkt in het parallel bouwen van derivaties, is de recursie hier tail-recursive en dus serieel.

Uit benchmarks blijkt dat de bouwtijd ook lineair is aan het aantal knopdrukken. De kosten per druk zijn ongeveer 1,27 seconden met substituters (cache) ingeschakeld, en 0,28 seconden wanneer deze uitgeschakeld zijn. De tijd die nodig is om te controleren of een derivatie in de cache staat, kost merkbaar meer dan het emuleren van de frames zelf. Men kan preferLocalBuild of allowSubstitutes instellen om deze kosten te vermijden.

Conclusie

We zijn gewend aan het idee dat een attribuutpad een naam is, simpelweg een coördinaat in een catalogus van bestaande zaken. Laziness betekent echter dat het in feite een programma is: een reeks stappen die de evaluator doorloopt en waarbij alles wat nodig is, gaandeweg wordt gegenereerd.

Nixpkgs gebruikt dit mechanisme om software te beschrijven, maar er is niets dat vereist dat de boom een catalogus moet zijn. Gecombineerd met het feit dat de store een uitstekende persistentielaag is voor reproduceerbare state-machines, maakt dit onze "package manager" verrassend bruikbaar voor het spelen van Mario. 🍄