Reserve targets, variables to avoid rehashing

7 files changed, 92 insertions, 0 deletions

diff --git a/build2/b.cxx b/build2/b.cxx
index f91eff5..68c77c8 100644
--- a/build2/b.cxx
+++ b/build2/b.cxx
@@ -468,6 +468,24 @@ main (int argc, char* argv[])
     if (bspec.empty ())
       bspec.push_back (metaopspec ()); // Default meta-operation.
 
+    // The reserve values were picked experimentally. They allow building a
+    // sample application that depends on Qt and Boost without causing a
+    // rehash.
+    //
+    // Note: omit reserving anything for the info meta-operation since it
+    // won't be loading the buildfiles and needs to be as fast as possible.
+    //
+    if (bspec.size () == 1 &&
+        bspec.front ().size () == 1 &&
+        (bspec.front ().name == "info" ||
+         (bspec.front ().name.empty () &&
+          bspec.front ().front ().name == "info")))
+      ;
+    else
+      pctx->reserve (context::reserves {
+          30000 /* targets */,
+          1100  /* variables */});
+
     const path& buildfile (ops.buildfile_specified ()
                            ? ops.buildfile ()
                            : empty_path);
diff --git a/libbuild2/context.cxx b/libbuild2/context.cxx
index 1da6fd3..967577f 100644
--- a/libbuild2/context.cxx
+++ b/libbuild2/context.cxx
@@ -60,6 +60,18 @@ namespace build2
           var_patterns (&c /* shared */, &var_pool) {}
   };
 
+  void context::
+  reserve (reserves res)
+  {
+    assert (phase == run_phase::load);
+
+    if (res.targets != 0)
+      data_->targets.map_.reserve (res.targets);
+
+    if (res.variables != 0)
+      data_->var_pool.map_.reserve (res.variables);
+  }
+
   context::
   context (scheduler& s,
            global_mutexes& ms,
@@ -70,6 +82,7 @@ namespace build2
            bool ndb,
            bool kg,
            const strings& cmd_vars,
+           reserves res,
            optional<context*> mc,
            const loaded_modules_lock* ml)
       : data_ (new data (*this)),
@@ -102,6 +115,8 @@ namespace build2
 
     l6 ([&]{trace << "initializing build state";});
 
+    reserve (res);
+
     scope_map& sm (data_->scopes);
     variable_pool& vp (data_->var_pool);
     variable_patterns& vpats (data_->var_patterns);
diff --git a/libbuild2/context.hxx b/libbuild2/context.hxx
index b71a068..27c3cc0 100644
--- a/libbuild2/context.hxx
+++ b/libbuild2/context.hxx
@@ -652,6 +652,15 @@ namespace build2
     // Note: see also the trace_* data members that, if needed, must be set
     // separately, after construction.
     //
+    struct reserves
+    {
+      size_t targets;
+      size_t variables;
+
+      reserves (): targets (0), variables (0) {}
+      reserves (size_t t, size_t v): targets (t), variables (v) {}
+    };
+
     explicit
     context (scheduler&,
              global_mutexes&,
@@ -662,9 +671,17 @@ namespace build2
              bool no_diag_buffer = false,
              bool keep_going = true,
              const strings& cmd_vars = {},
+             reserves = {0, 160},
              optional<context*> module_context = nullptr,
              const loaded_modules_lock* inherited_mudules_lock = nullptr);
 
+    // Reserve elements in containers to avoid re-allocation/re-hashing. Zero
+    // values are ignored (that is, the corresponding container reserve()
+    // function is not called). Can only be called in the load phase.
+    //
+    void
+    reserve (reserves);
+
     // Enter project-wide (as opposed to global) variable overrides.
     //
     void
diff --git a/libbuild2/module.cxx b/libbuild2/module.cxx
index 96901ff..62145ca 100644
--- a/libbuild2/module.cxx
+++ b/libbuild2/module.cxx
@@ -77,6 +77,9 @@ namespace build2
     // same global mutexes. Also disable nested module context for good
     // measure.
     //
+    // The reserve values were picked experimentally by building libbuild2 and
+    // adding a reasonable margin for future growth.
+    //
     ctx.module_context_storage->reset (
       new context (ctx.sched,
                    ctx.mutexes,
@@ -87,6 +90,10 @@ namespace build2
                    ctx.no_diag_buffer,
                    ctx.keep_going,
                    ctx.global_var_overrides, /* cmd_vars */
+                   context::reserves {
+                     2500,                    /* targets */
+                      900                     /* variables */
+                   },
                    nullopt));                /* module_context */
 
     // We use the same context for building any nested modules that might be
diff --git a/libbuild2/target.cxx b/libbuild2/target.cxx
index 9f26eee..76d45c7 100644
--- a/libbuild2/target.cxx
+++ b/libbuild2/target.cxx
@@ -760,6 +760,18 @@ namespace build2
 
       if (p.second)
       {
+#if 0
+        {
+          size_t n (map_.bucket_count ());
+          if (n > buckets_)
+          {
+            text << "target_set buckets: " << buckets_ << " -> " << n
+                 << " (" << map_.size () << ")";
+            buckets_ = n;
+          }
+        }
+#endif
+
         t->ext_ = &i->first.ext;
         t->decl = decl;
         t->state.inner.target_ = t;
diff --git a/libbuild2/target.hxx b/libbuild2/target.hxx
index 684fce9..26c7208 100644
--- a/libbuild2/target.hxx
+++ b/libbuild2/target.hxx
@@ -1879,6 +1879,10 @@ namespace build2
 
     mutable shared_mutex mutex_;
     map_type map_;
+
+#if 0
+    size_t buckets_ = 0;
+#endif
   };
 
   // Modification time-based target.
diff --git a/libbuild2/variable.hxx b/libbuild2/variable.hxx
index 3b444e6..400aaf1 100644
--- a/libbuild2/variable.hxx
+++ b/libbuild2/variable.hxx
@@ -16,6 +16,7 @@
 
 #include <libbuild2/context.hxx>
 #include <libbuild2/target-type.hxx>
+#include <libbuild2/diagnostics.hxx>
 
 #include <libbuild2/export.hxx>
 
@@ -1470,7 +1471,21 @@ namespace build2
       auto r (map_.insert (map::value_type (&n, move (var))));
 
       if (r.second)
+      {
+#if 0
+        if (shared_ && outer_ == nullptr) // Global pool in context.
+        {
+          size_t n (map_.bucket_count ());
+          if (n > buckets_)
+          {
+            text << "variable_pool buckets: " << buckets_ << " -> " << n
+                 << " (" << map_.size () << ")";
+            buckets_ = n;
+          }
+        }
+#endif
         r.first->first.p = &r.first->second.name;
+      }
 
       return r;
     }
@@ -1482,6 +1497,10 @@ namespace build2
     variable_pool* outer_;
     const variable_patterns* patterns_;
     map map_;
+
+#if 0
+    size_t buckets_ = 0;
+#endif
   };
 
   // Variable patterns.