[PATCH v2 12/12] remote: use strmap for apply_push_cas()

[Jon Simons <jon@jonsimons.org>]

Optimize apply_push_cas() by replacing a linear traversal of all
advertised remote refs with strmap lookups.

Before this change, applying N explicit --force-with-lease entries
to M remote advertised refs entails O(N * M) calls to refname_match()
in apply_one_cas().

After this change, we build a strmap of remote refs O(M), and use it
for O(N * rules) lookups of the lease entry refnames.

The refnames are resolved by issuing one strmap lookup for each
candidate rules pattern generated with expand_ref_prefix(), as
with earlier strmap conversions.

p5516 timings show the speedup:

  Test                        HEAD~1            HEAD
  --------------------------------------------------------------------
  5516.16: empty:lease:1      0.13(0.07+0.10)   0.14(0.08+0.11) +7.7%
  5516.19: empty:lease:10     0.16(0.10+0.10)   0.14(0.08+0.11) -12.5%
  5516.22: empty:lease:100    0.45(0.39+0.10)   0.16(0.09+0.11) -64.4%
  5516.25: mirror:lease:1     0.16(0.09+0.11)   0.17(0.10+0.12) +6.3%
  5516.28: mirror:lease:10    0.19(0.12+0.10)   0.17(0.10+0.11) -10.5%
  5516.31: mirror:lease:100   0.49(0.42+0.12)   0.19(0.11+0.12) -61.2%

Signed-off-by: Jon Simons <jon@jonsimons.org>
---
 remote.c | 23 +++++++++++++++--------
 1 file changed, 15 insertions(+), 8 deletions(-)

diff --git a/remote.c b/remote.c
index 8dd163038d..c16f1a2b82 100644
--- a/remote.c
+++ b/remote.c
@@ -2991,17 +2991,17 @@ static void apply_cas_tracking(struct push_cas_option *cas,
 		ref->check_reachable = cas->use_force_if_includes;
 }
 
-static void apply_one_cas(struct ref *remote_refs,
+static void apply_one_cas(struct strmap *ref_map,
 			  struct remote *remote,
 			  struct push_cas_option *cas,
 			  struct push_cas *entry)
 {
-	struct ref *ref;
+	struct strvec names = STRVEC_INIT;
 
-	for (ref = remote_refs; ref; ref = ref->next) {
-		if (ref->expect_old_sha1)
-			continue;
-		if (!refname_match(entry->refname, ref->name))
+	expand_ref_prefix(&names, entry->refname);
+	for (size_t i = 0; i < names.nr; i++) {
+		struct ref *ref = strmap_get(ref_map, names.v[i]);
+		if (!ref || ref->expect_old_sha1)
 			continue;
 		if (entry->use_tracking) {
 			apply_cas_tracking(cas, remote, ref);
@@ -3010,6 +3010,7 @@ static void apply_one_cas(struct ref *remote_refs,
 			oidcpy(&ref->old_oid_expect, &entry->expect);
 		}
 	}
+	strvec_clear(&names);
 }
 
 void apply_push_cas(struct push_cas_option *cas,
@@ -3019,8 +3020,14 @@ void apply_push_cas(struct push_cas_option *cas,
 	struct ref *ref;
 
 	/* Apply each explicit --<option>=<name>[:<value>] entry */
-	for (size_t i = 0; i < cas->nr; i++)
-		apply_one_cas(remote_refs, remote, cas, &cas->entry[i]);
+	if (cas->nr) {
+		struct strmap ref_map;
+
+		ref_map_init(&ref_map, remote_refs);
+		for (size_t i = 0; i < cas->nr; i++)
+			apply_one_cas(&ref_map, remote, cas, &cas->entry[i]);
+		strmap_clear(&ref_map, 0);
+	}
 
 	/* Are we using "--<option>" to cover all? */
 	if (cas->use_tracking_for_rest) {
-- 
2.55.0