From 198d0338be7c105b6dbd707f98e0c223a8358240 Mon Sep 17 00:00:00 2001
From: Eelco Dolstra <eelco.dolstra@logicblox.com>
Date: Mon, 13 Aug 2012 01:53:10 -0400
Subject: Add a primop ‘concatLists’
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

This can serve as a generic efficient list builder.  For instance, the
function ‘catAttrs’ in Nixpkgs can be rewritten from

  attr: l: fold (s: l: if hasAttr attr s then [(getAttr attr s)] ++ l else l) [] l

to

  attr: l: builtins.concatLists (map (s: if hasAttr attr s then [(getAttr attr s)] else []) l)

Statistics before:

  time elapsed: 1.08683
  size of a value: 24
  environments allocated: 1384376 (35809568 bytes)
  list elements: 6946783 (55574264 bytes)
  list concatenations: 37434
  values allocated: 1760440 (42250560 bytes)
  attribute sets allocated: 392040
  right-biased unions: 186334
  values copied in right-biased unions: 591137
  symbols in symbol table: 18273
  number of thunks: 1297673
  number of thunks avoided: 1380759
  number of attr lookups: 430802
  number of primop calls: 628912
  number of function calls: 1333544

Statistics after (including new catAttrs):

  time elapsed: 0.959854
  size of a value: 24
  environments allocated: 1010198 (26829296 bytes)
  list elements: 1984878 (15879024 bytes)
  list concatenations: 30488
  values allocated: 1589760 (38154240 bytes)
  attribute sets allocated: 392040
  right-biased unions: 186334
  values copied in right-biased unions: 591137
  symbols in symbol table: 18274
  number of thunks: 1040925
  number of thunks avoided: 1038428
  number of attr lookups: 438419
  number of primop calls: 474844
  number of function calls: 959366
---
 src/libexpr/eval.cc | 29 +++++++++++++++++++++--------
 1 file changed, 21 insertions(+), 8 deletions(-)

(limited to 'src/libexpr/eval.cc')

diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc
index 871dfa64cb..5351ca0c34 100644
--- a/src/libexpr/eval.cc
+++ b/src/libexpr/eval.cc
@@ -912,16 +912,29 @@ void ExprOpUpdate::eval(EvalState & state, Env & env, Value & v)
 
 void ExprOpConcatLists::eval(EvalState & state, Env & env, Value & v)
 {
-    state.nrListConcats++;
     Value v1; e1->eval(state, env, v1);
-    state.forceList(v1);
     Value v2; e2->eval(state, env, v2);
-    state.forceList(v2);
-    state.mkList(v, v1.list.length + v2.list.length);
-    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)
-        v.list.elems[n + v1.list.length] = v2.list.elems[n];
+    Value * lists[2] = { &v1, &v2 };
+    state.concatLists(v, 2, lists);
+}
+
+
+void EvalState::concatLists(Value & v, unsigned int nrLists, Value * * lists)
+{
+    nrListConcats++;
+    
+    unsigned int len = 0;
+    for (unsigned int n = 0; n < nrLists; ++n) {
+        forceList(*lists[n]);
+        len += lists[n]->list.length;
+    }
+
+    mkList(v, len);
+    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 *));
+        pos += l;
+    }
 }
 
 
-- 
cgit 1.4.1