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

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

[Julian Phillips]

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.

Julian Phillips (2):
  ref-dict: Add a set of functions for working with a ref dictionary
  fetch: Speed up fetch by using ref dictionary

 Makefile        |    1 +
 builtin-fetch.c |   19 ++++++-------
 ref-dict.c      |   76 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 ref-dict.h      |   13 +++++++++
 4 files changed, 99 insertions(+), 10 deletions(-)
 create mode 100644 ref-dict.c
 create mode 100644 ref-dict.h

[RFC/PATCH 1/2] ref-dict: Add a set of functions for working with a ref dictionary

[Julian Phillips]

These are a set of helper functions that use the generic hash table
functions to provide a quick and easy mapping from ref name to sha1.

Signed-off-by: Julian Phillips <julian@quantumfyre.co.uk>
---
 Makefile   |    1 +
 ref-dict.c |   76 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 ref-dict.h |   13 ++++++++++
 3 files changed, 90 insertions(+), 0 deletions(-)
 create mode 100644 ref-dict.c
 create mode 100644 ref-dict.h

diff --git a/Makefile b/Makefile
index d4958b8..815e4c9 100644
--- a/Makefile
+++ b/Makefile
@@ -531,6 +531,7 @@ LIB_OBJS += reachable.o
 LIB_OBJS += read-cache.o
 LIB_OBJS += reflog-walk.o
 LIB_OBJS += refs.o
+LIB_OBJS += ref-dict.o
 LIB_OBJS += remote.o
 LIB_OBJS += replace_object.o
 LIB_OBJS += rerere.o
diff --git a/ref-dict.c b/ref-dict.c
new file mode 100644
index 0000000..b9cab4b
--- /dev/null
+++ b/ref-dict.c
@@ -0,0 +1,76 @@
+/*
+ * ref-dict.c
+ *
+ * A Hash-based dictionary for storing name-sha1 data for refs.
+ *
+ * Copyright (C) 2009 Julian Phillips
+ */
+
+#include "cache.h"
+#include "hash.h"
+#include "remote.h"
+#include "ref-dict.h"
+
+/* hash_name based on the function of the same name in name-hash.c */
+static unsigned int hash_name(const char *name)
+{
+	unsigned int hash = 0x123;
+	int namelen = strlen(name);
+
+	do {
+		unsigned char c = *name++;
+		hash = hash*101 + c;
+	} while (--namelen);
+	return hash;
+}
+
+/*
+ * A convienience function for creating a ref_dict from a ref_list.
+ */
+void ref_dict_create(struct hash_table *dict, const struct ref *ref_list)
+{
+	struct ref *ref;
+
+	init_hash(dict);
+
+	for (ref = (struct ref *)ref_list; ref; ref = ref->next) {
+		ref_dict_add(dict, ref->name, ref->old_sha1);
+	}
+}
+
+/*
+ * Add an entry to the ref_dict, recording that name maps to sha1.
+ */
+void ref_dict_add(struct hash_table *dict, const char *name,
+		const unsigned char *sha1)
+{
+	struct ref **ref;
+	struct ref *new_ref = alloc_ref(name);
+
+	hashcpy(new_ref->old_sha1, sha1);
+	
+	ref = (struct ref **)insert_hash(hash_name(name), new_ref, dict);
+	if (ref) {
+		new_ref->next = *ref;
+		*ref = new_ref;
+	}
+}
+
+/*
+ * Find the sha1 for the given name.  Returns 1 if found and copies the sha1
+ * into the space pointed to by sha1, returns 0 otherwise and sha1 is untouched.
+ */
+int ref_dict_get(const struct hash_table *dict, const char *name,
+		unsigned char *sha1)
+{
+	struct ref *ref = lookup_hash(hash_name(name), dict);
+
+	for (; ref; ref = ref->next) {
+		if (!strcmp(name, ref->name)) {
+			hashcpy(sha1, ref->old_sha1);
+			return 1;
+		}
+	}
+
+	return 0;
+}
diff --git a/ref-dict.h b/ref-dict.h
new file mode 100644
index 0000000..ca1e9a7
--- /dev/null
+++ b/ref-dict.h
@@ -0,0 +1,13 @@
+#ifndef REF_DICT_H
+#define REF_DICT_H
+
+#include "cache.h"
+#include "hash.h"
+
+void ref_dict_create(struct hash_table *dict, const struct ref *ref_list);
+void ref_dict_add(struct hash_table *dict, const char *name,
+		const unsigned char *sha1);
+int ref_dict_get(const struct hash_table *dict, const char *name,
+		unsigned char *sha1);
+
+#endif /* REF_DICT_H */
-- 
1.6.4.2

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

[Julian Phillips]

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

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

[Junio C Hamano]

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

> 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) ||

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

[Julian Phillips]

On Wed, 16 Sep 2009, Junio C Hamano wrote:

> Julian Phillips <julian@quantumfyre.co.uk> writes:
>
>> 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.

I noticed the problem with a real repository at $dayjob, and did enough 
anaylsis to identiy the problem.  I deliberately created a repository that 
should emphasise the problem so that it was easy to get a handle on.

Having applied the ref-dict patches fetch on my $dayjob repo has gone from 
~30s to ~4.5s, which may not be as impressive - but is much easier to live 
with.

>   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?

I guess that main thing would be the extra memory usage.

> * 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.

Yeah, I just reused struct for speed and convience of developing, to 
veryify that ref-dict would give me the speed I wanted.  A final patch 
would want a more optimised version.  Except that I've thrown the whole 
hash table thing away anyway.

> * 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...

I actually arrived at somthing similar to this myself, after realising 
that I could use string_list as a basis.

> * 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?

I wasn't sure if we could rely on the refs list being sorted.  But I've 
got a new version that uses an extra string_list instead that is actually 
slightly faster.  I'll post that shortly.

>   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?

-- 
Julian

  ---
Bilbo's First Law:
 	You cannot count friends that are all packed up in barrels.

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

[Shawn O. Pearce]

Julian Phillips <julian@quantumfyre.co.uk> wrote:
> On Wed, 16 Sep 2009, Junio C Hamano wrote:
>> * 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?
>
> I wasn't sure if we could rely on the refs list being sorted.  But I've  
> got a new version that uses an extra string_list instead that is actually 
> slightly faster.  I'll post that shortly.

JGit depends on the fact that the refs list is sorted by the remote
peer, and that foo^{} immediately follows foo.  I don't think this
has ever been documented, but all sane implementations[1] follow
this convention and it may be something we could simply codify as
part of the protocol standard.

[1] Sane implementations are defined to be what I consider to be
    the two stable implementations in deployed use, git.git and JGit.

-- 
Shawn.

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

[Shawn O. Pearce]

Junio C Hamano <gitster@pobox.com> wrote:
> 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.

Under Gerrit Code Review it is normaly to have 2-5 refs per commit,
every iteration of a patch is held as a commit and anchored by a
unique ref.

So we're borderline insane.  :-)
 
-- 
Shawn.

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

[Junio C Hamano]

"Shawn O. Pearce" <spearce@spearce.org> writes:

> JGit depends on the fact that the refs list is sorted by the remote
> peer, and that foo^{} immediately follows foo.  I don't think this
> has ever been documented, but all sane implementations[1] follow
> this convention and it may be something we could simply codify as
> part of the protocol standard.
>
> [1] Sane implementations are defined to be what I consider to be
>     the two stable implementations in deployed use, git.git and JGit.

There is no strong reason for ordering of refs between themselves
(i.e. refs/heads/master comes before refs/heads/next) other than the fact
that we sort and then walk due to packed-refs reasons.

But emitting tag X and then its peeled representation X^{} immediately
after it is quite fundamental in the way how anybody sane would implement
ls-remote.  There is no reason to violate the established order other than
"I could do so", and in order not to show X and X^{} next to each other,
you would need _more_ processing.

So I would say it is very safe to assume this.

Also, you might not have noticed, but my illustration patch was merely
using it as a hint to optimize, and if the last ref we saw was not X when
it is turn to handle X^{}, it simply falled back to the original logic,
iow, the patch never compromised the correctness.

[RFC/PATCH v2] fetch: Speed up fetch by rewriting find_non_local_tags

[Julian Phillips]

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.  Rewrite the function so that we can do lookup in
string_lists instead.

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.2s.

Signed-off-by: Julian Phillips <julian@quantumfyre.co.uk>
---

Not only does this not require a custom hash table, it is also slightly
faster than the last version (~4.2s vs ~4.5s).

If nothing else, having rewritten it completely, at least I now
understand what the old find_non_local_tags function was actually doing
... ;)

 builtin-fetch.c |   85 ++++++++++++++++++++++++++++++++++++++-----------------
 1 files changed, 59 insertions(+), 26 deletions(-)

diff --git a/builtin-fetch.c b/builtin-fetch.c
index cb48c57..c9a2563 100644
--- a/builtin-fetch.c
+++ b/builtin-fetch.c
@@ -504,57 +504,90 @@ static int will_fetch(struct ref **head, const unsigned char *sha1)
 	return 0;
 }
 
+struct tag_data {
+	struct ref **head;
+	struct ref ***tail;
+	struct string_list *refs;
+};
+
+static int add_to_tail(struct string_list_item *item, void *cb_data)
+{
+	struct tag_data *data = (struct tag_data *)cb_data;
+	unsigned char *commit = (unsigned char *)item->util;
+	struct ref *rm = NULL;
+	struct string_list_item *sli;
+
+	/* Tag objects will have the commit sha1 associated with the peeled
+	 * ref, if there is not a peeled ref then the ref is probably a
+	 * lightweight tag and so refers to a commit directly */
+	sli = string_list_lookup(item->string, data->refs);
+	if (sli)
+		commit = sli->util;
+
+	/* skip over tags that we don't have the commits for. */
+	if (!has_sha1_file(commit) && !will_fetch(data->head, commit))
+		return 0;
+
+	rm = alloc_ref(item->string);
+	rm->peer_ref = alloc_ref(item->string);
+	hashcpy(rm->old_sha1, item->util);
+
+	**data->tail = rm;
+	*data->tail = &rm->next;
+
+	return 0;
+}
+
 static void find_non_local_tags(struct transport *transport,
 			struct ref **head,
 			struct ref ***tail)
 {
 	struct string_list existing_refs = { NULL, 0, 0, 0 };
-	struct string_list new_refs = { NULL, 0, 0, 1 };
+	struct string_list peeled_refs = { NULL, 0, 0, 1 };
+	struct string_list remote_refs = { NULL, 0, 0, 1 };
+	struct tag_data data = {head, tail, &peeled_refs};
+	struct string_list *refs;
 	char *ref_name;
 	int ref_name_len;
-	const unsigned char *ref_sha1;
-	const struct ref *tag_ref;
-	struct ref *rm = NULL;
 	const struct ref *ref;
+	struct string_list_item *item;
 
 	for_each_ref(add_existing, &existing_refs);
 	for (ref = transport_get_remote_refs(transport); ref; ref = ref->next) {
 		if (prefixcmp(ref->name, "refs/tags"))
 			continue;
 
+		/* skip duplicates */
+		if (string_list_lookup(ref->name, &remote_refs))
+			continue;
+
+		refs = &remote_refs;
 		ref_name = xstrdup(ref->name);
 		ref_name_len = strlen(ref_name);
-		ref_sha1 = ref->old_sha1;
 
+		/* we want to store peeled refs by the base ref name in the
+		 * peeled_refs string list */
 		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;
-			}
+			refs = &peeled_refs;
 		}
 
-		if (!string_list_has_string(&existing_refs, ref_name) &&
-		    !string_list_has_string(&new_refs, ref_name) &&
-		    (has_sha1_file(ref->old_sha1) ||
-		     will_fetch(head, ref->old_sha1))) {
-			string_list_insert(ref_name, &new_refs);
-
-			rm = alloc_ref(ref_name);
-			rm->peer_ref = alloc_ref(ref_name);
-			hashcpy(rm->old_sha1, ref_sha1);
-
-			**tail = rm;
-			*tail = &rm->next;
+		/* ignore refs that we already have */
+		if (!string_list_has_string(&existing_refs, ref_name)) {
+			item = string_list_insert(ref_name, refs);
+			item->util = (void *)ref->old_sha1;
 		}
+
 		free(ref_name);
 	}
+
+	/* For all the tags in the remote_refs string list, call add_to_tail to
+	 * add them to the list of refs to be fetched */
+	for_each_string_list(add_to_tail, &remote_refs, &data);
+
 	string_list_clear(&existing_refs, 0);
-	string_list_clear(&new_refs, 0);
+	string_list_clear(&peeled_refs, 0);
+	string_list_clear(&remote_refs, 0);
 }
 
 static void check_not_current_branch(struct ref *ref_map)
-- 
1.6.4.2

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

[Shawn O. Pearce]

Junio C Hamano <gitster@pobox.com> wrote:
> "Shawn O. Pearce" <spearce@spearce.org> writes:
> 
> > JGit depends on the fact that the refs list is sorted by the remote
> > peer, and that foo^{} immediately follows foo.  I don't think this
> > has ever been documented, but all sane implementations[1] follow
> > this convention and it may be something we could simply codify as
> > part of the protocol standard.
> >
> > [1] Sane implementations are defined to be what I consider to be
> >     the two stable implementations in deployed use, git.git and JGit.
> 
> There is no strong reason for ordering of refs between themselves
> (i.e. refs/heads/master comes before refs/heads/next) other than the fact
> that we sort and then walk due to packed-refs reasons.

Sorry, I misspoke a bit above.

JGit does not care about the ordering between two refs, e.g. in your
master/next example above JGit would accept them in either order
just fine.  Internally we enforce this by hashing the advertised
refs and walking the hash, callers presenting the data for a user
must copy to a list and sort by their desired sorting criteria
(usually name).

What I meant to say was this:
 
> But emitting tag X and then its peeled representation X^{} immediately
> after it is quite fundamental in the way how anybody sane would implement
> ls-remote.  There is no reason to violate the established order other than
> "I could do so", and in order not to show X and X^{} next to each other,
> you would need _more_ processing.

and right, explicitly placing X^{} away from X means that the sender
has to do more work to buffer one of the two values and then show
them later.  This is pointless other than to piss off any more
reasonable implementor.

I think we should formalize this rule of X^{} immediately follows
X if peeling is possible, and if not, then X^{} must not appear.
We already have a similar rule with packed-refs, although there it
is absolutely required by the format.

> Also, you might not have noticed, but my illustration patch was merely
> using it as a hint to optimize, and if the last ref we saw was not X when
> it is turn to handle X^{}, it simply falled back to the original logic,
> iow, the patch never compromised the correctness.

Oh, I missed that.  JGit I think flat out panics and disconnects
if the remote does this to us.  What is the incentive in supporting
a broken server with a slower client?

-- 
Shawn.

Re: [RFC/PATCH v2] fetch: Speed up fetch by rewriting find_non_local_tags

[Junio C Hamano]

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

> 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.  Rewrite the function so that we can do lookup in
> string_lists instead.
>
> 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.2s.
>
> Signed-off-by: Julian Phillips <julian@quantumfyre.co.uk>
> ---
>
> Not only does this not require a custom hash table, it is also slightly
> faster than the last version (~4.2s vs ~4.5s).

I am just curious.  How would a "just one item lookbehind" code perform
compared to this one?

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

[Junio C Hamano]

"Shawn O. Pearce" <spearce@spearce.org> writes:

>> Also, you might not have noticed, but my illustration patch was merely
>> using it as a hint to optimize, and if the last ref we saw was not X when
>> it is turn to handle X^{}, it simply falled back to the original logic,
>> iow, the patch never compromised the correctness.
>
> Oh, I missed that.  JGit I think flat out panics and disconnects
> if the remote does this to us.  What is the incentive in supporting
> a broken server with a slower client?

There is none.

I think the original logic, being written in shell, run grep in the
output, and the C code we are seeing is a literal translation of that.

In other words, I think it is simply a historical accident.

Re: [RFC/PATCH v2] fetch: Speed up fetch by rewriting find_non_local_tags

[Julian Phillips]

On Wed, 16 Sep 2009, Junio C Hamano wrote:

> Julian Phillips <julian@quantumfyre.co.uk> writes:
>
>> 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.  Rewrite the function so that we can do lookup in
>> string_lists instead.
>>
>> 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.2s.
>>
>> Signed-off-by: Julian Phillips <julian@quantumfyre.co.uk>
>> ---
>>
>> Not only does this not require a custom hash table, it is also slightly
>> faster than the last version (~4.2s vs ~4.5s).
>
> I am just curious.  How would a "just one item lookbehind" code perform
> compared to this one?

The code you wrote ealier is almost the same as the string_list version, 
~4.3s, so very marginally slower but a lot less code change.  Personally 
I'd be happy with any of the three, so long as I don't have to wait 30s to 
find out that nothing's happened at $dayjob anymore ;)

-- 
Julian

  ---
QOTD:
 	If it's too loud, you're too old.

Re: [RFC/PATCH v2] fetch: Speed up fetch by rewriting find_non_local_tags

[Julian Phillips]

On Thu, 17 Sep 2009, Julian Phillips wrote:

> On Wed, 16 Sep 2009, Junio C Hamano wrote:
>
>>  I am just curious.  How would a "just one item lookbehind" code perform
>>  compared to this one?
>
> The code you wrote ealier is almost the same as the string_list version, 
> ~ 4.3s, so very marginally slower but a lot less code change.  Personally 
> I'd be happy with any of the three, so long as I don't have to wait 30s to 
> find out that nothing's happened at $dayjob anymore ;)

FWIW: I've Just modified my v2 patch to make use of the requirement that 
the peeled ref immediately follow the base ref, and it's now ~4.1s and 
should use less memory than the original too.  I won't bother posting it 
unless someone thinks it worth it though.

-- 
Julian

  ---
Taxes, n.:
 	Of life's two certainties, the only one for which you can get
 	an extension.

Re: [RFC/PATCH v2] fetch: Speed up fetch by rewriting find_non_local_tags

[Johan Herland]

On Thursday 17 September 2009, Julian Phillips wrote:
> On Thu, 17 Sep 2009, Julian Phillips wrote:
> > On Wed, 16 Sep 2009, Junio C Hamano wrote:
> >>  I am just curious.  How would a "just one item lookbehind" code
> >> perform compared to this one?
> >
> > The code you wrote ealier is almost the same as the string_list
> > version, ~ 4.3s, so very marginally slower but a lot less code change. 
> > Personally I'd be happy with any of the three, so long as I don't have
> > to wait 30s to find out that nothing's happened at $dayjob anymore ;)
> 
> FWIW: I've Just modified my v2 patch to make use of the requirement that
> the peeled ref immediately follow the base ref, and it's now ~4.1s and
> should use less memory than the original too.  I won't bother posting it
> unless someone thinks it worth it though.

It's worth it. :)


...Johan


-- 
Johan Herland, <johan@herland.net>
www.herland.net

[RFC/PATCH v3] fetch: Speed up fetch by rewriting find_non_local_tags

[Julian Phillips]

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.  Rewrite the function so that we build up a
string_list of refs to fetch and then process that instead.

As an extreme example, 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.1s.

Signed-off-by: Julian Phillips <julian@quantumfyre.co.uk>
---

Ok, so here it is ...

Sometimes I forget just much we git users value our time and resources.
;)

 builtin-fetch.c |   98 ++++++++++++++++++++++++++++++++++++------------------
 1 files changed, 65 insertions(+), 33 deletions(-)

diff --git a/builtin-fetch.c b/builtin-fetch.c
index cb48c57..acb08e4 100644
--- a/builtin-fetch.c
+++ b/builtin-fetch.c
@@ -504,57 +504,89 @@ static int will_fetch(struct ref **head, const unsigned char *sha1)
 	return 0;
 }
 
+struct tag_data {
+	struct ref **head;
+	struct ref ***tail;
+};
+
+static int add_to_tail(struct string_list_item *item, void *cb_data)
+{
+	struct tag_data *data = (struct tag_data *)cb_data;
+	struct ref *rm = NULL;
+
+	/* We have already decided to ignore this item */
+	if (!item->util)
+		return 0;
+
+	rm = alloc_ref(item->string);
+	rm->peer_ref = alloc_ref(item->string);
+	hashcpy(rm->old_sha1, item->util);
+
+	**data->tail = rm;
+	*data->tail = &rm->next;
+
+	return 0;
+}
+
 static void find_non_local_tags(struct transport *transport,
 			struct ref **head,
 			struct ref ***tail)
 {
 	struct string_list existing_refs = { NULL, 0, 0, 0 };
-	struct string_list new_refs = { NULL, 0, 0, 1 };
-	char *ref_name;
-	int ref_name_len;
-	const unsigned char *ref_sha1;
-	const struct ref *tag_ref;
-	struct ref *rm = NULL;
+	struct string_list remote_refs = { NULL, 0, 0, 0 };
+	struct tag_data data = {head, tail};
 	const struct ref *ref;
+	struct string_list_item *item = NULL;
 
 	for_each_ref(add_existing, &existing_refs);
 	for (ref = transport_get_remote_refs(transport); ref; ref = ref->next) {
 		if (prefixcmp(ref->name, "refs/tags"))
 			continue;
 
-		ref_name = xstrdup(ref->name);
-		ref_name_len = strlen(ref_name);
-		ref_sha1 = ref->old_sha1;
-
-		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;
-			}
+		/* the peeled ref always follows the matching base ref, so if we
+		 * see a peeled ref that we don't want to fetch then we can mark
+		 * the ref entry in the list as one to ignore by setting util to
+		 * NULL. */
+		if (!strcmp(ref->name + strlen(ref->name) - 3, "^{}")) {
+			if (item && !has_sha1_file(ref->old_sha1) &&
+			    !will_fetch(head, ref->old_sha1) &&
+			    !has_sha1_file(item->util) &&
+			    !will_fetch(head, item->util) )
+				item->util = NULL;
+			item = NULL;
+			continue;
 		}
 
-		if (!string_list_has_string(&existing_refs, ref_name) &&
-		    !string_list_has_string(&new_refs, ref_name) &&
-		    (has_sha1_file(ref->old_sha1) ||
-		     will_fetch(head, ref->old_sha1))) {
-			string_list_insert(ref_name, &new_refs);
+		/* If item is non-NULL here, then we previously saw a ref not
+		 * followed by a peeled reference, so we need to check if it is
+		 * a lightweight tag that we want to fetch */
+		if (item && !has_sha1_file(item->util) &&
+		    !will_fetch(head, item->util) )
+			item->util = NULL;
 
-			rm = alloc_ref(ref_name);
-			rm->peer_ref = alloc_ref(ref_name);
-			hashcpy(rm->old_sha1, ref_sha1);
+		item = NULL;
 
-			**tail = rm;
-			*tail = &rm->next;
-		}
-		free(ref_name);
+		/* skip duplicates and refs that we already have */
+		if (string_list_has_string(&remote_refs, ref->name) ||
+		    string_list_has_string(&existing_refs, ref->name))
+			continue;
+
+		item = string_list_insert(ref->name, &remote_refs);
+		item->util = (void *)ref->old_sha1;
 	}
 	string_list_clear(&existing_refs, 0);
-	string_list_clear(&new_refs, 0);
+
+	/* We may have a final lightweight tag that needs to be checked to see
+	 * if it needs fetching. */
+	if (item && !has_sha1_file(item->util) &&
+	    !will_fetch(head, item->util) )
+		item->util = NULL;
+
+	/* For all the tags in the remote_refs string list, call add_to_tail to
+	 * add them to the list of refs to be fetched */
+	for_each_string_list(add_to_tail, &remote_refs, &data);
+
+	string_list_clear(&remote_refs, 0);
 }
 
 static void check_not_current_branch(struct ref *ref_map)
-- 
1.6.4.2

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

[Junio C Hamano]

"Shawn O. Pearce" <spearce@spearce.org> writes:

> Junio C Hamano <gitster@pobox.com> wrote:
>> 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.
>
> Under Gerrit Code Review it is normaly to have 2-5 refs per commit,
> every iteration of a patch is held as a commit and anchored by a
> unique ref.
>
> So we're borderline insane.  :-)

Heh, that's way below 10 refs per commit, isn't it?