* Merge the GC branch.

20 files changed, 607 insertions, 408 deletions

diff --git a/src/libexpr/Makefile.am b/src/libexpr/Makefile.am
index e7228e183..6c38ecdd5 100644
--- a/src/libexpr/Makefile.am
+++ b/src/libexpr/Makefile.am
@@ -11,7 +11,7 @@ pkginclude_HEADERS = \
  names.hh symbol-table.hh
 
 libexpr_la_LIBADD = ../libutil/libutil.la ../libstore/libstore.la \
- ../boost/format/libformat.la
+ ../boost/format/libformat.la @boehmgc_lib@
 
 BUILT_SOURCES = \
  parser-tab.hh lexer-tab.hh parser-tab.cc lexer-tab.cc
diff --git a/src/libexpr/attr-path.cc b/src/libexpr/attr-path.cc
index 0660ba1c1..49c08339a 100644
--- a/src/libexpr/attr-path.cc
+++ b/src/libexpr/attr-path.cc
@@ -5,8 +5,9 @@
 namespace nix {
 
 
+// !!! Shouldn't we return a pointer to a Value?
 void findAlongAttrPath(EvalState & state, const string & attrPath,
-    const Bindings & autoArgs, Expr * e, Value & v)
+    Bindings & autoArgs, Expr * e, Value & v)
 {
     Strings tokens = tokenizeString(attrPath, ".");
 
@@ -48,7 +49,7 @@ void findAlongAttrPath(EvalState & state, const string & attrPath,
             Bindings::iterator a = v.attrs->find(state.symbols.create(attr));
             if (a == v.attrs->end())
                 throw Error(format("attribute `%1%' in selection path `%2%' not found") % attr % curPath);
-            v = a->second.value;
+            v = *a->value;
         }
 
         else if (apType == apIndex) {
diff --git a/src/libexpr/attr-path.hh b/src/libexpr/attr-path.hh
index b4f5c29d2..b106da5ef 100644
--- a/src/libexpr/attr-path.hh
+++ b/src/libexpr/attr-path.hh
@@ -11,7 +11,7 @@ namespace nix {
 
     
 void findAlongAttrPath(EvalState & state, const string & attrPath,
-    const Bindings & autoArgs, Expr * e, Value & v);
+    Bindings & autoArgs, Expr * e, Value & v);
 
     
 }
diff --git a/src/libexpr/common-opts.cc b/src/libexpr/common-opts.cc
index 9131951e3..c364aa9cb 100644
--- a/src/libexpr/common-opts.cc
+++ b/src/libexpr/common-opts.cc
@@ -20,13 +20,17 @@ bool parseOptionArg(const string & arg, Strings::iterator & i,
     if (i == argsEnd) throw error;
     string value = *i++;
 
-    Value & v(autoArgs[state.symbols.create(name)].value);
+    /* !!! check for duplicates! */
+    Value * v = state.allocValue();
+    autoArgs.push_back(Attr(state.symbols.create(name), v));
 
     if (arg == "--arg")
-        state.mkThunk_(v, parseExprFromString(state, value, absPath(".")));
+        state.mkThunk_(*v, parseExprFromString(state, value, absPath(".")));
     else
-        mkString(v, value);
-    
+        mkString(*v, value);
+
+    autoArgs.sort(); // !!! inefficient
+
     return true;
 }
 
diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc
index e55f28822..3ef17c36a 100644
--- a/src/libexpr/eval.cc
+++ b/src/libexpr/eval.cc
@@ -8,12 +8,43 @@
 
 #include <cstring>
 
+#if HAVE_BOEHMGC
+
+#include <gc/gc.h>
+#include <gc/gc_cpp.h>
+
+#define NEW new (UseGC)
+
+#else
+
+#define GC_STRDUP strdup
+#define GC_MALLOC malloc
+
+#define NEW new
+
+#endif
+
 
 #define LocalNoInline(f) static f __attribute__((noinline)); f
 #define LocalNoInlineNoReturn(f) static f __attribute__((noinline, noreturn)); f
 
 
 namespace nix {
+
+
+Bindings::iterator Bindings::find(const Symbol & name)
+{
+    Attr key(name, 0);
+    iterator i = lower_bound(begin(), end(), key);
+    if (i != end() && i->name == name) return i;
+    return end();
+}
+
+
+void Bindings::sort()
+{
+    std::sort(begin(), end());
+}
     
 
 std::ostream & operator << (std::ostream & str, const Value & v)
@@ -46,7 +77,7 @@ std::ostream & operator << (std::ostream & str, const Value & v)
         typedef std::map<string, Value *> Sorted;
         Sorted sorted;
         foreach (Bindings::iterator, i, *v.attrs)
-            sorted[i->first] = &i->second.value;
+            sorted[i->name] = i->value;
         foreach (Sorted::iterator, i, sorted)
             str << i->first << " = " << *i->second << "; ";
         str << "}";
@@ -60,7 +91,6 @@ std::ostream & operator << (std::ostream & str, const Value & v)
         break;
     case tThunk:
     case tApp:
-    case tCopy:
         str << "<CODE>";
         break;
     case tLambda:
@@ -92,7 +122,6 @@ string showType(const Value & v)
         case tThunk: return "a thunk";
         case tApp: return "a function application";
         case tLambda: return "a function";
-        case tCopy: return "a copy";
         case tBlackhole: return "a black hole";
         case tPrimOp: return "a built-in function";
         case tPrimOpApp: return "a partially applied built-in function";
@@ -116,6 +145,7 @@ EvalState::EvalState()
 {
     nrEnvs = nrValuesInEnvs = nrValues = nrListElems = 0;
     nrEvaluated = recursionDepth = maxRecursionDepth = 0;
+    nrAttrsets = nrOpUpdates = nrOpUpdateValuesCopied = 0;
     deepestStack = (char *) -1;
 
     createBaseEnv();
@@ -132,25 +162,26 @@ EvalState::~EvalState()
 
 void EvalState::addConstant(const string & name, Value & v)
 {
+    Value * v2 = allocValue();
+    *v2 = v;
     staticBaseEnv.vars[symbols.create(name)] = baseEnvDispl;
-    baseEnv.values[baseEnvDispl++] = v;
+    baseEnv.values[baseEnvDispl++] = v2;
     string name2 = string(name, 0, 2) == "__" ? string(name, 2) : name;
-    (*baseEnv.values[0].attrs)[symbols.create(name2)].value = v;
+    baseEnv.values[0]->attrs->push_back(Attr(symbols.create(name2), v2));
 }
 
 
 void EvalState::addPrimOp(const string & name,
-    unsigned int arity, PrimOp primOp)
+    unsigned int arity, PrimOpFun primOp)
 {
-    Value v;
+    Value * v = allocValue();
     string name2 = string(name, 0, 2) == "__" ? string(name, 2) : name;
-    v.type = tPrimOp;
-    v.primOp.arity = arity;
-    v.primOp.fun = primOp;
-    v.primOp.name = strdup(name2.c_str());
+    Symbol sym = symbols.create(name2);
+    v->type = tPrimOp;
+    v->primOp = NEW PrimOp(primOp, arity, sym);
     staticBaseEnv.vars[symbols.create(name)] = baseEnvDispl;
     baseEnv.values[baseEnvDispl++] = v;
-    (*baseEnv.values[0].attrs)[symbols.create(name2)].value = v;
+    baseEnv.values[0]->attrs->push_back(Attr(sym, v));
 }
 
 
@@ -218,7 +249,7 @@ LocalNoInline(void addErrorPrefix(Error & e, const char * s, const string & s2,
 void mkString(Value & v, const char * s)
 {
     v.type = tString;
-    v.string.s = strdup(s);
+    v.string.s = GC_STRDUP(s);
     v.string.context = 0;
 }
 
@@ -228,18 +259,28 @@ void mkString(Value & v, const string & s, const PathSet & context)
     mkString(v, s.c_str());
     if (!context.empty()) {
         unsigned int n = 0;
-        v.string.context = new const char *[context.size() + 1];
-        foreach (PathSet::const_iterator, i, context) 
-            v.string.context[n++] = strdup(i->c_str());
+        v.string.context = (const char * *)
+            GC_MALLOC((context.size() + 1) * sizeof(char *));
+        foreach (PathSet::const_iterator, i, context)  
+            v.string.context[n++] = GC_STRDUP(i->c_str());
         v.string.context[n] = 0;
     }
 }
 
 
+void mkString(Value & v, const Symbol & s)
+{
+    v.type = tString;
+    v.string.s = ((string) s).c_str();
+    v.string.context = 0;
+}
+
+
 void mkPath(Value & v, const char * s)
 {
+    clearValue(v);
     v.type = tPath;
-    v.path = strdup(s);
+    v.path = GC_STRDUP(s);
 }
 
 
@@ -249,22 +290,22 @@ Value * EvalState::lookupVar(Env * env, const VarRef & var)
     
     if (var.fromWith) {
         while (1) {
-            Bindings::iterator j = env->values[0].attrs->find(var.name);
-            if (j != env->values[0].attrs->end())
-                return &j->second.value;
+            Bindings::iterator j = env->values[0]->attrs->find(var.name);
+            if (j != env->values[0]->attrs->end())
+                return j->value;
             if (env->prevWith == 0)
                 throwEvalError("undefined variable `%1%'", var.name);
             for (unsigned int l = env->prevWith; l; --l, env = env->up) ;
         }
     } else
-        return &env->values[var.displ];
+        return env->values[var.displ];
 }
 
 
-Value * EvalState::allocValues(unsigned int count)
+Value * EvalState::allocValue()
 {
-    nrValues += count;
-    return new Value[count]; // !!! check destructor
+    nrValues++;
+    return (Value *) GC_MALLOC(sizeof(Value));
 }
 
 
@@ -272,24 +313,51 @@ Env & EvalState::allocEnv(unsigned int size)
 {
     nrEnvs++;
     nrValuesInEnvs += size;
-    Env * env = (Env *) malloc(sizeof(Env) + size * sizeof(Value));
+    Env * env = (Env *) GC_MALLOC(sizeof(Env) + size * sizeof(Value *));
+
+    /* Clear the values because maybeThunk() expects this. */
+    for (unsigned i = 0; i < size; ++i)
+        env->values[i] = 0;
+    
     return *env;
 }
 
 
+Value * EvalState::allocAttr(Value & vAttrs, const Symbol & name)
+{
+    Value * v = allocValue();
+    vAttrs.attrs->push_back(Attr(name, v));
+    return v;
+}
+
+    
 void EvalState::mkList(Value & v, unsigned int length)
 {
     v.type = tList;
     v.list.length = length;
-    v.list.elems = new Value *[length];
+    v.list.elems = (Value * *) GC_MALLOC(length * sizeof(Value *));
     nrListElems += length;
 }
 
 
-void EvalState::mkAttrs(Value & v)
+void EvalState::mkAttrs(Value & v, unsigned int expected)
 {
+    clearValue(v);
     v.type = tAttrs;
-    v.attrs = new Bindings;
+    v.attrs = NEW Bindings;
+    v.attrs->reserve(expected);
+    nrAttrsets++;
+}
+
+
+unsigned long nrThunks = 0;
+
+static inline void mkThunk(Value & v, Env & env, Expr * expr)
+{
+    v.type = tThunk;
+    v.thunk.env = &env;
+    v.thunk.expr = expr;
+    nrThunks++;
 }
 
 
@@ -299,14 +367,28 @@ void EvalState::mkThunk_(Value & v, Expr * expr)
 }
 
 
-void EvalState::cloneAttrs(Value & src, Value & dst)
+unsigned long nrAvoided = 0;
+
+/* Create a thunk for the delayed computation of the given expression
+   in the given environment.  But if the expression is a variable,
+   then look it up right away.  This significantly reduces the number
+   of thunks allocated. */
+Value * EvalState::maybeThunk(Env & env, Expr * expr)
 {
-    mkAttrs(dst);
-    foreach (Bindings::iterator, i, *src.attrs) {
-        Attr & a = (*dst.attrs)[i->first];
-        mkCopy(a.value, i->second.value);
-        a.pos = i->second.pos;
+    ExprVar * var;
+    /* Ignore variables from `withs' because they can throw an
+       exception. */
+    if ((var = dynamic_cast<ExprVar *>(expr))) {
+        Value * v = lookupVar(&env, var->info);
+        /* The value might not be initialised in the environment yet.
+           In that case, ignore it. */
+        if (v) { nrAvoided++; return v; }
     }
+
+    Value * v = allocValue();
+    mkThunk(*v, env, expr);
+
+    return v;
 }
 
 
@@ -404,7 +486,7 @@ void ExprInt::eval(EvalState & state, Env & env, Value & v)
 
 void ExprString::eval(EvalState & state, Env & env, Value & v)
 {
-    mkString(v, s.c_str());
+    mkString(v, s);
 }
 
 
@@ -416,35 +498,38 @@ void ExprPath::eval(EvalState & state, Env & env, Value & v)
 
 void ExprAttrs::eval(EvalState & state, Env & env, Value & v)
 {
-    state.mkAttrs(v);
+    state.mkAttrs(v, attrs.size());
 
     if (recursive) {
         /* Create a new environment that contains the attributes in
            this `rec'. */
-        Env & env2(state.allocEnv(attrs.size() + inherited.size()));
+        Env & env2(state.allocEnv(attrs.size()));
         env2.up = &env;
 
+        AttrDefs::iterator overrides = attrs.find(state.sOverrides);
+        bool hasOverrides = overrides != attrs.end();
+
+        /* The recursive attributes are evaluated in the new
+           environment, while the inherited attributes are evaluated
+           in the original environment. */
         unsigned int displ = 0;
+        foreach (AttrDefs::iterator, i, attrs)
+            if (i->second.inherited) {
+                /* !!! handle overrides? */
+                Value * vAttr = state.lookupVar(&env, i->second.var);
+                env2.values[displ++] = vAttr;
+                v.attrs->push_back(Attr(i->first, vAttr, &i->second.pos));
+            } else {
+                Value * vAttr;
+                if (hasOverrides) {
+                    vAttr = state.allocValue();
+                    mkThunk(*vAttr, env2, i->second.e);
+                } else
+                    vAttr = state.maybeThunk(env2, i->second.e);
+                env2.values[displ++] = vAttr;
+                v.attrs->push_back(Attr(i->first, vAttr, &i->second.pos));
+            }
         
-        /* The recursive attributes are evaluated in the new
-           environment. */
-        foreach (Attrs::iterator, i, attrs) {
-            nix::Attr & a = (*v.attrs)[i->first];
-            mkThunk(a.value, env2, i->second.first);
-            mkCopy(env2.values[displ++], a.value);
-            a.pos = &i->second.second;
-        }
-
-        /* The inherited attributes, on the other hand, are
-           evaluated in the original environment. */
-        foreach (list<Inherited>::iterator, i, inherited) {
-            nix::Attr & a = (*v.attrs)[i->first.name];
-            Value * v2 = state.lookupVar(&env, i->first);
-            mkCopy(a.value, *v2);
-            mkCopy(env2.values[displ++], *v2);
-            a.pos = &i->second;
-        }
-
         /* If the rec contains an attribute called `__overrides', then
            evaluate it, and add the attributes in that set to the rec.
            This allows overriding of recursive attributes, which is
@@ -453,28 +538,27 @@ void ExprAttrs::eval(EvalState & state, Env & env, Value & v)
            still reference the original value, because that value has
            been substituted into the bodies of the other attributes.
            Hence we need __overrides.) */
-        Bindings::iterator overrides = v.attrs->find(state.sOverrides);
-        if (overrides != v.attrs->end()) {
-            state.forceAttrs(overrides->second.value);
-            foreach (Bindings::iterator, i, *overrides->second.value.attrs) {
-                nix::Attr & a = (*v.attrs)[i->first];
-                mkCopy(a.value, i->second.value);
+        if (hasOverrides) {
+            Value * vOverrides = (*v.attrs)[overrides->second.displ].value;
+            state.forceAttrs(*vOverrides);
+            foreach (Bindings::iterator, i, *vOverrides->attrs) {
+                AttrDefs::iterator j = attrs.find(i->name);
+                if (j != attrs.end()) {
+                    (*v.attrs)[j->second.displ] = *i;
+                    env2.values[j->second.displ] = i->value;
+                } else
+                    v.attrs->push_back(*i);
             }
+            v.attrs->sort();
         }
     }
 
     else {
-        foreach (Attrs::iterator, i, attrs) {
-            nix::Attr & a = (*v.attrs)[i->first];
-            mkThunk(a.value, env, i->second.first);
-            a.pos = &i->second.second;
-        }
-
-        foreach (list<Inherited>::iterator, i, inherited) {
-            nix::Attr & a = (*v.attrs)[i->first.name];
-            mkCopy(a.value, *state.lookupVar(&env, i->first));
-            a.pos = &i->second;
-        }
+        foreach (AttrDefs::iterator, i, attrs)
+            if (i->second.inherited)
+                v.attrs->push_back(Attr(i->first, state.lookupVar(&env, i->second.var), &i->second.pos));
+            else
+                v.attrs->push_back(Attr(i->first, state.maybeThunk(env, i->second.e), &i->second.pos));
     }
 }
 
@@ -483,20 +567,18 @@ void ExprLet::eval(EvalState & state, Env & env, Value & v)
 {
     /* Create a new environment that contains the attributes in this
        `let'. */
-    Env & env2(state.allocEnv(attrs->attrs.size() + attrs->inherited.size()));
+    Env & env2(state.allocEnv(attrs->attrs.size()));
     env2.up = &env;
 
-    unsigned int displ = 0;
-
-    /* The recursive attributes are evaluated in the new
+    /* The recursive attributes are evaluated in the new environment,
+       while the inherited attributes are evaluated in the original
        environment. */
-    foreach (ExprAttrs::Attrs::iterator, i, attrs->attrs)
-        mkThunk(env2.values[displ++], env2, i->second.first);
-
-    /* The inherited attributes, on the other hand, are evaluated in
-       the original environment. */
-    foreach (list<ExprAttrs::Inherited>::iterator, i, attrs->inherited)
-        mkCopy(env2.values[displ++], *state.lookupVar(&env, i->first));
+    unsigned int displ = 0;
+    foreach (ExprAttrs::AttrDefs::iterator, i, attrs->attrs)
+        if (i->second.inherited)
+            env2.values[displ++] = state.lookupVar(&env, i->second.var);
+        else
+            env2.values[displ++] = state.maybeThunk(env2, i->second.e);
 
     state.eval(env2, body, v);
 }
@@ -505,11 +587,8 @@ void ExprLet::eval(EvalState & state, Env & env, Value & v)
 void ExprList::eval(EvalState & state, Env & env, Value & v)
 {
     state.mkList(v, elems.size());
-    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]);
-    }
+    for (unsigned int n = 0; n < v.list.length; ++n)
+        v.list.elems[n] = state.maybeThunk(env, elems[n]);
 }
 
 
@@ -521,21 +600,26 @@ void ExprVar::eval(EvalState & state, Env & env, Value & v)
 }
 
 
+unsigned long nrLookups = 0;
+unsigned long nrLookupSize = 0;
+
 void ExprSelect::eval(EvalState & state, Env & env, Value & v)
 {
+    nrLookups++;
     Value v2;
     state.evalAttrs(env, e, v2);
+    nrLookupSize += v2.attrs->size();
     Bindings::iterator i = v2.attrs->find(name);
     if (i == v2.attrs->end())
         throwEvalError("attribute `%1%' missing", name);
     try {            
-        state.forceValue(i->second.value);
+        state.forceValue(*i->value);
     } catch (Error & e) {
         addErrorPrefix(e, "while evaluating the attribute `%1%' at %2%:\n",
-            name, *i->second.pos);
+            name, *i->pos);
         throw;
     }
-    v = i->second.value;
+    v = *i->value;
 }
 
 
@@ -559,24 +643,27 @@ void ExprApp::eval(EvalState & state, Env & env, Value & v)
 {
     Value vFun;
     state.eval(env, e1, vFun);
-    Value vArg;
-    mkThunk(vArg, env, e2); // !!! should this be on the heap?
-    state.callFunction(vFun, vArg, v);
+    state.callFunction(vFun, *state.maybeThunk(env, e2), v);
 }
 
 
 void EvalState::callFunction(Value & fun, Value & arg, Value & v)
 {
     if (fun.type == tPrimOp || fun.type == tPrimOpApp) {
-        unsigned int argsLeft =
-            fun.type == tPrimOp ? fun.primOp.arity : fun.primOpApp.argsLeft;
+
+        /* Figure out the number of arguments still needed. */
+        unsigned int argsDone = 0;
+        Value * primOp = &fun;
+        while (primOp->type == tPrimOpApp) {
+            argsDone++;
+            primOp = primOp->primOpApp.left;
+        }
+        assert(primOp->type == tPrimOp);
+        unsigned int arity = primOp->primOp->arity;
+        unsigned int argsLeft = arity - argsDone;
+        
         if (argsLeft == 1) {
-            /* We have all the arguments, so call the primop.  First
-               find the primop. */
-            Value * primOp = &fun;
-            while (primOp->type == tPrimOpApp) primOp = primOp->primOpApp.left;
-            assert(primOp->type == tPrimOp);
-            unsigned int arity = primOp->primOp.arity;
+            /* We have all the arguments, so call the primop. */
                 
             /* Put all the arguments in an array. */
             Value * vArgs[arity];
@@ -587,19 +674,16 @@ void EvalState::callFunction(Value & fun, Value & arg, Value & v)
 
             /* And call the primop. */
             try {
-                primOp->primOp.fun(*this, vArgs, v);
+                primOp->primOp->fun(*this, vArgs, v);
             } catch (Error & e) {
-                addErrorPrefix(e, "while evaluating the builtin function `%1%':\n", primOp->primOp.name);
+                addErrorPrefix(e, "while evaluating the builtin function `%1%':\n", primOp->primOp->name);
                 throw;
             }
         } else {
-            Value * v2 = allocValues(2);
-            v2[0] = fun;
-            v2[1] = arg;
             v.type = tPrimOpApp;
-            v.primOpApp.left = &v2[0];
-            v.primOpApp.right = &v2[1];
-            v.primOpApp.argsLeft = argsLeft - 1;
+            v.primOpApp.left = allocValue();
+            *v.primOpApp.left = fun;
+            v.primOpApp.right = &arg;
         }
         return;
     }
@@ -617,13 +701,13 @@ void EvalState::callFunction(Value & fun, Value & arg, Value & v)
     unsigned int displ = 0;
 
     if (!fun.lambda.fun->matchAttrs)
-        env2.values[displ++] = arg;
+        env2.values[displ++] = &arg;
 
     else {
         forceAttrs(arg);
         
         if (!fun.lambda.fun->arg.empty())
-            env2.values[displ++] = arg;
+            env2.values[displ++] = &arg;
 
         /* For each formal argument, get the actual argument.  If
            there is no matching actual argument but the formal
@@ -633,11 +717,11 @@ void EvalState::callFunction(Value & fun, Value & arg, Value & v)
             Bindings::iterator j = arg.attrs->find(i->name);
             if (j == arg.attrs->end()) {
                 if (!i->def) throwTypeError("function at %1% called without required argument `%2%'",
-                    fun.lambda.fun->pos, i->name);   
-                mkThunk(env2.values[displ++], env2, i->def);
+                    fun.lambda.fun->pos, i->name);
+                env2.values[displ++] = maybeThunk(env2, i->def);
             } else {
                 attrsUsed++;
-                mkCopy(env2.values[displ++], j->second.value);
+                env2.values[displ++] = j->value;
             }
         }
 
@@ -645,7 +729,7 @@ void EvalState::callFunction(Value & fun, Value & arg, Value & v)
            argument (unless the attribute match specifies a `...').
            TODO: show the names of the expected/unexpected
            arguments. */
-        if (!fun.lambda.fun->formals->ellipsis && attrsUsed != arg.attrs->size())
+        if (!fun.lambda.fun->formals->ellipsis && attrsUsed != arg.attrs->size()) 
             throwTypeError("function at %1% called with unexpected argument", fun.lambda.fun->pos);
     }
 
@@ -658,7 +742,7 @@ void EvalState::callFunction(Value & fun, Value & arg, Value & v)
 }
 
 
-void EvalState::autoCallFunction(const Bindings & args, Value & fun, Value & res)
+void EvalState::autoCallFunction(Bindings & args, Value & fun, Value & res)
 {
     forceValue(fun);
 
@@ -668,16 +752,18 @@ void EvalState::autoCallFunction(const Bindings & args, Value & fun, Value & res
     }
 
     Value actualArgs;
-    mkAttrs(actualArgs);
+    mkAttrs(actualArgs, fun.lambda.fun->formals->formals.size());
 
     foreach (Formals::Formals_::iterator, i, fun.lambda.fun->formals->formals) {
-        Bindings::const_iterator j = args.find(i->name);
+        Bindings::iterator j = args.find(i->name);
         if (j != args.end())
-            (*actualArgs.attrs)[i->name] = j->second;
+            actualArgs.attrs->push_back(*j);
         else if (!i->def)
             throwTypeError("cannot auto-call a function that has an argument without a default value (`%1%')", i->name);
     }
 
+    actualArgs.attrs->sort();
+
     callFunction(fun, actualArgs, res);
 }
 
@@ -688,7 +774,8 @@ void ExprWith::eval(EvalState & state, Env & env, Value & v)
     env2.up = &env;
     env2.prevWith = prevWith;
 
-    state.evalAttrs(env, attrs, env2.values[0]);
+    env2.values[0] = state.allocValue();
+    state.evalAttrs(env, attrs, *env2.values[0]);
 
     state.eval(env2, body, v);
 }
@@ -754,16 +841,34 @@ void ExprOpUpdate::eval(EvalState & state, Env & env, Value & v)
     state.evalAttrs(env, e1, v1);
     state.evalAttrs(env, e2, v2);
 
+    state.nrOpUpdates++;
+
     if (v1.attrs->size() == 0) { v = v2; return; }
     if (v2.attrs->size() == 0) { v = v1; return; }
 
-    state.cloneAttrs(v1, v);
+    state.mkAttrs(v, v1.attrs->size() + v2.attrs->size());
+
+    /* Merge the attribute sets, preferring values from the second
+       set.  Make sure to keep the resulting vector in sorted
+       order. */
+    Bindings::iterator i = v1.attrs->begin();
+    Bindings::iterator j = v2.attrs->begin();
 
-    foreach (Bindings::iterator, i, *v2.attrs) {
-        Attr & a = (*v.attrs)[i->first];
-        mkCopy(a.value, i->second.value);
-        a.pos = i->second.pos;
+    while (i != v1.attrs->end() && j != v2.attrs->end()) {
+        if (i->name == j->name) {
+            v.attrs->push_back(*j);
+            ++i; ++j;
+        }
+        else if (i->name < j->name)
+            v.attrs->push_back(*i++);
+        else
+            v.attrs->push_back(*j++);
     }
+
+    while (i != v1.attrs->end()) v.attrs->push_back(*i++);
+    while (j != v2.attrs->end()) v.attrs->push_back(*j++);
+    
+    state.nrOpUpdateValuesCopied += v.attrs->size();
 }
 
 
@@ -826,10 +931,6 @@ void EvalState::forceValue(Value & v)
             throw;
         }
     }
-    else if (v.type == tCopy) {
-        forceValue(*v.val);
-        v = *v.val;
-    }
     else if (v.type == tApp)
         callFunction(*v.app.left, *v.app.right, v);
     else if (v.type == tBlackhole)
@@ -843,7 +944,7 @@ void EvalState::strictForceValue(Value & v)
     
     if (v.type == tAttrs) {
         foreach (Bindings::iterator, i, *v.attrs)
-            strictForceValue(i->second.value);
+            strictForceValue(*i->value);
     }
     
     else if (v.type == tList) {
@@ -934,7 +1035,7 @@ bool EvalState::isDerivation(Value & v)
 {
     if (v.type != tAttrs) return false;
     Bindings::iterator i = v.attrs->find(sType);
-    return i != v.attrs->end() && forceStringNoCtx(i->second.value) == "derivation";
+    return i != v.attrs->end() && forceStringNoCtx(*i->value) == "derivation";
 }
 
 
@@ -978,7 +1079,7 @@ string EvalState::coerceToString(Value & v, PathSet & context,
         Bindings::iterator i = v.attrs->find(sOutPath);
         if (i == v.attrs->end())
             throwTypeError("cannot coerce an attribute set (except a derivation) to a string");
-        return coerceToString(i->second.value, context, coerceMore, copyToStore);
+        return coerceToString(*i->value, context, coerceMore, copyToStore);
     }
 
     if (coerceMore) {
@@ -1064,9 +1165,9 @@ bool EvalState::eqValues(Value & v1, Value & v2)
 
         case tAttrs: {
             if (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 (i->first != j->first || !eqValues(i->second.value, j->second.value))
+            Bindings::iterator i = v1.attrs->begin(), j = v2.attrs->begin();
+            for ( ; i != v1.attrs->end(); ++i, ++j)
+                if (i->name != j->name || !eqValues(*i->value, *j->value))
                     return false;
             return true;
         }
@@ -1089,20 +1190,26 @@ void EvalState::printStats()
     bool showStats = getEnv("NIX_SHOW_STATS", "0") != "0";
     Verbosity v = showStats ? lvlInfo : lvlDebug;
     printMsg(v, "evaluation statistics:");
+    printMsg(v, format("  size of a value: %1%") % sizeof(Value));
     printMsg(v, format("  expressions evaluated: %1%") % nrEvaluated);
     printMsg(v, format("  stack space used: %1% bytes") % (&x - deepestStack));
     printMsg(v, format("  max eval() nesting depth: %1%") % maxRecursionDepth);
     printMsg(v, format("  stack space per eval() level: %1% bytes")
         % ((&x - deepestStack) / (float) maxRecursionDepth));
     printMsg(v, format("  environments allocated: %1% (%2% bytes)")
-        % nrEnvs % (nrEnvs * sizeof(Env)));
-    printMsg(v, format("  values allocated in environments: %1% (%2% bytes)")
-        % nrValuesInEnvs % (nrValuesInEnvs * sizeof(Value)));
+        % nrEnvs % (nrEnvs * sizeof(Env) + nrValuesInEnvs * sizeof(Value *)));
     printMsg(v, format("  list elements: %1% (%2% bytes)")
         % nrListElems % (nrListElems * sizeof(Value *)));
-    printMsg(v, format("  misc. values allocated: %1% (%2% bytes)")
+    printMsg(v, format("  values allocated: %1% (%2% bytes)")
         % nrValues % (nrValues * sizeof(Value)));
+    printMsg(v, format("  attribute sets allocated: %1%") % nrAttrsets);
+    printMsg(v, format("  right-biased unions: %1%") % nrOpUpdates);
+    printMsg(v, format("  values copied in right-biased unions: %1%") % nrOpUpdateValuesCopied);
     printMsg(v, format("  symbols in symbol table: %1%") % symbols.size());
+    printMsg(v, format("  number of thunks: %1%") % nrThunks);
+    printMsg(v, format("  number of thunks avoided: %1%") % nrAvoided);
+    printMsg(v, format("  number of attr lookups: %1%") % nrLookups);
+    printMsg(v, format("  attr lookup size: %1%") % nrLookupSize);
 }
 
 
diff --git a/src/libexpr/eval.hh b/src/libexpr/eval.hh
index 501ac93d0..7453ac189 100644
--- a/src/libexpr/eval.hh
+++ b/src/libexpr/eval.hh
@@ -7,6 +7,10 @@
 
 #include <map>
 
+#if HAVE_BOEHMGC
+#include <gc/gc_allocator.h>
+#endif
+
 
 namespace nix {
 
@@ -16,7 +20,22 @@ struct Env;
 struct Value;
 struct Attr;
 
-typedef std::map<Symbol, Attr> Bindings;
+
+/* Attribute sets are represented as a vector of attributes, sorted by
+   symbol (i.e. pointer to the attribute name in the symbol table). */
+#if HAVE_BOEHMGC
+typedef std::vector<Attr, gc_allocator<Attr> > BindingsBase;
+#else
+typedef std::vector<Attr> BindingsBase;
+#endif
+
+
+class Bindings : public BindingsBase
+{
+public:
+    iterator find(const Symbol & name);
+    void sort();
+};
 
 
 typedef enum {
@@ -30,14 +49,23 @@ typedef enum {
     tThunk,
     tApp,
     tLambda,
-    tCopy,
     tBlackhole,
     tPrimOp,
     tPrimOpApp,
 } ValueType;
 
 
-typedef void (* PrimOp) (EvalState & state, Value * * args, Value & v);
+typedef void (* PrimOpFun) (EvalState & state, Value * * args, Value & v);
+
+
+struct PrimOp
+{
+    PrimOpFun fun;
+    unsigned int arity;
+    Symbol name;
+    PrimOp(PrimOpFun fun, unsigned int arity, Symbol name)
+        : fun(fun), arity(arity), name(name) { }
+};
 
 
 struct Value
@@ -90,15 +118,9 @@ struct Value
             Env * env;
             ExprLambda * fun;
         } lambda;
-        Value * val;
-        struct {
-            PrimOp fun;
-            char * name;
-            unsigned int arity;
-        } primOp;
+        PrimOp * primOp;
         struct {
             Value * left, * right;
-            unsigned int argsLeft;
         } primOpApp;
     };
 };
@@ -108,20 +130,36 @@ struct Env
 {
     Env * up;
     unsigned int prevWith; // nr of levels up to next `with' environment
-    Value values[0];
+    Value * values[0];
 };
 
 
 struct Attr
 {
-    Value value;
+    Symbol name;
+    Value * value;
     Pos * pos;
+    Attr(Symbol name, Value * value, Pos * pos = &noPos)
+        : name(name), value(value), pos(pos) { };
     Attr() : pos(&noPos) { };
+    bool operator < (const Attr & a) const
+    {
+        return name < a.name;
+    }
 };
 
 
+/* After overwriting an app node, be sure to clear pointers in the
+   Value to ensure that the target isn't kept alive unnecessarily. */
+static inline void clearValue(Value & v)
+{
+    v.app.right = 0;
+}
+
+
 static inline void mkInt(Value & v, int n)
 {
+    clearValue(v);
     v.type = tInt;
     v.integer = n;
 }
@@ -129,26 +167,12 @@ static inline void mkInt(Value & v, int n)
 
 static inline void mkBool(Value & v, bool b)
 {
+    clearValue(v);
     v.type = tBool;
     v.boolean = b;
 }
 
 
-static inline void mkThunk(Value & v, Env & env, Expr * expr)
-{
-    v.type = tThunk;
-    v.thunk.env = &env;
-    v.thunk.expr = expr;
-}
-
-
-static inline void mkCopy(Value & v, Value & src)
-{
-    v.type = tCopy;
-    v.val = &src;
-}
-
-
 static inline void mkApp(Value & v, Value & left, Value & right)
 {
     v.type = tApp;
@@ -268,7 +292,7 @@ private:
     void addConstant(const string & name, Value & v);
 
     void addPrimOp(const string & name,
-        unsigned int arity, PrimOp primOp);
+        unsigned int arity, PrimOpFun primOp);
 
     Value * lookupVar(Env * env, const VarRef & var);
     
@@ -286,18 +310,20 @@ public:
 
     /* Automatically call a function for which each argument has a
        default value or has a binding in the `args' map. */
-    void autoCallFunction(const Bindings & args, Value & fun, Value & res);
+    void autoCallFunction(Bindings & args, Value & fun, Value & res);
     
     /* Allocation primitives. */
-    Value * allocValues(unsigned int count);
+    Value * allocValue();
     Env & allocEnv(unsigned int size);
 
+    Value * allocAttr(Value & vAttrs, const Symbol & name);
+
     void mkList(Value & v, unsigned int length);
-    void mkAttrs(Value & v);
+    void mkAttrs(Value & v, unsigned int expected);
     void mkThunk_(Value & v, Expr * expr);
-    
-    void cloneAttrs(Value & src, Value & dst);
 
+    Value * maybeThunk(Env & env, Expr * expr);
+    
     /* Print statistics. */
     void printStats();
 
@@ -308,11 +334,15 @@ private:
     unsigned long nrValues;
     unsigned long nrListElems;
     unsigned long nrEvaluated;
+    unsigned long nrAttrsets;
+    unsigned long nrOpUpdates;
+    unsigned long nrOpUpdateValuesCopied;
     unsigned int recursionDepth;
     unsigned int maxRecursionDepth;
     char * deepestStack; /* for measuring stack usage */
     
     friend class RecursionCounter;
+    friend class ExprOpUpdate;
 };
 
 
diff --git a/src/libexpr/get-drvs.cc b/src/libexpr/get-drvs.cc
index 82a92416b..a28a705d2 100644
--- a/src/libexpr/get-drvs.cc
+++ b/src/libexpr/get-drvs.cc
@@ -10,7 +10,7 @@ string DrvInfo::queryDrvPath(EvalState & state) const
     if (drvPath == "" && attrs) {
         Bindings::iterator i = attrs->find(state.sDrvPath);
         PathSet context;
-        (string &) drvPath = i != attrs->end() ? state.coerceToPath(i->second.value, context) : "";
+        (string &) drvPath = i != attrs->end() ? state.coerceToPath(*i->value, context) : "";
     }
     return drvPath;
 }
@@ -21,7 +21,7 @@ string DrvInfo::queryOutPath(EvalState & state) const
     if (outPath == "" && attrs) {
         Bindings::iterator i = attrs->find(state.sOutPath);
         PathSet context;
-        (string &) outPath = i != attrs->end() ? state.coerceToPath(i->second.value, context) : "";
+        (string &) outPath = i != attrs->end() ? state.coerceToPath(*i->value, context) : "";
     }
     return outPath;
 }
@@ -36,23 +36,23 @@ MetaInfo DrvInfo::queryMetaInfo(EvalState & state) const
     Bindings::iterator a = attrs->find(state.sMeta);
     if (a == attrs->end()) return meta; /* fine, empty meta information */
 
-    state.forceAttrs(a->second.value);
+    state.forceAttrs(*a->value);
 
-    foreach (Bindings::iterator, i, *a->second.value.attrs) {
+    foreach (Bindings::iterator, i, *a->value->attrs) {
         MetaValue value;
-        state.forceValue(i->second.value);
-        if (i->second.value.type == tString) {
+        state.forceValue(*i->value);
+        if (i->value->type == tString) {
             value.type = MetaValue::tpString;
-            value.stringValue = i->second.value.string.s;
-        } else if (i->second.value.type == tInt) {
+            value.stringValue = i->value->string.s;
+        } else if (i->value->type == tInt) {
             value.type = MetaValue::tpInt;
-            value.intValue = i->second.value.integer;
-        } else if (i->second.value.type == tList) {
+            value.intValue = i->value->integer;
+        } else if (i->value->type == tList) {
             value.type = MetaValue::tpStrings;
-            for (unsigned int j = 0; j < i->second.value.list.length; ++j)
-                value.stringValues.push_back(state.forceStringNoCtx(*i->second.value.list.elems[j]));
+            for (unsigned int j = 0; j < i->value->list.length; ++j)
+                value.stringValues.push_back(state.forceStringNoCtx(*i->value->list.elems[j]));
         } else continue;
-        ((MetaInfo &) meta)[i->first] = value;
+        ((MetaInfo &) meta)[i->name] = value;
     }
 
     return meta;
@@ -99,13 +99,13 @@ static bool getDerivation(EvalState & state, Value & v,
         Bindings::iterator i = v.attrs->find(state.sName);
         /* !!! We really would like to have a decent back trace here. */
         if (i == v.attrs->end()) throw TypeError("derivation name missing");
-        drv.name = state.forceStringNoCtx(i->second.value);
+        drv.name = state.forceStringNoCtx(*i->value);
 
-        i = v.attrs->find(state.sSystem);
-        if (i == v.attrs->end())
+        Bindings::iterator i2 = v.attrs->find(state.sSystem);
+        if (i2 == v.attrs->end())
             drv.system = "unknown";
         else
-            drv.system = state.forceStringNoCtx(i->second.value);
+            drv.system = state.forceStringNoCtx(*i2->value);
 
         drv.attrs = v.attrs;
 
@@ -138,7 +138,7 @@ static string addToPath(const string & s1, const string & s2)
 
 
 static void getDerivations(EvalState & state, Value & vIn,
-    const string & pathPrefix, const Bindings & autoArgs,
+    const string & pathPrefix, Bindings & autoArgs,
     DrvInfos & drvs, Done & done)
 {
     Value v;
@@ -163,12 +163,12 @@ static void getDerivations(EvalState & state, Value & vIn,
         typedef std::map<string, Symbol> SortedSymbols;
         SortedSymbols attrs;
         foreach (Bindings::iterator, i, *v.attrs)
-            attrs.insert(std::pair<string, Symbol>(i->first, i->first));
+            attrs.insert(std::pair<string, Symbol>(i->name, i->name));
 
         foreach (SortedSymbols::iterator, i, attrs) {
             startNest(nest, lvlDebug, format("evaluating attribute `%1%'") % i->first);
             string pathPrefix2 = addToPath(pathPrefix, i->first);
-            Value & v2((*v.attrs)[i->second].value);
+            Value & v2(*v.attrs->find(i->second)->value);
             if (combineChannels)
                 getDerivations(state, v2, pathPrefix2, autoArgs, drvs, done);
             else if (getDerivation(state, v2, pathPrefix2, drvs, done)) {
@@ -178,7 +178,7 @@ static void getDerivations(EvalState & state, Value & vIn,
                    attribute. */
                 if (v2.type == tAttrs) {
                     Bindings::iterator j = v2.attrs->find(state.symbols.create("recurseForDerivations"));
-                    if (j != v2.attrs->end() && state.forceBool(j->second.value))
+                    if (j != v2.attrs->end() && state.forceBool(*j->value))
                         getDerivations(state, v2, pathPrefix2, autoArgs, drvs, done);
                 }
             }
@@ -200,7 +200,7 @@ static void getDerivations(EvalState & state, Value & vIn,
 
 
 void getDerivations(EvalState & state, Value & v, const string & pathPrefix,
-    const Bindings & autoArgs, DrvInfos & drvs)
+    Bindings & autoArgs, DrvInfos & drvs)
 {
     Done done;
     getDerivations(state, v, pathPrefix, autoArgs, drvs, done);
diff --git a/src/libexpr/get-drvs.hh b/src/libexpr/get-drvs.hh
index 7b96decf4..7c014b7e4 100644
--- a/src/libexpr/get-drvs.hh
+++ b/src/libexpr/get-drvs.hh
@@ -70,7 +70,7 @@ typedef list<DrvInfo> DrvInfos;
 bool getDerivation(EvalState & state, Value & v, DrvInfo & drv);
 
 void getDerivations(EvalState & state, Value & v, const string & pathPrefix,
-    const Bindings & autoArgs, DrvInfos & drvs);
+    Bindings & autoArgs, DrvInfos & drvs);
 
  
 }
diff --git a/src/libexpr/lexer.l b/src/libexpr/lexer.l
index f29f9b684..5b27e2582 100644
--- a/src/libexpr/lexer.l
+++ b/src/libexpr/lexer.l
@@ -46,7 +46,7 @@ static void adjustLoc(YYLTYPE * loc, const char * s, size_t len)
 }
 
 
-static Expr * unescapeStr(const char * s)
+static Expr * unescapeStr(SymbolTable & symbols, const char * s)
 {
     string t;
     char c;
@@ -66,7 +66,7 @@ static Expr * unescapeStr(const char * s)
         }
         else t += c;
     }
-    return new ExprString(t);
+    return new ExprString(symbols.create(t));
 }
 
  
@@ -119,7 +119,7 @@ inherit     { return INHERIT; }
                  "$\"" will be consumed as part of a string, rather
                  than a "$" followed by the string terminator.
                  Disallow "$\"" for now. */
-              yylval->e = unescapeStr(yytext);
+              yylval->e = unescapeStr(data->symbols, yytext);
               return STR;
             }
 <STRING>\$\{  { BEGIN(INITIAL); return DOLLAR_CURLY; }
@@ -140,7 +140,7 @@ inherit     { return INHERIT; }
                    return IND_STR;
                  }
 <IND_STRING>\'\'\\. {
-                   yylval->e = unescapeStr(yytext + 2);
+                   yylval->e = unescapeStr(data->symbols, yytext + 2);
                    return IND_STR;
                  }
 <IND_STRING>\$\{ { BEGIN(INITIAL); return DOLLAR_CURLY; }
diff --git a/src/libexpr/nixexpr.cc b/src/libexpr/nixexpr.cc
index 898fdb609..147f50853 100644
--- a/src/libexpr/nixexpr.cc
+++ b/src/libexpr/nixexpr.cc
@@ -55,10 +55,11 @@ void ExprAttrs::show(std::ostream & str)
 {
     if (recursive) str << "rec ";
     str << "{ ";
-    foreach (list<Inherited>::iterator, i, inherited)
-        str << "inherit " << i->first.name << "; ";
-    foreach (Attrs::iterator, i, attrs)
-        str << i->first << " = " << *i->second.first << "; ";
+    foreach (AttrDefs::iterator, i, attrs)
+        if (i->second.inherited)
+            str << "inherit " << i->first << " " << "; ";
+        else
+            str << i->first << " = " << *i->second.e << "; ";
     str << "}";
 }
 
@@ -91,10 +92,11 @@ void ExprLambda::show(std::ostream & str)
 void ExprLet::show(std::ostream & str)
 {
     str << "let ";
-    foreach (list<ExprAttrs::Inherited>::iterator, i, attrs->inherited)
-        str << "inherit " << i->first.name << "; ";
-    foreach (ExprAttrs::Attrs::iterator, i, attrs->attrs)
-        str << i->first << " = " << *i->second.first << "; ";
+    foreach (ExprAttrs::AttrDefs::iterator, i, attrs->attrs)
+        if (i->second.inherited)
+            str << "inherit " << i->first << "; ";
+        else
+            str << i->first << " = " << *i->second.e << "; ";
     str << "in " << *body;
 }
 
@@ -211,26 +213,18 @@ void ExprAttrs::bindVars(const StaticEnv & env)
         StaticEnv newEnv(false, &env);
     
         unsigned int displ = 0;
-
-        foreach (ExprAttrs::Attrs::iterator, i, attrs)
-            newEnv.vars[i->first] = displ++;
-
-        foreach (list<Inherited>::iterator, i, inherited) {
-            newEnv.vars[i->first.name] = displ++;
-            i->first.bind(env);
-        }
-
-        foreach (ExprAttrs::Attrs::iterator, i, attrs)
-            i->second.first->bindVars(newEnv);
+        foreach (AttrDefs::iterator, i, attrs)
+            newEnv.vars[i->first] = i->second.displ = displ++;
+        
+        foreach (AttrDefs::iterator, i, attrs)
+            if (i->second.inherited) i->second.var.bind(env);
+            else i->second.e->bindVars(newEnv);
     }
 
-    else {
-        foreach (ExprAttrs::Attrs::iterator, i, attrs)
-            i->second.first->bindVars(env);
-
-        foreach (list<Inherited>::iterator, i, inherited)
-            i->first.bind(env);
-    }
+    else
+        foreach (AttrDefs::iterator, i, attrs)
+            if (i->second.inherited) i->second.var.bind(env);
+            else i->second.e->bindVars(env);
 }
 
 void ExprList::bindVars(const StaticEnv & env)
@@ -263,17 +257,12 @@ void ExprLet::bindVars(const StaticEnv & env)
     StaticEnv newEnv(false, &env);
     
     unsigned int displ = 0;
-
-    foreach (ExprAttrs::Attrs::iterator, i, attrs->attrs)
-        newEnv.vars[i->first] = displ++;
-
-    foreach (list<ExprAttrs::Inherited>::iterator, i, attrs->inherited) {
-        newEnv.vars[i->first.name] = displ++;
-        i->first.bind(env);
-    }
-
-    foreach (ExprAttrs::Attrs::iterator, i, attrs->attrs)
-        i->second.first->bindVars(newEnv);
+    foreach (ExprAttrs::AttrDefs::iterator, i, attrs->attrs)
+        newEnv.vars[i->first] = i->second.displ = displ++;
+    
+    foreach (ExprAttrs::AttrDefs::iterator, i, attrs->attrs)
+        if (i->second.inherited) i->second.var.bind(env);
+        else i->second.e->bindVars(newEnv);
     
     body->bindVars(newEnv);
 }
diff --git a/src/libexpr/nixexpr.hh b/src/libexpr/nixexpr.hh
index 1d03220f6..8f976f1de 100644
--- a/src/libexpr/nixexpr.hh
+++ b/src/libexpr/nixexpr.hh
@@ -65,8 +65,8 @@ struct ExprInt : Expr
 
 struct ExprString : Expr
 {
-    string s;
-    ExprString(const string & s) : s(s) { };
+    Symbol s;
+    ExprString(const Symbol & s) : s(s) { };
     COMMON_METHODS
 };
 
@@ -101,6 +101,7 @@ struct VarRef
     unsigned int level;
     unsigned int displ;
 
+    VarRef() { };
     VarRef(const Symbol & name) : name(name) { };
     void bind(const StaticEnv & env);
 };
@@ -131,12 +132,18 @@ struct ExprOpHasAttr : Expr
 struct ExprAttrs : Expr
 {
     bool recursive;
-    typedef std::pair<Expr *, Pos> Attr;
-    typedef std::pair<VarRef, Pos> Inherited;
-    typedef std::map<Symbol, Attr> Attrs;
-    Attrs attrs;
-    list<Inherited> inherited;
-    std::map<Symbol, Pos> attrNames; // used during parsing
+    struct AttrDef {
+        bool inherited;
+        Expr * e; // if not inherited
+        VarRef var; // if inherited
+        Pos pos;
+        unsigned int displ; // displacement
+        AttrDef(Expr * e, const Pos & pos) : inherited(false), e(e), pos(pos) { };
+        AttrDef(const Symbol & name, const Pos & pos) : inherited(true), var(name), pos(pos) { };
+        AttrDef() { };
+    };
+    typedef std::map<Symbol, AttrDef> AttrDefs;
+    AttrDefs attrs;
     ExprAttrs() : recursive(false) { };
     COMMON_METHODS
 };
diff --git a/src/libexpr/parser.y b/src/libexpr/parser.y
index b0c54339b..c6d29b6ca 100644
--- a/src/libexpr/parser.y
+++ b/src/libexpr/parser.y
@@ -7,19 +7,44 @@
 %parse-param { yyscan_t scanner }
 %parse-param { ParseData * data }
 %lex-param { yyscan_t scanner }
+%lex-param { ParseData * data }
 
-
-%{
-/* Newer versions of Bison copy the declarations below to
-   parser-tab.hh, which sucks bigtime since lexer.l doesn't want that
-   stuff.  So allow it to be excluded. */
-#ifndef BISON_HEADER_HACK
-#define BISON_HEADER_HACK
-
+%code requires {
+    
+#ifndef BISON_HEADER
+#define BISON_HEADER
+    
 #include "util.hh"
     
 #include "nixexpr.hh"
 
+namespace nix {
+
+    struct ParseData 
+    {
+        SymbolTable & symbols;
+        Expr * result;
+        Path basePath;
+        Path path;
+        string error;
+        Symbol sLetBody;
+        ParseData(SymbolTable & symbols)
+            : symbols(symbols)
+            , sLetBody(symbols.create("<let-body>"))
+            { };
+    };
+    
+}
+
+#define YY_DECL int yylex \
+    (YYSTYPE * yylval_param, YYLTYPE * yylloc_param, yyscan_t yyscanner, nix::ParseData * data)
+
+#endif
+
+}
+
+%{
+
 #include "parser-tab.hh"
 #include "lexer-tab.hh"
 #define YYSTYPE YYSTYPE // workaround a bug in Bison 2.4
@@ -28,27 +53,13 @@
 #include <stdlib.h>
 #include <string.h>
 
+YY_DECL;
 
 using namespace nix;
 
 
 namespace nix {
-
     
-struct ParseData 
-{
-    SymbolTable & symbols;
-    Expr * result;
-    Path basePath;
-    Path path;
-    string error;
-    Symbol sLetBody;
-    ParseData(SymbolTable & symbols)
-        : symbols(symbols)
-        , sLetBody(symbols.create("<let-body>"))
-    { };
-};
-
 
 static string showAttrPath(const vector<Symbol> & attrPath)
 {
@@ -82,20 +93,20 @@ static void addAttr(ExprAttrs * attrs, const vector<Symbol> & attrPath,
     unsigned int n = 0;
     foreach (vector<Symbol>::const_iterator, i, attrPath) {
         n++;
-        ExprAttrs::Attrs::iterator j = attrs->attrs.find(*i);
+        ExprAttrs::AttrDefs::iterator j = attrs->attrs.find(*i);
         if (j != attrs->attrs.end()) {
-            ExprAttrs * attrs2 = dynamic_cast<ExprAttrs *>(j->second.first);
-            if (!attrs2 || n == attrPath.size()) dupAttr(attrPath, pos, j->second.second);
-            attrs = attrs2;
+            if (!j->second.inherited) {
+                ExprAttrs * attrs2 = dynamic_cast<ExprAttrs *>(j->second.e);
+                if (!attrs2 || n == attrPath.size()) dupAttr(attrPath, pos, j->second.pos);
+                attrs = attrs2;
+            } else
+                dupAttr(attrPath, pos, j->second.pos);
         } else {
-            if (attrs->attrNames.find(*i) != attrs->attrNames.end())
-                dupAttr(attrPath, pos, attrs->attrNames[*i]);
-            attrs->attrNames[*i] = pos;
             if (n == attrPath.size())
-                attrs->attrs[*i] = ExprAttrs::Attr(e, pos);
+                attrs->attrs[*i] = ExprAttrs::AttrDef(e, pos);
             else {
                 ExprAttrs * nested = new ExprAttrs;
-                attrs->attrs[*i] = ExprAttrs::Attr(nested, pos);
+                attrs->attrs[*i] = ExprAttrs::AttrDef(nested, pos);
                 attrs = nested;
             }
         }
@@ -113,9 +124,9 @@ static void addFormal(const Pos & pos, Formals * formals, const Formal & formal)
 }
 
 
-static Expr * stripIndentation(vector<Expr *> & es)
+static Expr * stripIndentation(SymbolTable & symbols, vector<Expr *> & es)
 {
-    if (es.empty()) return new ExprString("");
+    if (es.empty()) return new ExprString(symbols.create(""));
     
     /* Figure out the minimum indentation.  Note that by design
        whitespace-only final lines are not taken into account.  (So
@@ -195,7 +206,7 @@ static Expr * stripIndentation(vector<Expr *> & es)
                 s2 = string(s2, 0, p + 1);
         }
 
-        es2->push_back(new ExprString(s2));
+        es2->push_back(new ExprString(symbols.create(s2)));
     }
 
     return new ExprConcatStrings(es2);
@@ -224,9 +235,6 @@ void yyerror(YYLTYPE * loc, yyscan_t scanner, ParseData * data, const char * err
 }
 
 
-#endif
-
-
 %}
 
 %union {
@@ -337,15 +345,15 @@ expr_simple
   | INT { $$ = new ExprInt($1); }
   | '"' string_parts '"' {
       /* For efficiency, and to simplify parse trees a bit. */
-      if ($2->empty()) $$ = new ExprString("");
+      if ($2->empty()) $$ = new ExprString(data->symbols.create(""));
       else if ($2->size() == 1) $$ = $2->front();
       else $$ = new ExprConcatStrings($2);
   }
   | IND_STRING_OPEN ind_string_parts IND_STRING_CLOSE {
-      $$ = stripIndentation(*$2);
+      $$ = stripIndentation(data->symbols, *$2);
   }
   | PATH { $$ = new ExprPath(absPath($1, data->basePath)); }
-  | URI { $$ = new ExprString($1); }
+  | URI { $$ = new ExprString(data->symbols.create($1)); }
   | '(' expr ')' { $$ = $2; }
   /* Let expressions `let {..., body = ...}' are just desugared
      into `(rec {..., body = ...}).body'. */
@@ -375,21 +383,19 @@ binds
   | binds INHERIT ids ';'
     { $$ = $1;
       foreach (vector<Symbol>::iterator, i, *$3) {
-          if ($$->attrNames.find(*i) != $$->attrNames.end())
-              dupAttr(*i, makeCurPos(@3, data), $$->attrNames[*i]);
+          if ($$->attrs.find(*i) != $$->attrs.end())
+              dupAttr(*i, makeCurPos(@3, data), $$->attrs[*i].pos);
           Pos pos = makeCurPos(@3, data);
-          $$->inherited.push_back(ExprAttrs::Inherited(*i, pos));
-          $$->attrNames[*i] = pos;
+          $$->attrs[*i] = ExprAttrs::AttrDef(*i, pos);
       }
     }
   | binds INHERIT '(' expr ')' ids ';'
     { $$ = $1;
       /* !!! Should ensure sharing of the expression in $4. */
       foreach (vector<Symbol>::iterator, i, *$6) {
-          if ($$->attrNames.find(*i) != $$->attrNames.end())
-              dupAttr(*i, makeCurPos(@6, data), $$->attrNames[*i]);
-          $$->attrs[*i] = ExprAttrs::Attr(new ExprSelect($4, *i), makeCurPos(@6, data));
-          $$->attrNames[*i] = makeCurPos(@6, data);
+          if ($$->attrs.find(*i) != $$->attrs.end())
+              dupAttr(*i, makeCurPos(@6, data), $$->attrs[*i].pos);
+          $$->attrs[*i] = ExprAttrs::AttrDef(new ExprSelect($4, *i), makeCurPos(@6, data));
       }}
 
   | { $$ = new ExprAttrs; }
diff --git a/src/libexpr/primops.cc b/src/libexpr/primops.cc
index 973670e68..a4812de06 100644
--- a/src/libexpr/primops.cc
+++ b/src/libexpr/primops.cc
@@ -119,24 +119,24 @@ static void prim_genericClosure(EvalState & state, Value * * args, Value & v)
         args[0]->attrs->find(state.symbols.create("startSet"));
     if (startSet == args[0]->attrs->end())
         throw EvalError("attribute `startSet' required");
-    state.forceList(startSet->second.value);
+    state.forceList(*startSet->value);
 
     list<Value *> workSet;
-    for (unsigned int n = 0; n < startSet->second.value.list.length; ++n)
-        workSet.push_back(startSet->second.value.list.elems[n]);
+    for (unsigned int n = 0; n < startSet->value->list.length; ++n)
+        workSet.push_back(startSet->value->list.elems[n]);
 
     /* Get the operator. */
     Bindings::iterator op =
         args[0]->attrs->find(state.symbols.create("operator"));
     if (op == args[0]->attrs->end())
         throw EvalError("attribute `operator' required");
-    state.forceValue(op->second.value);
+    state.forceValue(*op->value);
 
     /* Construct the closure by applying the operator to element of
        `workSet', adding the result to `workSet', continuing until
        no new elements are found. */
     list<Value> res;
-    set<Value, CompareValues> doneKeys;
+    set<Value, CompareValues> doneKeys; // !!! use Value *?
     while (!workSet.empty()) {
 	Value * e = *(workSet.begin());
 	workSet.pop_front();
@@ -147,15 +147,15 @@ static void prim_genericClosure(EvalState & state, Value * * args, Value & v)
             e->attrs->find(state.symbols.create("key"));
         if (key == e->attrs->end())
             throw EvalError("attribute `key' required");
-        state.forceValue(key->second.value);
+        state.forceValue(*key->value);
 
-        if (doneKeys.find(key->second.value) != doneKeys.end()) continue;
-        doneKeys.insert(key->second.value);
+        if (doneKeys.find(*key->value) != doneKeys.end()) continue;
+        doneKeys.insert(*key->value);
         res.push_back(*e);
         
         /* Call the `operator' function with `e' as argument. */
         Value call;
-        mkApp(call, op->second.value, *e);
+        mkApp(call, *op->value, *e);
         state.forceList(call);
 
         /* Add the values returned by the operator to the work set. */
@@ -167,13 +167,9 @@ static void prim_genericClosure(EvalState & state, Value * * args, Value & v)
 
     /* Create the result list. */
     state.mkList(v, res.size());
-    Value * vs = state.allocValues(res.size());
-
     unsigned int n = 0;
-    foreach (list<Value>::iterator, i, res) {
-        v.list.elems[n] = &vs[n];
-        vs[n++] = *i;
-    }
+    foreach (list<Value>::iterator, i, res)
+        *(v.list.elems[n++] = state.allocValue()) = *i;
 }
 
 
@@ -210,15 +206,16 @@ static void prim_addErrorContext(EvalState & state, Value * * args, Value & v)
  * else => {success=false; value=false;} */
 static void prim_tryEval(EvalState & state, Value * * args, Value & v)
 {
-    state.mkAttrs(v);
+    state.mkAttrs(v, 2);
     try {
         state.forceValue(*args[0]);
-        (*v.attrs)[state.symbols.create("value")].value = *args[0];
-        mkBool((*v.attrs)[state.symbols.create("success")].value, true);
+        v.attrs->push_back(Attr(state.symbols.create("value"), args[0]));
+        mkBool(*state.allocAttr(v, state.symbols.create("success")), true);
     } catch (AssertionError & e) {
-        mkBool((*v.attrs)[state.symbols.create("value")].value, false);
-        mkBool((*v.attrs)[state.symbols.create("success")].value, false);
+        mkBool(*state.allocAttr(v, state.symbols.create("value")), false);
+        mkBool(*state.allocAttr(v, state.symbols.create("success")), false);
     }
+    v.attrs->sort();
 }
 
 
@@ -324,9 +321,9 @@ static void prim_derivationStrict(EvalState & state, Value * * args, Value & v)
     if (attr == args[0]->attrs->end())
         throw EvalError("required attribute `name' missing");
     string drvName;
-    Pos & posDrvName(*attr->second.pos);
+    Pos & posDrvName(*attr->pos);
     try {        
-        drvName = state.forceStringNoCtx(attr->second.value);
+        drvName = state.forceStringNoCtx(*attr->value);
     } catch (Error & e) {
         e.addPrefix(format("while evaluating the derivation attribute `name' at %1%:\n") % posDrvName);
         throw;
@@ -341,7 +338,7 @@ static void prim_derivationStrict(EvalState & state, Value * * args, Value & v)
     bool outputHashRecursive = false;
 
     foreach (Bindings::iterator, i, *args[0]->attrs) {
-        string key = i->first;
+        string key = i->name;
         startNest(nest, lvlVomit, format("processing attribute `%1%'") % key);
 
         try {
@@ -349,9 +346,9 @@ static void prim_derivationStrict(EvalState & state, Value * * args, Value & v)
             /* The `args' attribute is special: it supplies the
                command-line arguments to the builder. */
             if (key == "args") {
-                state.forceList(i->second.value);
-                for (unsigned int n = 0; n < i->second.value.list.length; ++n) {
-                    string s = state.coerceToString(*i->second.value.list.elems[n], context, true);
+                state.forceList(*i->value);
+                for (unsigned int n = 0; n < i->value->list.length; ++n) {
+                    string s = state.coerceToString(*i->value->list.elems[n], context, true);
                     drv.args.push_back(s);
                 }
             }
@@ -359,11 +356,11 @@ static void prim_derivationStrict(EvalState & state, Value * * args, Value & v)
             /* All other attributes are passed to the builder through
                the environment. */
             else {
-                string s = state.coerceToString(i->second.value, context, true);
+                string s = state.coerceToString(*i->value, context, true);
                 drv.env[key] = s;
                 if (key == "builder") drv.builder = s;
-                else if (i->first == state.sSystem) drv.platform = s;
-                else if (i->first == state.sName) drvName = s;
+                else if (i->name == state.sSystem) drv.platform = s;
+                else if (i->name == state.sName) drvName = s;
                 else if (key == "outputHash") outputHash = s;
                 else if (key == "outputHashAlgo") outputHashAlgo = s;
                 else if (key == "outputHashMode") {
@@ -375,7 +372,7 @@ static void prim_derivationStrict(EvalState & state, Value * * args, Value & v)
 
         } catch (Error & e) {
             e.addPrefix(format("while evaluating the derivation attribute `%1%' at %2%:\n")
-                % key % *i->second.pos);
+                % key % *i->pos);
             e.addPrefix(format("while instantiating the derivation named `%1%' at %2%:\n")
                 % drvName % posDrvName);
             throw;
@@ -487,9 +484,10 @@ static void prim_derivationStrict(EvalState & state, Value * * args, Value & v)
     state.drvHashes[drvPath] = hashDerivationModulo(state, drv);
 
     /* !!! assumes a single output */
-    state.mkAttrs(v);
-    mkString((*v.attrs)[state.sOutPath].value, outPath, singleton<PathSet>(drvPath));
-    mkString((*v.attrs)[state.sDrvPath].value, drvPath, singleton<PathSet>("=" + drvPath));
+    state.mkAttrs(v, 2);
+    mkString(*state.allocAttr(v, state.sOutPath), outPath, singleton<PathSet>(drvPath));
+    mkString(*state.allocAttr(v, state.sDrvPath), drvPath, singleton<PathSet>("=" + drvPath));
+    v.attrs->sort();
 }
 
 
@@ -689,17 +687,14 @@ 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);
+        names.insert(i->name);
 
     unsigned int n = 0;
-    foreach (StringSet::iterator, i, names) {
-        v.list.elems[n] = &vs[n];
-        mkString(vs[n++], *i);
-    }
+    foreach (StringSet::iterator, i, names)
+        mkString(*(v.list.elems[n++] = state.allocValue()), *i);
 }
 
 
@@ -713,8 +708,8 @@ static void prim_getAttr(EvalState & state, Value * * args, Value & v)
     if (i == args[1]->attrs->end())
         throw EvalError(format("attribute `%1%' missing") % attr);
     // !!! add to stack trace?
-    state.forceValue(i->second.value);
-    v = i->second.value;
+    state.forceValue(*i->value);
+    v = *i->value;
 }
 
 
@@ -740,11 +735,20 @@ static void prim_removeAttrs(EvalState & state, Value * * args, Value & v)
     state.forceAttrs(*args[0]);
     state.forceList(*args[1]);
 
-    state.cloneAttrs(*args[0], v);
-
+    /* 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]);
-        v.attrs->erase(state.symbols.create(args[1]->list.elems[i]->string.s));
+        names.insert(state.symbols.create(args[1]->list.elems[i]->string.s));
+    }
+
+    /* Copy all attributes not in that set.  Note that we don't need
+       to sort v.attrs because it's a subset of an already sorted
+       vector. */
+    state.mkAttrs(v, args[0]->attrs->size());
+    foreach (Bindings::iterator, i, *args[0]->attrs) {
+        if (names.find(i->name) == names.end())
+            v.attrs->push_back(*i);
     }
 }
 
@@ -757,7 +761,9 @@ static void prim_listToAttrs(EvalState & state, Value * * args, Value & v)
 {
     state.forceList(*args[0]);
 
-    state.mkAttrs(v);
+    state.mkAttrs(v, args[0]->list.length);
+
+    std::set<Symbol> seen;
 
     for (unsigned int i = 0; i < args[0]->list.length; ++i) {
         Value & v2(*args[0]->list.elems[i]);
@@ -766,16 +772,21 @@ static void prim_listToAttrs(EvalState & state, Value * * args, Value & v)
         Bindings::iterator j = v2.attrs->find(state.sName);
         if (j == v2.attrs->end())
             throw TypeError("`name' attribute missing in a call to `listToAttrs'");
-        string name = state.forceStringNoCtx(j->second.value);
+        string name = state.forceStringNoCtx(*j->value);
         
-        j = v2.attrs->find(state.symbols.create("value"));
-        if (j == v2.attrs->end())
+        Bindings::iterator j2 = v2.attrs->find(state.symbols.create("value"));
+        if (j2 == v2.attrs->end())
             throw TypeError("`value' attribute missing in a call to `listToAttrs'");
 
-        Attr & a = (*v.attrs)[state.symbols.create(name)];
-        mkCopy(a.value, j->second.value);
-        a.pos = j->second.pos;
+        Symbol sym = state.symbols.create(name);
+        if (seen.find(sym) == seen.end()) {
+            v.attrs->push_back(Attr(sym, j2->value, j2->pos));
+            seen.insert(sym);
+        }
+        /* !!! Throw an error if `name' already exists? */
     }
+
+    v.attrs->sort();
 }
 
 
@@ -787,15 +798,12 @@ static void prim_intersectAttrs(EvalState & state, Value * * args, Value & v)
     state.forceAttrs(*args[0]);
     state.forceAttrs(*args[1]);
         
-    state.mkAttrs(v);
+    state.mkAttrs(v, std::min(args[0]->attrs->size(), args[1]->attrs->size()));
 
     foreach (Bindings::iterator, i, *args[0]->attrs) {
-        Bindings::iterator j = args[1]->attrs->find(i->first);
-        if (j != args[1]->attrs->end()) {
-            Attr & a = (*v.attrs)[j->first];
-            mkCopy(a.value, j->second.value);
-            a.pos = j->second.pos;
-        }
+        Bindings::iterator j = args[1]->attrs->find(i->name);
+        if (j != args[1]->attrs->end())
+            v.attrs->push_back(*j);
     }
 }
 
@@ -819,12 +827,16 @@ static void prim_functionArgs(EvalState & state, Value * * args, Value & v)
     if (args[0]->type != tLambda)
         throw TypeError("`functionArgs' requires a function");
 
-    state.mkAttrs(v);
-
-    if (!args[0]->lambda.fun->matchAttrs) return;
+    if (!args[0]->lambda.fun->matchAttrs) {
+        state.mkAttrs(v, 0);
+        return;
+    }
 
+    state.mkAttrs(v, args[0]->lambda.fun->formals->formals.size());
     foreach (Formals::Formals_::iterator, i, args[0]->lambda.fun->formals->formals)
-        mkBool((*v.attrs)[i->name].value, i->def);
+        // !!! should optimise booleans (allocate only once)
+        mkBool(*state.allocAttr(v, i->name), i->def);
+    v.attrs->sort();
 }
 
 
@@ -872,12 +884,10 @@ 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] = &vs[n];
-        mkApp(vs[n], *args[0], *args[1]->list.elems[n]);
-    }
+    for (unsigned int n = 0; n < v.list.length; ++n)
+        mkApp(*(v.list.elems[n] = state.allocValue()), 
+            *args[0], *args[1]->list.elems[n]);
 }
 
 
@@ -1006,9 +1016,10 @@ static void prim_parseDrvName(EvalState & state, Value * * args, Value & v)
 {
     string name = state.forceStringNoCtx(*args[0]);
     DrvName parsed(name);
-    state.mkAttrs(v);
-    mkString((*v.attrs)[state.sName].value, parsed.name);
-    mkString((*v.attrs)[state.symbols.create("version")].value, parsed.version);
+    state.mkAttrs(v, 2);
+    mkString(*state.allocAttr(v, state.sName), parsed.name);
+    mkString(*state.allocAttr(v, state.symbols.create("version")), parsed.version);
+    v.attrs->sort();
 }
 
 
@@ -1033,7 +1044,7 @@ void EvalState::createBaseEnv()
     Value v;
 
     /* `builtins' must be first! */
-    mkAttrs(v);
+    mkAttrs(v, 128);
     addConstant("builtins", v);
 
     mkBool(v, true);
@@ -1072,7 +1083,7 @@ void EvalState::createBaseEnv()
     /* Add a wrapper around the derivation primop that computes the
        `drvPath' and `outPath' attributes lazily. */
     string s = "attrs: let res = derivationStrict attrs; in attrs // { drvPath = res.drvPath; outPath = res.outPath; type = \"derivation\"; }";
-    mkThunk(v, baseEnv, parseExprFromString(*this, s, "/"));
+    mkThunk_(v, parseExprFromString(*this, s, "/"));
     addConstant("derivation", v);
 
     // Paths
@@ -1121,7 +1132,11 @@ void EvalState::createBaseEnv()
 
     // Versions
     addPrimOp("__parseDrvName", 1, prim_parseDrvName);
-    addPrimOp("__compareVersions", 2, prim_compareVersions);    
+    addPrimOp("__compareVersions", 2, prim_compareVersions);
+
+    /* Now that we've added all primops, sort the `builtins' attribute
+       set, because attribute lookups expect it to be sorted. */
+    baseEnv.values[0]->attrs->sort();
 }
 
 
diff --git a/src/libexpr/symbol-table.hh b/src/libexpr/symbol-table.hh
index 20ebe5fed..976117a20 100644
--- a/src/libexpr/symbol-table.hh
+++ b/src/libexpr/symbol-table.hh
@@ -28,6 +28,8 @@ private:
     friend class SymbolTable;
 
 public:
+    Symbol() : s(0) { };
+    
     bool operator == (const Symbol & s2) const
     {
         return s == s2.s;
diff --git a/src/libexpr/value-to-xml.cc b/src/libexpr/value-to-xml.cc
index 8955a8a33..bc63f7762 100644
--- a/src/libexpr/value-to-xml.cc
+++ b/src/libexpr/value-to-xml.cc
@@ -34,10 +34,10 @@ static void showAttrs(EvalState & state, bool strict, bool location,
     StringSet names;
     
     foreach (Bindings::iterator, i, attrs)
-        names.insert(i->first);
+        names.insert(i->name);
     
     foreach (StringSet::iterator, i, names) {
-        Attr & a(attrs[state.symbols.create(*i)]);
+        Attr & a(*attrs.find(state.symbols.create(*i)));
         
         XMLAttrs xmlAttrs;
         xmlAttrs["name"] = *i;
@@ -45,7 +45,7 @@ static void showAttrs(EvalState & state, bool strict, bool location,
         
         XMLOpenElement _(doc, "attr", xmlAttrs);
         printValueAsXML(state, strict, location,
-            a.value, doc, context, drvsSeen);
+            *a.value, doc, context, drvsSeen);
     }
 }
 
@@ -90,16 +90,16 @@ static void printValueAsXML(EvalState & state, bool strict, bool location,
                 Path drvPath;
                 a = v.attrs->find(state.sDrvPath);
                 if (a != v.attrs->end()) {
-                    if (strict) state.forceValue(a->second.value);
-                    if (a->second.value.type == tString)
-                        xmlAttrs["drvPath"] = drvPath = a->second.value.string.s;
+                    if (strict) state.forceValue(*a->value);
+                    if (a->value->type == tString)
+                        xmlAttrs["drvPath"] = drvPath = a->value->string.s;
                 }
         
                 a = v.attrs->find(state.sOutPath);
                 if (a != v.attrs->end()) {
-                    if (strict) state.forceValue(a->second.value);
-                    if (a->second.value.type == tString)
-                        xmlAttrs["outPath"] = a->second.value.string.s;
+                    if (strict) state.forceValue(*a->value);
+                    if (a->value->type == tString)
+                        xmlAttrs["outPath"] = a->value->string.s;
                 }
 
                 XMLOpenElement _(doc, "derivation", xmlAttrs);
diff --git a/src/libmain/Makefile.am b/src/libmain/Makefile.am
index a9ee66042..1a2146e04 100644
--- a/src/libmain/Makefile.am
+++ b/src/libmain/Makefile.am
@@ -2,7 +2,7 @@ pkglib_LTLIBRARIES = libmain.la
 
 libmain_la_SOURCES = shared.cc
 
-libmain_la_LIBADD = ../libstore/libstore.la
+libmain_la_LIBADD = ../libstore/libstore.la @boehmgc_lib@
 
 pkginclude_HEADERS = shared.hh
 
diff --git a/src/libmain/shared.cc b/src/libmain/shared.cc
index eddc4e64b..29fc13e33 100644
--- a/src/libmain/shared.cc
+++ b/src/libmain/shared.cc
@@ -13,6 +13,10 @@
 #include <sys/stat.h>
 #include <unistd.h>
 
+#if HAVE_BOEHMGC
+#include <gc/gc.h>
+#endif
+
 
 namespace nix {
 
@@ -314,6 +318,14 @@ static void setuidInit()
 }
 
 
+/* Called when the Boehm GC runs out of memory. */
+static void * oomHandler(size_t requested)
+{
+    /* Convert this to a proper C++ exception. */
+    throw std::bad_alloc();
+}
+
+
 }
 
 
@@ -335,6 +347,26 @@ int main(int argc, char * * argv)
 
     std::ios::sync_with_stdio(false);
 
+#if HAVE_BOEHMGC
+    /* Initialise the Boehm garbage collector.  This isn't necessary
+       on most platforms, but for portability we do it anyway. */
+    GC_INIT();
+
+    GC_oom_fn = oomHandler;
+
+    /* Set the initial heap size to something fairly big (384 MiB) so
+       that in most cases we don't need to garbage collect at all.
+       (Collection has a fairly significant overhead, some.)  The heap
+       size can be overriden through libgc's GC_INITIAL_HEAP_SIZE
+       environment variable.  We should probably also provide a
+       nix.conf setting for this.  Note that GC_expand_hp() causes a
+       lot of virtual, but not physical (resident) memory to be
+       allocated.  This might be a problem on systems that don't
+       overcommit. */
+    if (!getenv("GC_INITIAL_HEAP_SIZE"))
+        GC_expand_hp(384 * 1024 * 1024);
+#endif
+
     try {
         try {
             initAndRun(argc, argv);
diff --git a/src/nix-env/nix-env.cc b/src/nix-env/nix-env.cc
index df32b9f60..58bc9af12 100644
--- a/src/nix-env/nix-env.cc
+++ b/src/nix-env/nix-env.cc
@@ -132,7 +132,7 @@ static void getAllExprs(EvalState & state,
             if (hasSuffix(attrName, ".nix"))
                 attrName = string(attrName, 0, attrName.size() - 4);
             attrs.attrs[state.symbols.create(attrName)] =
-                ExprAttrs::Attr(parseExprFromFile(state, absPath(path2)), noPos);
+                ExprAttrs::AttrDef(parseExprFromFile(state, absPath(path2)), noPos);
         }
         else
             /* `path2' is a directory (with no default.nix in it);
@@ -154,14 +154,14 @@ static Expr * loadSourceExpr(EvalState & state, const Path & path)
        some system-wide directory). */
     ExprAttrs * attrs = new ExprAttrs;
     attrs->attrs[state.symbols.create("_combineChannels")] =
-        ExprAttrs::Attr(new ExprList(), noPos);
+        ExprAttrs::AttrDef(new ExprList(), noPos);
     getAllExprs(state, path, *attrs);
     return attrs;
 }
 
 
 static void loadDerivations(EvalState & state, Path nixExprPath,
-    string systemFilter, const Bindings & autoArgs,
+    string systemFilter, Bindings & autoArgs,
     const string & pathPrefix, DrvInfos & elems)
 {
     Value v;
@@ -321,7 +321,7 @@ static bool isPath(const string & s)
 
 
 static void queryInstSources(EvalState & state,
-    const InstallSourceInfo & instSource, const Strings & args,
+    InstallSourceInfo & instSource, const Strings & args,
     DrvInfos & elems, bool newestOnly)
 {
     InstallSourceType type = instSource.type;
diff --git a/src/nix-env/user-env.cc b/src/nix-env/user-env.cc
index 0a619f698..865d24e2f 100644
--- a/src/nix-env/user-env.cc
+++ b/src/nix-env/user-env.cc
@@ -25,7 +25,8 @@ DrvInfos queryInstalled(EvalState & state, const Path & userEnv)
     if (pathExists(manifestFile)) {
         Value v;
         state.eval(parseExprFromFile(state, manifestFile), v);
-        getDerivations(state, v, "", Bindings(), elems);
+        Bindings bindings;
+        getDerivations(state, v, "", bindings, elems);
     } else if (pathExists(oldManifestFile))
         readLegacyManifest(oldManifestFile, elems);
 
@@ -58,23 +59,24 @@ bool createUserEnv(EvalState & state, DrvInfos & elems,
            the meta attributes. */
         Path drvPath = keepDerivations ? i->queryDrvPath(state) : "";
 
-        Value & v(*state.allocValues(1));
+        Value & v(*state.allocValue());
         manifest.list.elems[n++] = &v;
-        state.mkAttrs(v);
+        state.mkAttrs(v, 8);
 
-        mkString((*v.attrs)[state.sType].value, "derivation");
-        mkString((*v.attrs)[state.sName].value, i->name);
-        mkString((*v.attrs)[state.sSystem].value, i->system);
-        mkString((*v.attrs)[state.sOutPath].value, i->queryOutPath(state));
+        mkString(*state.allocAttr(v, state.sType), "derivation");
+        mkString(*state.allocAttr(v, state.sName), i->name);
+        mkString(*state.allocAttr(v, state.sSystem), i->system);
+        mkString(*state.allocAttr(v, state.sOutPath), i->queryOutPath(state));
         if (drvPath != "")
-            mkString((*v.attrs)[state.sDrvPath].value, i->queryDrvPath(state));
-        
-        state.mkAttrs((*v.attrs)[state.sMeta].value);
-        
+            mkString(*state.allocAttr(v, state.sDrvPath), i->queryDrvPath(state));
+
+        Value & vMeta = *state.allocAttr(v, state.sMeta);
+        state.mkAttrs(vMeta, 16);
+
         MetaInfo meta = i->queryMetaInfo(state);
 
         foreach (MetaInfo::const_iterator, j, meta) {
-            Value & v2((*(*v.attrs)[state.sMeta].value.attrs)[state.symbols.create(j->first)].value);
+            Value & v2(*state.allocAttr(vMeta, state.symbols.create(j->first)));
             switch (j->second.type) {
                 case MetaValue::tpInt: mkInt(v2, j->second.intValue); break;
                 case MetaValue::tpString: mkString(v2, j->second.stringValue); break;
@@ -82,7 +84,7 @@ bool createUserEnv(EvalState & state, DrvInfos & elems,
                     state.mkList(v2, j->second.stringValues.size());
                     unsigned int m = 0;
                     foreach (Strings::const_iterator, k, j->second.stringValues) {
-                        v2.list.elems[m] = state.allocValues(1);
+                        v2.list.elems[m] = state.allocValue();
                         mkString(*v2.list.elems[m++], *k);
                     }
                     break;
@@ -91,6 +93,9 @@ bool createUserEnv(EvalState & state, DrvInfos & elems,
             }
         }
     
+        vMeta.attrs->sort();
+        v.attrs->sort();
+        
         /* This is only necessary when installing store paths, e.g.,
            `nix-env -i /nix/store/abcd...-foo'. */
         store->addTempRoot(i->queryOutPath(state));
@@ -113,11 +118,12 @@ bool createUserEnv(EvalState & state, DrvInfos & elems,
     /* Construct a Nix expression that calls the user environment
        builder with the manifest as argument. */
     Value args, topLevel;
-    state.mkAttrs(args);
-    mkString((*args.attrs)[state.sSystem].value, thisSystem);
-    mkString((*args.attrs)[state.symbols.create("manifest")].value,
+    state.mkAttrs(args, 3);
+    mkString(*state.allocAttr(args, state.sSystem), thisSystem);
+    mkString(*state.allocAttr(args, state.symbols.create("manifest")),
         manifestFile, singleton<PathSet>(manifestFile));
-    (*args.attrs)[state.symbols.create("derivations")].value = manifest;
+    args.attrs->push_back(Attr(state.symbols.create("derivations"), &manifest));
+    args.attrs->sort();
     mkApp(topLevel, envBuilder, args);
         
     /* Evaluate it. */
diff --git a/src/nix-instantiate/nix-instantiate.cc b/src/nix-instantiate/nix-instantiate.cc
index 2925f9c5e..b330f0cf1 100644
--- a/src/nix-instantiate/nix-instantiate.cc
+++ b/src/nix-instantiate/nix-instantiate.cc
@@ -38,7 +38,7 @@ static bool indirectRoot = false;
 
 
 void processExpr(EvalState & state, const Strings & attrPaths,
-    bool parseOnly, bool strict, const Bindings & autoArgs,
+    bool parseOnly, bool strict, Bindings & autoArgs,
     bool evalOnly, bool xmlOutput, bool location, Expr * e)
 {
     if (parseOnly)