From c4ac2a164af1c4198852844ae4fcfb99c7e8c110 Mon Sep 17 00:00:00 2001 From: Eelco Dolstra Date: Tue, 30 Mar 2004 15:05:35 +0000 Subject: * 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)'. --- src/libexpr/eval.cc | 5 +++++ 1 file changed, 5 insertions(+) (limited to 'src/libexpr/eval.cc') diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc index 0623e4953..5ae4d6de8 100644 --- a/src/libexpr/eval.cc +++ b/src/libexpr/eval.cc @@ -201,6 +201,11 @@ Expr evalExpr2(EvalState & state, Expr e) cons == "List")) return e; + /* The `Closed' constructor is just a way to prevent substitutions + into expressions not containing free variables. */ + if (atMatch(m, e) >> "Closed" >> e1) + return evalExpr(state, e1); + /* Any encountered variables must be undeclared or primops. */ if (atMatch(m, e) >> "Var" >> name) { PrimOp0 primOp = (PrimOp0) lookupPrimOp(state.primOps0, name); -- cgit v1.2.3