{"thread":{"id":"6366","subject":"[PATCH 2/4] Hash tags by commit SHA1 in git-describe.","startedAt":"2007-01-13T22:28:16Z","lastAt":"2007-01-14T23:19:37Z","messageCount":8,"participants":["Shawn O. Pearce","Johannes Schindelin","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":4},"messages":[{"id":"31661","messageId":"20070113222816.GB18011@spearce.org","threadId":"6366","inReplyTo":"8e29bab8b4b9f53cbdc85e6e783bf3b5d3787f0f.1168727248.git.spearce@spearce.org","subject":"[PATCH 2/4] Hash tags by commit SHA1 in git-describe.","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-01-13T22:28:16Z","receivedAt":"2007-01-13T22:28:16Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"If a project has a very large number of tags then git-describe\nwill spend a good part of its time looping over the tags testing\nthem one at a time to determine if it matches a given commit.\nFor 10 tags this is not a big deal, but for hundreds of tags the\ntime could become considerable if we don't find an exact match for\nthe input commit and we need to walk back along the history chain.\n\nSigned-off-by: Shawn O. Pearce <spearce@spearce.org>\n---\n builtin-describe.c |   29 +++++++++++++++++------------\n 1 files changed, 17 insertions(+), 12 deletions(-)\n\ndiff --git a/builtin-describe.c b/builtin-describe.c\nindex ad672aa..582ef02 100644\n--- a/builtin-describe.c\n+++ b/builtin-describe.c\n@@ -12,20 +12,20 @@ static const char describe_usage[] =\n \n static int all;\t/* Default to annotated tags only */\n static int tags;\t/* But allow any tags if --tags is specified */\n-\n static int abbrev = DEFAULT_ABBREV;\n \n-static int names, allocs;\n+static unsigned int names[256], allocs[256];\n static struct commit_name {\n \tstruct commit *commit;\n \tint prio; /* annotated tag = 2, tag = 1, head = 0 */\n \tchar path[FLEX_ARRAY]; /* more */\n-} **name_array = NULL;\n+} **name_array[256];\n \n static struct commit_name *match(struct commit *cmit)\n {\n-\tint i = names;\n-\tstruct commit_name **p = name_array;\n+\tunsigned char m = cmit->object.sha1[0];\n+\tunsigned int i = names[m];\n+\tstruct commit_name **p = name_array[m];\n \n \twhile (i-- > 0) {\n \t\tstruct commit_name *n = *p++;\n@@ -42,17 +42,19 @@ static void add_to_known_names(const char *path,\n \tint idx;\n \tint len = strlen(path)+1;\n \tstruct commit_name *name = xmalloc(sizeof(struct commit_name) + len);\n+\tunsigned char m = commit->object.sha1[0];\n \n \tname->commit = commit;\n \tname->prio = prio;\n \tmemcpy(name->path, path, len);\n-\tidx = names;\n-\tif (idx >= allocs) {\n-\t\tallocs = (idx + 50) * 3 / 2;\n-\t\tname_array = xrealloc(name_array, allocs*sizeof(*name_array));\n+\tidx = names[m];\n+\tif (idx >= allocs[m]) {\n+\t\tallocs[m] = (idx + 50) * 3 / 2;\n+\t\tname_array[m] = xrealloc(name_array[m],\n+\t\t\tallocs[m] * sizeof(*name_array));\n \t}\n-\tname_array[idx] = name;\n-\tnames = ++idx;\n+\tname_array[m][idx] = name;\n+\tnames[m] = ++idx;\n }\n \n static int get_name(const char *path, const unsigned char *sha1, int flag, void *cb_data)\n@@ -121,9 +123,12 @@ static void describe(const char *arg, int last_one)\n \t\tdie(\"%s is not a valid '%s' object\", arg, commit_type);\n \n \tif (!initialized) {\n+\t\tunsigned int m;\n \t\tinitialized = 1;\n \t\tfor_each_ref(get_name, NULL);\n-\t\tqsort(name_array, names, sizeof(*name_array), compare_names);\n+\t\tfor (m = 0; m < ARRAY_SIZE(name_array); m++)\n+\t\t\tqsort(name_array[m], names[m],\n+\t\t\t\tsizeof(*name_array[m]), compare_names);\n \t}\n \n \tn = match(cmit);\n-- \n1.5.0.rc1.g4494\n"},{"id":"31662","messageId":"20070113222900.GC18011@spearce.org","threadId":"6366","inReplyTo":"8e29bab8b4b9f53cbdc85e6e783bf3b5d3787f0f.1168727248.git.spearce@spearce.org","subject":"[PATCH 3/4] Use binary searching on large buckets in git-describe.","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-01-13T22:29:00Z","receivedAt":"2007-01-13T22:29:00Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"If a project has a really huge number of tags (such as several\nthousand tags) then we are likely to have nearly a hundred tags in\nsome buckets.  Scanning those buckets as linked lists could take\na large amount of time if done repeatedly during history traversal.\n\nSince we are searching for a unique commit SHA1 we can sort all\ntags by commit SHA1 and perform a binary search within the bucket.\nOnce we identify a particular tag as matching this commit we walk\nbackwards within the bucket matches to make sure we pick up the\nhighest priority tag for that commit, as the binary search may\nhave landed us in the middle of a set of tags which point at the\nsame commit.\n\nSigned-off-by: Shawn O. Pearce <spearce@spearce.org>\n---\n builtin-describe.c |   29 +++++++++++++++++++++--------\n 1 files changed, 21 insertions(+), 8 deletions(-)\n\ndiff --git a/builtin-describe.c b/builtin-describe.c\nindex 582ef02..5d6865b 100644\n--- a/builtin-describe.c\n+++ b/builtin-describe.c\n@@ -23,14 +23,24 @@ static struct commit_name {\n \n static struct commit_name *match(struct commit *cmit)\n {\n-\tunsigned char m = cmit->object.sha1[0];\n-\tunsigned int i = names[m];\n-\tstruct commit_name **p = name_array[m];\n-\n-\twhile (i-- > 0) {\n-\t\tstruct commit_name *n = *p++;\n-\t\tif (n->commit == cmit)\n-\t\t\treturn n;\n+\tunsigned char level0 = cmit->object.sha1[0];\n+\tstruct commit_name **p = name_array[level0];\n+\tunsigned int hi = names[level0];\n+\tunsigned int lo = 0;\n+\n+\twhile (lo < hi) {\n+\t\tunsigned int mi = (lo + hi) / 2;\n+\t\tint cmp = hashcmp(p[mi]->commit->object.sha1,\n+\t\t\tcmit->object.sha1);\n+\t\tif (!cmp) {\n+\t\t\twhile (mi && p[mi - 1]->commit == cmit)\n+\t\t\t\tmi--;\n+\t\t\treturn p[mi];\n+\t\t}\n+\t\tif (cmp > 0)\n+\t\t\thi = mi;\n+\t\telse\n+\t\t\tlo = mi+1;\n \t}\n \treturn NULL;\n }\n@@ -95,7 +105,10 @@ static int compare_names(const void *_a, const void *_b)\n \tstruct commit_name *b = *(struct commit_name **)_b;\n \tunsigned long a_date = a->commit->date;\n \tunsigned long b_date = b->commit->date;\n+\tint cmp = hashcmp(a->commit->object.sha1, b->commit->object.sha1);\n \n+\tif (cmp)\n+\t\treturn cmp;\n \tif (a->prio != b->prio)\n \t\treturn b->prio - a->prio;\n \treturn (a_date > b_date) ? -1 : (a_date == b_date) ? 0 : 1;\n-- \n1.5.0.rc1.g4494\n"},{"id":"31663","messageId":"20070113223053.GD18011@spearce.org","threadId":"6366","inReplyTo":"8e29bab8b4b9f53cbdc85e6e783bf3b5d3787f0f.1168727248.git.spearce@spearce.org","subject":"[PATCH 4/4] Improve git-describe performance by reducing revision listing.","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-01-13T22:30:53Z","receivedAt":"2007-01-13T22:30:53Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"My prior version of git-describe ran very slowly on even reasonably\nsized projects like git.git and linux.git as it tended to identify\na large number of possible tags and then needed to generate the\nrevision list for each of those tags to sort them and select the\nbest tag to describe the input commit.\n\nAll we really need is the number of commits in the input revision\nwhich are not in the tag.  We can generate these counts during\nthe revision walking and tag matching loop by assigning a color to\neach tag and coloring the commits as we walk them.  This limits us\nto identifying no more than 26 possible tags, as there is limited\nspace available within the flags field of struct commit.\n\nThe limitation of 26 possible tags is hopefully not going to be a\nproblem in real usage, as most projects won't create 26 maintenance\nreleases and merge them back into a development trunk after the\ndevelopment trunk was tagged with a release candidate tag.  If that\ndoes occur git-describe will start to revert to its old behavior of\nusing the newer maintenance release tag to describe the development\ntrunk, rather than the development trunk's own tag.  The suggested\nworkaround would be to retag the development trunk's tip.\n\nHowever since even 26 possible tags can take a while to generate a\ndescription for on some projects I'm defaulting the limit to 10 but\noffering the user --candidates to increase the number of possible\nmatches if they need a more accurate result.  I specifically chose\n10 for the default as it seems unlikely projects will have more\nthan 10 maintenance releases merged into a development trunk before\nretagging the development trunk, and it seems to perform about the\nsame on linux.git as v1.4.4.4 git-describe.\n\nA large amount of debugging information was also added during\nthe development of this change, so I've left it in to be toggled\non with --debug.  It may be useful to the end user to help them\nunderstand why git-describe took one particular tag over another.\n\nSigned-off-by: Shawn O. Pearce <spearce@spearce.org>\n---\n\n Junio C Hamano <junkio@cox.net> wrote:\n > This actually is QUITE bad.\n > \n > With the tip of linux-2.6 repository, v1.4.4 series takes 0.03s\n > while v1.5.0-rc1 takes about 3.6s.  That is 100x fold, not just 4x.\n\n This should restore git-describe to taking 0.03s on your system,\n yet get us 10 tag accuracy.  It is running close to even with\n 1.4.4.4's git-describe on my system.\n\n Documentation/git-describe.txt |   30 ++++++++++\n builtin-describe.c             |  125 ++++++++++++++++++++++++----------------\n 2 files changed, 106 insertions(+), 49 deletions(-)\n\ndiff --git a/Documentation/git-describe.txt b/Documentation/git-describe.txt\nindex 2700f35..b87783c 100644\n--- a/Documentation/git-describe.txt\n+++ b/Documentation/git-describe.txt\n@@ -35,6 +35,16 @@ OPTIONS\n \tInstead of using the default 8 hexadecimal digits as the\n \tabbreviated object name, use <n> digits.\n \n+--candidates=<n>::\n+\tInstead of considering only the 10 most recent tags as\n+\tcandidates to describe the input committish consider\n+\tup to <n> candidates.  Increasing <n> above 10 will take\n+\tslightly longer but may produce a more accurate result.\n+\n+--debug::\n+\tVerbosely display information about the searching strategy\n+\tbeing employed to standard error.  The tag name will still\n+\tbe printed to standard out.\n \n EXAMPLES\n --------\n@@ -63,6 +73,26 @@ the output shows the reference path as well:\n \t[torvalds@g5 git]$ git describe --all HEAD^\n \theads/lt/describe-g975b\n \n+SEARCH STRATEGY\n+---------------\n+\n+For each committish supplied \"git describe\" will first look for\n+a tag which tags exactly that commit.  Annotated tags will always\n+be preferred over lightweight tags, and tags with newer dates will\n+always be preferred over tags with older dates.  If an exact match\n+is found, its name will be output and searching will stop.\n+\n+If an exact match was not found \"git describe\" will walk back\n+through the commit history to locate an ancestor commit which\n+has been tagged.  The ancestor's tag will be output along with an\n+abbreviation of the input committish's SHA1.\n+\n+If multiple tags were found during the walk then the tag which\n+has the fewest commits different from the input committish will be\n+selected and output.  Here fewest commits different is defined as\n+the number of commits which would be shown by \"git log tag..input\"\n+will be the smallest number of commits possible.\n+\n \n Author\n ------\ndiff --git a/builtin-describe.c b/builtin-describe.c\nindex 5d6865b..421658d 100644\n--- a/builtin-describe.c\n+++ b/builtin-describe.c\n@@ -2,17 +2,19 @@\n #include \"commit.h\"\n #include \"tag.h\"\n #include \"refs.h\"\n-#include \"diff.h\"\n-#include \"diffcore.h\"\n-#include \"revision.h\"\n #include \"builtin.h\"\n \n+#define SEEN\t\t(1u<<0)\n+#define MAX_TAGS\t(FLAG_BITS - 1)\n+\n static const char describe_usage[] =\n \"git-describe [--all] [--tags] [--abbrev=<n>] <committish>*\";\n \n+static int debug;\t/* Display lots of verbose info */\n static int all;\t/* Default to annotated tags only */\n static int tags;\t/* But allow any tags if --tags is specified */\n static int abbrev = DEFAULT_ABBREV;\n+static int max_candidates = 10;\n \n static unsigned int names[256], allocs[256];\n static struct commit_name {\n@@ -115,19 +117,21 @@ static int compare_names(const void *_a, const void *_b)\n }\n \n struct possible_tag {\n-\tstruct possible_tag *next;\n \tstruct commit_name *name;\n \tunsigned long depth;\n+\tunsigned flag_within;\n };\n \n static void describe(const char *arg, int last_one)\n {\n \tunsigned char sha1[20];\n-\tstruct commit *cmit;\n+\tstruct commit *cmit, *gave_up_on = NULL;\n \tstruct commit_list *list;\n \tstatic int initialized = 0;\n \tstruct commit_name *n;\n-\tstruct possible_tag *all_matches, *min_match, *cur_match;\n+\tstruct possible_tag all_matches[MAX_TAGS], *min_match;\n+\tunsigned int match_cnt = 0, annotated_cnt = 0, cur_match;\n+\tunsigned long seen_commits = 0;\n \n \tif (get_sha1(arg, sha1))\n \t\tdie(\"Not a valid object name %s\", arg);\n@@ -150,71 +154,85 @@ static void describe(const char *arg, int last_one)\n \t\treturn;\n \t}\n \n+\tif (debug)\n+\t\tfprintf(stderr, \"searching to describe %s\\n\", arg);\n+\n \tlist = NULL;\n-\tall_matches = NULL;\n-\tcur_match = NULL;\n+\tcmit->object.flags = SEEN;\n \tcommit_list_insert(cmit, &list);\n \twhile (list) {\n \t\tstruct commit *c = pop_commit(&list);\n \t\tstruct commit_list *parents = c->parents;\n+\t\tseen_commits++;\n \t\tn = match(c);\n \t\tif (n) {\n-\t\t\tstruct possible_tag *p = xmalloc(sizeof(*p));\n-\t\t\tp->name = n;\n-\t\t\tp->next = NULL;\n-\t\t\tif (cur_match)\n-\t\t\t\tcur_match->next = p;\n-\t\t\telse\n-\t\t\t\tall_matches = p;\n-\t\t\tcur_match = p;\n-\t\t\tif (n->prio == 2)\n-\t\t\t\tcontinue;\n+\t\t\tif (match_cnt < max_candidates) {\n+\t\t\t\tstruct possible_tag *t = &all_matches[match_cnt++];\n+\t\t\t\tt->name = n;\n+\t\t\t\tt->depth = seen_commits - 1;\n+\t\t\t\tt->flag_within = 1u << match_cnt;\n+\t\t\t\tc->object.flags |= t->flag_within;\n+\t\t\t\tif (n->prio == 2)\n+\t\t\t\t\tannotated_cnt++;\n+\t\t\t}\n+\t\t\telse {\n+\t\t\t\tgave_up_on = c;\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t}\n+\t\tfor (cur_match = 0; cur_match < match_cnt; cur_match++) {\n+\t\t\tstruct possible_tag *t = &all_matches[cur_match];\n+\t\t\tif (!(c->object.flags & t->flag_within))\n+\t\t\t\tt->depth++;\n+\t\t}\n+\t\tif (annotated_cnt && !list) {\n+\t\t\tif (debug)\n+\t\t\t\tfprintf(stderr, \"finished search at %s\\n\",\n+\t\t\t\t\tsha1_to_hex(c->object.sha1));\n+\t\t\tbreak;\n \t\t}\n \t\twhile (parents) {\n \t\t\tstruct commit *p = parents->item;\n \t\t\tparse_commit(p);\n-\t\t\tif (!(p->object.flags & SEEN)) {\n-\t\t\t\tp->object.flags |= SEEN;\n+\t\t\tif (!(p->object.flags & SEEN))\n \t\t\t\tinsert_by_date(p, &list);\n-\t\t\t}\n+\t\t\tp->object.flags |= c->object.flags;\n \t\t\tparents = parents->next;\n \t\t}\n \t}\n+\tfree_commit_list(list);\n \n-\tif (!all_matches)\n+\tif (!match_cnt)\n \t\tdie(\"cannot describe '%s'\", sha1_to_hex(cmit->object.sha1));\n \n-\tmin_match = NULL;\n-\tfor (cur_match = all_matches; cur_match; cur_match = cur_match->next) {\n-\t\tstruct rev_info revs;\n-\t\tstruct commit *tagged = cur_match->name->commit;\n-\n-\t\tclear_commit_marks(cmit, -1);\n-\t\tinit_revisions(&revs, NULL);\n-\t\ttagged->object.flags |= UNINTERESTING;\n-\t\tadd_pending_object(&revs, &tagged->object, NULL);\n-\t\tadd_pending_object(&revs, &cmit->object, NULL);\n-\n-\t\tprepare_revision_walk(&revs);\n-\t\tcur_match->depth = 0;\n-\t\twhile ((!min_match || cur_match->depth < min_match->depth)\n-\t\t\t&& get_revision(&revs))\n-\t\t\tcur_match->depth++;\n-\t\tif (!min_match || (cur_match->depth < min_match->depth\n-\t\t\t&& cur_match->name->prio >= min_match->name->prio))\n-\t\t\tmin_match = cur_match;\n-\t\tfree_commit_list(revs.commits);\n+\tmin_match = &all_matches[0];\n+\tfor (cur_match = 1; cur_match < match_cnt; cur_match++) {\n+\t\tstruct possible_tag *t = &all_matches[cur_match];\n+\t\tif (t->depth < min_match->depth\n+\t\t\t&& t->name->prio >= min_match->name->prio)\n+\t\t\tmin_match = t;\n+\t}\n+\tif (debug) {\n+\t\tfor (cur_match = 0; cur_match < match_cnt; cur_match++) {\n+\t\t\tstruct possible_tag *t = &all_matches[cur_match];\n+\t\t\tfprintf(stderr, \" %c %8lu %s\\n\",\n+\t\t\t\tmin_match == t ? '*' : ' ',\n+\t\t\t\tt->depth, t->name->path);\n+\t\t}\n+\t\tfprintf(stderr, \"traversed %lu commits\\n\", seen_commits);\n+\t\tif (gave_up_on) {\n+\t\t\tfprintf(stderr,\n+\t\t\t\t\"more than %i tags found; listed %i most recent\\n\"\n+\t\t\t\t\"gave up search at %s\\n\",\n+\t\t\t\tmax_candidates, max_candidates,\n+\t\t\t\tsha1_to_hex(gave_up_on->object.sha1));\n+\t\t}\n \t}\n \tprintf(\"%s-g%s\\n\", min_match->name->path,\n \t\t   find_unique_abbrev(cmit->object.sha1, abbrev));\n \n-\tif (!last_one) {\n-\t\tfor (cur_match = all_matches; cur_match; cur_match = min_match) {\n-\t\t\tmin_match = cur_match->next;\n-\t\t\tfree(cur_match);\n-\t\t}\n-\t\tclear_commit_marks(cmit, SEEN);\n-\t}\n+\tif (!last_one)\n+\t\tclear_commit_marks(cmit, -1);\n }\n \n int cmd_describe(int argc, const char **argv, const char *prefix)\n@@ -226,6 +244,8 @@ int cmd_describe(int argc, const char **argv, const char *prefix)\n \n \t\tif (*arg != '-')\n \t\t\tbreak;\n+\t\telse if (!strcmp(arg, \"--debug\"))\n+\t\t\tdebug = 1;\n \t\telse if (!strcmp(arg, \"--all\"))\n \t\t\tall = 1;\n \t\telse if (!strcmp(arg, \"--tags\"))\n@@ -235,6 +255,13 @@ int cmd_describe(int argc, const char **argv, const char *prefix)\n \t\t\tif (abbrev < MINIMUM_ABBREV || 40 < abbrev)\n \t\t\t\tabbrev = DEFAULT_ABBREV;\n \t\t}\n+\t\telse if (!strncmp(arg, \"--candidates=\", 13)) {\n+\t\t\tmax_candidates = strtoul(arg + 13, NULL, 10);\n+\t\t\tif (max_candidates < 1)\n+\t\t\t\tmax_candidates = 1;\n+\t\t\telse if (max_candidates > MAX_TAGS)\n+\t\t\t\tmax_candidates = MAX_TAGS;\n+\t\t}\n \t\telse\n \t\t\tusage(describe_usage);\n \t}\n-- \n1.5.0.rc1.g4494\n"},{"id":"31684","messageId":"Pine.LNX.4.63.0701141358440.22628@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"6366","inReplyTo":"20070113222816.GB18011@spearce.org","subject":"Re: [PATCH 2/4] Hash tags by commit SHA1 in git-describe.","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-01-14T13:01:16Z","receivedAt":"2007-01-14T13:01:16Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Sat, 13 Jan 2007, Shawn O. Pearce wrote:\n\n> If a project has a very large number of tags then git-describe\n> will spend a good part of its time looping over the tags testing\n> them one at a time to determine if it matches a given commit.\n\nWhy not just use object_refs? This also obviates the need for your patch \n3/4, since you no longer have buckets to search binarily. Plus, it uses a \nhash map, which already turned out to beat (in terms of performance) the \nhell out of bucketed lists in git history.\n\nCiao,\nDscho\n"},{"id":"31698","messageId":"7vr6txh278.fsf@assigned-by-dhcp.cox.net","threadId":"6366","inReplyTo":"Pine.LNX.4.63.0701141358440.22628@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [PATCH 2/4] Hash tags by commit SHA1 in git-describe.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-01-14T18:51:07Z","receivedAt":"2007-01-14T18:51:07Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n\n> On Sat, 13 Jan 2007, Shawn O. Pearce wrote:\n>\n>> If a project has a very large number of tags then git-describe\n>> will spend a good part of its time looping over the tags testing\n>> them one at a time to determine if it matches a given commit.\n>\n> Why not just use object_refs? This also obviates the need for your patch \n> 3/4, since you no longer have buckets to search binarily. Plus, it uses a \n> hash map, which already turned out to beat (in terms of performance) the \n> hell out of bucketed lists in git history.\n\nVery good point.\n"},{"id":"31750","messageId":"7v3b6dh19y.fsf@assigned-by-dhcp.cox.net","threadId":"6366","inReplyTo":"20070113222900.GC18011@spearce.org","subject":"Re: [PATCH 3/4] Use binary searching on large buckets in git-describe.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2007-01-14T19:11:05Z","receivedAt":"2007-01-14T19:11:05Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Shawn O. Pearce\" <spearce@spearce.org> writes:\n\n> If a project has a really huge number of tags (such as several\n> thousand tags) then we are likely to have nearly a hundred tags in\n> some buckets.  Scanning those buckets as linked lists could take\n> a large amount of time if done repeatedly during history traversal.\n\nI think this is a good idea -- but would you still need the 256\nbuckets if you do this?\n"},{"id":"31711","messageId":"20070114230721.GD10888@spearce.org","threadId":"6366","inReplyTo":"7v3b6dh19y.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH 3/4] Use binary searching on large buckets in git-describe.","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-01-14T23:07:21Z","receivedAt":"2007-01-14T23:07:21Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano <junkio@cox.net> wrote:\n> \"Shawn O. Pearce\" <spearce@spearce.org> writes:\n> \n> > If a project has a really huge number of tags (such as several\n> > thousand tags) then we are likely to have nearly a hundred tags in\n> > some buckets.  Scanning those buckets as linked lists could take\n> > a large amount of time if done repeatedly during history traversal.\n> \n> I think this is a good idea -- but would you still need the 256\n> buckets if you do this?\n\nWell, yes and no.  The binary search would make it O(log N) rather\nthan O(N), which is clearly an improvement.  But we're hashing by\nthe commit SHA1 and since SHA1 does such a good job of distributing\nvalues around we get pretty even distribution among the buckets.\nThis gets us a 1/256 reduction within each bucket, at the cost of\njust one array index operation.\n\nSince the buckets are so small (1 pointer) and the match function\nis in the critical path of describe it would seem reasonable to\ntake the small memory hit in return for better behavior on very\nlarge sets of tags.  It certainly doesn't hurt on smaller tag sets\n(like git.git), we wind up with 1 tag per bucket and our lookups\nare constant time.\n\n-- \nShawn.\n"},{"id":"31695","messageId":"20070114231937.GF10888@spearce.org","threadId":"6366","inReplyTo":"7vr6txh278.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH 2/4] Hash tags by commit SHA1 in git-describe.","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-01-14T23:19:37Z","receivedAt":"2007-01-14T23:19:37Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Junio C Hamano <junkio@cox.net> wrote:\n> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n> \n> > On Sat, 13 Jan 2007, Shawn O. Pearce wrote:\n> >\n> >> If a project has a very large number of tags then git-describe\n> >> will spend a good part of its time looping over the tags testing\n> >> them one at a time to determine if it matches a given commit.\n> >\n> > Why not just use object_refs? This also obviates the need for your patch \n> > 3/4, since you no longer have buckets to search binarily. Plus, it uses a \n> > hash map, which already turned out to beat (in terms of performance) the \n> > hell out of bucketed lists in git history.\n> \n> Very good point.\n\nOK. I didn't realize we had a better system already implemented.\nThanks for pointing it out.\n\nI'll work up a patch to replace the crude hash/list arrangement\nwith something based on object_refs instead.\n\n-- \nShawn.\n"}]}