[Nix-dev] `fast-eval' branch merged

[Eelco Dolstra]

Hi,

I've merged the Nix `fast-eval' branch into the trunk.  This replaces the
current Nix expression evaluator by a new, faster implementation.  It no longer
uses the term-rewriting based approach (described in [1]) but a more
conventional functional language implementation based on thunk updating.  As a
result, Nix no longer depends on the ATerm library.

Here are some benchmark results to show the performance improvement.  The
benchmarks are:

- `nix-env -f /etc/nixos/nixpkgs -qa \*' on Nixpkgs r21747.
- `nix-env -f /etc/nixos/nixpkgs -qa \* --drv-path'.
- `nix-instantiate /etc/nixos/nixos -A system --readonly-mode' (also on r21747
of NixOS).  This is what every `nixos-rebuild' operation does.
- `nix-instantiate /etc/nixos/nixos/tests/ -A proxy.test --readonly-mode' (which
evaluates 4 NixOS system configurations).

These were done on a 32-bit Linux machine (Intel Core 2 Duo T7700 @ 2.40GHz, 2
GiB RAM) and on a 64-bit Linux machine (Intel Core i5 750 @ 2.67GHz, 6 GiB RAM).
 Here are the timings in seconds:

                                         | Old   | New  | Speedup
-----------------------------------------+-------+------+--------
`nix-env -qa' (32-bit)                   |  2.96 | 0.60 | 4.9x
`nix-env -qa' (64-bit)                   |  1.86 | 0.32 | 5.8x
`nix-env -qa --drv-path' (32-bit)        | 12.48 | 3.96 | 3.2x
`nix-env -qa --drv-path' (64-bit)        |  7.65 | 2.04 | 3.8x
`nix-instantiate -A system' (32-bit)     |  6.79 | 1.32 | 5.1x
`nix-instantiate -A system' (64-bit)     |  4.63 | 0.71 | 6.5x
`nix-instantiate -A proxy.test' (32-bit) | 23.86 | 3.55 | 6.7x
`nix-instantiate -A proxy.test' (64-bit) | 15.76 | 1.95 | 8.1x

Another goal of the `fast-eval' branch was to reduce memory consumption by the
evaluator.  The old evaluator basically never released memory due to its normal
form cache.  With the new evaluator, we can in principle reclaim garbage memory.
 However, it doesn't actually have a garbage collector yet.  I intend to use the
Boehm GC for that.  Nevertheless, the new evaluator already uses less memory
than the old one.  For instance, `nix-instantiate -A system' on 64-bit Linux
uses 358.6 MiB with the old evaluator, but only 213.7 MiB with the new evaluator
(according to Valgrind's `massif' tool).

[1] http://www.st.ewi.tudelft.nl/~dolstra/pubs/laziness-ldta2008-final.pdf

-- 
Eelco Dolstra | http://www.st.ewi.tudelft.nl/~dolstra/