Fibonacci

Nix dependencies can be nested arbitrarily deep. We can demonstrate that by building a fibonacci Nix derivation with the following behavior:

Answers are produced in $out/answer.
Each build takes 3 seconds to produce the answer.
fib(0) is 0, and fib(1) is 1.
fib(n) depends on the answers from fib(n-1) and fib(n-2).
The builds are prefixed with a name, so that we can force Nix to re-evaluate the whole sequence by changing the name.

fib.nix:

let
  nixpkgs = import ../../nixpkgs.nix;

  inherit (nixpkgs) stdenv;

  prefixed-fib = prefix:
    let fib = n:
      assert builtins.isInt n;
      assert n >= 0;
      let
        n-str = builtins.toString n;
      in
        if n == 0 || n == 1
        then
          stdenv.mkDerivation {
            name = "${prefix}-fib-${n-str}";
            unpackPhase = "true";

            buildPhase = ''
              echo "Producing base case fib(${n-str})..."
              sleep 3
              echo "The answer to fib(${n-str}) is ${n-str}"
            '';

            installPhase = ''
              mkdir -p $out
              echo "${n-str}" > $out/answer
            '';
          }
        else
          let
            fib-1 = fib (n - 1);
            fib-2 = fib (n - 2);

            n-1-str = builtins.toString (n - 1);
            n-2-str = builtins.toString (n - 2);
          in
          stdenv.mkDerivation {
            name = "${prefix}-fib-${n-str}";
            unpackPhase = "true";

            buildPhase = ''
              fib_1=$(cat ${fib-1}/answer)
              fib_2=$(cat ${fib-2}/answer)

              echo "Calculating the answer of fib(${n-str}).."
              echo "Given fib(${n-1-str}) = $fib_1,"
              echo "and given fib(${n-2-str}) = $fib_2.."

              sleep 3

              answer=$(( $fib_1 + $fib_2 ))
              echo "The answer to fib(${n-str}) is $answer"
            '';

            installPhase = ''
              mkdir -p $out
              echo "$answer" > $out/answer
            '';
          }
    ;
  in fib;
in
prefixed-fib

To make sure we build the fibonacci sequence from scratch each time, we can use $(date +%s) with the Unix timestamp as the prefix to our builds.

Let's try fib(0) and fib(1):

$ time nix-build -E "import ./code/04-derivations/03-fibonacci/fib.nix \"$(date +%s)\" 0"
these derivations will be built:
  /nix/store/yyy5fz5rsws6a812c9xc5ps1hwh9lm98-1605561354-fib-0.drv
building '/nix/store/yyy5fz5rsws6a812c9xc5ps1hwh9lm98-1605561354-fib-0.drv'...
...
no configure script, doing nothing
building
Producing base case fib(0)...
The answer to fib(0) is 0
...
checking for references to /build/ in /nix/store/9kvw6x88l9nx42mvrgzif60a72h66fqz-1605561354-fib-0...
/nix/store/9kvw6x88l9nx42mvrgzif60a72h66fqz-1605561354-fib-0

real    0m4,763s
user    0m0,476s
sys     0m0,130s

$ time nix-build -E "import ./code/04-derivations/03-fibonacci/fib.nix \"$(date +%s)\" 1"
these derivations will be built:
  /nix/store/qs2pc54dmd21xlhlqgzwmgfj98y1kr8n-1605561412-fib-1.drv
building '/nix/store/qs2pc54dmd21xlhlqgzwmgfj98y1kr8n-1605561412-fib-1.drv'...
...
Producing base case fib(1)...
The answer to fib(1) is 1
...
checking for references to /build/ in /nix/store/426cpqvvr7lbg92hywmbw7552vggpway-1605561412-fib-1...
/nix/store/426cpqvvr7lbg92hywmbw7552vggpway-1605561412-fib-1

real    0m5,279s
user    0m0,415s
sys     0m0,102s

So both fib(0) and fib(1) takes roughly 4~5 seconds to build.

Let's try fib(2):

$ time nix-build -E "import ./code/04-derivations/03-fibonacci/fib.nix \"$(date +%s)\" 2"
these derivations will be built:
  /nix/store/r8n1v9ifk0q6mf75j35scn3s2dwa03j7-1605561535-fib-1.drv
  /nix/store/xxrzkbsnq1jpp4s5fdkpklxr3fbc0aq6-1605561535-fib-0.drv
  /nix/store/1bgy17jbakr9yn1yz0bnwhnnz1y1xsdc-1605561535-fib-2.drv
building '/nix/store/xxrzkbsnq1jpp4s5fdkpklxr3fbc0aq6-1605561535-fib-0.drv'...
...
Producing base case fib(0)...
The answer to fib(0) is 0
...
checking for references to /build/ in /nix/store/8k74irn8w8rzpccd30wdn8589nq0wdv5-1605561535-fib-0...
building '/nix/store/r8n1v9ifk0q6mf75j35scn3s2dwa03j7-1605561535-fib-1.drv'...
...
Producing base case fib(1)...
The answer to fib(1) is 1
...
checking for references to /build/ in /nix/store/p716qrpmyi4649k2njfy7gb97ksyi5y3-1605561535-fib-1...
building '/nix/store/1bgy17jbakr9yn1yz0bnwhnnz1y1xsdc-1605561535-fib-2.drv'...
...
Calculating the answer of fib(2)..
Given fib(1) = 1,
and given fib(0) = 0..
The answer to fib(2) is 1
...
checking for references to /build/ in /nix/store/qnaad56wgknlgki9r3kpmr4fhc7x8vxv-1605561535-fib-2...
/nix/store/qnaad56wgknlgki9r3kpmr4fhc7x8vxv-1605561535-fib-2

real    0m12,599s
user    0m0,658s
sys     0m0,198s

So building fib(2) causes fib(1) and fib(0) to also be built.

With this going on, if we are going to build fib(5), then in total it is going to take a lot of time! but if we have built fib(4) already, then building fib(5) will be very fast.

Let's fix our prefix to see Nix cache in effect:

$ prefix=$(date +%s)
$ time nix-build -E "import ./code/04-derivations/03-fibonacci/fib.nix \"$prefix\" 4"
these derivations will be built:
  /nix/store/gz9bgzmna8v7pw5giclfhrk81dp1z0rw-1605561962-fib-1.drv
  /nix/store/y2waqw60jqawallz4q3r64iwrrihnd1p-1605561962-fib-0.drv
  /nix/store/nwj4bmrqgfv1fkvhh00bl2v03c3zqpy1-1605561962-fib-2.drv
  /nix/store/17d2r2dd52qvmfa5k3dm9gkl1k09wdb8-1605561962-fib-3.drv
  /nix/store/w4w4la01p9a2i8mlg6fm15il6vmgcqzl-1605561962-fib-4.drv
building '/nix/store/y2waqw60jqawallz4q3r64iwrrihnd1p-1605561962-fib-0.drv'...
...
Calculating the answer of fib(4)..
Given fib(3) = 2,
and given fib(2) = 1..
The answer to fib(4) is 3
...
checking for references to /build/ in /nix/store/c26q5vs8vdfr268nqgamjk8bcypf8b7r-1605561962-fib-4...
/nix/store/c26q5vs8vdfr268nqgamjk8bcypf8b7r-1605561962-fib-4

real    0m19,486s
user    0m0,910s
sys     0m0,253s

Now run fib(5):

$ time nix-build -E "import ./code/04-derivations/03-fibonacci/fib.nix \"$prefix\" 5"
these derivations will be built:
  /nix/store/nyb25403l4m5n69y3djlffsyzvpwyv6g-1605561962-fib-5.drv
building '/nix/store/nyb25403l4m5n69y3djlffsyzvpwyv6g-1605561962-fib-5.drv'...
unpacking sources
patching sources
configuring
no configure script, doing nothing
building
Calculating the answer of fib(5)..
Given fib(4) = 3,
and given fib(3) = 2..
The answer to fib(5) is 5
installing
post-installation fixup
shrinking RPATHs of ELF executables and libraries in /nix/store/p4iq9jaiid469ycgjm5v3ks3w0v35spi-1605561962-fib-5
strip is /nix/store/bnjps68g8ax6abzvys2xpx12imrx8949-binutils-2.31.1/bin/strip
patching script interpreter paths in /nix/store/p4iq9jaiid469ycgjm5v3ks3w0v35spi-1605561962-fib-5
checking for references to /build/ in /nix/store/p4iq9jaiid469ycgjm5v3ks3w0v35spi-1605561962-fib-5...
/nix/store/p4iq9jaiid469ycgjm5v3ks3w0v35spi-1605561962-fib-5

real    0m7,916s
user    0m0,461s
sys     0m0,151s

Now only fib-5.drv needs to be built.

Lazy Evaluation

A derivation like fib(10) is going to take a long time to build. So we don't really want to build it unless we actually need it. In fact, we also wouldn't want to build fib(0) through fib(10) unless they are actually needed.

With Nix's lazy evaluation strategy, we in fact get the laziness property that none of the fibonacci derivations are going to be built unless they are needed:

$ time nix-instantiate -E "import ./code/04-derivations/03-fibonacci/fib.nix \"$(date +%s)\" 10"
warning: you did not specify '--add-root'; the result might be removed by the garbage collector
/nix/store/dwjxm9rqxfbhf4m8nbg5wzddx1j4rcpl-1605562192-fib-10.drv

real    0m0,235s
user    0m0,182s
sys     0m0,038s

We can see that while fib(10) has fib(0) through fib(9) as its dependencies, but they are not being built just yet.

$ nix-store -qR /nix/store/dwjxm9rqxfbhf4m8nbg5wzddx1j4rcpl-1605562192-fib-10.drv | grep fib
/nix/store/31xdxhxynqndaiym043bjjky0l229vlg-1605562192-fib-1.drv
/nix/store/r4wkf6774ahva1zchk77kpvjf14xigrl-1605562192-fib-0.drv
/nix/store/8agah8vidgxi6yp9ki066yimfr16kigg-1605562192-fib-2.drv
/nix/store/ka3glx20pgzkvgan88xl87xki51y5pmi-1605562192-fib-3.drv
/nix/store/v5zra6kayssdg04n7xpjljqa1q5jjyqn-1605562192-fib-4.drv
/nix/store/1cqwdhnk8f55lxlajmjw6rzq2lq12x5l-1605562192-fib-5.drv
/nix/store/qrbrgdv16f7mc2xfalrgmypfz6c7yljq-1605562192-fib-6.drv
/nix/store/p5chc4l9mjqw5871lkd6har4hyjp55fj-1605562192-fib-7.drv
/nix/store/gn9hp9jcsfclrsdx6qlvjd051w4rsx8b-1605562192-fib-8.drv
/nix/store/6av3vlibm4knm4m3djcrfrhhb6jck3zx-1605562192-fib-9.drv
/nix/store/dwjxm9rqxfbhf4m8nbg5wzddx1j4rcpl-1605562192-fib-10.drv

Input Derivations

If we inspect the derivation, the derivations fib-9.drv and fib-8.drv are listed as one of the input derivations:

$ nix show-derivation /nix/store/dwjxm9rqxfbhf4m8nbg5wzddx1j4rcpl-1605562192-fib-10.drv
{
  "/nix/store/dwjxm9rqxfbhf4m8nbg5wzddx1j4rcpl-1605562192-fib-10.drv": {
    "outputs": {
      "out": {
        "path": "/nix/store/g7415lrzl6b43vnw58dgkxg5nzbjplp0-1605562192-fib-10"
      }
    },
    "inputSrcs": [
      "/nix/store/9krlzvny65gdc8s7kpb6lkx8cd02c25b-default-builder.sh"
    ],
    "inputDrvs": {
      "/nix/store/6av3vlibm4knm4m3djcrfrhhb6jck3zx-1605562192-fib-9.drv": [
        "out"
      ],
      "/nix/store/gn9hp9jcsfclrsdx6qlvjd051w4rsx8b-1605562192-fib-8.drv": [
        "out"
      ],
      "/nix/store/l54djrh1n7d8zdfn26w7v6zjh5wp7faa-bash-4.4-p23.drv": [
        "out"
      ],
      "/nix/store/x9why09hwx2pcnmw0fw7hhh1511hyskl-stdenv-linux.drv": [
        "out"
      ]
    },
    ...
    "env": {
      "buildInputs": "",
      "buildPhase": "fib_1=$(cat /nix/store/zr1ziy94ig8isdg0gdliz0sm59abh2l1-1605562192-fib-9/answer)\nfib_2=$(cat /nix/store/zvivby98nbjlb6pszp6qla4v1r6zwj82
-1605562192-fib-8/answer)\n\necho \"Calculating the answer of fib(10)..\"\necho \"Given fib(9) = $fib_1,\"\necho \"and given fib(8) = $fib_2..\"\n\nsleep 3\n\
nanswer=$(( $fib_1 + $fib_2 ))\necho \"The answer to fib(10) is $answer\"\n",
...

Building Actual Derivation

We can build them later on when nix-build is actually called, or we can get the cached result from else where before building them.

$ time nix-build /nix/store/dwjxm9rqxfbhf4m8nbg5wzddx1j4rcpl-1605562192-fib-10.drv
these derivations will be built:
  /nix/store/31xdxhxynqndaiym043bjjky0l229vlg-1605562192-fib-1.drv
  /nix/store/r4wkf6774ahva1zchk77kpvjf14xigrl-1605562192-fib-0.drv
  /nix/store/8agah8vidgxi6yp9ki066yimfr16kigg-1605562192-fib-2.drv
  /nix/store/ka3glx20pgzkvgan88xl87xki51y5pmi-1605562192-fib-3.drv
  /nix/store/v5zra6kayssdg04n7xpjljqa1q5jjyqn-1605562192-fib-4.drv
  /nix/store/1cqwdhnk8f55lxlajmjw6rzq2lq12x5l-1605562192-fib-5.drv
  /nix/store/qrbrgdv16f7mc2xfalrgmypfz6c7yljq-1605562192-fib-6.drv
  /nix/store/p5chc4l9mjqw5871lkd6har4hyjp55fj-1605562192-fib-7.drv
  /nix/store/gn9hp9jcsfclrsdx6qlvjd051w4rsx8b-1605562192-fib-8.drv
  /nix/store/6av3vlibm4knm4m3djcrfrhhb6jck3zx-1605562192-fib-9.drv
  /nix/store/dwjxm9rqxfbhf4m8nbg5wzddx1j4rcpl-1605562192-fib-10.drv
building '/nix/store/r4wkf6774ahva1zchk77kpvjf14xigrl-1605562192-fib-0.drv'...
...
Calculating the answer of fib(10)..
Given fib(9) = 34,
and given fib(8) = 21..
The answer to fib(10) is 55
...
checking for references to /build/ in /nix/store/g7415lrzl6b43vnw58dgkxg5nzbjplp0-1605562192-fib-10...
/nix/store/g7415lrzl6b43vnw58dgkxg5nzbjplp0-1605562192-fib-10

real    0m39,818s
user    0m1,260s
sys     0m0,413s

Evaluation-Time Dependencies

In our original fib.nix, the build output of earlier fibonacci numbers are used during the build phase of the current derivation. But if we somehow uses the earlier fibonacci numbers to build the derviation itself, Nix would behave quite differently.

fib-serialized.nix:

let
  fib-1 = fib (n - 1);
  fib-2 = fib (n - 2);

  n-1-str = builtins.toString (n - 1);
  n-2-str = builtins.toString (n - 2);

  fib-1-answer = nixpkgs.lib.removeSuffix "\n"
    (builtins.readFile "${fib-1}/answer");
  fib-2-answer = nixpkgs.lib.removeSuffix "\n"
    (builtins.readFile "${fib-2}/answer");
in
stdenv.mkDerivation {
  name = "${prefix}-fib-${n-str}";
  unpackPhase = "true";

  buildPhase = ''
    echo "Calculating the answer of fib(${n-str}).."
    echo "Given fib(${n-1-str}) = ${fib-1-answer},"
    echo "and given fib(${n-2-str}) = ${fib-2-answer}.."

    sleep 3

    answer=$(( ${fib-1-answer} + ${fib-2-answer} ))
    echo "The answer to fib(${n-str}) is $answer"
  '';
  ...
}

Let's try to instantiate the serialized version of fib(4):

$ time nix-instantiate -E "import ./code/04-derivations/03-fibonacci/fib-serialized.nix \"$(date +%s)\" 4"
building '/nix/store/97h18adc1358s8ri9mjzmnbvbbsj7p0a-1606145205-fib-1.drv'...
...
Producing base case fib(1)...
The answer to fib(1) is 1
...
building '/nix/store/fyizpk51qr2k6pm6v2pbqynfqf8ws68p-1606145205-fib-0.drv'...
...
Producing base case fib(0)...
The answer to fib(0) is 0
...
building '/nix/store/8qglzk0vq984mx65f3993rqjpipc3q9j-1606145205-fib-2.drv'...
...
Calculating the answer of fib(2)..
Given fib(1) = 1,
and given fib(0) = 0..
The answer to fib(2) is 1
...
building '/nix/store/4p8xy858gwc348576h6rz39a3l7wk64l-1606145205-fib-3.drv'...
...
Calculating the answer of fib(3)..
Given fib(2) = 1,
and given fib(1) = 1..
The answer to fib(3) is 2
...
/nix/store/c29ap9ljazs7k0jx687hnm3s0rgsz2vm-1606145205-fib-4.drv

real    0m20,016s
user    0m1,221s
sys     0m0,261s

What happened here? fib(0) to fib(3) are built even though we are just instantiating fib(4).

Inspecting Input Derivation

Showing the derivation of fib-4.drv gives us a better idea:

$ nix show-derivation /nix/store/c29ap9ljazs7k0jx687hnm3s0rgsz2vm-1606145205-fib-4.drv
{
  "/nix/store/c29ap9ljazs7k0jx687hnm3s0rgsz2vm-1606145205-fib-4.drv": {
    "outputs": {
      "out": {
        "path": "/nix/store/fgq0j5mlqpy99mfdfc3v4bvbd6wr2slg-1606145205-fib-4"
      }
    },
    ...
    "inputDrvs": {
      "/nix/store/l54djrh1n7d8zdfn26w7v6zjh5wp7faa-bash-4.4-p23.drv": [
        "out"
      ],
      "/nix/store/x9why09hwx2pcnmw0fw7hhh1511hyskl-stdenv-linux.drv": [
        "out"
      ]
    },
    "env": {
      "buildInputs": "",
      "buildPhase": "echo \"Calculating the answer of fib(4)..\"\necho \"Given fib(3) = 2,\"\necho \"and given fib(2) = 1..\"\n\nsleep 3\n\nanswer=$(( 2 + 1 ))\necho \"The answer to fib(4) is $answer\"\n",
  ...

Thanks to builtins.readFile, the results for fib(3) and fib(2) have in fact been calculated and inlined inside the the derivation itself. They are no longer listed in the input derivation.

Caching Problem of Evaluation-Time Dependencies

In fact, fib(3) and fib(2) are not even shown as dependencies in fib(4) anymore:

$ nix-store -qR --include-outputs /nix/store/c29ap9ljazs7k0jx687hnm3s0rgsz2vm-1606145205-fib-4.drv | grep fib
/nix/store/c29ap9ljazs7k0jx687hnm3s0rgsz2vm-1606145205-fib-4.drv
/nix/store/fgq0j5mlqpy99mfdfc3v4bvbd6wr2slg-1606145205-fib-4

This has a consequence in caching Nix dependencies. Not knowing fib(0) to fib(3) are actually input to fib(4), it would be difficult to properly cache these dependencies to Cachix.

Import From Derivation

Evaluation-time dependencies can also occur if we import a .nix file from a derivation. Since Nix has to read the file content to be able to import the .nix file, the derivation has to be built at evaluation time. This is more commonly known as Import From Derivation, or IFD in short.

IFD should be avoided if possible. However as we will see in later chapters, there are valid use cases that can only be solved using IFD.

Non-Lazy Build

If we build fib(4) now, indeed only fib(4) itself is being built.

$ nix-build /nix/store/c29ap9ljazs7k0jx687hnm3s0rgsz2vm-1606145205-fib-4.drv
these derivations will be built:
  /nix/store/c29ap9ljazs7k0jx687hnm3s0rgsz2vm-1606145205-fib-4.drv
building '/nix/store/c29ap9ljazs7k0jx687hnm3s0rgsz2vm-1606145205-fib-4.drv'...
...
Calculating the answer of fib(4)..
Given fib(3) = 2,
and given fib(2) = 1..
The answer to fib(4) is 3
...
/nix/store/fgq0j5mlqpy99mfdfc3v4bvbd6wr2slg-1606145205-fib-4

The same effect can also happen if we import .nix files from derivation outputs.

Lesson learnt: parallelization in Nix can still be tricky. Try your best to include dependencies as input derivations, and lazily refer to the built output of dependencies only during build time.

Scrive Nix Workshop