[RFC/PATCH 2/2] fetch: Speed up fetch by using ref dictionary

[Julian Phillips <julian@quantumfyre.co.uk>]

When trying to get a list of remote tags to see if we need to fetch
any we were doing a linear search for the matching tag ref for the
tag^{} commit entries.  This proves to be incredibly slow for large
numbers of tags.

For a repository with 50000 tags (and just a single commit on a single
branch), a fetch that does nothing goes from ~ 1m50s to ~4.5s.

Signed-off-by: Julian Phillips <julian@quantumfyre.co.uk>
---
 builtin-fetch.c |   19 +++++++++----------
 1 files changed, 9 insertions(+), 10 deletions(-)

diff --git a/builtin-fetch.c b/builtin-fetch.c
index cb48c57..16cfee6 100644
--- a/builtin-fetch.c
+++ b/builtin-fetch.c
@@ -11,6 +11,7 @@
 #include "run-command.h"
 #include "parse-options.h"
 #include "sigchain.h"
+#include "ref-dict.h"
 
 static const char * const builtin_fetch_usage[] = {
 	"git fetch [options] [<repository> <refspec>...]",
@@ -513,12 +514,16 @@ static void find_non_local_tags(struct transport *transport,
 	char *ref_name;
 	int ref_name_len;
 	const unsigned char *ref_sha1;
-	const struct ref *tag_ref;
+	unsigned char tag_sha1[40];
 	struct ref *rm = NULL;
 	const struct ref *ref;
+	struct hash_table dict;
+	const struct ref *remote_refs = transport_get_remote_refs(transport);
+
+	ref_dict_create(&dict, remote_refs);
 
 	for_each_ref(add_existing, &existing_refs);
-	for (ref = transport_get_remote_refs(transport); ref; ref = ref->next) {
+	for (ref = remote_refs; ref; ref = ref->next) {
 		if (prefixcmp(ref->name, "refs/tags"))
 			continue;
 
@@ -528,14 +533,8 @@ static void find_non_local_tags(struct transport *transport,
 
 		if (!strcmp(ref_name + ref_name_len - 3, "^{}")) {
 			ref_name[ref_name_len - 3] = 0;
-			tag_ref = transport_get_remote_refs(transport);
-			while (tag_ref) {
-				if (!strcmp(tag_ref->name, ref_name)) {
-					ref_sha1 = tag_ref->old_sha1;
-					break;
-				}
-				tag_ref = tag_ref->next;
-			}
+			if (ref_dict_get(&dict, ref_name, tag_sha1))
+				ref_sha1 = tag_sha1;
 		}
 
 		if (!string_list_has_string(&existing_refs, ref_name) &&
-- 
1.6.4.2