From a4ab0a74d97c7c31df69f04870fa56cde89701a3 Mon Sep 17 00:00:00 2001 From: Yorick van Pelt Date: Mon, 27 Dec 2021 13:18:55 +0100 Subject: Fix accidental O(n^2 * log n) performance in NixRepl::addAttrsToScope Only sort once, after adding all of the attrs first. This reduces my `nix repl ''` loading time from 1.07s to 103ms. Fixes #5823 --- src/libexpr/nixexpr.hh | 7 +++++++ src/nix/repl.cc | 12 ++++++++++-- 2 files changed, 17 insertions(+), 2 deletions(-) diff --git a/src/libexpr/nixexpr.hh b/src/libexpr/nixexpr.hh index c013f5deb..b328b3941 100644 --- a/src/libexpr/nixexpr.hh +++ b/src/libexpr/nixexpr.hh @@ -368,6 +368,13 @@ struct StaticEnv [](const Vars::value_type & a, const Vars::value_type & b) { return a.first < b.first; }); } + void deduplicate() + { + const auto last = std::unique(vars.begin(), vars.end(), + [] (const Vars::value_type & a, const Vars::value_type & b) { return a.first == b.first; }); + vars.erase(last, vars.end()); + } + Vars::const_iterator find(const Symbol & name) const { Vars::value_type key(name, 0); diff --git a/src/nix/repl.cc b/src/nix/repl.cc index 63ccbfda3..39a5a31de 100644 --- a/src/nix/repl.cc +++ b/src/nix/repl.cc @@ -661,8 +661,16 @@ void NixRepl::reloadFiles() void NixRepl::addAttrsToScope(Value & attrs) { state->forceAttrs(attrs); - for (auto & i : *attrs.attrs) - addVarToScope(i.name, *i.value); + if (displ + attrs.attrs->size() >= envSize) + throw Error("environment full; cannot add more variables"); + + for (auto & i : *attrs.attrs) { + staticEnv.vars.emplace_back(i.name, displ); + env->values[displ++] = i.value; + varNames.insert((string) i.name); + } + staticEnv.sort(); + staticEnv.deduplicate(); notice("Added %1% variables.", attrs.attrs->size()); } -- cgit v1.2.3