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

[Jon Simons <jon@jonsimons.org>]

Optimize match_explicit_refs() by replacing two linear refs traversals
with strmap lookups.

Before this change, matching R explicit refspecs against N local refs
and M remote refs in match_explicit() entails O(R * N) and O(R * M)
calls to refname_match() for sources and destinations respectively.

After this change, we build a strmap for local refs O(N), a strmap for
remote refs O(M), and use them for O(R * rules) lookups of the refspecs.

Refspecs are resolved using count_refspec_match_in_map() introduced
earlier in the series, which issues one strmap lookup for each candidate
rules pattern generated with expand_ref_prefix().

The match_explicit_lhs_map() function introduced in a previous commit
has now been recombined into match_explicit_lhs(): all call sites are
now using the new strmap variation.

Timings show benefit where one or both of the client and remote have
many refs, and multiple refspecs are specified:

  Test                           HEAD~1            HEAD
  -----------------------------------------------------------------------
  5516.3: empty:refspecs:1       0.13(0.07+0.10)   0.14(0.07+0.10) +7.7%
  5516.5: empty:refspecs:10      0.17(0.10+0.11)   0.14(0.07+0.11) -17.6%
  5516.7: empty:refspecs:100     0.47(0.41+0.10)   0.15(0.08+0.10) -68.1%
  5516.9: mirror:refspecs:1      0.17(0.10+0.11)   0.17(0.10+0.11) +0.0%
  5516.11: mirror:refspecs:10    0.23(0.16+0.11)   0.17(0.10+0.11) -26.1%
  5516.13: mirror:refspecs:100   0.87(0.80+0.11)   0.18(0.11+0.11) -79.3%

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

diff --git a/remote.c b/remote.c
index f4cf63b756..8074750601 100644
--- a/remote.c
+++ b/remote.c
@@ -1214,12 +1214,12 @@ static char *guess_ref(const char *name, struct ref *peer)
 	return strbuf_detach(&buf, NULL);
 }
 
-static int match_explicit_lhs_count(const int count,
-				    struct refspec_item *rs,
-				    struct ref **match,
-				    int *allocated_match)
+static int match_explicit_lhs(struct strmap *src,
+			      struct refspec_item *rs,
+			      struct ref **match,
+			      int *allocated_match)
 {
-	switch (count) {
+	switch (count_refspec_match_in_map(rs->src, src, match)) {
 	case 1:
 		if (allocated_match)
 			*allocated_match = 0;
@@ -1239,24 +1239,6 @@ static int match_explicit_lhs_count(const int count,
 	}
 }
 
-static int match_explicit_lhs(struct ref *src,
-			      struct refspec_item *rs,
-			      struct ref **match,
-			      int *allocated_match)
-{
-	return match_explicit_lhs_count(count_refspec_match(rs->src, src, match),
-					rs, match, allocated_match);
-}
-
-static int match_explicit_lhs_map(struct strmap *src,
-				  struct refspec_item *rs,
-				  struct ref **match,
-				  int *allocated_match)
-{
-	return match_explicit_lhs_count(count_refspec_match_in_map(rs->src, src, match),
-					rs, match, allocated_match);
-}
-
 static void show_push_unqualified_ref_name_error(const char *dst_value,
 						 const char *matched_src_name)
 {
@@ -1333,7 +1315,7 @@ static bool any_refspec_item_is_explicit(const struct refspec *rs)
 	return false;
 }
 
-static int match_explicit(struct ref *src, struct ref *dst,
+static int match_explicit(struct strmap *src, struct strmap *dst,
 			  struct ref ***dst_tail,
 			  struct refspec_item *rs)
 {
@@ -1367,7 +1349,7 @@ static int match_explicit(struct ref *src, struct ref *dst,
 			    matched_src->name);
 	}
 
-	switch (count_refspec_match(dst_value, dst, &matched_dst)) {
+	switch (count_refspec_match_in_map(dst_value, dst, &matched_dst)) {
 	case 1:
 		break;
 	case 0:
@@ -1383,6 +1365,9 @@ static int match_explicit(struct ref *src, struct ref *dst,
 			show_push_unqualified_ref_name_error(dst_value,
 							     matched_src->name);
 		}
+		/* later refspecs must see the ref we just added to dst */
+		if (matched_dst)
+			strmap_put(dst, matched_dst->name, matched_dst);
 		break;
 	default:
 		matched_dst = NULL;
@@ -1416,12 +1401,23 @@ static int match_explicit(struct ref *src, struct ref *dst,
 	return ret;
 }
 
-static int match_explicit_refs(struct ref *src, struct ref **dst,
+static int match_explicit_refs(struct ref *src, struct ref *dst,
 			       struct ref ***dst_tail, struct refspec *rs)
 {
 	int i, errs;
+	struct strmap src_map, dst_map;
+
+	if (!any_refspec_item_is_explicit(rs))
+		return 0;
+
+	ref_map_init(&src_map, src);
+	ref_map_init(&dst_map, dst);
 	for (i = errs = 0; i < rs->nr; i++)
-		errs += match_explicit(src, *dst, dst_tail, &rs->items[i]);
+		errs += match_explicit(&src_map, &dst_map, dst_tail,
+				       &rs->items[i]);
+	strmap_clear(&dst_map, 0);
+	strmap_clear(&src_map, 0);
+
 	return errs;
 }
 
@@ -1644,7 +1640,7 @@ int check_push_refs(struct ref *src, struct refspec *rs)
 		if (!refspec_item_is_explicit(item))
 			continue;
 
-		ret |= match_explicit_lhs_map(&src_map, item, NULL, NULL);
+		ret |= match_explicit_lhs(&src_map, item, NULL, NULL);
 	}
 	strmap_clear(&src_map, 0);
 
@@ -1673,7 +1669,7 @@ int match_push_refs(struct ref *src, struct ref **dst,
 	if (!rs->nr)
 		refspec_append(rs, ":");
 
-	errs = match_explicit_refs(src, dst, &dst_tail, rs);
+	errs = match_explicit_refs(src, *dst, &dst_tail, rs);
 
 	/* pick the remainder */
 	for (ref = src; ref; ref = ref->next) {
-- 
2.55.0