Skip find() inside target_set::insert*() if target is unlikely to be there

5 files changed, 39 insertions, 14 deletions

diff --git a/libbuild2/algorithm.cxx b/libbuild2/algorithm.cxx
index 287ab2e..7116b8b 100644
--- a/libbuild2/algorithm.cxx
+++ b/libbuild2/algorithm.cxx
@@ -341,7 +341,8 @@ namespace build2
                                      move (n),
                                      nullopt /* ext     */,
                                      target_decl::implied,
-                                     trace));
+                                     trace,
+                                     true /* skip_find */));
 
       if (r.second) // Inserted.
       {
diff --git a/libbuild2/cc/compile-rule.cxx b/libbuild2/cc/compile-rule.cxx
index 002c889..2faa711 100644
--- a/libbuild2/cc/compile-rule.cxx
+++ b/libbuild2/cc/compile-rule.cxx
@@ -6056,7 +6056,8 @@ namespace build2
                 move (mf),
                 nullopt,     // Use default extension.
                 target_decl::implied,
-                trace));
+                trace,
+                true /* skip_find */));
       file& bt (p.first.as<file> ());
 
       // Note that this is racy and someone might have created this target
@@ -6294,7 +6295,8 @@ namespace build2
                 move (mf),
                 nullopt,     // Use default extension.
                 target_decl::implied,
-                trace));
+                trace,
+                true /* skip_find */));
       file& bt (p.first.as<file> ());
 
       // Note that this is racy and someone might have created this target
diff --git a/libbuild2/search.cxx b/libbuild2/search.cxx
index d3638d7..19385b0 100644
--- a/libbuild2/search.cxx
+++ b/libbuild2/search.cxx
@@ -187,13 +187,16 @@ namespace build2
 
     // Find or insert. Note that we are using our updated extension.
     //
+    // More often insert than find, so skip find in insert().
+    //
     auto r (ctx.targets.insert (*tk.type,
                                 move (d),
                                 move (out),
                                 *tk.name,
                                 ext,
                                 target_decl::prereq_file,
-                                trace));
+                                trace,
+                                true /* skip_find */));
 
     const file& t (r.first.as<file> ());
 
@@ -230,6 +233,8 @@ namespace build2
 
     // Find or insert.
     //
+    // More often insert than find, so skip find in insert().
+    //
     // @@ OUT: same story as in search_existing_target() re out.
     //
     auto r (ctx.targets.insert (*tk.type,
@@ -238,7 +243,8 @@ namespace build2
                                 *tk.name,
                                 tk.ext,
                                 target_decl::prereq_new,
-                                trace));
+                                trace,
+                                true /* skip_find */));
 
     const target& t (r.first);
     l5 ([&]{trace << (r.second ? "new" : "existing") << " target " << t
@@ -271,6 +277,8 @@ namespace build2
 
     // Find or insert.
     //
+    // More often insert than find, so skip find in insert_locked().
+    //
     // @@ OUT: same story as in search_existing_target() re out.
     //
     auto r (ctx.targets.insert_locked (*tk.type,
@@ -279,7 +287,8 @@ namespace build2
                                        *tk.name,
                                        tk.ext,
                                        target_decl::prereq_new,
-                                       trace));
+                                       trace,
+                                       true /* skip_find */));
     l5 ([&]
         {
           diag_record dr (trace);
diff --git a/libbuild2/target.cxx b/libbuild2/target.cxx
index 7eaa3a6..4f11b54 100644
--- a/libbuild2/target.cxx
+++ b/libbuild2/target.cxx
@@ -698,10 +698,11 @@ namespace build2
                  optional<string> ext,
                  target_decl decl,
                  tracer& trace,
+                 bool skip_find,
                  bool need_lock)
   {
     target_key tk {&tt, &dir, &out, &name, move (ext)};
-    target* t (const_cast<target*> (find (tk, trace)));
+    target* t (skip_find ? nullptr : const_cast<target*> (find (tk, trace)));
 
     if (t == nullptr)
     {
diff --git a/libbuild2/target.hxx b/libbuild2/target.hxx
index f652347..1562746 100644
--- a/libbuild2/target.hxx
+++ b/libbuild2/target.hxx
@@ -1541,6 +1541,11 @@ namespace build2
     // is normally quite a bit of contention around this map so make sure to
     // not hold the lock longer than absolutely necessary.
     //
+    // If skip_find is true, then don't first try to find an existing target
+    // with a shared lock, instead going directly for the unique lock and
+    // insert. It's a good idea to pass true as this argument if you know the
+    // target is unlikely to be there.
+    //
     // If need_lock is false, then release the lock (the target insertion is
     // indicated by the presence of the associated mutex).
     //
@@ -1552,6 +1557,7 @@ namespace build2
                    optional<string> ext,
                    target_decl,
                    tracer&,
+                   bool skip_find = false,
                    bool need_lock = true);
 
     // As above but instead of the lock return an indication of whether the
@@ -1564,7 +1570,8 @@ namespace build2
             string name,
             optional<string> ext,
             target_decl decl,
-            tracer& t)
+            tracer& t,
+            bool skip_find = false)
     {
       auto p (insert_locked (tt,
                              move (dir),
@@ -1573,6 +1580,7 @@ namespace build2
                              move (ext),
                              decl,
                              t,
+                             skip_find,
                              false));
 
       return pair<target&, bool> (p.first, p.second.mutex () != nullptr);
@@ -1587,7 +1595,8 @@ namespace build2
             dir_path out,
             string name,
             optional<string> ext,
-            tracer& t)
+            tracer& t,
+            bool skip_find = false)
     {
       return insert (tt,
                      move (dir),
@@ -1595,7 +1604,8 @@ namespace build2
                      move (name),
                      move (ext),
                      target_decl::implied,
-                     t).first.template as<T> ();
+                     t,
+                     skip_find).first.template as<T> ();
     }
 
     template <typename T>
@@ -1604,9 +1614,10 @@ namespace build2
             const dir_path& out,
             const string& name,
             const optional<string>& ext,
-            tracer& t)
+            tracer& t,
+            bool skip_find = false)
     {
-      return insert<T> (T::static_type, dir, out, name, ext, t);
+      return insert<T> (T::static_type, dir, out, name, ext, t, skip_find);
     }
 
     template <typename T>
@@ -1614,9 +1625,10 @@ namespace build2
     insert (const dir_path& dir,
             const dir_path& out,
             const string& name,
-            tracer& t)
+            tracer& t,
+            bool skip_find = false)
     {
-      return insert<T> (dir, out, name, nullopt, t);
+      return insert<T> (dir, out, name, nullopt, t, skip_find);
     }
 
     // Note: not MT-safe so can only be used during serial execution.