diff options
| author | Eelco Dolstra <e.dolstra@tudelft.nl> | 2004-03-30 15:05:35 +0000 |
|---|---|---|
| committer | Eelco Dolstra <e.dolstra@tudelft.nl> | 2004-03-30 15:05:35 +0000 |
| commit | c4ac2a164af1c4198852844ae4fcfb99c7e8c110 (patch) | |
| tree | ec6354d55f2bcb793756b1dd29d30d8c3a209d95 | |
| parent | df101d6fca1d60d4159056e87dd1b3d6c2855661 (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)'.
| -rw-r--r-- | src/libexpr/eval.cc | 5 | ||||
| -rw-r--r-- | src/libexpr/nixexpr.cc | 8 |
2 files changed, 11 insertions, 2 deletions
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); diff --git a/src/libexpr/nixexpr.cc b/src/libexpr/nixexpr.cc index 0d14623cc..2736daf32 100644 --- a/src/libexpr/nixexpr.cc +++ b/src/libexpr/nixexpr.cc @@ -177,9 +177,13 @@ Expr substitute(const ATermMap & subs, Expr e) ATMatcher m; ATerm name; + /* As an optimisation, don't substitute in subterms known to be + closed. */ + if (atMatch(m, e) >> "Closed") return e; + if (atMatch(m, e) >> "Var" >> name) { Expr sub = subs.get(name); - return sub ? sub : e; + return sub ? ATmake("Closed(<term>)", sub) : e; } /* In case of a function, filter out all variables bound by this @@ -199,7 +203,7 @@ Expr substitute(const ATermMap & subs, Expr e) substitute(subs2, body)); } - if (atMatch(m, e) >> "Function" >> name >> body) { + if (atMatch(m, e) >> "Function1" >> name >> body) { ATermMap subs2(subs); subs2.remove(name); return ATmake("Function1(<term>, <term>)", name, |