* 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)'.
    

2 files changed, 11 insertions, 2 deletions

diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc
index 0623e4953239..5ae4d6de8edc 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 0d14623ccca0..2736daf32301 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,