Optimize small lists

The value pointers of lists with 1 or 2 elements are now stored in the
list value itself. In particular, this makes the "concatMap (x: if
cond then [(f x)] else [])" idiom cheaper.

11 files changed, 157 insertions, 121 deletions

diff --git a/src/libexpr/attr-path.cc b/src/libexpr/attr-path.cc
index a4945111e0a8..55379f94b189 100644
--- a/src/libexpr/attr-path.cc
+++ b/src/libexpr/attr-path.cc
@@ -76,15 +76,15 @@ Value * findAlongAttrPath(EvalState & state, const string & attrPath,
 
         else if (apType == apIndex) {
 
-            if (v->type != tList)
+            if (!v->isList())
                 throw TypeError(
                     format("the expression selected by the selection path ‘%1%’ should be a list but is %2%")
                     % attrPath % showType(*v));
 
-            if (attrIndex >= v->list.length)
+            if (attrIndex >= v->listSize())
                 throw Error(format("list index %1% in selection path ‘%2%’ is out of range") % attrIndex % attrPath);
 
-            v = v->list.elems[attrIndex];
+            v = v->listElems()[attrIndex];
         }
 
     }
diff --git a/src/libexpr/eval-inline.hh b/src/libexpr/eval-inline.hh
index c275f7ba83e8..178e06c80186 100644
--- a/src/libexpr/eval-inline.hh
+++ b/src/libexpr/eval-inline.hh
@@ -66,7 +66,7 @@ inline void EvalState::forceAttrs(Value & v, const Pos & pos)
 inline void EvalState::forceList(Value & v)
 {
     forceValue(v);
-    if (v.type != tList)
+    if (!v.isList())
         throwTypeError("value is %1% while a list was expected", v);
 }
 
@@ -74,7 +74,7 @@ inline void EvalState::forceList(Value & v)
 inline void EvalState::forceList(Value & v, const Pos & pos)
 {
     forceValue(v);
-    if (v.type != tList)
+    if (!v.isList())
         throwTypeError("value is %1% while a list was expected, at %2%", v, pos);
 }
 
diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc
index b1436b842dc0..2dc7b17f685d 100644
--- a/src/libexpr/eval.cc
+++ b/src/libexpr/eval.cc
@@ -108,10 +108,12 @@ static void printValue(std::ostream & str, std::set<const Value *> & active, con
         str << "}";
         break;
     }
-    case tList:
+    case tList1:
+    case tList2:
+    case tListN:
         str << "[ ";
-        for (unsigned int n = 0; n < v.list.length; ++n) {
-            printValue(str, active, *v.list.elems[n]);
+        for (unsigned int n = 0; n < v.listSize(); ++n) {
+            printValue(str, active, *v.listElems()[n]);
             str << " ";
         }
         str << "]";
@@ -157,7 +159,7 @@ string showType(const Value & v)
         case tPath: return "a path";
         case tNull: return "null";
         case tAttrs: return "a set";
-        case tList: return "a list";
+        case tList1: case tList2: case tListN: return "a list";
         case tThunk: return "a thunk";
         case tApp: return "a function application";
         case tLambda: return "a function";
@@ -519,13 +521,19 @@ Bindings * EvalState::allocBindings(Bindings::size_t capacity)
 }
 
 
-void EvalState::mkList(Value & v, unsigned int length)
+void EvalState::mkList(Value & v, unsigned int size)
 {
     clearValue(v);
-    v.type = tList;
-    v.list.length = length;
-    v.list.elems = length ? (Value * *) allocBytes(length * sizeof(Value *)) : 0;
-    nrListElems += length;
+    if (size == 1)
+        v.type = tList1;
+    else if (size == 2)
+        v.type = tList2;
+    else {
+        v.type = tListN;
+        v.bigList.size = size;
+        v.bigList.elems = size ? (Value * *) allocBytes(size * sizeof(Value *)) : 0;
+    }
+    nrListElems += size;
 }
 
 
@@ -807,8 +815,8 @@ 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)
-        v.list.elems[n] = elems[n]->maybeThunk(state, env);
+    for (unsigned int n = 0; n < elems.size(); ++n)
+        v.listElems()[n] = elems[n]->maybeThunk(state, env);
 }
 
 
@@ -1201,20 +1209,21 @@ void EvalState::concatLists(Value & v, unsigned int nrLists, Value * * lists, co
     unsigned int len = 0;
     for (unsigned int n = 0; n < nrLists; ++n) {
         forceList(*lists[n], pos);
-        unsigned int l = lists[n]->list.length;
+        unsigned int l = lists[n]->listSize();
         len += l;
         if (l) nonEmpty = lists[n];
     }
 
-    if (nonEmpty && len == nonEmpty->list.length) {
+    if (nonEmpty && len == nonEmpty->listSize()) {
         v = *nonEmpty;
         return;
     }
 
     mkList(v, len);
+    auto out = v.listElems();
     for (unsigned int n = 0, pos = 0; n < nrLists; ++n) {
-        unsigned int l = lists[n]->list.length;
-        memcpy(v.list.elems + pos, lists[n]->list.elems, l * sizeof(Value *));
+        unsigned int l = lists[n]->listSize();
+        memcpy(out + pos, lists[n]->listElems(), l * sizeof(Value *));
         pos += l;
     }
 }
@@ -1290,9 +1299,9 @@ void EvalState::forceValueDeep(Value & v)
                 }
         }
 
-        else if (v.type == tList) {
-            for (unsigned int n = 0; n < v.list.length; ++n)
-                recurse(*v.list.elems[n]);
+        else if (v.isList()) {
+            for (unsigned int n = 0; n < v.listSize(); ++n)
+                recurse(*v.listElems()[n]);
         }
     };
 
@@ -1416,14 +1425,14 @@ string EvalState::coerceToString(const Pos & pos, Value & v, PathSet & context,
         if (v.type == tInt) return int2String(v.integer);
         if (v.type == tNull) return "";
 
-        if (v.type == tList) {
+        if (v.isList()) {
             string result;
-            for (unsigned int n = 0; n < v.list.length; ++n) {
-                result += coerceToString(pos, *v.list.elems[n],
+            for (unsigned int n = 0; n < v.listSize(); ++n) {
+                result += coerceToString(pos, *v.listElems()[n],
                     context, coerceMore, copyToStore);
-                if (n < v.list.length - 1
+                if (n < v.listSize() - 1
                     /* !!! not quite correct */
-                    && (v.list.elems[n]->type != tList || v.list.elems[n]->list.length != 0))
+                    && (!v.listElems()[n]->isList() || v.listElems()[n]->listSize() != 0))
                     result += " ";
             }
             return result;
@@ -1494,10 +1503,12 @@ bool EvalState::eqValues(Value & v1, Value & v2)
         case tNull:
             return true;
 
-        case tList:
-            if (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;
+        case tList1:
+        case tList2:
+        case tListN:
+            if (v1.listSize() != v2.listSize()) return false;
+            for (unsigned int n = 0; n < v1.listSize(); ++n)
+                if (!eqValues(*v1.listElems()[n], *v2.listElems()[n])) return false;
             return true;
 
         case tAttrs: {
@@ -1645,12 +1656,14 @@ size_t valueSize(Value & v)
                     sz += doValue(*i.value);
             }
             break;
-        case tList:
-            if (seen.find(v.list.elems) == seen.end()) {
-                seen.insert(v.list.elems);
-                sz += v.list.length * sizeof(Value *);
-                for (unsigned int n = 0; n < v.list.length; ++n)
-                    sz += doValue(*v.list.elems[n]);
+        case tList1:
+        case tList2:
+        case tListN:
+            if (seen.find(v.listElems()) == seen.end()) {
+                seen.insert(v.listElems());
+                sz += v.listSize() * sizeof(Value *);
+                for (unsigned int n = 0; n < v.listSize(); ++n)
+                    sz += doValue(*v.listElems()[n]);
             }
             break;
         case tThunk:
diff --git a/src/libexpr/get-drvs.cc b/src/libexpr/get-drvs.cc
index b7c3b0d33b11..1002ee6285af 100644
--- a/src/libexpr/get-drvs.cc
+++ b/src/libexpr/get-drvs.cc
@@ -39,9 +39,9 @@ DrvInfo::Outputs DrvInfo::queryOutputs()
             state->forceList(*i->value, *i->pos);
 
             /* For each output... */
-            for (unsigned int j = 0; j < i->value->list.length; ++j) {
+            for (unsigned int j = 0; j < i->value->listSize(); ++j) {
                 /* Evaluate the corresponding set. */
-                string name = state->forceStringNoCtx(*i->value->list.elems[j], *i->pos);
+                string name = state->forceStringNoCtx(*i->value->listElems()[j], *i->pos);
                 Bindings::iterator out = attrs->find(state->symbols.create(name));
                 if (out == attrs->end()) continue; // FIXME: throw error?
                 state->forceAttrs(*out->value);
@@ -94,9 +94,9 @@ StringSet DrvInfo::queryMetaNames()
 bool DrvInfo::checkMeta(Value & v)
 {
     state->forceValue(v);
-    if (v.type == tList) {
-        for (unsigned int n = 0; n < v.list.length; ++n)
-            if (!checkMeta(*v.list.elems[n])) return false;
+    if (v.isList()) {
+        for (unsigned int n = 0; n < v.listSize(); ++n)
+            if (!checkMeta(*v.listElems()[n])) return false;
         return true;
     }
     else if (v.type == tAttrs) {
@@ -277,13 +277,13 @@ static void getDerivations(EvalState & state, Value & vIn,
         }
     }
 
-    else if (v.type == tList) {
-        for (unsigned int n = 0; n < v.list.length; ++n) {
+    else if (v.isList()) {
+        for (unsigned int n = 0; n < v.listSize(); ++n) {
             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, ignoreAssertionFailures))
-                getDerivations(state, *v.list.elems[n], pathPrefix2, autoArgs, drvs, done, ignoreAssertionFailures);
+            if (getDerivation(state, *v.listElems()[n], pathPrefix2, drvs, done, ignoreAssertionFailures))
+                getDerivations(state, *v.listElems()[n], pathPrefix2, autoArgs, drvs, done, ignoreAssertionFailures);
         }
     }
 
diff --git a/src/libexpr/json-to-value.cc b/src/libexpr/json-to-value.cc
index 1892b0bac1af..0898b560911b 100644
--- a/src/libexpr/json-to-value.cc
+++ b/src/libexpr/json-to-value.cc
@@ -73,7 +73,7 @@ static void parseJSON(EvalState & state, const char * & s, Value & v)
         s++;
         state.mkList(v, values.size());
         for (size_t n = 0; n < values.size(); ++n)
-            v.list.elems[n] = values[n];
+            v.listElems()[n] = values[n];
     }
 
     else if (*s == '{') {
diff --git a/src/libexpr/primops.cc b/src/libexpr/primops.cc
index d1ad75a286e7..7a4aad3cd57b 100644
--- a/src/libexpr/primops.cc
+++ b/src/libexpr/primops.cc
@@ -100,8 +100,8 @@ static void prim_scopedImport(EvalState & state, const Pos & pos, Value * * args
             v2 = state.allocAttr(w, state.symbols.create(o.first));
             mkString(*v2, o.second.path,
                 singleton<PathSet>("!" + o.first + "!" + path));
-            outputsVal->list.elems[outputs_index] = state.allocValue();
-            mkString(*(outputsVal->list.elems[outputs_index++]), o.first);
+            outputsVal->listElems()[outputs_index] = state.allocValue();
+            mkString(*(outputsVal->listElems()[outputs_index++]), o.first);
         }
         w.attrs->sort();
         Value fun;
@@ -188,7 +188,7 @@ static void prim_typeOf(EvalState & state, const Pos & pos, Value * * args, Valu
         case tPath: t = "path"; break;
         case tNull: t = "null"; break;
         case tAttrs: t = "set"; break;
-        case tList: t = "list"; break;
+        case tList1: case tList2: case tListN: t = "list"; break;
         case tLambda:
         case tPrimOp:
         case tPrimOpApp:
@@ -284,8 +284,8 @@ static void prim_genericClosure(EvalState & state, const Pos & pos, Value * * ar
     state.forceList(*startSet->value, pos);
 
     ValueList workSet;
-    for (unsigned int n = 0; n < startSet->value->list.length; ++n)
-        workSet.push_back(startSet->value->list.elems[n]);
+    for (unsigned int n = 0; n < startSet->value->listSize(); ++n)
+        workSet.push_back(startSet->value->listElems()[n]);
 
     /* Get the operator. */
     Bindings::iterator op =
@@ -323,9 +323,9 @@ static void prim_genericClosure(EvalState & state, const Pos & pos, Value * * ar
         state.forceList(call, pos);
 
         /* Add the values returned by the operator to the work set. */
-        for (unsigned int n = 0; n < call.list.length; ++n) {
-            state.forceValue(*call.list.elems[n]);
-            workSet.push_back(call.list.elems[n]);
+        for (unsigned int n = 0; n < call.listSize(); ++n) {
+            state.forceValue(*call.listElems()[n]);
+            workSet.push_back(call.listElems()[n]);
         }
     }
 
@@ -333,7 +333,7 @@ static void prim_genericClosure(EvalState & state, const Pos & pos, Value * * ar
     state.mkList(v, res.size());
     unsigned int n = 0;
     for (auto & i : res)
-        v.list.elems[n++] = i;
+        v.listElems()[n++] = i;
 }
 
 
@@ -495,8 +495,8 @@ static void prim_derivationStrict(EvalState & state, const Pos & pos, Value * *
                command-line arguments to the builder. */
             if (key == "args") {
                 state.forceList(*i.value, pos);
-                for (unsigned int n = 0; n < i.value->list.length; ++n) {
-                    string s = state.coerceToString(posDrvName, *i.value->list.elems[n], context, true);
+                for (unsigned int n = 0; n < i.value->listSize(); ++n) {
+                    string s = state.coerceToString(posDrvName, *i.value->listElems()[n], context, true);
                     drv.args.push_back(s);
                 }
             }
@@ -766,8 +766,8 @@ static void prim_findFile(EvalState & state, const Pos & pos, Value * * args, Va
     SearchPath searchPath;
 
     PathSet context;
-    for (unsigned int n = 0; n < args[0]->list.length; ++n) {
-        Value & v2(*args[0]->list.elems[n]);
+    for (unsigned int n = 0; n < args[0]->listSize(); ++n) {
+        Value & v2(*args[0]->listElems()[n]);
         state.forceAttrs(v2, pos);
 
         string prefix;
@@ -972,9 +972,9 @@ static void prim_attrNames(EvalState & state, const Pos & pos, Value * * args, V
 
     unsigned int n = 0;
     for (auto & i : *args[0]->attrs)
-        mkString(*(v.list.elems[n++] = state.allocValue()), i.name);
+        mkString(*(v.listElems()[n++] = state.allocValue()), i.name);
 
-    std::sort(v.list.elems, v.list.elems + n,
+    std::sort(v.listElems(), v.listElems() + n,
         [](Value * v1, Value * v2) { return strcmp(v1->string.s, v2->string.s) < 0; });
 }
 
@@ -989,13 +989,13 @@ static void prim_attrValues(EvalState & state, const Pos & pos, Value * * args,
 
     unsigned int n = 0;
     for (auto & i : *args[0]->attrs)
-        v.list.elems[n++] = (Value *) &i;
+        v.listElems()[n++] = (Value *) &i;
 
-    std::sort(v.list.elems, v.list.elems + n,
+    std::sort(v.listElems(), v.listElems() + n,
         [](Value * v1, Value * v2) { return (string) ((Attr *) v1)->name < (string) ((Attr *) v2)->name; });
 
     for (unsigned int i = 0; i < n; ++i)
-        v.list.elems[i] = ((Attr *) v.list.elems[i])->value;
+        v.listElems()[i] = ((Attr *) v.listElems()[i])->value;
 }
 
 
@@ -1052,9 +1052,9 @@ static void prim_removeAttrs(EvalState & state, const Pos & pos, Value * * args,
 
     /* Get the attribute names to be removed. */
     std::set<Symbol> names;
-    for (unsigned int i = 0; i < args[1]->list.length; ++i) {
-        state.forceStringNoCtx(*args[1]->list.elems[i], pos);
-        names.insert(state.symbols.create(args[1]->list.elems[i]->string.s));
+    for (unsigned int i = 0; i < args[1]->listSize(); ++i) {
+        state.forceStringNoCtx(*args[1]->listElems()[i], pos);
+        names.insert(state.symbols.create(args[1]->listElems()[i]->string.s));
     }
 
     /* Copy all attributes not in that set.  Note that we don't need
@@ -1077,12 +1077,12 @@ static void prim_listToAttrs(EvalState & state, const Pos & pos, Value * * args,
 {
     state.forceList(*args[0], pos);
 
-    state.mkAttrs(v, args[0]->list.length);
+    state.mkAttrs(v, args[0]->listSize());
 
     std::set<Symbol> seen;
 
-    for (unsigned int i = 0; i < args[0]->list.length; ++i) {
-        Value & v2(*args[0]->list.elems[i]);
+    for (unsigned int i = 0; i < args[0]->listSize(); ++i) {
+        Value & v2(*args[0]->listElems()[i]);
         state.forceAttrs(v2, pos);
 
         Bindings::iterator j = v2.attrs->find(state.sName);
@@ -1135,11 +1135,11 @@ static void prim_catAttrs(EvalState & state, const Pos & pos, Value * * args, Va
     Symbol attrName = state.symbols.create(state.forceStringNoCtx(*args[0], pos));
     state.forceList(*args[1], pos);
 
-    Value * res[args[1]->list.length];
+    Value * res[args[1]->listSize()];
     unsigned int found = 0;
 
-    for (unsigned int n = 0; n < args[1]->list.length; ++n) {
-        Value & v2(*args[1]->list.elems[n]);
+    for (unsigned int n = 0; n < args[1]->listSize(); ++n) {
+        Value & v2(*args[1]->listElems()[n]);
         state.forceAttrs(v2, pos);
         Bindings::iterator i = v2.attrs->find(attrName);
         if (i != v2.attrs->end())
@@ -1148,7 +1148,7 @@ static void prim_catAttrs(EvalState & state, const Pos & pos, Value * * args, Va
 
     state.mkList(v, found);
     for (unsigned int n = 0; n < found; ++n)
-        v.list.elems[n] = res[n];
+        v.listElems()[n] = res[n];
 }
 
 
@@ -1193,17 +1193,17 @@ static void prim_functionArgs(EvalState & state, const Pos & pos, Value * * args
 static void prim_isList(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
     state.forceValue(*args[0]);
-    mkBool(v, args[0]->type == tList);
+    mkBool(v, args[0]->isList());
 }
 
 
 static void elemAt(EvalState & state, const Pos & pos, Value & list, int n, Value & v)
 {
     state.forceList(list, pos);
-    if (n < 0 || (unsigned int) n >= list.list.length)
+    if (n < 0 || (unsigned int) n >= list.listSize())
         throw Error(format("list index %1% is out of bounds, at %2%") % n % pos);
-    state.forceValue(*list.list.elems[n]);
-    v = *list.list.elems[n];
+    state.forceValue(*list.listElems()[n]);
+    v = *list.listElems()[n];
 }
 
 
@@ -1227,11 +1227,11 @@ static void prim_head(EvalState & state, const Pos & pos, Value * * args, Value
 static void prim_tail(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
     state.forceList(*args[0], pos);
-    if (args[0]->list.length == 0)
+    if (args[0]->listSize() == 0)
         throw Error(format("‘tail’ called on an empty list, at %1%") % pos);
-    state.mkList(v, args[0]->list.length - 1);
-    for (unsigned int n = 0; n < v.list.length; ++n)
-        v.list.elems[n] = args[0]->list.elems[n + 1];
+    state.mkList(v, args[0]->listSize() - 1);
+    for (unsigned int n = 0; n < v.listSize(); ++n)
+        v.listElems()[n] = args[0]->listElems()[n + 1];
 }
 
 
@@ -1241,11 +1241,11 @@ static void prim_map(EvalState & state, const Pos & pos, Value * * args, Value &
     state.forceFunction(*args[0], pos);
     state.forceList(*args[1], pos);
 
-    state.mkList(v, args[1]->list.length);
+    state.mkList(v, args[1]->listSize());
 
-    for (unsigned int n = 0; n < v.list.length; ++n)
-        mkApp(*(v.list.elems[n] = state.allocValue()),
-            *args[0], *args[1]->list.elems[n]);
+    for (unsigned int n = 0; n < v.listSize(); ++n)
+        mkApp(*(v.listElems()[n] = state.allocValue()),
+            *args[0], *args[1]->listElems()[n]);
 }
 
 
@@ -1258,15 +1258,15 @@ static void prim_filter(EvalState & state, const Pos & pos, Value * * args, Valu
     state.forceList(*args[1], pos);
 
     // FIXME: putting this on the stack is risky.
-    Value * vs[args[1]->list.length];
+    Value * vs[args[1]->listSize()];
     unsigned int k = 0;
 
     bool same = true;
-    for (unsigned int n = 0; n < args[1]->list.length; ++n) {
+    for (unsigned int n = 0; n < args[1]->listSize(); ++n) {
         Value res;
-        state.callFunction(*args[0], *args[1]->list.elems[n], res, noPos);
+        state.callFunction(*args[0], *args[1]->listElems()[n], res, noPos);
         if (state.forceBool(res))
-            vs[k++] = args[1]->list.elems[n];
+            vs[k++] = args[1]->listElems()[n];
         else
             same = false;
     }
@@ -1275,7 +1275,7 @@ static void prim_filter(EvalState & state, const Pos & pos, Value * * args, Valu
         v = *args[1];
     else {
         state.mkList(v, k);
-        for (unsigned int n = 0; n < k; ++n) v.list.elems[n] = vs[n];
+        for (unsigned int n = 0; n < k; ++n) v.listElems()[n] = vs[n];
     }
 }
 
@@ -1285,8 +1285,8 @@ static void prim_elem(EvalState & state, const Pos & pos, Value * * args, Value
 {
     bool res = false;
     state.forceList(*args[1], pos);
-    for (unsigned int n = 0; n < args[1]->list.length; ++n)
-        if (state.eqValues(*args[0], *args[1]->list.elems[n])) {
+    for (unsigned int n = 0; n < args[1]->listSize(); ++n)
+        if (state.eqValues(*args[0], *args[1]->listElems()[n])) {
             res = true;
             break;
         }
@@ -1298,7 +1298,7 @@ static void prim_elem(EvalState & state, const Pos & pos, Value * * args, Value
 static void prim_concatLists(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
     state.forceList(*args[0], pos);
-    state.concatLists(v, args[0]->list.length, args[0]->list.elems, pos);
+    state.concatLists(v, args[0]->listSize(), args[0]->listElems(), pos);
 }
 
 
@@ -1306,7 +1306,7 @@ static void prim_concatLists(EvalState & state, const Pos & pos, Value * * args,
 static void prim_length(EvalState & state, const Pos & pos, Value * * args, Value & v)
 {
     state.forceList(*args[0], pos);
-    mkInt(v, args[0]->list.length);
+    mkInt(v, args[0]->listSize());
 }
 
 
@@ -1319,12 +1319,12 @@ static void prim_foldlStrict(EvalState & state, const Pos & pos, Value * * args,
 
     Value * vCur = args[1];
 
-    if (args[2]->list.length)
-        for (unsigned int n = 0; n < args[2]->list.length; ++n) {
+    if (args[2]->listSize())
+        for (unsigned int n = 0; n < args[2]->listSize(); ++n) {
             Value vTmp;
             state.callFunction(*args[0], *vCur, vTmp, pos);
-            vCur = n == args[2]->list.length - 1 ? &v : state.allocValue();
-            state.callFunction(vTmp, *args[2]->list.elems[n], *vCur, pos);
+            vCur = n == args[2]->listSize() - 1 ? &v : state.allocValue();
+            state.callFunction(vTmp, *args[2]->listElems()[n], *vCur, pos);
         }
     else
         v = *vCur;
@@ -1339,8 +1339,8 @@ static void anyOrAll(bool any, EvalState & state, const Pos & pos, Value * * arg
     state.forceList(*args[1], pos);
 
     Value vTmp;
-    for (unsigned int n = 0; n < args[1]->list.length; ++n) {
-        state.callFunction(*args[0], *args[1]->list.elems[n], vTmp, pos);
+    for (unsigned int n = 0; n < args[1]->listSize(); ++n) {
+        state.callFunction(*args[0], *args[1]->listElems()[n], vTmp, pos);
         bool res = state.forceBool(vTmp);
         if (res == any) {
             mkBool(v, any);
@@ -1507,9 +1507,9 @@ static void prim_match(EvalState & state, const Pos & pos, Value * * args, Value
     for (unsigned int n = 0; n < len; ++n) {
         auto i = subs.find(n);
         if (i == subs.end())
-            mkNull(*(v.list.elems[n] = state.allocValue()));
+            mkNull(*(v.listElems()[n] = state.allocValue()));
         else
-            mkString(*(v.list.elems[n] = state.allocValue()), i->second);
+            mkString(*(v.listElems()[n] = state.allocValue()), i->second);
     }
 }
 
@@ -1743,7 +1743,7 @@ void EvalState::createBaseEnv()
     mkList(v, searchPath.size());
     int n = 0;
     for (auto & i : searchPath) {
-        v2 = v.list.elems[n++] = allocValue();
+        v2 = v.listElems()[n++] = allocValue();
         mkAttrs(*v2, 2);
         mkString(*allocAttr(*v2, symbols.create("path")), i.second);
         mkString(*allocAttr(*v2, symbols.create("prefix")), i.first);
diff --git a/src/libexpr/value-to-json.cc b/src/libexpr/value-to-json.cc
index b08d824975aa..b0cf85e21f18 100644
--- a/src/libexpr/value-to-json.cc
+++ b/src/libexpr/value-to-json.cc
@@ -71,11 +71,11 @@ void printValueAsJSON(EvalState & state, bool strict,
             break;
         }
 
-        case tList: {
+        case tList1: case tList2: case tListN: {
             JSONList json(str);
-            for (unsigned int n = 0; n < v.list.length; ++n) {
+            for (unsigned int n = 0; n < v.listSize(); ++n) {
                 json.elem();
-                printValueAsJSON(state, strict, *v.list.elems[n], str, context);
+                printValueAsJSON(state, strict, *v.listElems()[n], str, context);
             }
             break;
         }
diff --git a/src/libexpr/value-to-xml.cc b/src/libexpr/value-to-xml.cc
index 9cb04bad3769..cb52ce1e67bd 100644
--- a/src/libexpr/value-to-xml.cc
+++ b/src/libexpr/value-to-xml.cc
@@ -119,10 +119,10 @@ static void printValueAsXML(EvalState & state, bool strict, bool location,
 
             break;
 
-        case tList: {
+        case tList1: case tList2: case tListN: {
             XMLOpenElement _(doc, "list");
-            for (unsigned int n = 0; n < v.list.length; ++n)
-                printValueAsXML(state, strict, location, *v.list.elems[n], doc, context, drvsSeen);
+            for (unsigned int n = 0; n < v.listSize(); ++n)
+                printValueAsXML(state, strict, location, *v.listElems()[n], doc, context, drvsSeen);
             break;
         }
 
diff --git a/src/libexpr/value.hh b/src/libexpr/value.hh
index c06b5a6d1153..e6d1502cb607 100644
--- a/src/libexpr/value.hh
+++ b/src/libexpr/value.hh
@@ -12,7 +12,9 @@ typedef enum {
     tPath,
     tNull,
     tAttrs,
-    tList,
+    tList1,
+    tList2,
+    tListN,
     tThunk,
     tApp,
     tLambda,
@@ -119,9 +121,10 @@ struct Value
         const char * path;
         Bindings * attrs;
         struct {
-            unsigned int length;
+            unsigned int size;
             Value * * elems;
-        } list;
+        } bigList;
+        Value * smallList[2];
         struct {
             Env * env;
             Expr * expr;
@@ -139,6 +142,26 @@ struct Value
         } primOpApp;
         ExternalValueBase * external;
     };
+
+    bool isList() const
+    {
+        return type == tList1 || type == tList2 || type == tListN;
+    }
+
+    Value * * listElems()
+    {
+        return type == tList1 || type == tList2 ? smallList : bigList.elems;
+    }
+
+    const Value * const * listElems() const
+    {
+        return type == tList1 || type == tList2 ? smallList : bigList.elems;
+    }
+
+    unsigned int listSize() const
+    {
+        return type == tList1 ? 1 : type == tList2 ? 2 : bigList.size;
+    }
 };
 
 
diff --git a/src/nix-env/nix-env.cc b/src/nix-env/nix-env.cc
index 04f1016167a9..97a2bbdb7de0 100644
--- a/src/nix-env/nix-env.cc
+++ b/src/nix-env/nix-env.cc
@@ -1127,13 +1127,13 @@ static void opQuery(Globals & globals, Strings opFlags, Strings opArgs)
                                     attrs2["type"] = "bool";
                                     attrs2["value"] = v->boolean ? "true" : "false";
                                     xml.writeEmptyElement("meta", attrs2);
-                                } else if (v->type == tList) {
+                                } else if (v->isList()) {
                                     attrs2["type"] = "strings";
                                     XMLOpenElement m(xml, "meta", attrs2);
-                                    for (unsigned int j = 0; j < v->list.length; ++j) {
-                                        if (v->list.elems[j]->type != tString) continue;
+                                    for (unsigned int j = 0; j < v->listSize(); ++j) {
+                                        if (v->listElems()[j]->type != tString) continue;
                                         XMLAttrs attrs3;
-                                        attrs3["value"] = v->list.elems[j]->string.s;
+                                        attrs3["value"] = v->listElems()[j]->string.s;
                                         xml.writeEmptyElement("string", attrs3);
                                     }
                                 }
diff --git a/src/nix-env/user-env.cc b/src/nix-env/user-env.cc
index 35b1628e3c5c..9a20b94334f2 100644
--- a/src/nix-env/user-env.cc
+++ b/src/nix-env/user-env.cc
@@ -52,7 +52,7 @@ bool createUserEnv(EvalState & state, DrvInfos & elems,
         Path drvPath = keepDerivations ? i.queryDrvPath() : "";
 
         Value & v(*state.allocValue());
-        manifest.list.elems[n++] = &v;
+        manifest.listElems()[n++] = &v;
         state.mkAttrs(v, 16);
 
         mkString(*state.allocAttr(v, state.sType), "derivation");
@@ -69,7 +69,7 @@ bool createUserEnv(EvalState & state, DrvInfos & elems,
         state.mkList(vOutputs, outputs.size());
         unsigned int m = 0;
         for (auto & j : outputs) {
-            mkString(*(vOutputs.list.elems[m++] = state.allocValue()), j.first);
+            mkString(*(vOutputs.listElems()[m++] = state.allocValue()), j.first);
             Value & vOutputs = *state.allocAttr(v, state.symbols.create(j.first));
             state.mkAttrs(vOutputs, 2);
             mkString(*state.allocAttr(vOutputs, state.sOutPath), j.second);