* Store lists as lists of pointers to values rather than as lists of

  values.  This improves sharing and gives another speed up.
  Evaluation of the NixOS system attribute is now almost 7 times
  faster than the old evaluator.

7 files changed, 41 insertions, 34 deletions

diff --git a/src/libexpr/attr-path.cc b/src/libexpr/attr-path.cc
index b53837781..769acb6b8 100644
--- a/src/libexpr/attr-path.cc
+++ b/src/libexpr/attr-path.cc
@@ -61,7 +61,7 @@ void findAlongAttrPath(EvalState & state, const string & attrPath,
             if (attrIndex >= v.list.length)
                 throw Error(format("list index %1% in selection path `%2%' is out of range") % attrIndex % curPath);
 
-            v = v.list.elems[attrIndex];
+            v = *v.list.elems[attrIndex];
         }
         
     }
diff --git a/src/libexpr/eval-test.cc b/src/libexpr/eval-test.cc
index a7786561e..f7f91f503 100644
--- a/src/libexpr/eval-test.cc
+++ b/src/libexpr/eval-test.cc
@@ -113,6 +113,7 @@ void run(Strings args)
     doTest(state, "with { x = 1; }; let inherit x; y = x; in y");
     doTest(state, "builtins.toXML 123");
     doTest(state, "builtins.toXML { a.b = \"x\" + \"y\"; c = [ 1 2 ] ++ [ 3 4 ]; }");
+    doTest(state, "builtins.attrNames { x = 1; y = 2; }");
 
     state.printStats();
 }
diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc
index d6e39f365..69e7bd8b3 100644
--- a/src/libexpr/eval.cc
+++ b/src/libexpr/eval.cc
@@ -50,7 +50,7 @@ std::ostream & operator << (std::ostream & str, Value & v)
     case tList:
         str << "[ ";
         for (unsigned int n = 0; n < v.list.length; ++n)
-            str << v.list.elems[n] << " ";
+            str << *v.list.elems[n] << " ";
         str << "]";
         break;
     case tThunk:
@@ -102,7 +102,7 @@ EvalState::EvalState()
     , baseEnvDispl(0)
     , staticBaseEnv(false, 0)
 {
-    nrEnvs = nrValuesInEnvs = nrValuesInLists = nrValues = 0;
+    nrEnvs = nrValuesInEnvs = nrValues = nrListElems = 0;
     nrEvaluated = recursionDepth = maxRecursionDepth = 0;
     deepestStack = (char *) -1;
 
@@ -251,6 +251,7 @@ Value * EvalState::lookupVar(Env * env, const VarRef & var)
 
 Value * EvalState::allocValues(unsigned int count)
 {
+    nrValues += count;
     return new Value[count]; // !!! check destructor
 }
 
@@ -268,8 +269,8 @@ void EvalState::mkList(Value & v, unsigned int length)
 {
     v.type = tList;
     v.list.length = length;
-    v.list.elems = allocValues(length);
-    nrValuesInLists += length;
+    v.list.elems = new Value *[length];
+    nrListElems += length;
 }
 
 
@@ -461,8 +462,11 @@ void ExprLet::eval(EvalState & state, Env & env, Value & v)
 void ExprList::eval(EvalState & state, Env & env, Value & v)
 {
     state.mkList(v, elems.size());
-    for (unsigned int n = 0; n < v.list.length; ++n)
-        mkThunk(v.list.elems[n], env, elems[n]);
+    Value * vs = state.allocValues(v.list.length);
+    for (unsigned int n = 0; n < v.list.length; ++n) {
+        v.list.elems[n] = &vs[n];
+        mkThunk(vs[n], env, elems[n]);
+    }
 }
 
 
@@ -543,7 +547,6 @@ void EvalState::callFunction(Value & fun, Value & arg, Value & v)
             primOp->primOp.fun(*this, vArgs, v);
         } else {
             Value * v2 = allocValues(2);
-            nrValues += 2;
             v2[0] = fun;
             v2[1] = arg;
             v.type = tPrimOpApp;
@@ -734,8 +737,6 @@ void ExprOpConcatLists::eval(EvalState & state, Env & env, Value & v)
     Value v2; state.eval(env, e2, v2);
     state.forceList(v2);
     state.mkList(v, v1.list.length + v2.list.length);
-    /* !!! This loses sharing with the original lists.  We could use a
-       tCopy node, but that would use more memory. */
     for (unsigned int n = 0; n < v1.list.length; ++n)
         v.list.elems[n] = v1.list.elems[n];
     for (unsigned int n = 0; n < v2.list.length; ++n)
@@ -810,7 +811,7 @@ void EvalState::strictForceValue(Value & v)
     
     else if (v.type == tList) {
         for (unsigned int n = 0; n < v.list.length; ++n)
-            strictForceValue(v.list.elems[n]);
+            strictForceValue(*v.list.elems[n]);
     }
 }
 
@@ -951,11 +952,11 @@ string EvalState::coerceToString(Value & v, PathSet & context,
         if (v.type == tList) {
             string result;
             for (unsigned int n = 0; n < v.list.length; ++n) {
-                result += coerceToString(v.list.elems[n],
+                result += coerceToString(*v.list.elems[n],
                     context, coerceMore, copyToStore);
                 if (n < v.list.length - 1
                     /* !!! not quite correct */
-                    && (v.list.elems[n].type != tList || v.list.elems[n].list.length != 0))
+                    && (v.list.elems[n]->type != tList || v.list.elems[n]->list.length != 0))
                     result += " ";
             }
             return result;
@@ -1009,14 +1010,14 @@ bool EvalState::eqValues(Value & v1, Value & v2)
         case tList:
             if (v2.type != tList || v1.list.length != v2.list.length) return false;
             for (unsigned int n = 0; n < v1.list.length; ++n)
-                if (!eqValues(v1.list.elems[n], v2.list.elems[n])) return false;
+                if (!eqValues(*v1.list.elems[n], *v2.list.elems[n])) return false;
             return true;
 
         case tAttrs: {
             if (v2.type != tAttrs || v1.attrs->size() != v2.attrs->size()) return false;
             Bindings::iterator i, j;
             for (i = v1.attrs->begin(), j = v2.attrs->begin(); i != v1.attrs->end(); ++i, ++j)
-                if (!eqValues(i->second, j->second)) return false;
+                if (i->first != j->first || !eqValues(i->second, j->second)) return false;
             return true;
         }
 
@@ -1046,8 +1047,8 @@ void EvalState::printStats()
         % nrEnvs % (nrEnvs * sizeof(Env)));
     printMsg(v, format("  values allocated in environments: %1% (%2% bytes)")
         % nrValuesInEnvs % (nrValuesInEnvs * sizeof(Value)));
-    printMsg(v, format("  values allocated in lists: %1% (%2% bytes)")
-        % nrValuesInLists % (nrValuesInLists * sizeof(Value)));
+    printMsg(v, format("  list elements: %1% (%2% bytes)")
+        % nrListElems % (nrListElems * sizeof(Value *)));
     printMsg(v, format("  misc. values allocated: %1% (%2% bytes) ")
         % nrValues % (nrValues * sizeof(Value)));
     printMsg(v, format("  symbols in symbol table: %1%") % symbols.size());
diff --git a/src/libexpr/eval.hh b/src/libexpr/eval.hh
index 313a1d9b8..7252cae4b 100644
--- a/src/libexpr/eval.hh
+++ b/src/libexpr/eval.hh
@@ -76,7 +76,7 @@ struct Value
         Bindings * attrs;
         struct {
             unsigned int length;
-            Value * elems;
+            Value * * elems;
         } list;
         struct {
             Env * env;
@@ -282,8 +282,8 @@ private:
     
     unsigned long nrEnvs;
     unsigned long nrValuesInEnvs;
-    unsigned long nrValuesInLists;
     unsigned long nrValues;
+    unsigned long nrListElems;
     unsigned long nrEvaluated;
     unsigned int recursionDepth;
     unsigned int maxRecursionDepth;
diff --git a/src/libexpr/get-drvs.cc b/src/libexpr/get-drvs.cc
index 399470192..6964e3e3b 100644
--- a/src/libexpr/get-drvs.cc
+++ b/src/libexpr/get-drvs.cc
@@ -48,7 +48,7 @@ MetaInfo DrvInfo::queryMetaInfo(EvalState & state) const
         } else if (i->second.type == tList) {
             value.type = MetaValue::tpStrings;
             for (unsigned int j = 0; j < i->second.list.length; ++j)
-                value.stringValues.push_back(state.forceStringNoCtx(i->second.list.elems[j]));
+                value.stringValues.push_back(state.forceStringNoCtx(*i->second.list.elems[j]));
         } else continue;
         meta[i->first] = value;
     }
@@ -206,8 +206,8 @@ static void getDerivations(EvalState & state, Value & vIn,
             startNest(nest, lvlDebug,
                 format("evaluating list element"));
             string pathPrefix2 = addToPath(pathPrefix, (format("%1%") % n).str());
-            if (getDerivation(state, v.list.elems[n], pathPrefix2, drvs, done))
-                getDerivations(state, v.list.elems[n], pathPrefix2, autoArgs, drvs, done);
+            if (getDerivation(state, *v.list.elems[n], pathPrefix2, drvs, done))
+                getDerivations(state, *v.list.elems[n], pathPrefix2, autoArgs, drvs, done);
         }
     }
 
diff --git a/src/libexpr/primops.cc b/src/libexpr/primops.cc
index 0d7459fee..ae17506ce 100644
--- a/src/libexpr/primops.cc
+++ b/src/libexpr/primops.cc
@@ -311,7 +311,7 @@ static void prim_derivationStrict(EvalState & state, Value * * args, Value & v)
             if (key == "args") {
                 state.forceList(i->second);
                 for (unsigned int n = 0; n < i->second.list.length; ++n) {
-                    string s = state.coerceToString(i->second.list.elems[n], context, true);
+                    string s = state.coerceToString(*i->second.list.elems[n], context, true);
                     drv.args.push_back(s);
                 }
             }
@@ -651,14 +651,17 @@ static void prim_attrNames(EvalState & state, Value * * args, Value & v)
     state.forceAttrs(*args[0]);
 
     state.mkList(v, args[0]->attrs->size());
+    Value * vs = state.allocValues(v.list.length);
 
     StringSet names;
     foreach (Bindings::iterator, i, *args[0]->attrs)
         names.insert(i->first);
 
     unsigned int n = 0;
-    foreach (StringSet::iterator, i, names)
-        mkString(v.list.elems[n++], *i);
+    foreach (StringSet::iterator, i, names) {
+        v.list.elems[n] = &vs[n];
+        mkString(vs[n++], *i);
+    }
 }
 
 
@@ -701,8 +704,8 @@ static void prim_removeAttrs(EvalState & state, Value * * args, Value & v)
     state.cloneAttrs(*args[0], v);
 
     for (unsigned int i = 0; i < args[1]->list.length; ++i) {
-        state.forceStringNoCtx(args[1]->list.elems[i]);
-        v.attrs->erase(state.symbols.create(args[1]->list.elems[i].string.s));
+        state.forceStringNoCtx(*args[1]->list.elems[i]);
+        v.attrs->erase(state.symbols.create(args[1]->list.elems[i]->string.s));
     }
 }
 
@@ -718,7 +721,7 @@ static void prim_listToAttrs(EvalState & state, Value * * args, Value & v)
     state.mkAttrs(v);
 
     for (unsigned int i = 0; i < args[0]->list.length; ++i) {
-        Value & v2(args[0]->list.elems[i]);
+        Value & v2(*args[0]->list.elems[i]);
         state.forceAttrs(v2);
         
         Bindings::iterator j = v2.attrs->find(state.sName);
@@ -815,8 +818,8 @@ static void prim_head(EvalState & state, Value * * args, Value & v)
     state.forceList(*args[0]);
     if (args[0]->list.length == 0)
         throw Error("`head' called on an empty list");
-    state.forceValue(args[0]->list.elems[0]);
-    v = args[0]->list.elems[0];
+    state.forceValue(*args[0]->list.elems[0]);
+    v = *args[0]->list.elems[0];
 }
 
 
@@ -840,11 +843,13 @@ static void prim_map(EvalState & state, Value * * args, Value & v)
     state.forceList(*args[1]);
 
     state.mkList(v, args[1]->list.length);
+    Value * vs = state.allocValues(v.list.length);
 
     for (unsigned int n = 0; n < v.list.length; ++n) {
-        v.list.elems[n].type = tApp;
-        v.list.elems[n].app.left = args[0];
-        v.list.elems[n].app.right = &args[1]->list.elems[n];
+        v.list.elems[n] = &vs[n];
+        vs[n].type = tApp;
+        vs[n].app.left = args[0];
+        vs[n].app.right = args[1]->list.elems[n];
     }
 }
 
diff --git a/src/libexpr/value-to-xml.cc b/src/libexpr/value-to-xml.cc
index 0c8fc143c..58e89925c 100644
--- a/src/libexpr/value-to-xml.cc
+++ b/src/libexpr/value-to-xml.cc
@@ -97,7 +97,7 @@ static void printValueAsXML(EvalState & state, bool strict, Value & v,
         case tList: {
             XMLOpenElement _(doc, "list");
             for (unsigned int n = 0; n < v.list.length; ++n)
-                printValueAsXML(state, strict, v.list.elems[n], doc, context, drvsSeen);
+                printValueAsXML(state, strict, *v.list.elems[n], doc, context, drvsSeen);
             break;
         }