From: Brandon Casey <drafnel@xxxxxxxxx>
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@xxxxxxxxx>
---
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
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html