{"thread":{"id":"20964","subject":"[RFC/PATCH 2/2] fetch: Speed up fetch by using ref dictionary","startedAt":"2009-09-16T07:53:01Z","lastAt":"2009-09-22T20:36:24Z","messageCount":17,"participants":["Julian Phillips","Junio C Hamano","Shawn O. Pearce","Johan Herland"],"isPatch":true,"patchVersion":1,"patchTotal":2},"messages":[{"id":"123308","messageId":"20090916074737.58044.42776.julian@quantumfyre.co.uk","threadId":"20964","inReplyTo":null,"subject":"[RFC/PATCH 0/2] Speed up fetch with large number of tags","fromName":"Julian Phillips","fromEmail":"julian@quantumfyre.co.uk","sentAt":"2009-09-16T07:53:01Z","receivedAt":"2009-09-16T07:53:01Z","isPatch":true,"sender":{"key":"julian@quantumfyre.co.uk","avatar":"https://avatars.githubusercontent.com/u/948888?v=4"},"body":"I have a repository at $dayjob where fetch was taking ~30s to tell me\nthat there were no updates.\n\nIt turns out that I appear to have added a nasty linear search of all\nremote refs for every commit (i.e. tag^{}) tag ref way back in the\noriginal C implementation of fetch. This doesn't scale well to large\nnumbers of refs, so this replaces it with a hash table based lookup\ninstead, which brings the time down to a few seconds even for very large\nref counts.\n\nI haven't tested it with non-native transports, but there is no reason\nto believe that the code should be transport specific.\n\nJulian Phillips (2):\n ref-dict: Add a set of functions for working with a ref dictionary\n fetch: Speed up fetch by using ref dictionary\n\n Makefile | 1 +\n builtin-fetch.c | 19 ++++++-------\n ref-dict.c | 76 +++++++++++++++++++++++++++++++++++++++++++++++++++++++\n ref-dict.h | 13 +++++++++\n 4 files changed, 99 insertions(+), 10 deletions(-)\n create mode 100644 ref-dict.c\n create mode 100644 ref-dict.h\n"},{"id":"123309","messageId":"20090916075304.58044.664.julian@quantumfyre.co.uk","threadId":"20964","inReplyTo":"20090916074737.58044.42776.julian@quantumfyre.co.uk","subject":"[RFC/PATCH 1/2] ref-dict: Add a set of functions for working with a ref dictionary","fromName":"Julian Phillips","fromEmail":"julian@quantumfyre.co.uk","sentAt":"2009-09-16T07:53:02Z","receivedAt":"2009-09-16T07:53:02Z","isPatch":true,"sender":{"key":"julian@quantumfyre.co.uk","avatar":"https://avatars.githubusercontent.com/u/948888?v=4"},"body":"These are a set of helper functions that use the generic hash table\nfunctions to provide a quick and easy mapping from ref name to sha1.\n\nSigned-off-by: Julian Phillips \n---\n Makefile | 1 +\n ref-dict.c | 76 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n ref-dict.h | 13 ++++++++++\n 3 files changed, 90 insertions(+), 0 deletions(-)\n create mode 100644 ref-dict.c\n create mode 100644 ref-dict.h\n\ndiff --git a/Makefile b/Makefile\nindex d4958b8..815e4c9 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -531,6 +531,7 @@ LIB_OBJS += reachable.o\n LIB_OBJS += read-cache.o\n LIB_OBJS += reflog-walk.o\n LIB_OBJS += refs.o\n+LIB_OBJS += ref-dict.o\n LIB_OBJS += remote.o\n LIB_OBJS += replace_object.o\n LIB_OBJS += rerere.o\ndiff --git a/ref-dict.c b/ref-dict.c\nnew file mode 100644\nindex 0000000..b9cab4b\n--- /dev/null\n+++ b/ref-dict.c\n@@ -0,0 +1,76 @@\n+/*\n+ * ref-dict.c\n+ *\n+ * A Hash-based dictionary for storing name-sha1 data for refs.\n+ *\n+ * Copyright (C) 2009 Julian Phillips\n+ */\n+\n+#include \"cache.h\"\n+#include \"hash.h\"\n+#include \"remote.h\"\n+#include \"ref-dict.h\"\n+\n+/* hash_name based on the function of the same name in name-hash.c */\n+static unsigned int hash_name(const char *name)\n+{\n+\tunsigned int hash = 0x123;\n+\tint namelen = strlen(name);\n+\n+\tdo {\n+\t\tunsigned char c = *name++;\n+\t\thash = hash*101 + c;\n+\t} while (--namelen);\n+\treturn hash;\n+}\n+\n+/*\n+ * A convienience function for creating a ref_dict from a ref_list.\n+ */\n+void ref_dict_create(struct hash_table *dict, const struct ref *ref_list)\n+{\n+\tstruct ref *ref;\n+\n+\tinit_hash(dict);\n+\n+\tfor (ref = (struct ref *)ref_list; ref; ref = ref->next) {\n+\t\tref_dict_add(dict, ref->name, ref->old_sha1);\n+\t}\n+}\n+\n+/*\n+ * Add an entry to the ref_dict, recording that name maps to sha1.\n+ */\n+void ref_dict_add(struct hash_table *dict, const char *name,\n+\t\tconst unsigned char *sha1)\n+{\n+\tstruct ref **ref;\n+\tstruct ref *new_ref = alloc_ref(name);\n+\n+\thashcpy(new_ref->old_sha1, sha1);\n+\t\n+\tref = (struct ref **)insert_hash(hash_name(name), new_ref, dict);\n+\tif (ref) {\n+\t\tnew_ref->next = *ref;\n+\t\t*ref = new_ref;\n+\t}\n+}\n+\n+/*\n+ * Find the sha1 for the given name. Returns 1 if found and copies the sha1\n+ * into the space pointed to by sha1, returns 0 otherwise and sha1 is untouched.\n+ */\n+int ref_dict_get(const struct hash_table *dict, const char *name,\n+\t\tunsigned char *sha1)\n+{\n+\tstruct ref *ref = lookup_hash(hash_name(name), dict);\n+\n+\tfor (; ref; ref = ref->next) {\n+\t\tif (!strcmp(name, ref->name)) {\n+\t\t\thashcpy(sha1, ref->old_sha1);\n+\t\t\treturn 1;\n+\t\t}\n+\t}\n+\n+\treturn 0;\n+}\ndiff --git a/ref-dict.h b/ref-dict.h\nnew file mode 100644\nindex 0000000..ca1e9a7\n--- /dev/null\n+++ b/ref-dict.h\n@@ -0,0 +1,13 @@\n+#ifndef REF_DICT_H\n+#define REF_DICT_H\n+\n+#include \"cache.h\"\n+#include \"hash.h\"\n+\n+void ref_dict_create(struct hash_table *dict, const struct ref *ref_list);\n+void ref_dict_add(struct hash_table *dict, const char *name,\n+\t\tconst unsigned char *sha1);\n+int ref_dict_get(const struct hash_table *dict, const char *name,\n+\t\tunsigned char *sha1);\n+\n+#endif /* REF_DICT_H */\n-- \n1.6.4.2\n"},{"id":"123307","messageId":"20090916075304.58044.83034.julian@quantumfyre.co.uk","threadId":"20964","inReplyTo":"20090916074737.58044.42776.julian@quantumfyre.co.uk","subject":"[RFC/PATCH 2/2] fetch: Speed up fetch by using ref dictionary","fromName":"Julian Phillips","fromEmail":"julian@quantumfyre.co.uk","sentAt":"2009-09-16T07:53:03Z","receivedAt":"2009-09-16T07:53:03Z","isPatch":true,"sender":{"key":"julian@quantumfyre.co.uk","avatar":"https://avatars.githubusercontent.com/u/948888?v=4"},"body":"When trying to get a list of remote tags to see if we need to fetch\nany we were doing a linear search for the matching tag ref for the\ntag^{} commit entries. This proves to be incredibly slow for large\nnumbers of tags.\n\nFor a repository with 50000 tags (and just a single commit on a single\nbranch), a fetch that does nothing goes from ~ 1m50s to ~4.5s.\n\nSigned-off-by: Julian Phillips \n---\n builtin-fetch.c | 19 +++++++++----------\n 1 files changed, 9 insertions(+), 10 deletions(-)\n\ndiff --git a/builtin-fetch.c b/builtin-fetch.c\nindex cb48c57..16cfee6 100644\n--- a/builtin-fetch.c\n+++ b/builtin-fetch.c\n@@ -11,6 +11,7 @@\n #include \"run-command.h\"\n #include \"parse-options.h\"\n #include \"sigchain.h\"\n+#include \"ref-dict.h\"\n \n static const char * const builtin_fetch_usage[] = {\n \t\"git fetch [options] [ ...]\",\n@@ -513,12 +514,16 @@ static void find_non_local_tags(struct transport *transport,\n \tchar *ref_name;\n \tint ref_name_len;\n \tconst unsigned char *ref_sha1;\n-\tconst struct ref *tag_ref;\n+\tunsigned char tag_sha1[40];\n \tstruct ref *rm = NULL;\n \tconst struct ref *ref;\n+\tstruct hash_table dict;\n+\tconst struct ref *remote_refs = transport_get_remote_refs(transport);\n+\n+\tref_dict_create(&dict, remote_refs);\n \n \tfor_each_ref(add_existing, &existing_refs);\n-\tfor (ref = transport_get_remote_refs(transport); ref; ref = ref->next) {\n+\tfor (ref = remote_refs; ref; ref = ref->next) {\n \t\tif (prefixcmp(ref->name, \"refs/tags\"))\n \t\t\tcontinue;\n \n@@ -528,14 +533,8 @@ static void find_non_local_tags(struct transport *transport,\n \n \t\tif (!strcmp(ref_name + ref_name_len - 3, \"^{}\")) {\n \t\t\tref_name[ref_name_len - 3] = 0;\n-\t\t\ttag_ref = transport_get_remote_refs(transport);\n-\t\t\twhile (tag_ref) {\n-\t\t\t\tif (!strcmp(tag_ref->name, ref_name)) {\n-\t\t\t\t\tref_sha1 = tag_ref->old_sha1;\n-\t\t\t\t\tbreak;\n-\t\t\t\t}\n-\t\t\t\ttag_ref = tag_ref->next;\n-\t\t\t}\n+\t\t\tif (ref_dict_get(&dict, ref_name, tag_sha1))\n+\t\t\t\tref_sha1 = tag_sha1;\n \t\t}\n \n \t\tif (!string_list_has_string(&existing_refs, ref_name) &&\n-- \n1.6.4.2\n"},{"id":"123329","messageId":"7vbplb2pi7.fsf@alter.siamese.dyndns.org","threadId":"20964","inReplyTo":"20090916074737.58044.42776.julian@quantumfyre.co.uk","subject":"Re: [RFC/PATCH 0/2] Speed up fetch with large number of tags","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-09-16T09:44:00Z","receivedAt":"2009-09-16T09:44:00Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Julian Phillips writes:\n\n> I have a repository at $dayjob where fetch was taking ~30s to tell me\n> that there were no updates.\n>\n> It turns out that I appear to have added a nasty linear search of all\n> remote refs for every commit (i.e. tag^{}) tag ref way back in the\n> original C implementation of fetch. This doesn't scale well to large\n> numbers of refs, so this replaces it with a hash table based lookup\n> instead, which brings the time down to a few seconds even for very large\n> ref counts.\n>\n> I haven't tested it with non-native transports, but there is no reason\n> to believe that the code should be transport specific.\n\nVery interesting.\n\nA few questions (not criticisms).\n\n * 1m50s to 4.5s is quite impressive, even if it is only in a repository\n with unusual refs-vs-commits ratio, but I personally think 10 refs per\n every commit is already on the borderline of being insane, and the\n normal ratio would be more like 1 refs per every 10-20 commits.\n\n What are possible downsides with the new code in repositories with more\n reasonable refs-vs-commits ratio? A hash table (with a sensible hash\n function) would almost always outperform linear search in an randomly\n ordered collection, so my gut tells me that there won't be performance\n downsides, but are there other potential issues we should worry about?\n\n * In an insanely large refs-vs-commits case, perhaps not 50000:1 but more\n like 100:1, but with a history with far more than one commit, what is\n the memory consumption? Judging from a cursory view, I think the way\n ref-dict re-uses struct ref might be quite suboptimal, as you are using\n only next (for hash-bucket link), old_sha1[] and its name field, and\n also your ref_dict_add() calls alloc_ref() which calls one calloc() per\n requested ref, instead of attempting any bulk allocation.\n\n * The outer loop is walking the list of refs from a transport, and the\n inner loop is walking a copy of the same list of refs from the same\n transport, looking for each refs/tags/X^{} what record, if any, existed\n for refs/tags/X.\n\n Would it make sense to further specialize your optimization? For\n example, something like...\n\n /* Your hash records this structure */\n struct tag_ref_record {\n const char *name;\n struct ref *self;\n struct ref *peeled;\n };\n\n static void add_to_tail(struct ref ***tail,\n struct string_list *existing_refs,\n struct string_list *new_refs,\n const struct ref *ref,\n const unsigned char sha1[]) {\n ... the \"appending to *tail\" thing as a helper function ...\n }\n\n for (ref in all refs from transport) {\n if (ref is of form \"refs/tags/X^{}\")\n look up tag_ref_record for \"refs/tags/X\" and store\n ref in its peeled member;\n else if (ref is of form \"refs/tags/X\")\n look up tag_ref_record for \"refs/tags/X\" and store\n ref in its self member;\n }\n\n for (trr in all tag_ref_record database) {\n add_to_tail(tail, &existing_refs, &new_refs,\n trr->self, self->old_sha1);\n add_to_tail(tail, &existing_refs, &new_refs,\n trr->peeled, self->old_sha1);\n }\n\n * It is tempting to use a hash table when you have to deal with an\n unordered collection, but in this case, wouldn't the refs obtained from\n the transport (it's essentially a ls-remote output, isn't it?) be\n sorted? Can't you take advantage of that fact to optimize the loop,\n without adding a specialized hash table implementation?\n\n We find refs/tags/v0.99 immediately followed by refs/tags/v0.99^{} in\n the ls-remote output. And the inefficient loop is about finding\n refs/tags/v0.99 when we see refs/tags/v0.99^{}, so if we remember the\n tag ref we saw in the previous round, we can check with that first to\n make sure our \"sorted\" assumption holds true, and optimize the loop out\n that way, no?\n\ndiff --git a/builtin-fetch.c b/builtin-fetch.c\nindex cb48c57..3f12e28 100644\n--- a/builtin-fetch.c\n+++ b/builtin-fetch.c\n@@ -516,6 +516,7 @@ static void find_non_local_tags(struct transport *transport,\n \tconst struct ref *tag_ref;\n \tstruct ref *rm = NULL;\n \tconst struct ref *ref;\n+\tconst struct ref *last_tag_seen = NULL;\n \n \tfor_each_ref(add_existing, &existing_refs);\n \tfor (ref = transport_get_remote_refs(transport); ref; ref = ref->next) {\n@@ -528,6 +529,11 @@ static void find_non_local_tags(struct transport *transport,\n \n \t\tif (!strcmp(ref_name + ref_name_len - 3, \"^{}\")) {\n \t\t\tref_name[ref_name_len - 3] = 0;\n+\t\t\tif (last_tag_seen &&\n+\t\t\t !strcmp(last_tag_seen->name, ref_name)) {\n+\t\t\t\tref_sha1 = last_tag_seen->old_sha1;\n+\t\t\t\tgoto quick;\n+\t\t\t}\n \t\t\ttag_ref = transport_get_remote_refs(transport);\n \t\t\twhile (tag_ref) {\n \t\t\t\tif (!strcmp(tag_ref->name, ref_name)) {\n@@ -536,8 +542,11 @@ static void find_non_local_tags(struct transport *transport,\n \t\t\t\t}\n \t\t\t\ttag_ref = tag_ref->next;\n \t\t\t}\n+\t\t} else {\n+\t\t\tlast_tag_seen = ref;\n \t\t}\n \n+\tquick:\n \t\tif (!string_list_has_string(&existing_refs, ref_name) &&\n \t\t !string_list_has_string(&new_refs, ref_name) &&\n \t\t (has_sha1_file(ref->old_sha1) ||\n"},{"id":"123381","messageId":"alpine.LNX.2.00.0909162141140.13697@reaper.quantumfyre.co.uk","threadId":"20964","inReplyTo":"7vbplb2pi7.fsf@alter.siamese.dyndns.org","subject":"Re: [RFC/PATCH 0/2] Speed up fetch with large number of tags","fromName":"Julian Phillips","fromEmail":"julian@quantumfyre.co.uk","sentAt":"2009-09-16T22:32:52Z","receivedAt":"2009-09-16T22:32:52Z","isPatch":true,"sender":{"key":"julian@quantumfyre.co.uk","avatar":"https://avatars.githubusercontent.com/u/948888?v=4"},"body":"On Wed, 16 Sep 2009, Junio C Hamano wrote:\n\n> Julian Phillips writes:\n>\n>> I have a repository at $dayjob where fetch was taking ~30s to tell me\n>> that there were no updates.\n>>\n>> It turns out that I appear to have added a nasty linear search of all\n>> remote refs for every commit (i.e. tag^{}) tag ref way back in the\n>> original C implementation of fetch. This doesn't scale well to large\n>> numbers of refs, so this replaces it with a hash table based lookup\n>> instead, which brings the time down to a few seconds even for very large\n>> ref counts.\n>>\n>> I haven't tested it with non-native transports, but there is no reason\n>> to believe that the code should be transport specific.\n>\n> Very interesting.\n>\n> A few questions (not criticisms).\n>\n> * 1m50s to 4.5s is quite impressive, even if it is only in a repository\n> with unusual refs-vs-commits ratio, but I personally think 10 refs per\n> every commit is already on the borderline of being insane, and the\n> normal ratio would be more like 1 refs per every 10-20 commits.\n\nI noticed the problem with a real repository at $dayjob, and did enough \nanaylsis to identiy the problem. I deliberately created a repository that \nshould emphasise the problem so that it was easy to get a handle on.\n\nHaving applied the ref-dict patches fetch on my $dayjob repo has gone from \n~30s to ~4.5s, which may not be as impressive - but is much easier to live \nwith.\n\n> What are possible downsides with the new code in repositories with more\n> reasonable refs-vs-commits ratio? A hash table (with a sensible hash\n> function) would almost always outperform linear search in an randomly\n> ordered collection, so my gut tells me that there won't be performance\n> downsides, but are there other potential issues we should worry about?\n\nI guess that main thing would be the extra memory usage.\n\n> * In an insanely large refs-vs-commits case, perhaps not 50000:1 but more\n> like 100:1, but with a history with far more than one commit, what is\n> the memory consumption? Judging from a cursory view, I think the way\n> ref-dict re-uses struct ref might be quite suboptimal, as you are using\n> only next (for hash-bucket link), old_sha1[] and its name field, and\n> also your ref_dict_add() calls alloc_ref() which calls one calloc() per\n> requested ref, instead of attempting any bulk allocation.\n\nYeah, I just reused struct for speed and convience of developing, to \nveryify that ref-dict would give me the speed I wanted. A final patch \nwould want a more optimised version. Except that I've thrown the whole \nhash table thing away anyway.\n\n> * The outer loop is walking the list of refs from a transport, and the\n> inner loop is walking a copy of the same list of refs from the same\n> transport, looking for each refs/tags/X^{} what record, if any, existed\n> for refs/tags/X.\n>\n> Would it make sense to further specialize your optimization? For\n> example, something like...\n\nI actually arrived at somthing similar to this myself, after realising \nthat I could use string_list as a basis.\n\n> * It is tempting to use a hash table when you have to deal with an\n> unordered collection, but in this case, wouldn't the refs obtained from\n> the transport (it's essentially a ls-remote output, isn't it?) be\n> sorted? Can't you take advantage of that fact to optimize the loop,\n> without adding a specialized hash table implementation?\n\nI wasn't sure if we could rely on the refs list being sorted. But I've \ngot a new version that uses an extra string_list instead that is actually \nslightly faster. I'll post that shortly.\n\n> We find refs/tags/v0.99 immediately followed by refs/tags/v0.99^{} in\n> the ls-remote output. And the inefficient loop is about finding\n> refs/tags/v0.99 when we see refs/tags/v0.99^{}, so if we remember the\n> tag ref we saw in the previous round, we can check with that first to\n> make sure our \"sorted\" assumption holds true, and optimize the loop out\n> that way, no?\n\n-- \nJulian\n\n ---\nBilbo's First Law:\n \tYou cannot count friends that are all packed up in barrels.\n"},{"id":"123382","messageId":"20090916224253.GB14660@spearce.org","threadId":"20964","inReplyTo":"alpine.LNX.2.00.0909162141140.13697@reaper.quantumfyre.co.uk","subject":"Re: [RFC/PATCH 0/2] Speed up fetch with large number of tags","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-09-16T22:42:53Z","receivedAt":"2009-09-16T22:42:53Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Julian Phillips wrote:\n> On Wed, 16 Sep 2009, Junio C Hamano wrote:\n>> * It is tempting to use a hash table when you have to deal with an\n>> unordered collection, but in this case, wouldn't the refs obtained from\n>> the transport (it's essentially a ls-remote output, isn't it?) be\n>> sorted? Can't you take advantage of that fact to optimize the loop,\n>> without adding a specialized hash table implementation?\n>\n> I wasn't sure if we could rely on the refs list being sorted. But I've \n> got a new version that uses an extra string_list instead that is actually \n> slightly faster. I'll post that shortly.\n\nJGit depends on the fact that the refs list is sorted by the remote\npeer, and that foo^{} immediately follows foo. I don't think this\nhas ever been documented, but all sane implementations[1] follow\nthis convention and it may be something we could simply codify as\npart of the protocol standard.\n\n[1] Sane implementations are defined to be what I consider to be\n the two stable implementations in deployed use, git.git and JGit.\n\n-- \nShawn.\n"},{"id":"123383","messageId":"20090916224651.GA15259@spearce.org","threadId":"20964","inReplyTo":"7vbplb2pi7.fsf@alter.siamese.dyndns.org","subject":"Re: [RFC/PATCH 0/2] Speed up fetch with large number of tags","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-09-16T22:46:51Z","receivedAt":"2009-09-16T22:46:51Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano wrote:\n> A few questions (not criticisms).\n> \n> * 1m50s to 4.5s is quite impressive, even if it is only in a repository\n> with unusual refs-vs-commits ratio, but I personally think 10 refs per\n> every commit is already on the borderline of being insane, and the\n> normal ratio would be more like 1 refs per every 10-20 commits.\n\nUnder Gerrit Code Review it is normaly to have 2-5 refs per commit,\nevery iteration of a patch is held as a commit and anchored by a\nunique ref.\n\nSo we're borderline insane. :-)\n \n-- \nShawn.\n"},{"id":"123384","messageId":"7vtyz2wlhm.fsf@alter.siamese.dyndns.org","threadId":"20964","inReplyTo":"20090916224253.GB14660@spearce.org","subject":"Re: [RFC/PATCH 0/2] Speed up fetch with large number of tags","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-09-16T22:52:37Z","receivedAt":"2009-09-16T22:52:37Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Shawn O. Pearce\" writes:\n\n> JGit depends on the fact that the refs list is sorted by the remote\n> peer, and that foo^{} immediately follows foo. I don't think this\n> has ever been documented, but all sane implementations[1] follow\n> this convention and it may be something we could simply codify as\n> part of the protocol standard.\n>\n> [1] Sane implementations are defined to be what I consider to be\n> the two stable implementations in deployed use, git.git and JGit.\n\nThere is no strong reason for ordering of refs between themselves\n(i.e. refs/heads/master comes before refs/heads/next) other than the fact\nthat we sort and then walk due to packed-refs reasons.\n\nBut emitting tag X and then its peeled representation X^{} immediately\nafter it is quite fundamental in the way how anybody sane would implement\nls-remote. There is no reason to violate the established order other than\n\"I could do so\", and in order not to show X and X^{} next to each other,\nyou would need _more_ processing.\n\nSo I would say it is very safe to assume this.\n\nAlso, you might not have noticed, but my illustration patch was merely\nusing it as a hint to optimize, and if the last ref we saw was not X when\nit is turn to handle X^{}, it simply falled back to the original logic,\niow, the patch never compromised the correctness.\n"},{"id":"123385","messageId":"20090916225350.45746.85139.julian@quantumfyre.co.uk","threadId":"20964","inReplyTo":"alpine.LNX.2.00.0909162141140.13697@reaper.quantumfyre.co.uk","subject":"[RFC/PATCH v2] fetch: Speed up fetch by rewriting find_non_local_tags","fromName":"Julian Phillips","fromEmail":"julian@quantumfyre.co.uk","sentAt":"2009-09-16T22:53:49Z","receivedAt":"2009-09-16T22:53:49Z","isPatch":true,"sender":{"key":"julian@quantumfyre.co.uk","avatar":"https://avatars.githubusercontent.com/u/948888?v=4"},"body":"When trying to get a list of remote tags to see if we need to fetch\nany we were doing a linear search for the matching tag ref for the\ntag^{} commit entries. This proves to be incredibly slow for large\nnumbers of tags. Rewrite the function so that we can do lookup in\nstring_lists instead.\n\nFor a repository with 50000 tags (and just a single commit on a single\nbranch), a fetch that does nothing goes from ~ 1m50s to ~4.2s.\n\nSigned-off-by: Julian Phillips \n---\n\nNot only does this not require a custom hash table, it is also slightly\nfaster than the last version (~4.2s vs ~4.5s).\n\nIf nothing else, having rewritten it completely, at least I now\nunderstand what the old find_non_local_tags function was actually doing\n... ;)\n\n builtin-fetch.c | 85 ++++++++++++++++++++++++++++++++++++++-----------------\n 1 files changed, 59 insertions(+), 26 deletions(-)\n\ndiff --git a/builtin-fetch.c b/builtin-fetch.c\nindex cb48c57..c9a2563 100644\n--- a/builtin-fetch.c\n+++ b/builtin-fetch.c\n@@ -504,57 +504,90 @@ static int will_fetch(struct ref **head, const unsigned char *sha1)\n \treturn 0;\n }\n \n+struct tag_data {\n+\tstruct ref **head;\n+\tstruct ref ***tail;\n+\tstruct string_list *refs;\n+};\n+\n+static int add_to_tail(struct string_list_item *item, void *cb_data)\n+{\n+\tstruct tag_data *data = (struct tag_data *)cb_data;\n+\tunsigned char *commit = (unsigned char *)item->util;\n+\tstruct ref *rm = NULL;\n+\tstruct string_list_item *sli;\n+\n+\t/* Tag objects will have the commit sha1 associated with the peeled\n+\t * ref, if there is not a peeled ref then the ref is probably a\n+\t * lightweight tag and so refers to a commit directly */\n+\tsli = string_list_lookup(item->string, data->refs);\n+\tif (sli)\n+\t\tcommit = sli->util;\n+\n+\t/* skip over tags that we don't have the commits for. */\n+\tif (!has_sha1_file(commit) && !will_fetch(data->head, commit))\n+\t\treturn 0;\n+\n+\trm = alloc_ref(item->string);\n+\trm->peer_ref = alloc_ref(item->string);\n+\thashcpy(rm->old_sha1, item->util);\n+\n+\t**data->tail = rm;\n+\t*data->tail = &rm->next;\n+\n+\treturn 0;\n+}\n+\n static void find_non_local_tags(struct transport *transport,\n \t\t\tstruct ref **head,\n \t\t\tstruct ref ***tail)\n {\n \tstruct string_list existing_refs = { NULL, 0, 0, 0 };\n-\tstruct string_list new_refs = { NULL, 0, 0, 1 };\n+\tstruct string_list peeled_refs = { NULL, 0, 0, 1 };\n+\tstruct string_list remote_refs = { NULL, 0, 0, 1 };\n+\tstruct tag_data data = {head, tail, &peeled_refs};\n+\tstruct string_list *refs;\n \tchar *ref_name;\n \tint ref_name_len;\n-\tconst unsigned char *ref_sha1;\n-\tconst struct ref *tag_ref;\n-\tstruct ref *rm = NULL;\n \tconst struct ref *ref;\n+\tstruct string_list_item *item;\n \n \tfor_each_ref(add_existing, &existing_refs);\n \tfor (ref = transport_get_remote_refs(transport); ref; ref = ref->next) {\n \t\tif (prefixcmp(ref->name, \"refs/tags\"))\n \t\t\tcontinue;\n \n+\t\t/* skip duplicates */\n+\t\tif (string_list_lookup(ref->name, &remote_refs))\n+\t\t\tcontinue;\n+\n+\t\trefs = &remote_refs;\n \t\tref_name = xstrdup(ref->name);\n \t\tref_name_len = strlen(ref_name);\n-\t\tref_sha1 = ref->old_sha1;\n \n+\t\t/* we want to store peeled refs by the base ref name in the\n+\t\t * peeled_refs string list */\n \t\tif (!strcmp(ref_name + ref_name_len - 3, \"^{}\")) {\n \t\t\tref_name[ref_name_len - 3] = 0;\n-\t\t\ttag_ref = transport_get_remote_refs(transport);\n-\t\t\twhile (tag_ref) {\n-\t\t\t\tif (!strcmp(tag_ref->name, ref_name)) {\n-\t\t\t\t\tref_sha1 = tag_ref->old_sha1;\n-\t\t\t\t\tbreak;\n-\t\t\t\t}\n-\t\t\t\ttag_ref = tag_ref->next;\n-\t\t\t}\n+\t\t\trefs = &peeled_refs;\n \t\t}\n \n-\t\tif (!string_list_has_string(&existing_refs, ref_name) &&\n-\t\t !string_list_has_string(&new_refs, ref_name) &&\n-\t\t (has_sha1_file(ref->old_sha1) ||\n-\t\t will_fetch(head, ref->old_sha1))) {\n-\t\t\tstring_list_insert(ref_name, &new_refs);\n-\n-\t\t\trm = alloc_ref(ref_name);\n-\t\t\trm->peer_ref = alloc_ref(ref_name);\n-\t\t\thashcpy(rm->old_sha1, ref_sha1);\n-\n-\t\t\t**tail = rm;\n-\t\t\t*tail = &rm->next;\n+\t\t/* ignore refs that we already have */\n+\t\tif (!string_list_has_string(&existing_refs, ref_name)) {\n+\t\t\titem = string_list_insert(ref_name, refs);\n+\t\t\titem->util = (void *)ref->old_sha1;\n \t\t}\n+\n \t\tfree(ref_name);\n \t}\n+\n+\t/* For all the tags in the remote_refs string list, call add_to_tail to\n+\t * add them to the list of refs to be fetched */\n+\tfor_each_string_list(add_to_tail, &remote_refs, &data);\n+\n \tstring_list_clear(&existing_refs, 0);\n-\tstring_list_clear(&new_refs, 0);\n+\tstring_list_clear(&peeled_refs, 0);\n+\tstring_list_clear(&remote_refs, 0);\n }\n \n static void check_not_current_branch(struct ref *ref_map)\n-- \n1.6.4.2\n"},{"id":"123386","messageId":"20090916230350.GC14660@spearce.org","threadId":"20964","inReplyTo":"7vtyz2wlhm.fsf@alter.siamese.dyndns.org","subject":"Re: [RFC/PATCH 0/2] Speed up fetch with large number of tags","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2009-09-16T23:03:50Z","receivedAt":"2009-09-16T23:03:50Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano wrote:\n> \"Shawn O. Pearce\" writes:\n> \n> > JGit depends on the fact that the refs list is sorted by the remote\n> > peer, and that foo^{} immediately follows foo. I don't think this\n> > has ever been documented, but all sane implementations[1] follow\n> > this convention and it may be something we could simply codify as\n> > part of the protocol standard.\n> >\n> > [1] Sane implementations are defined to be what I consider to be\n> > the two stable implementations in deployed use, git.git and JGit.\n> \n> There is no strong reason for ordering of refs between themselves\n> (i.e. refs/heads/master comes before refs/heads/next) other than the fact\n> that we sort and then walk due to packed-refs reasons.\n\nSorry, I misspoke a bit above.\n\nJGit does not care about the ordering between two refs, e.g. in your\nmaster/next example above JGit would accept them in either order\njust fine. Internally we enforce this by hashing the advertised\nrefs and walking the hash, callers presenting the data for a user\nmust copy to a list and sort by their desired sorting criteria\n(usually name).\n\nWhat I meant to say was this:\n \n> But emitting tag X and then its peeled representation X^{} immediately\n> after it is quite fundamental in the way how anybody sane would implement\n> ls-remote. There is no reason to violate the established order other than\n> \"I could do so\", and in order not to show X and X^{} next to each other,\n> you would need _more_ processing.\n\nand right, explicitly placing X^{} away from X means that the sender\nhas to do more work to buffer one of the two values and then show\nthem later. This is pointless other than to piss off any more\nreasonable implementor.\n\nI think we should formalize this rule of X^{} immediately follows\nX if peeling is possible, and if not, then X^{} must not appear.\nWe already have a similar rule with packed-refs, although there it\nis absolutely required by the format.\n\n> Also, you might not have noticed, but my illustration patch was merely\n> using it as a hint to optimize, and if the last ref we saw was not X when\n> it is turn to handle X^{}, it simply falled back to the original logic,\n> iow, the patch never compromised the correctness.\n\nOh, I missed that. JGit I think flat out panics and disconnects\nif the remote does this to us. What is the incentive in supporting\na broken server with a slower client?\n\n-- \nShawn.\n"},{"id":"123388","messageId":"7veiq6wkfu.fsf@alter.siamese.dyndns.org","threadId":"20964","inReplyTo":"20090916225350.45746.85139.julian@quantumfyre.co.uk","subject":"Re: [RFC/PATCH v2] fetch: Speed up fetch by rewriting find_non_local_tags","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-09-16T23:15:17Z","receivedAt":"2009-09-16T23:15:17Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Julian Phillips writes:\n\n> When trying to get a list of remote tags to see if we need to fetch\n> any we were doing a linear search for the matching tag ref for the\n> tag^{} commit entries. This proves to be incredibly slow for large\n> numbers of tags. Rewrite the function so that we can do lookup in\n> string_lists instead.\n>\n> For a repository with 50000 tags (and just a single commit on a single\n> branch), a fetch that does nothing goes from ~ 1m50s to ~4.2s.\n>\n> Signed-off-by: Julian Phillips \n> ---\n>\n> Not only does this not require a custom hash table, it is also slightly\n> faster than the last version (~4.2s vs ~4.5s).\n\nI am just curious. How would a \"just one item lookbehind\" code perform\ncompared to this one?\n"},{"id":"123389","messageId":"7vab0uwk8w.fsf@alter.siamese.dyndns.org","threadId":"20964","inReplyTo":"20090916230350.GC14660@spearce.org","subject":"Re: [RFC/PATCH 0/2] Speed up fetch with large number of tags","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-09-16T23:19:27Z","receivedAt":"2009-09-16T23:19:27Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Shawn O. Pearce\" writes:\n\n>> Also, you might not have noticed, but my illustration patch was merely\n>> using it as a hint to optimize, and if the last ref we saw was not X when\n>> it is turn to handle X^{}, it simply falled back to the original logic,\n>> iow, the patch never compromised the correctness.\n>\n> Oh, I missed that. JGit I think flat out panics and disconnects\n> if the remote does this to us. What is the incentive in supporting\n> a broken server with a slower client?\n\nThere is none.\n\nI think the original logic, being written in shell, run grep in the\noutput, and the C code we are seeing is a literal translation of that.\n\nIn other words, I think it is simply a historical accident.\n"},{"id":"123393","messageId":"alpine.LNX.2.00.0909170039410.14993@reaper.quantumfyre.co.uk","threadId":"20964","inReplyTo":"7veiq6wkfu.fsf@alter.siamese.dyndns.org","subject":"Re: [RFC/PATCH v2] fetch: Speed up fetch by rewriting find_non_local_tags","fromName":"Julian Phillips","fromEmail":"julian@quantumfyre.co.uk","sentAt":"2009-09-16T23:46:02Z","receivedAt":"2009-09-16T23:46:02Z","isPatch":true,"sender":{"key":"julian@quantumfyre.co.uk","avatar":"https://avatars.githubusercontent.com/u/948888?v=4"},"body":"On Wed, 16 Sep 2009, Junio C Hamano wrote:\n\n> Julian Phillips writes:\n>\n>> When trying to get a list of remote tags to see if we need to fetch\n>> any we were doing a linear search for the matching tag ref for the\n>> tag^{} commit entries. This proves to be incredibly slow for large\n>> numbers of tags. Rewrite the function so that we can do lookup in\n>> string_lists instead.\n>>\n>> For a repository with 50000 tags (and just a single commit on a single\n>> branch), a fetch that does nothing goes from ~ 1m50s to ~4.2s.\n>>\n>> Signed-off-by: Julian Phillips \n>> ---\n>>\n>> Not only does this not require a custom hash table, it is also slightly\n>> faster than the last version (~4.2s vs ~4.5s).\n>\n> I am just curious. How would a \"just one item lookbehind\" code perform\n> compared to this one?\n\nThe code you wrote ealier is almost the same as the string_list version, \n~4.3s, so very marginally slower but a lot less code change. Personally \nI'd be happy with any of the three, so long as I don't have to wait 30s to \nfind out that nothing's happened at $dayjob anymore ;)\n\n-- \nJulian\n\n ---\nQOTD:\n \tIf it's too loud, you're too old.\n"},{"id":"123397","messageId":"alpine.LNX.2.00.0909170227160.15719@reaper.quantumfyre.co.uk","threadId":"20964","inReplyTo":"alpine.LNX.2.00.0909170039410.14993@reaper.quantumfyre.co.uk","subject":"Re: [RFC/PATCH v2] fetch: Speed up fetch by rewriting find_non_local_tags","fromName":"Julian Phillips","fromEmail":"julian@quantumfyre.co.uk","sentAt":"2009-09-17T01:30:38Z","receivedAt":"2009-09-17T01:30:38Z","isPatch":true,"sender":{"key":"julian@quantumfyre.co.uk","avatar":"https://avatars.githubusercontent.com/u/948888?v=4"},"body":"On Thu, 17 Sep 2009, Julian Phillips wrote:\n\n> On Wed, 16 Sep 2009, Junio C Hamano wrote:\n>\n>> I am just curious. How would a \"just one item lookbehind\" code perform\n>> compared to this one?\n>\n> The code you wrote ealier is almost the same as the string_list version, \n> ~ 4.3s, so very marginally slower but a lot less code change. Personally \n> I'd be happy with any of the three, so long as I don't have to wait 30s to \n> find out that nothing's happened at $dayjob anymore ;)\n\nFWIW: I've Just modified my v2 patch to make use of the requirement that \nthe peeled ref immediately follow the base ref, and it's now ~4.1s and \nshould use less memory than the original too. I won't bother posting it \nunless someone thinks it worth it though.\n\n-- \nJulian\n\n ---\nTaxes, n.:\n \tOf life's two certainties, the only one for which you can get\n \tan extension.\n"},{"id":"123415","messageId":"200909170913.03639.johan@herland.net","threadId":"20964","inReplyTo":"alpine.LNX.2.00.0909170227160.15719@reaper.quantumfyre.co.uk","subject":"Re: [RFC/PATCH v2] fetch: Speed up fetch by rewriting find_non_local_tags","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2009-09-17T07:13:03Z","receivedAt":"2009-09-17T07:13:03Z","isPatch":true,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"On Thursday 17 September 2009, Julian Phillips wrote:\n> On Thu, 17 Sep 2009, Julian Phillips wrote:\n> > On Wed, 16 Sep 2009, Junio C Hamano wrote:\n> >> I am just curious. How would a \"just one item lookbehind\" code\n> >> perform compared to this one?\n> >\n> > The code you wrote ealier is almost the same as the string_list\n> > version, ~ 4.3s, so very marginally slower but a lot less code change. \n> > Personally I'd be happy with any of the three, so long as I don't have\n> > to wait 30s to find out that nothing's happened at $dayjob anymore ;)\n> \n> FWIW: I've Just modified my v2 patch to make use of the requirement that\n> the peeled ref immediately follow the base ref, and it's now ~4.1s and\n> should use less memory than the original too. I won't bother posting it\n> unless someone thinks it worth it though.\n\nIt's worth it. :)\n\n\n...Johan\n\n\n-- \nJohan Herland, \nwww.herland.net\n"},{"id":"123422","messageId":"20090917073320.58452.41718.julian@quantumfyre.co.uk","threadId":"20964","inReplyTo":"200909170913.03639.johan@herland.net","subject":"[RFC/PATCH v3] fetch: Speed up fetch by rewriting find_non_local_tags","fromName":"Julian Phillips","fromEmail":"julian@quantumfyre.co.uk","sentAt":"2009-09-17T07:33:19Z","receivedAt":"2009-09-17T07:33:19Z","isPatch":true,"sender":{"key":"julian@quantumfyre.co.uk","avatar":"https://avatars.githubusercontent.com/u/948888?v=4"},"body":"When trying to get a list of remote tags to see if we need to fetch\nany we were doing a linear search for the matching tag ref for the\ntag^{} commit entries. This proves to be incredibly slow for large\nnumbers of tags. Rewrite the function so that we build up a\nstring_list of refs to fetch and then process that instead.\n\nAs an extreme example, for a repository with 50000 tags (and just a\nsingle commit on a single branch), a fetch that does nothing goes from\n~1m50s to ~4.1s.\n\nSigned-off-by: Julian Phillips \n---\n\nOk, so here it is ...\n\nSometimes I forget just much we git users value our time and resources.\n;)\n\n builtin-fetch.c | 98 ++++++++++++++++++++++++++++++++++++------------------\n 1 files changed, 65 insertions(+), 33 deletions(-)\n\ndiff --git a/builtin-fetch.c b/builtin-fetch.c\nindex cb48c57..acb08e4 100644\n--- a/builtin-fetch.c\n+++ b/builtin-fetch.c\n@@ -504,57 +504,89 @@ static int will_fetch(struct ref **head, const unsigned char *sha1)\n \treturn 0;\n }\n \n+struct tag_data {\n+\tstruct ref **head;\n+\tstruct ref ***tail;\n+};\n+\n+static int add_to_tail(struct string_list_item *item, void *cb_data)\n+{\n+\tstruct tag_data *data = (struct tag_data *)cb_data;\n+\tstruct ref *rm = NULL;\n+\n+\t/* We have already decided to ignore this item */\n+\tif (!item->util)\n+\t\treturn 0;\n+\n+\trm = alloc_ref(item->string);\n+\trm->peer_ref = alloc_ref(item->string);\n+\thashcpy(rm->old_sha1, item->util);\n+\n+\t**data->tail = rm;\n+\t*data->tail = &rm->next;\n+\n+\treturn 0;\n+}\n+\n static void find_non_local_tags(struct transport *transport,\n \t\t\tstruct ref **head,\n \t\t\tstruct ref ***tail)\n {\n \tstruct string_list existing_refs = { NULL, 0, 0, 0 };\n-\tstruct string_list new_refs = { NULL, 0, 0, 1 };\n-\tchar *ref_name;\n-\tint ref_name_len;\n-\tconst unsigned char *ref_sha1;\n-\tconst struct ref *tag_ref;\n-\tstruct ref *rm = NULL;\n+\tstruct string_list remote_refs = { NULL, 0, 0, 0 };\n+\tstruct tag_data data = {head, tail};\n \tconst struct ref *ref;\n+\tstruct string_list_item *item = NULL;\n \n \tfor_each_ref(add_existing, &existing_refs);\n \tfor (ref = transport_get_remote_refs(transport); ref; ref = ref->next) {\n \t\tif (prefixcmp(ref->name, \"refs/tags\"))\n \t\t\tcontinue;\n \n-\t\tref_name = xstrdup(ref->name);\n-\t\tref_name_len = strlen(ref_name);\n-\t\tref_sha1 = ref->old_sha1;\n-\n-\t\tif (!strcmp(ref_name + ref_name_len - 3, \"^{}\")) {\n-\t\t\tref_name[ref_name_len - 3] = 0;\n-\t\t\ttag_ref = transport_get_remote_refs(transport);\n-\t\t\twhile (tag_ref) {\n-\t\t\t\tif (!strcmp(tag_ref->name, ref_name)) {\n-\t\t\t\t\tref_sha1 = tag_ref->old_sha1;\n-\t\t\t\t\tbreak;\n-\t\t\t\t}\n-\t\t\t\ttag_ref = tag_ref->next;\n-\t\t\t}\n+\t\t/* the peeled ref always follows the matching base ref, so if we\n+\t\t * see a peeled ref that we don't want to fetch then we can mark\n+\t\t * the ref entry in the list as one to ignore by setting util to\n+\t\t * NULL. */\n+\t\tif (!strcmp(ref->name + strlen(ref->name) - 3, \"^{}\")) {\n+\t\t\tif (item && !has_sha1_file(ref->old_sha1) &&\n+\t\t\t !will_fetch(head, ref->old_sha1) &&\n+\t\t\t !has_sha1_file(item->util) &&\n+\t\t\t !will_fetch(head, item->util) )\n+\t\t\t\titem->util = NULL;\n+\t\t\titem = NULL;\n+\t\t\tcontinue;\n \t\t}\n \n-\t\tif (!string_list_has_string(&existing_refs, ref_name) &&\n-\t\t !string_list_has_string(&new_refs, ref_name) &&\n-\t\t (has_sha1_file(ref->old_sha1) ||\n-\t\t will_fetch(head, ref->old_sha1))) {\n-\t\t\tstring_list_insert(ref_name, &new_refs);\n+\t\t/* If item is non-NULL here, then we previously saw a ref not\n+\t\t * followed by a peeled reference, so we need to check if it is\n+\t\t * a lightweight tag that we want to fetch */\n+\t\tif (item && !has_sha1_file(item->util) &&\n+\t\t !will_fetch(head, item->util) )\n+\t\t\titem->util = NULL;\n \n-\t\t\trm = alloc_ref(ref_name);\n-\t\t\trm->peer_ref = alloc_ref(ref_name);\n-\t\t\thashcpy(rm->old_sha1, ref_sha1);\n+\t\titem = NULL;\n \n-\t\t\t**tail = rm;\n-\t\t\t*tail = &rm->next;\n-\t\t}\n-\t\tfree(ref_name);\n+\t\t/* skip duplicates and refs that we already have */\n+\t\tif (string_list_has_string(&remote_refs, ref->name) ||\n+\t\t string_list_has_string(&existing_refs, ref->name))\n+\t\t\tcontinue;\n+\n+\t\titem = string_list_insert(ref->name, &remote_refs);\n+\t\titem->util = (void *)ref->old_sha1;\n \t}\n \tstring_list_clear(&existing_refs, 0);\n-\tstring_list_clear(&new_refs, 0);\n+\n+\t/* We may have a final lightweight tag that needs to be checked to see\n+\t * if it needs fetching. */\n+\tif (item && !has_sha1_file(item->util) &&\n+\t !will_fetch(head, item->util) )\n+\t\titem->util = NULL;\n+\n+\t/* For all the tags in the remote_refs string list, call add_to_tail to\n+\t * add them to the list of refs to be fetched */\n+\tfor_each_string_list(add_to_tail, &remote_refs, &data);\n+\n+\tstring_list_clear(&remote_refs, 0);\n }\n \n static void check_not_current_branch(struct ref *ref_map)\n-- \n1.6.4.2\n"},{"id":"123649","messageId":"7viqfapvhz.fsf@alter.siamese.dyndns.org","threadId":"20964","inReplyTo":"20090916224651.GA15259@spearce.org","subject":"Re: [RFC/PATCH 0/2] Speed up fetch with large number of tags","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-09-22T20:36:24Z","receivedAt":"2009-09-22T20:36:24Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Shawn O. Pearce\" writes:\n\n> Junio C Hamano wrote:\n>> A few questions (not criticisms).\n>> \n>> * 1m50s to 4.5s is quite impressive, even if it is only in a repository\n>> with unusual refs-vs-commits ratio, but I personally think 10 refs per\n>> every commit is already on the borderline of being insane, and the\n>> normal ratio would be more like 1 refs per every 10-20 commits.\n>\n> Under Gerrit Code Review it is normaly to have 2-5 refs per commit,\n> every iteration of a patch is held as a commit and anchored by a\n> unique ref.\n>\n> So we're borderline insane. :-)\n\nHeh, that's way below 10 refs per commit, isn't it?\n"}]}