From 5b58991a71d15123c010bbbd7f08530dbc31173f Mon Sep 17 00:00:00 2001 From: Eelco Dolstra Date: Fri, 19 Sep 2014 16:49:41 +0200 Subject: 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 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 & in, Bindings & out) +Bindings * evalAutoArgs(EvalState & state, std::map & 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 & res); -void evalAutoArgs(EvalState & state, std::map & in, Bindings & out); +Bindings * evalAutoArgs(EvalState & state, std::map & 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 > BindingsBase; -#else -typedef std::vector 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 > ValueVector; +typedef std::map, gc_allocator > ValueMap; #else typedef std::vector ValueVector; +typedef std::map 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 5116d955fe09..c24165da8f1d 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 3ebd6c1f2362..3bc31b9eafeb 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 7a38f2ac4269..6bd1a9d6ca32 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; -- cgit 1.4.1