Store Attrs inside Bindings

This prevents a double allocation per attribute set.

6 files changed, 92 insertions, 50 deletions

diff --git a/src/libexpr/common-opts.cc b/src/libexpr/common-opts.cc
index 25f1e7117b76..c03d720bde82 100644
--- a/src/libexpr/common-opts.cc
+++ b/src/libexpr/common-opts.cc
@@ -25,17 +25,19 @@ bool parseAutoArgs(Strings::iterator & i,
 }
 
 
-void evalAutoArgs(EvalState & state, std::map<string, string> & in, Bindings & out)
+Bindings * evalAutoArgs(EvalState & state, std::map<string, string> & in)
 {
-    for (auto & i: in) {
+    Bindings * res = state.allocBindings(in.size());
+    for (auto & i : in) {
         Value * v = state.allocValue();
         if (i.second[0] == 'E')
             state.mkThunk_(*v, state.parseExprFromString(string(i.second, 1), absPath(".")));
         else
             mkString(*v, string(i.second, 1));
-        out.push_back(Attr(state.symbols.create(i.first), v));
+        res->push_back(Attr(state.symbols.create(i.first), v));
     }
-    out.sort();
+    res->sort();
+    return res;
 }
 
 
diff --git a/src/libexpr/common-opts.hh b/src/libexpr/common-opts.hh
index bb6d399a8a61..be0f40202430 100644
--- a/src/libexpr/common-opts.hh
+++ b/src/libexpr/common-opts.hh
@@ -8,7 +8,7 @@ namespace nix {
 bool parseAutoArgs(Strings::iterator & i,
     const Strings::iterator & argsEnd, std::map<string, string> & res);
 
-void evalAutoArgs(EvalState & state, std::map<string, string> & in, Bindings & out);
+Bindings * evalAutoArgs(EvalState & state, std::map<string, string> & in);
 
 bool parseSearchPathArg(Strings::iterator & i,
     const Strings::iterator & argsEnd, Strings & searchPath);
diff --git a/src/libexpr/eval.cc b/src/libexpr/eval.cc
index 70b3365639b2..b07d210c1b39 100644
--- a/src/libexpr/eval.cc
+++ b/src/libexpr/eval.cc
@@ -35,7 +35,7 @@ namespace nix {
 Bindings::iterator Bindings::find(const Symbol & name)
 {
     Attr key(name, 0);
-    iterator i = lower_bound(begin(), end(), key);
+    iterator i = std::lower_bound(begin(), end(), key);
     if (i != end() && i->name == name) return i;
     return end();
 }
@@ -175,7 +175,7 @@ EvalState::EvalState(const Strings & _searchPath)
     , baseEnvDispl(0)
 {
     nrEnvs = nrValuesInEnvs = nrValues = nrListElems = 0;
-    nrAttrsets = nrOpUpdates = nrOpUpdateValuesCopied = 0;
+    nrAttrsets = nrAttrsInAttrsets = nrOpUpdates = nrOpUpdateValuesCopied = 0;
     nrListConcats = nrPrimOpCalls = nrFunctionCalls = 0;
     countCalls = getEnv("NIX_COUNT_CALLS", "0") != "0";
 
@@ -433,6 +433,12 @@ Value * EvalState::allocAttr(Value & vAttrs, const Symbol & name)
 }
 
 
+Bindings * EvalState::allocBindings(Bindings::size_t capacity)
+{
+    return new (GC_MALLOC(sizeof(Bindings) + sizeof(Attr) * capacity)) Bindings(capacity);
+}
+
+
 void EvalState::mkList(Value & v, unsigned int length)
 {
     v.type = tList;
@@ -446,9 +452,9 @@ void EvalState::mkAttrs(Value & v, unsigned int expected)
 {
     clearValue(v);
     v.type = tAttrs;
-    v.attrs = NEW Bindings;
-    v.attrs->reserve(expected);
+    v.attrs = allocBindings(expected);
     nrAttrsets++;
+    nrAttrsInAttrsets += expected;
 }
 
 
@@ -619,7 +625,7 @@ void ExprPath::eval(EvalState & state, Env & env, Value & v)
 
 void ExprAttrs::eval(EvalState & state, Env & env, Value & v)
 {
-    state.mkAttrs(v, attrs.size());
+    state.mkAttrs(v, attrs.size() + dynamicAttrs.size());
     Env *dynamicEnv = &env;
 
     if (recursive) {
@@ -658,15 +664,19 @@ void ExprAttrs::eval(EvalState & state, Env & env, Value & v)
         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);
+            Bindings * newBnds = state.allocBindings(v.attrs->size() + vOverrides->attrs->size());
+            for (auto & i : *v.attrs)
+                newBnds->push_back(i);
+            for (auto & 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;
+                    (*newBnds)[j->second.displ] = i;
+                    env2.values[j->second.displ] = i.value;
                 } else
-                    v.attrs->push_back(*i);
+                    newBnds->push_back(i);
             }
-            v.attrs->sort();
+            newBnds->sort();
+            v.attrs = newBnds;
         }
     }
 
@@ -692,8 +702,8 @@ void ExprAttrs::eval(EvalState & state, Env & env, Value & v)
 
         i->valueExpr->setName(nameSym);
         /* Keep sorted order so find can catch duplicates */
-        v.attrs->insert(lower_bound(v.attrs->begin(), v.attrs->end(), Attr(nameSym, 0)),
-                Attr(nameSym, i->valueExpr->maybeThunk(state, *dynamicEnv), &i->pos));
+        v.attrs->push_back(Attr(nameSym, i->valueExpr->maybeThunk(state, *dynamicEnv), &i->pos));
+        v.attrs->sort(); // FIXME: inefficient
     }
 }
 
@@ -1424,7 +1434,8 @@ void EvalState::printStats()
     printMsg(v, format("  list concatenations: %1%") % nrListConcats);
     printMsg(v, format("  values allocated: %1% (%2% bytes)")
         % nrValues % (nrValues * sizeof(Value)));
-    printMsg(v, format("  sets allocated: %1%") % nrAttrsets);
+    printMsg(v, format("  sets allocated: %1% (%2% bytes)")
+        % nrAttrsets % (nrAttrsets * sizeof(Bindings) + nrAttrsInAttrsets * sizeof(Attr)));
     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());
diff --git a/src/libexpr/eval.hh b/src/libexpr/eval.hh
index af9452c7539f..3ac40ed34eec 100644
--- a/src/libexpr/eval.hh
+++ b/src/libexpr/eval.hh
@@ -16,23 +16,59 @@ namespace nix {
 
 
 class EvalState;
-struct Attr;
 
 
-/* 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
+struct Attr
+{
+    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;
+    }
+};
 
 
-class Bindings : public BindingsBase
+class Bindings
 {
 public:
+    typedef uint32_t size_t;
+
+private:
+    size_t size_, capacity;
+    Attr attrs[0];
+
+    Bindings(uint32_t capacity) : size_(0), capacity(capacity) { }
+
+public:
+    size_t size() { return size_; }
+
+    bool empty() { return !size_; }
+
+    typedef Attr * iterator;
+
+    void push_back(const Attr & attr)
+    {
+        assert(size_ < capacity);
+        attrs[size_++] = attr;
+    }
+
     iterator find(const Symbol & name);
+    iterator begin() { return &attrs[0]; }
+    iterator end() { return &attrs[size_]; }
+
+    Attr & operator[](size_t pos)
+    {
+        return attrs[pos];
+    }
+
     void sort();
+
+    friend class EvalState;
 };
 
 
@@ -58,21 +94,6 @@ struct Env
 };
 
 
-struct Attr
-{
-    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;
-    }
-};
-
-
 void mkString(Value & v, const string & s, const PathSet & context = PathSet());
 
 void copyContext(const Value & v, PathSet & context);
@@ -245,6 +266,8 @@ public:
 
     Value * allocAttr(Value & vAttrs, const Symbol & name);
 
+    Bindings * allocBindings(Bindings::size_t capacity);
+
     void mkList(Value & v, unsigned int length);
     void mkAttrs(Value & v, unsigned int expected);
     void mkThunk_(Value & v, Expr * expr);
@@ -264,6 +287,7 @@ private:
     unsigned long nrValues;
     unsigned long nrListElems;
     unsigned long nrAttrsets;
+    unsigned long nrAttrsInAttrsets;
     unsigned long nrOpUpdates;
     unsigned long nrOpUpdateValuesCopied;
     unsigned long nrListConcats;
diff --git a/src/libexpr/get-drvs.cc b/src/libexpr/get-drvs.cc
index db91eab37156..1c9fa02a366a 100644
--- a/src/libexpr/get-drvs.cc
+++ b/src/libexpr/get-drvs.cc
@@ -161,12 +161,12 @@ void DrvInfo::setMeta(const string & name, Value * v)
 {
     getMeta();
     Bindings * old = meta;
-    meta = new Bindings();
+    meta = state->allocBindings(1 + (old ? old->size() : 0));
     Symbol sym = state->symbols.create(name);
     if (old)
-        foreach (Bindings::iterator, i, *old)
-            if (i->name != sym)
-                meta->push_back(*i);
+        for (auto i : *old)
+            if (i.name != sym)
+                meta->push_back(i);
     if (v) meta->push_back(Attr(sym, v));
     meta->sort();
 }
diff --git a/src/libexpr/json-to-value.cc b/src/libexpr/json-to-value.cc
index af4394b0bbba..1892b0bac1af 100644
--- a/src/libexpr/json-to-value.cc
+++ b/src/libexpr/json-to-value.cc
@@ -14,8 +14,10 @@ static void skipWhitespace(const char * & s)
 
 #if HAVE_BOEHMGC
 typedef std::vector<Value *, gc_allocator<Value *> > ValueVector;
+typedef std::map<Symbol, Value *, std::less<Symbol>, gc_allocator<Value *> > ValueMap;
 #else
 typedef std::vector<Value *> ValueVector;
+typedef std::map<Symbol, Value *> ValueMap;
 #endif
 
 
@@ -76,22 +78,25 @@ static void parseJSON(EvalState & state, const char * & s, Value & v)
 
     else if (*s == '{') {
         s++;
-        state.mkAttrs(v, 1);
+        ValueMap attrs;
         while (1) {
             skipWhitespace(s);
-            if (v.attrs->empty() && *s == '}') break;
+            if (attrs.empty() && *s == '}') break;
             string name = parseJSONString(s);
             skipWhitespace(s);
             if (*s != ':') throw JSONParseError("expected ‘:’ in JSON object");
             s++;
             Value * v2 = state.allocValue();
             parseJSON(state, s, *v2);
-            v.attrs->push_back(Attr(state.symbols.create(name), v2));
+            attrs[state.symbols.create(name)] = v2;
             skipWhitespace(s);
             if (*s == '}') break;
             if (*s != ',') throw JSONParseError("expected ‘,’ or ‘}’ after JSON member");
             s++;
         }
+        state.mkAttrs(v, attrs.size());
+        for (auto & i : attrs)
+            v.attrs->push_back(Attr(i.first, i.second));
         v.attrs->sort();
         s++;
     }