about summary refs log tree commit diff
path: root/src/nix-instantiate
diff options
context:
space:
mode:
authorEelco Dolstra <e.dolstra@tudelft.nl>2004-03-30T15·05+0000
committerEelco Dolstra <e.dolstra@tudelft.nl>2004-03-30T15·05+0000
commitc4ac2a164af1c4198852844ae4fcfb99c7e8c110 (patch)
treeec6354d55f2bcb793756b1dd29d30d8c3a209d95 /src/nix-instantiate
parentdf101d6fca1d60d4159056e87dd1b3d6c2855661 (diff)
* The recent change in nixpkgs of calling `stdenv.mkDerivation'
  instead of `derivation' triggered a huge slowdown in the Nix
  expression evaluator.  Total execution time of `nix-env -qa' went up
  by a factor of 60 or so.

  This scalability problem was caused by expressions such as

    (x: y: ... x ...) a b

  where `a' is a large term (say, the one in
  `all-packages-generic.nix').  Then the first beta-reduction would
  produce

    (y: ... a ...) b

  by substituting `a' for `x'.  The second beta-reduction would then
  substitute `b' for `y' into the body `... a ...', which is a large
  term due to `a', and thus causes a large traversal to be performed
  by substitute() in the second reduction.  This is however entirely
  redundant, since `a' cannot contain free variables (since we never
  substitute below a weak head normal form).

  The solution is to wrap substituted terms into a `Closed'
  constructor, i.e.,

    subst(subs, Var(x)) = Closed(e) iff subs[x] = e

  have substitution not descent into closed terms,

    subst(subs, Closed(x)) = Closed(x)

  and otherwise ignore them for evaluation,

    eval(Closed(x)) = eval(x).

* Fix a typo that caused incorrect substitutions to be performed in
  simple lambdas, e.g., `(x: x: x) a' would reduce to `(x: a)'.
    

Diffstat (limited to 'src/nix-instantiate')
0 files changed, 0 insertions, 0 deletions