[PATCH] remote.c: avoid O(n^2) behavior in match_push_refs by using string_list

[Brandon Casey <bcasey@nvidia.com>]

From: Brandon Casey <drafnel@gmail.com>

When pushing, each ref in the local repository must be paired with a
ref advertised by the remote server.  Currently, this is performed by
first applying the refspec to the local ref to transform the local ref
into the name of the remote ref, and then performing a linear search
through the list of remote refs to see if the remote ref was advertised
by the remote system.

This has O(n) complexity and makes match_push_refs() be an O(n^2)
operation.  If there are many refs 100,000+, then this ref matching
can take a significant amount of time.  Let's populate a string_list
with the remote ref names to allow searching in O(log n) time and
reduce the complexity of match_push_refs() to O(n log n).

Dry-run push of a repository with 121913 refs:

        before     after
real    1m40.582s  0m0.804s
user    1m39.914s  0m0.515s
sys     0m0.125s   0m0.106s

Signed-off-by: Brandon Casey <drafnel@gmail.com>
---
 remote.c | 26 ++++++++++++++++++++++++--
 1 file changed, 24 insertions(+), 2 deletions(-)

diff --git a/remote.c b/remote.c
index 6f57830..b416b8e 100644
--- a/remote.c
+++ b/remote.c
@@ -1302,6 +1302,15 @@ static void add_missing_tags(struct ref *src, struct ref **dst, struct ref ***ds
 	free(sent_tips.tip);
 }
 
+static void prepare_searchable_ref_list(struct ref *ref, struct string_list *ref_list)
+{
+	for ( ; ref; ref = ref->next)
+		string_list_append_nodup(ref_list, ref->name)->util = ref;
+
+	sort_string_list(ref_list);
+}
+
+
 /*
  * Given the set of refs the local repository has, the set of refs the
  * remote repository has, and the refspec used for push, determine
@@ -1320,6 +1329,7 @@ int match_push_refs(struct ref *src, struct ref **dst,
 	int errs;
 	static const char *default_refspec[] = { ":", NULL };
 	struct ref *ref, **dst_tail = tail_ref(dst);
+	struct string_list ref_list = STRING_LIST_INIT_NODUP;
 
 	if (!nr_refspec) {
 		nr_refspec = 1;
@@ -1328,8 +1338,11 @@ int match_push_refs(struct ref *src, struct ref **dst,
 	rs = parse_push_refspec(nr_refspec, (const char **) refspec);
 	errs = match_explicit_refs(src, *dst, &dst_tail, rs, nr_refspec);
 
+	prepare_searchable_ref_list(*dst, &ref_list);
+
 	/* pick the remainder */
 	for (ref = src; ref; ref = ref->next) {
+		struct string_list_item *dst_item;
 		struct ref *dst_peer;
 		const struct refspec *pat = NULL;
 		char *dst_name;
@@ -1338,7 +1351,8 @@ int match_push_refs(struct ref *src, struct ref **dst,
 		if (!dst_name)
 			continue;
 
-		dst_peer = find_ref_by_name(*dst, dst_name);
+		dst_item = string_list_lookup(&ref_list, dst_name);
+		dst_peer = dst_item ? dst_item->util : NULL;
 		if (dst_peer) {
 			if (dst_peer->peer_ref)
 				/* We're already sending something to this ref. */
@@ -1355,6 +1369,8 @@ int match_push_refs(struct ref *src, struct ref **dst,
 			/* Create a new one and link it */
 			dst_peer = make_linked_ref(dst_name, &dst_tail);
 			hashcpy(dst_peer->new_sha1, ref->new_sha1);
+			string_list_insert(&ref_list, dst_peer->name)->util =
+				dst_peer;
 		}
 		dst_peer->peer_ref = copy_ref(ref);
 		dst_peer->force = pat->force;
@@ -1362,6 +1378,8 @@ int match_push_refs(struct ref *src, struct ref **dst,
 		free(dst_name);
 	}
 
+	string_list_clear(&ref_list, 0);
+
 	if (flags & MATCH_REFS_FOLLOW_TAGS)
 		add_missing_tags(src, dst, &dst_tail);
 
@@ -1376,11 +1394,15 @@ int match_push_refs(struct ref *src, struct ref **dst,
 
 			src_name = get_ref_match(rs, nr_refspec, ref, send_mirror, FROM_DST, NULL);
 			if (src_name) {
-				if (!find_ref_by_name(src, src_name))
+				if (!ref_list.nr)
+					prepare_searchable_ref_list(src,
+						&ref_list);
+				if (!string_list_has_string(&ref_list, src_name))
 					ref->peer_ref = alloc_delete_ref();
 				free(src_name);
 			}
 		}
+		string_list_clear(&ref_list, 0);
 	}
 	if (errs)
 		return -1;
-- 
1.8.3.1.440.gc2bf105