Re: [RFC/PATCH 0/2] Speed up fetch with large number of tags

From: Junio C Hamano <gitster@pobox.com>
Date: Sep 16, 2009, 09:44 UTC
Message-ID: <7vbplb2pi7.fsf@alter.siamese.dyndns.org>
In-Reply-To: <20090916074737.58044.42776.julian@quantumfyre.co.uk>

Julian Phillips <julian@quantumfyre.co.uk> writes:

Show 12 quoted lines

> I have a repository at $dayjob where fetch was taking ~30s to tell me
> that there were no updates.
>
> It turns out that I appear to have added a nasty linear search of all
> remote refs for every commit (i.e. tag^{}) tag ref way back in the
> original C implementation of fetch.  This doesn't scale well to large
> numbers of refs, so this replaces it with a hash table based lookup
> instead, which brings the time down to a few seconds even for very large
> ref counts.
>
> I haven't tested it with non-native transports, but there is no reason
> to believe that the code should be transport specific.

Very interesting.

A few questions (not criticisms).

 * 1m50s to 4.5s is quite impressive, even if it is only in a repository
   with unusual refs-vs-commits ratio, but I personally think 10 refs per
   every commit is already on the borderline of being insane, and the
   normal ratio would be more like 1 refs per every 10-20 commits.

   What are possible downsides with the new code in repositories with more
   reasonable refs-vs-commits ratio?  A hash table (with a sensible hash
   function) would almost always outperform linear search in an randomly
   ordered collection, so my gut tells me that there won't be performance
   downsides, but are there other potential issues we should worry about?

 * In an insanely large refs-vs-commits case, perhaps not 50000:1 but more
   like 100:1, but with a history with far more than one commit, what is
   the memory consumption?  Judging from a cursory view, I think the way
   ref-dict re-uses struct ref might be quite suboptimal, as you are using
   only next (for hash-bucket link), old_sha1[] and its name field, and
   also your ref_dict_add() calls alloc_ref() which calls one calloc() per
   requested ref, instead of attempting any bulk allocation.

 * The outer loop is walking the list of refs from a transport, and the
   inner loop is walking a copy of the same list of refs from the same
   transport, looking for each refs/tags/X^{} what record, if any, existed
   for refs/tags/X.

   Would it make sense to further specialize your optimization?  For
   example, something like...

        /* Your hash records this structure */
        struct tag_ref_record {
                const char *name;
                struct ref *self;
                struct ref *peeled;
        };

        static void add_to_tail(struct ref ***tail,
                                struct string_list *existing_refs,
                                struct string_list *new_refs,
                                const struct ref *ref,
                                const unsigned char sha1[]) {
                ... the "appending to *tail" thing as a helper function ...
        }

        for (ref in all refs from transport) {
                if (ref is of form "refs/tags/X^{}")
                        look up tag_ref_record for "refs/tags/X" and store
                        ref in its peeled member;
                else if (ref is of form "refs/tags/X")
                        look up tag_ref_record for "refs/tags/X" and store
                        ref in its self member;
        }

        for (trr in all tag_ref_record database) {
                add_to_tail(tail, &existing_refs, &new_refs,
                            trr->self, self->old_sha1);
                add_to_tail(tail, &existing_refs, &new_refs,
                            trr->peeled, self->old_sha1);
        }

 * It is tempting to use a hash table when you have to deal with an
   unordered collection, but in this case, wouldn't the refs obtained from
   the transport (it's essentially a ls-remote output, isn't it?) be
   sorted?  Can't you take advantage of that fact to optimize the loop,
   without adding a specialized hash table implementation?

   We find refs/tags/v0.99 immediately followed by refs/tags/v0.99^{} in
   the ls-remote output.  And the inefficient loop is about finding
   refs/tags/v0.99 when we see refs/tags/v0.99^{}, so if we remember the
   tag ref we saw in the previous round, we can check with that first to
   make sure our "sorted" assumption holds true, and optimize the loop out
   that way, no?

diff --git a/builtin-fetch.c b/builtin-fetch.c
index cb48c57..3f12e28 100644
--- a/builtin-fetch.c
+++ b/builtin-fetch.c
@@ -516,6 +516,7 @@ static void find_non_local_tags(struct transport *transport,
 	const struct ref *tag_ref;
 	struct ref *rm = NULL;
 	const struct ref *ref;
+	const struct ref *last_tag_seen = NULL;
 
 	for_each_ref(add_existing, &existing_refs);
 	for (ref = transport_get_remote_refs(transport); ref; ref = ref->next) {
@@ -528,6 +529,11 @@ static void find_non_local_tags(struct transport *transport,
 
 		if (!strcmp(ref_name + ref_name_len - 3, "^{}")) {
 			ref_name[ref_name_len - 3] = 0;
+			if (last_tag_seen &&
+			    !strcmp(last_tag_seen->name, ref_name)) {
+				ref_sha1 = last_tag_seen->old_sha1;
+				goto quick;
+			}
 			tag_ref = transport_get_remote_refs(transport);
 			while (tag_ref) {
 				if (!strcmp(tag_ref->name, ref_name)) {
@@ -536,8 +542,11 @@ static void find_non_local_tags(struct transport *transport,
 				}
 				tag_ref = tag_ref->next;
 			}
+		} else {
+			last_tag_seen = ref;
 		}
 
+	quick:
 		if (!string_list_has_string(&existing_refs, ref_name) &&
 		    !string_list_has_string(&new_refs, ref_name) &&
 		    (has_sha1_file(ref->old_sha1) ||