209/376: Store Attrs inside Bindings

[Ludovic Courtès]

civodul pushed a commit to tag 1.8
in repository guix.

commit 5b58991a71d15123c010bbbd7f08530dbc31173f
Author: Eelco Dolstra <address@hidden>
Date:   Fri Sep 19 16:49:41 2014 +0200

    Store Attrs inside Bindings
    
    This prevents a double allocation per attribute set.
---
 src/libexpr/common-opts.cc             |   10 +++--
 src/libexpr/common-opts.hh             |    2 +-
 src/libexpr/eval.cc                    |   39 +++++++++++------
 src/libexpr/eval.hh                    |   72 +++++++++++++++++++++-----------
 src/libexpr/get-drvs.cc                |    8 ++--
 src/libexpr/json-to-value.cc           |   11 ++++-
 src/nix-env/nix-env.cc                 |   14 +++---
 src/nix-env/user-env.cc                |    2 +-
 src/nix-instantiate/nix-instantiate.cc |    3 +-
 9 files changed, 101 insertions(+), 60 deletions(-)

diff --git a/src/libexpr/common-opts.cc b/src/libexpr/common-opts.cc
index 25f1e71..c03d720 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 bb6d399..be0f402 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 70b3365..b07d210 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 af9452c..3ac40ed 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 db91eab..1c9fa02 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 af4394b..1892b0b 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++;
     }
diff --git a/src/nix-env/nix-env.cc b/src/nix-env/nix-env.cc
index 5116d95..c24165d 100644
--- a/src/nix-env/nix-env.cc
+++ b/src/nix-env/nix-env.cc
@@ -44,7 +44,7 @@ struct InstallSourceInfo
     Path nixExprPath; /* for srcNixExprDrvs, srcNixExprs */
     Path profile; /* for srcProfile */
     string systemFilter; /* for srcNixExprDrvs */
-    Bindings autoArgs;
+    Bindings * autoArgs;
 };
 
 
@@ -350,7 +350,7 @@ static void queryInstSources(EvalState & state,
                Nix expression. */
             DrvInfos allElems;
             loadDerivations(state, instSource.nixExprPath,
-                instSource.systemFilter, instSource.autoArgs, "", allElems);
+                instSource.systemFilter, *instSource.autoArgs, "", allElems);
 
             elems = filterBySelector(state, allElems, args, newestOnly);
 
@@ -373,7 +373,7 @@ static void queryInstSources(EvalState & state,
                 Value vFun, vTmp;
                 state.eval(eFun, vFun);
                 mkApp(vTmp, vFun, vArg);
-                getDerivations(state, vTmp, "", instSource.autoArgs, elems, 
true);
+                getDerivations(state, vTmp, "", *instSource.autoArgs, elems, 
true);
             }
 
             break;
@@ -423,8 +423,8 @@ static void queryInstSources(EvalState & state,
             Value vRoot;
             loadSourceExpr(state, instSource.nixExprPath, vRoot);
             foreach (Strings::const_iterator, i, args) {
-                Value & v(*findAlongAttrPath(state, *i, instSource.autoArgs, 
vRoot));
-                getDerivations(state, v, "", instSource.autoArgs, elems, true);
+                Value & v(*findAlongAttrPath(state, *i, *instSource.autoArgs, 
vRoot));
+                getDerivations(state, v, "", *instSource.autoArgs, elems, 
true);
             }
             break;
         }
@@ -926,7 +926,7 @@ static void opQuery(Globals & globals, Strings opFlags, 
Strings opArgs)
 
     if (source == sAvailable || compareVersions)
         loadDerivations(*globals.state, globals.instSource.nixExprPath,
-            globals.instSource.systemFilter, globals.instSource.autoArgs,
+            globals.instSource.systemFilter, *globals.instSource.autoArgs,
             attrPath, availElems);
 
     DrvInfos elems_ = filterBySelector(*globals.state,
@@ -1423,7 +1423,7 @@ int main(int argc, char * * argv)
         if (file != "")
             globals.instSource.nixExprPath = lookupFileArg(*globals.state, 
file);
 
-        evalAutoArgs(*globals.state, autoArgs_, globals.instSource.autoArgs);
+        globals.instSource.autoArgs = evalAutoArgs(*globals.state, autoArgs_);
 
         if (globals.profile == "")
             globals.profile = getEnv("NIX_PROFILE", "");
diff --git a/src/nix-env/user-env.cc b/src/nix-env/user-env.cc
index 3ebd6c1..3bc31b9 100644
--- a/src/nix-env/user-env.cc
+++ b/src/nix-env/user-env.cc
@@ -19,7 +19,7 @@ DrvInfos queryInstalled(EvalState & state, const Path & 
userEnv)
     if (pathExists(manifestFile)) {
         Value v;
         state.evalFile(manifestFile, v);
-        Bindings bindings;
+        Bindings & bindings(*state.allocBindings(0));
         getDerivations(state, v, "", bindings, elems, false);
     }
     return elems;
diff --git a/src/nix-instantiate/nix-instantiate.cc 
b/src/nix-instantiate/nix-instantiate.cc
index 7a38f2a..6bd1a9d 100644
--- a/src/nix-instantiate/nix-instantiate.cc
+++ b/src/nix-instantiate/nix-instantiate.cc
@@ -159,8 +159,7 @@ int main(int argc, char * * argv)
         EvalState state(searchPath);
         state.repair = repair;
 
-        Bindings autoArgs;
-        evalAutoArgs(state, autoArgs_, autoArgs);
+        Bindings & autoArgs(*evalAutoArgs(state, autoArgs_));
 
         if (evalOnly && !wantsReadWrite)
             settings.readOnlyMode = true;