{"thread":{"id":"25773","subject":"[PATCH] describe: Don’t look up commits with --exact-match","startedAt":"2010-11-17T23:33:06Z","lastAt":"2010-12-09T06:47:29Z","messageCount":28,"participants":["Anders Kaseorg","Jonathan Nieder","Thomas Rast","SZEDER Gábor","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"156071","messageId":"alpine.DEB.2.02.1011171830050.14285@dr-wily.mit.edu","threadId":"25773","inReplyTo":null,"subject":"[PATCH] describe: Don’t look up commits with --exact-match","fromName":"Anders Kaseorg","fromEmail":"andersk@ksplice.com","sentAt":"2010-11-17T23:33:06Z","receivedAt":"2010-11-17T23:33:06Z","isPatch":true,"sender":{"key":"andersk@mit.edu","avatar":"https://avatars.githubusercontent.com/u/26471?v=4"},"body":"This makes ‘git describe --exact-match HEAD’ about 15 times faster on\na cold cache (2.3s instead of 35s) in a linux-2.6 repository with many\npacked tags. That’s a huge win for the interactivity of the __git_ps1\nshell prompt helper.\n\nSigned-off-by: Anders Kaseorg \n---\n builtin/describe.c | 64 ++++++++++++++++++++++++++-------------------------\n 1 files changed, 33 insertions(+), 31 deletions(-)\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 43caff2..1cdb831 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -22,7 +22,7 @@ static int tags;\t/* Allow lightweight tags */\n static int longformat;\n static int abbrev = DEFAULT_ABBREV;\n static int max_candidates = 10;\n-static int found_names;\n+struct commit_name *names = NULL;\n static const char *pattern;\n static int always;\n static const char *dirty;\n@@ -34,6 +34,8 @@ static const char *diff_index_args[] = {\n \n \n struct commit_name {\n+\tstruct commit_name *next;\n+\tunsigned char peeled[20];\n \tstruct tag *tag;\n \tunsigned prio:2; /* annotated tag = 2, tag = 1, head = 0 */\n \tunsigned name_checked:1;\n@@ -78,31 +80,26 @@ static int replace_name(struct commit_name *e,\n }\n \n static void add_to_known_names(const char *path,\n-\t\t\t struct commit *commit,\n+\t\t\t const unsigned char *peeled,\n \t\t\t int prio,\n \t\t\t const unsigned char *sha1)\n {\n-\tstruct commit_name *e = commit->util;\n \tstruct tag *tag = NULL;\n-\tif (replace_name(e, prio, sha1, &tag)) {\n-\t\tsize_t len = strlen(path)+1;\n-\t\tfree(e);\n-\t\te = xmalloc(sizeof(struct commit_name) + len);\n-\t\te->tag = tag;\n-\t\te->prio = prio;\n-\t\te->name_checked = 0;\n-\t\thashcpy(e->sha1, sha1);\n-\t\tmemcpy(e->path, path, len);\n-\t\tcommit->util = e;\n-\t}\n-\tfound_names = 1;\n+\tsize_t len = strlen(path)+1;\n+\tstruct commit_name *e = xmalloc(sizeof(struct commit_name) + len);\n+\thashcpy(e->peeled, peeled);\n+\te->tag = tag;\n+\te->prio = prio;\n+\te->name_checked = 0;\n+\thashcpy(e->sha1, sha1);\n+\tmemcpy(e->path, path, len);\n+\te->next = names;\n+\tnames = e;\n }\n \n static int get_name(const char *path, const unsigned char *sha1, int flag, void *cb_data)\n {\n \tint might_be_tag = !prefixcmp(path, \"refs/tags/\");\n-\tstruct commit *commit;\n-\tstruct object *object;\n \tunsigned char peeled[20];\n \tint is_tag, prio;\n \n@@ -110,16 +107,10 @@ static int get_name(const char *path, const unsigned char *sha1, int flag, void\n \t\treturn 0;\n \n \tif (!peel_ref(path, peeled) && !is_null_sha1(peeled)) {\n-\t\tcommit = lookup_commit_reference_gently(peeled, 1);\n-\t\tif (!commit)\n-\t\t\treturn 0;\n-\t\tis_tag = !!hashcmp(sha1, commit->object.sha1);\n+\t\tis_tag = !!hashcmp(sha1, peeled);\n \t} else {\n-\t\tcommit = lookup_commit_reference_gently(sha1, 1);\n-\t\tobject = parse_object(sha1);\n-\t\tif (!commit || !object)\n-\t\t\treturn 0;\n-\t\tis_tag = object->type == OBJ_TAG;\n+\t\thashcpy(peeled, sha1);\n+\t\tis_tag = 0;\n \t}\n \n \t/* If --all, then any refs are used.\n@@ -142,7 +133,7 @@ static int get_name(const char *path, const unsigned char *sha1, int flag, void\n \t\tif (!prio)\n \t\t\treturn 0;\n \t}\n-\tadd_to_known_names(all ? path + 5 : path + 10, commit, prio, sha1);\n+\tadd_to_known_names(all ? path + 5 : path + 10, peeled, prio, sha1);\n \treturn 0;\n }\n \n@@ -228,7 +219,7 @@ static void describe(const char *arg, int last_one)\n \tunsigned char sha1[20];\n \tstruct commit *cmit, *gave_up_on = NULL;\n \tstruct commit_list *list;\n-\tstruct commit_name *n;\n+\tstruct commit_name *n, *e;\n \tstruct possible_tag all_matches[MAX_TAGS];\n \tunsigned int match_cnt = 0, annotated_cnt = 0, cur_match;\n \tunsigned long seen_commits = 0;\n@@ -240,7 +231,12 @@ static void describe(const char *arg, int last_one)\n \tif (!cmit)\n \t\tdie(\"%s is not a valid '%s' object\", arg, commit_type);\n \n-\tn = cmit->util;\n+\tn = NULL;\n+\tfor (e = names; e; e = e->next) {\n+\t\tif (hashcmp(e->peeled, cmit->object.sha1) == 0 &&\n+\t\t replace_name(n, e->prio, e->sha1, &e->tag))\n+\t\t\tn = e;\n+\t}\n \tif (n && (tags || all || n->prio == 2)) {\n \t\t/*\n \t\t * Exact match to an existing ref.\n@@ -259,6 +255,12 @@ static void describe(const char *arg, int last_one)\n \tif (debug)\n \t\tfprintf(stderr, \"searching to describe %s\\n\", arg);\n \n+\tfor (e = names; e; e = e->next) {\n+\t\tstruct commit *c = lookup_commit_reference_gently(e->peeled, 1);\n+\t\tif (c && replace_name(c->util, e->prio, e->sha1, &e->tag))\n+\t\t\tc->util = e;\n+\t}\n+\n \tlist = NULL;\n \tcmit->object.flags = SEEN;\n \tcommit_list_insert(cmit, &list);\n@@ -418,8 +420,8 @@ int cmd_describe(int argc, const char **argv, const char *prefix)\n \t\treturn cmd_name_rev(i + argc, args, prefix);\n \t}\n \n-\tfor_each_ref(get_name, NULL);\n-\tif (!found_names && !always)\n+\tfor_each_rawref(get_name, NULL);\n+\tif (!names && !always)\n \t\tdie(\"No names found, cannot describe anything.\");\n \n \tif (argc == 0) {\n-- \n1.7.3.2\n"},{"id":"157184","messageId":"20101203084348.GD18202@burratino","threadId":"25773","inReplyTo":"alpine.DEB.2.02.1011171830050.14285@dr-wily.mit.edu","subject":"Re: [PATCH] describe: Don’t look up commits with --exact-match","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2010-12-03T08:43:48Z","receivedAt":"2010-12-03T08:43:48Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"(+cc: completion people, who might test; Thomas, who knows this\ncode well)\n\nAnders Kaseorg wrote:\n\n> This makes ‘git describe --exact-match HEAD’ about 15 times faster on\n> a cold cache (2.3s instead of 35s) in a linux-2.6 repository with many\n> packed tags. That’s a huge win for the interactivity of the __git_ps1\n> shell prompt helper.\n\nNice.\n\n> --- a/builtin/describe.c\n> +++ b/builtin/describe.c\n> @@ -22,7 +22,7 @@ static int tags;\t/* Allow lightweight tags */\n> static int longformat;\n> static int abbrev = DEFAULT_ABBREV;\n> static int max_candidates = 10;\n> -static int found_names;\n> +struct commit_name *names = NULL;\n\nNits:\n - static?\n - the convention in git is to leave off the zero-initializers\n for bss-allocated vars (static and globals).\n\n> @@ -34,6 +34,8 @@ static const char *diff_index_args[] = {\n> \n> \n> struct commit_name {\n> +\tstruct commit_name *next;\n> +\tunsigned char peeled[20];\n> \tstruct tag *tag;\n> \tunsigned prio:2; /* annotated tag = 2, tag = 1, head = 0 */\n> \tunsigned name_checked:1;\n\nHm, so the tags read so far will be stored in the \"names\" list.\n\n> @@ -240,7 +231,12 @@ static void describe(const char *arg, int last_one)\n> \tif (!cmit)\n> \t\tdie(\"%s is not a valid '%s' object\", arg, commit_type);\n> \n> -\tn = cmit->util;\n> +\tn = NULL;\n> +\tfor (e = names; e; e = e->next) {\n> +\t\tif (hashcmp(e->peeled, cmit->object.sha1) == 0 &&\n\nThe usual convention is to use !hashcmp(...) to match the !strcmp(...)\nidiom.\n\n> +\t\t replace_name(n, e->prio, e->sha1, &e->tag))\n> +\t\t\tn = e;\n> +\t}\n\nInstead of looking up the commit to be matched exactly in the commits\nhash table, this makes a linear search.\n\nNo change to the assymptotic running time, but would this make things\nmuch slower in the case of many tags? How many before it's a problem\n(if ever)? (If it's a problem in ordinary cases, I think the\noptimization could be limited to --exact-match pretty easily.)\n\n> @@ -259,6 +255,12 @@ static void describe(const char *arg, int last_one)\n> \tif (debug)\n> \t\tfprintf(stderr, \"searching to describe %s\\n\", arg);\n> \n> +\tfor (e = names; e; e = e->next) {\n> +\t\tstruct commit *c = lookup_commit_reference_gently(e->peeled, 1);\n> +\t\tif (c && replace_name(c->util, e->prio, e->sha1, &e->tag))\n> +\t\t\tc->util = e;\n> +\t}\n\nFilling the commits table in preparation for object traversal. Now\nthe world's back to normal.\n\n> @@ -418,8 +420,8 @@ int cmd_describe(int argc, const char **argv, const char *prefix)\n> \t\treturn cmd_name_rev(i + argc, args, prefix);\n> \t}\n> \n> -\tfor_each_ref(get_name, NULL);\n> +\tfor_each_rawref(get_name, NULL);\n\nOrthogonal change snuck in?\n\n> -\tif (!found_names && !always)\n> +\tif (!names && !always)\n\nEverything else looks good and very readable.\n"},{"id":"157385","messageId":"alpine.DEB.2.02.1012060149550.23348@dr-wily.mit.edu","threadId":"25773","inReplyTo":"20101203084348.GD18202@burratino","subject":"Re: [PATCH] describe: Don’t look up commits with --exact-match","fromName":"Anders Kaseorg","fromEmail":"andersk@ksplice.com","sentAt":"2010-12-06T07:19:52Z","receivedAt":"2010-12-06T07:19:52Z","isPatch":true,"sender":{"key":"andersk@mit.edu","avatar":"https://avatars.githubusercontent.com/u/26471?v=4"},"body":"On Fri, 3 Dec 2010, Jonathan Nieder wrote:\n> - static?\n> - the convention in git is to leave off the zero-initializers\n> for bss-allocated vars (static and globals).\n\nWill fix.\n\n> The usual convention is to use !hashcmp(...) to match the !strcmp(...)\n> idiom.\n\nWill fix (I hate that idiom, but yeah, match existing style).\n\n> > +\tfor (e = names; e; e = e->next) {\n> > +\t\tif (!hashcmp(e->peeled, cmit->object.sha1) &&\n> > +\t\t replace_name(n, e->prio, e->sha1, &e->tag))\n> > +\t\t\tn = e;\n> > +\t}\n> \n> Instead of looking up the commit to be matched exactly in the commits\n> hash table, this makes a linear search.\n> \n> No change to the assymptotic running time, but would this make things\n> much slower in the case of many tags? How many before it's a problem\n> (if ever)?\n\nI don’t think it’s ever a problem: in my repository with 1800 tags on a \nwarm cache, that loop accounts for about 0.1% of even the fastest \nnon-exact-match query (a commit right after a tag).\n\n> (If it's a problem in ordinary cases, I think the optimization could be \n> limited to --exact-match pretty easily.)\n\nThen you’d lose the speedup in the case where --exact-match wasn’t \nspecified but a tag happens to match exactly (which isn’t critical, but \nseemed nice).\n\n> > -\tfor_each_ref(get_name, NULL);\n> > +\tfor_each_rawref(get_name, NULL);\n> \n> Orthogonal change snuck in?\n\nThis does fall under the category of “Don’t lookup commits,” and is \nnecessary to get the speedup (otherwise for_each_ref has already looked up \nthe commits that the rest of the patch is trying to avoid looking up). \nBut I could split it out if you want.\n\nAnders\n"},{"id":"157386","messageId":"alpine.DEB.2.02.1012060221100.23348@dr-wily.mit.edu","threadId":"25773","inReplyTo":"alpine.DEB.2.02.1012060149550.23348@dr-wily.mit.edu","subject":"[PATCH] describe: Don’t look up commits with --exact-match","fromName":"Anders Kaseorg","fromEmail":"andersk@ksplice.com","sentAt":"2010-12-06T07:22:15Z","receivedAt":"2010-12-06T07:22:15Z","isPatch":true,"sender":{"key":"andersk@mit.edu","avatar":"https://avatars.githubusercontent.com/u/26471?v=4"},"body":"This makes ‘git describe --exact-match HEAD’ about 15 times faster on\na cold cache (2.3s instead of 35s) in a linux-2.6 repository with many\npacked tags. That’s a huge win for the interactivity of the __git_ps1\nshell prompt helper.\n\nSigned-off-by: Anders Kaseorg \n---\n builtin/describe.c | 64 ++++++++++++++++++++++++++-------------------------\n 1 files changed, 33 insertions(+), 31 deletions(-)\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 43caff2..0cddef1 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -22,7 +22,7 @@ static int tags;\t/* Allow lightweight tags */\n static int longformat;\n static int abbrev = DEFAULT_ABBREV;\n static int max_candidates = 10;\n-static int found_names;\n+static struct commit_name *names;\n static const char *pattern;\n static int always;\n static const char *dirty;\n@@ -34,6 +34,8 @@ static const char *diff_index_args[] = {\n \n \n struct commit_name {\n+\tstruct commit_name *next;\n+\tunsigned char peeled[20];\n \tstruct tag *tag;\n \tunsigned prio:2; /* annotated tag = 2, tag = 1, head = 0 */\n \tunsigned name_checked:1;\n@@ -78,31 +80,26 @@ static int replace_name(struct commit_name *e,\n }\n \n static void add_to_known_names(const char *path,\n-\t\t\t struct commit *commit,\n+\t\t\t const unsigned char *peeled,\n \t\t\t int prio,\n \t\t\t const unsigned char *sha1)\n {\n-\tstruct commit_name *e = commit->util;\n \tstruct tag *tag = NULL;\n-\tif (replace_name(e, prio, sha1, &tag)) {\n-\t\tsize_t len = strlen(path)+1;\n-\t\tfree(e);\n-\t\te = xmalloc(sizeof(struct commit_name) + len);\n-\t\te->tag = tag;\n-\t\te->prio = prio;\n-\t\te->name_checked = 0;\n-\t\thashcpy(e->sha1, sha1);\n-\t\tmemcpy(e->path, path, len);\n-\t\tcommit->util = e;\n-\t}\n-\tfound_names = 1;\n+\tsize_t len = strlen(path)+1;\n+\tstruct commit_name *e = xmalloc(sizeof(struct commit_name) + len);\n+\thashcpy(e->peeled, peeled);\n+\te->tag = tag;\n+\te->prio = prio;\n+\te->name_checked = 0;\n+\thashcpy(e->sha1, sha1);\n+\tmemcpy(e->path, path, len);\n+\te->next = names;\n+\tnames = e;\n }\n \n static int get_name(const char *path, const unsigned char *sha1, int flag, void *cb_data)\n {\n \tint might_be_tag = !prefixcmp(path, \"refs/tags/\");\n-\tstruct commit *commit;\n-\tstruct object *object;\n \tunsigned char peeled[20];\n \tint is_tag, prio;\n \n@@ -110,16 +107,10 @@ static int get_name(const char *path, const unsigned char *sha1, int flag, void\n \t\treturn 0;\n \n \tif (!peel_ref(path, peeled) && !is_null_sha1(peeled)) {\n-\t\tcommit = lookup_commit_reference_gently(peeled, 1);\n-\t\tif (!commit)\n-\t\t\treturn 0;\n-\t\tis_tag = !!hashcmp(sha1, commit->object.sha1);\n+\t\tis_tag = !!hashcmp(sha1, peeled);\n \t} else {\n-\t\tcommit = lookup_commit_reference_gently(sha1, 1);\n-\t\tobject = parse_object(sha1);\n-\t\tif (!commit || !object)\n-\t\t\treturn 0;\n-\t\tis_tag = object->type == OBJ_TAG;\n+\t\thashcpy(peeled, sha1);\n+\t\tis_tag = 0;\n \t}\n \n \t/* If --all, then any refs are used.\n@@ -142,7 +133,7 @@ static int get_name(const char *path, const unsigned char *sha1, int flag, void\n \t\tif (!prio)\n \t\t\treturn 0;\n \t}\n-\tadd_to_known_names(all ? path + 5 : path + 10, commit, prio, sha1);\n+\tadd_to_known_names(all ? path + 5 : path + 10, peeled, prio, sha1);\n \treturn 0;\n }\n \n@@ -228,7 +219,7 @@ static void describe(const char *arg, int last_one)\n \tunsigned char sha1[20];\n \tstruct commit *cmit, *gave_up_on = NULL;\n \tstruct commit_list *list;\n-\tstruct commit_name *n;\n+\tstruct commit_name *n, *e;\n \tstruct possible_tag all_matches[MAX_TAGS];\n \tunsigned int match_cnt = 0, annotated_cnt = 0, cur_match;\n \tunsigned long seen_commits = 0;\n@@ -240,7 +231,12 @@ static void describe(const char *arg, int last_one)\n \tif (!cmit)\n \t\tdie(\"%s is not a valid '%s' object\", arg, commit_type);\n \n-\tn = cmit->util;\n+\tn = NULL;\n+\tfor (e = names; e; e = e->next) {\n+\t\tif (!hashcmp(e->peeled, cmit->object.sha1) &&\n+\t\t replace_name(n, e->prio, e->sha1, &e->tag))\n+\t\t\tn = e;\n+\t}\n \tif (n && (tags || all || n->prio == 2)) {\n \t\t/*\n \t\t * Exact match to an existing ref.\n@@ -259,6 +255,12 @@ static void describe(const char *arg, int last_one)\n \tif (debug)\n \t\tfprintf(stderr, \"searching to describe %s\\n\", arg);\n \n+\tfor (e = names; e; e = e->next) {\n+\t\tstruct commit *c = lookup_commit_reference_gently(e->peeled, 1);\n+\t\tif (c && replace_name(c->util, e->prio, e->sha1, &e->tag))\n+\t\t\tc->util = e;\n+\t}\n+\n \tlist = NULL;\n \tcmit->object.flags = SEEN;\n \tcommit_list_insert(cmit, &list);\n@@ -418,8 +420,8 @@ int cmd_describe(int argc, const char **argv, const char *prefix)\n \t\treturn cmd_name_rev(i + argc, args, prefix);\n \t}\n \n-\tfor_each_ref(get_name, NULL);\n-\tif (!found_names && !always)\n+\tfor_each_rawref(get_name, NULL);\n+\tif (!names && !always)\n \t\tdie(\"No names found, cannot describe anything.\");\n \n \tif (argc == 0) {\n-- \n1.7.3.2\n"},{"id":"157387","messageId":"20101206073214.GA3745@burratino","threadId":"25773","inReplyTo":"alpine.DEB.2.02.1012060149550.23348@dr-wily.mit.edu","subject":"Re: [PATCH] describe: Don’t look up commits with --exact-match","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2010-12-06T07:32:14Z","receivedAt":"2010-12-06T07:32:14Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Anders Kaseorg wrote:\n> On Fri, 3 Dec 2010, Jonathan Nieder wrote:\n\n>> Instead of looking up the commit to be matched exactly in the commits\n>> hash table, this makes a linear search.\n[...]\n> I don’t think it’s ever a problem: in my repository with 1800 tags on a \n> warm cache, that loop accounts for about 0.1% of even the fastest \n> non-exact-match query (a commit right after a tag).\n\nThanks for checking. Makes sense.\n\n>>> -\tfor_each_ref(get_name, NULL);\n>>> +\tfor_each_rawref(get_name, NULL);\n>>\n>> Orthogonal change snuck in?\n>\n> This does fall under the category of “Don’t lookup commits,” and is \n> necessary to get the speedup (otherwise for_each_ref has already looked up \n> the commits that the rest of the patch is trying to avoid looking up). \n\nDepends on what \"Don't lookup commits\" means, I suppose. I\nthink the difference between _ref and _rawref is\n\n if (!(flags & DO_FOR_EACH_INCLUDE_BROKEN)) {\n if (entry->flag & REF_BROKEN)\n return 0; /* ignore dangling symref */\n if (!has_sha1_file(entry->sha1)) {\n error(\"%s does not point to a valid object!\", entry->name);\n return 0;\n }\n }\n\nso if I understand correctly, for_each_ref would still allow one to\nget away without unpacking the objects. Is that correct?\n"},{"id":"157399","messageId":"201012061153.59635.trast@student.ethz.ch","threadId":"25773","inReplyTo":"20101206073214.GA3745@burratino","subject":"Re: [PATCH] describe: Don’t look up commits with --exact-match","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2010-12-06T10:53:59Z","receivedAt":"2010-12-06T10:53:59Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Jonathan Nieder wrote:\n> Anders Kaseorg wrote:\n> > On Fri, 3 Dec 2010, Jonathan Nieder wrote:\n> \n> >> Instead of looking up the commit to be matched exactly in the commits\n> >> hash table, this makes a linear search.\n> [...]\n> > I don’t think it’s ever a problem: in my repository with 1800 tags on a \n> > warm cache, that loop accounts for about 0.1% of even the fastest \n> > non-exact-match query (a commit right after a tag).\n> \n> Thanks for checking. Makes sense.\n\nApart from measuring: for_each_ref *loads* the tags in a linear scan,\nso another linear scan doesn't add to the runtime w.r.t. number of\ntags. It only hurts if you also describe many refs in one go.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"157409","messageId":"alpine.DEB.2.02.1012061159500.23348@dr-wily.mit.edu","threadId":"25773","inReplyTo":"20101206073214.GA3745@burratino","subject":"Re: [PATCH] describe: Don’t look up commits with --exact-match","fromName":"Anders Kaseorg","fromEmail":"andersk@ksplice.com","sentAt":"2010-12-06T17:28:59Z","receivedAt":"2010-12-06T17:28:59Z","isPatch":true,"sender":{"key":"andersk@mit.edu","avatar":"https://avatars.githubusercontent.com/u/26471?v=4"},"body":"On Mon, 6 Dec 2010, Jonathan Nieder wrote:\n> Depends on what \"Don't lookup commits\" means, I suppose. I\n> think the difference between _ref and _rawref is\n> […]\n> so if I understand correctly, for_each_ref would still allow one to\n> get away without unpacking the objects. Is that correct?\n\nYeah. Okay, I see that “lookup” implies unpacking, as opposed to “find”, \nwhich doesn’t. The important part is to avoid the find, of course, \nbecause the I/O is expensive.\n\nAnyway, here’s a series with that change split out.\n\nAnders\n\n-- 8< --\nFrom 2ad1e58b8f6e9c117c77748b6e8b85227d9d5412 Mon Sep 17 00:00:00 2001\nFrom: Anders Kaseorg \nSubject: [PATCH 1/2] describe: Use for_each_rawref\n\nDon’t waste time checking for dangling refs; they wouldn’t affect the\noutput of ‘git describe’ anyway. Although this doesn’t gain much\nperformance by itself, it does in conjunction with the next commit.\n\nSigned-off-by: Anders Kaseorg \n---\n builtin/describe.c | 2 +-\n 1 files changed, 1 insertions(+), 1 deletions(-)\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 43caff2..700f740 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -418,7 +418,7 @@ int cmd_describe(int argc, const char **argv, const char *prefix)\n \t\treturn cmd_name_rev(i + argc, args, prefix);\n \t}\n \n-\tfor_each_ref(get_name, NULL);\n+\tfor_each_rawref(get_name, NULL);\n \tif (!found_names && !always)\n \t\tdie(\"No names found, cannot describe anything.\");\n \n-- \n1.7.3.3\n\n\nFrom ce8a2ab9cf80247c2834d21f36f63cedb794e62f Mon Sep 17 00:00:00 2001\nFrom: Anders Kaseorg \nSubject: describe: Don’t look up commits with --exact-match\n\nThis makes ‘git describe --exact-match HEAD’ about 15 times faster on\na cold cache (2.3s instead of 35s) in a linux-2.6 repository with many\npacked tags. That’s a huge win for the interactivity of the __git_ps1\nshell prompt helper.\n\nSigned-off-by: Anders Kaseorg \n---\n builtin/describe.c | 62 ++++++++++++++++++++++++++-------------------------\n 1 files changed, 32 insertions(+), 30 deletions(-)\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 700f740..0cddef1 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -22,7 +22,7 @@ static int tags;\t/* Allow lightweight tags */\n static int longformat;\n static int abbrev = DEFAULT_ABBREV;\n static int max_candidates = 10;\n-static int found_names;\n+static struct commit_name *names;\n static const char *pattern;\n static int always;\n static const char *dirty;\n@@ -34,6 +34,8 @@ static const char *diff_index_args[] = {\n \n \n struct commit_name {\n+\tstruct commit_name *next;\n+\tunsigned char peeled[20];\n \tstruct tag *tag;\n \tunsigned prio:2; /* annotated tag = 2, tag = 1, head = 0 */\n \tunsigned name_checked:1;\n@@ -78,31 +80,26 @@ static int replace_name(struct commit_name *e,\n }\n \n static void add_to_known_names(const char *path,\n-\t\t\t struct commit *commit,\n+\t\t\t const unsigned char *peeled,\n \t\t\t int prio,\n \t\t\t const unsigned char *sha1)\n {\n-\tstruct commit_name *e = commit->util;\n \tstruct tag *tag = NULL;\n-\tif (replace_name(e, prio, sha1, &tag)) {\n-\t\tsize_t len = strlen(path)+1;\n-\t\tfree(e);\n-\t\te = xmalloc(sizeof(struct commit_name) + len);\n-\t\te->tag = tag;\n-\t\te->prio = prio;\n-\t\te->name_checked = 0;\n-\t\thashcpy(e->sha1, sha1);\n-\t\tmemcpy(e->path, path, len);\n-\t\tcommit->util = e;\n-\t}\n-\tfound_names = 1;\n+\tsize_t len = strlen(path)+1;\n+\tstruct commit_name *e = xmalloc(sizeof(struct commit_name) + len);\n+\thashcpy(e->peeled, peeled);\n+\te->tag = tag;\n+\te->prio = prio;\n+\te->name_checked = 0;\n+\thashcpy(e->sha1, sha1);\n+\tmemcpy(e->path, path, len);\n+\te->next = names;\n+\tnames = e;\n }\n \n static int get_name(const char *path, const unsigned char *sha1, int flag, void *cb_data)\n {\n \tint might_be_tag = !prefixcmp(path, \"refs/tags/\");\n-\tstruct commit *commit;\n-\tstruct object *object;\n \tunsigned char peeled[20];\n \tint is_tag, prio;\n \n@@ -110,16 +107,10 @@ static int get_name(const char *path, const unsigned char *sha1, int flag, void\n \t\treturn 0;\n \n \tif (!peel_ref(path, peeled) && !is_null_sha1(peeled)) {\n-\t\tcommit = lookup_commit_reference_gently(peeled, 1);\n-\t\tif (!commit)\n-\t\t\treturn 0;\n-\t\tis_tag = !!hashcmp(sha1, commit->object.sha1);\n+\t\tis_tag = !!hashcmp(sha1, peeled);\n \t} else {\n-\t\tcommit = lookup_commit_reference_gently(sha1, 1);\n-\t\tobject = parse_object(sha1);\n-\t\tif (!commit || !object)\n-\t\t\treturn 0;\n-\t\tis_tag = object->type == OBJ_TAG;\n+\t\thashcpy(peeled, sha1);\n+\t\tis_tag = 0;\n \t}\n \n \t/* If --all, then any refs are used.\n@@ -142,7 +133,7 @@ static int get_name(const char *path, const unsigned char *sha1, int flag, void\n \t\tif (!prio)\n \t\t\treturn 0;\n \t}\n-\tadd_to_known_names(all ? path + 5 : path + 10, commit, prio, sha1);\n+\tadd_to_known_names(all ? path + 5 : path + 10, peeled, prio, sha1);\n \treturn 0;\n }\n \n@@ -228,7 +219,7 @@ static void describe(const char *arg, int last_one)\n \tunsigned char sha1[20];\n \tstruct commit *cmit, *gave_up_on = NULL;\n \tstruct commit_list *list;\n-\tstruct commit_name *n;\n+\tstruct commit_name *n, *e;\n \tstruct possible_tag all_matches[MAX_TAGS];\n \tunsigned int match_cnt = 0, annotated_cnt = 0, cur_match;\n \tunsigned long seen_commits = 0;\n@@ -240,7 +231,12 @@ static void describe(const char *arg, int last_one)\n \tif (!cmit)\n \t\tdie(\"%s is not a valid '%s' object\", arg, commit_type);\n \n-\tn = cmit->util;\n+\tn = NULL;\n+\tfor (e = names; e; e = e->next) {\n+\t\tif (!hashcmp(e->peeled, cmit->object.sha1) &&\n+\t\t replace_name(n, e->prio, e->sha1, &e->tag))\n+\t\t\tn = e;\n+\t}\n \tif (n && (tags || all || n->prio == 2)) {\n \t\t/*\n \t\t * Exact match to an existing ref.\n@@ -259,6 +255,12 @@ static void describe(const char *arg, int last_one)\n \tif (debug)\n \t\tfprintf(stderr, \"searching to describe %s\\n\", arg);\n \n+\tfor (e = names; e; e = e->next) {\n+\t\tstruct commit *c = lookup_commit_reference_gently(e->peeled, 1);\n+\t\tif (c && replace_name(c->util, e->prio, e->sha1, &e->tag))\n+\t\t\tc->util = e;\n+\t}\n+\n \tlist = NULL;\n \tcmit->object.flags = SEEN;\n \tcommit_list_insert(cmit, &list);\n@@ -419,7 +421,7 @@ int cmd_describe(int argc, const char **argv, const char *prefix)\n \t}\n \n \tfor_each_rawref(get_name, NULL);\n-\tif (!found_names && !always)\n+\tif (!names && !always)\n \t\tdie(\"No names found, cannot describe anything.\");\n \n \tif (argc == 0) {\n-- \n1.7.3.3\n"},{"id":"157411","messageId":"20101206174723.GB6272@burratino","threadId":"25773","inReplyTo":"alpine.DEB.2.02.1012061159500.23348@dr-wily.mit.edu","subject":"Re: [PATCH] describe: Don’t look up commits with --exact-match","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2010-12-06T17:47:23Z","receivedAt":"2010-12-06T17:47:23Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Anders Kaseorg wrote:\n\n> Yeah. Okay, I see that “lookup” implies unpacking, as opposed to “find”, \n> which doesn’t. The important part is to avoid the find, of course, \n> because the I/O is expensive.\n>\n> Anyway, here’s a series with that change split out.\n\nThanks.\n\nIn theory finding an object would only require looking at the pack\nindex (and directory listings), but find_pack_entry does\n\n\t\t/*\n\t\t * We are about to tell the caller where they can\n\t\t * locate the requested object. We better make\n\t\t * sure the packfile is still here and can be\n\t\t * accessed before supplying that answer, as\n\t\t * it may have been deleted since the index\n\t\t * was loaded!\n\t\t */\n\nwhich spoils that plan.\n\nYour original use of the word \"lookup\" seemed sane, too; I was just\nfishing for a more detailed explanation.\n\nReviewed-by: Jonathan Nieder \n\n> -- 8< --\n> From 2ad1e58b8f6e9c117c77748b6e8b85227d9d5412 Mon Sep 17 00:00:00 2001\n[...]\n\nFor the future: this does not follow the preferred patch format (one\npatch per message, each of the form \"description/---/diff\"). In this\ncase I am guessing it won't be much trouble to massage on the\nreceiving end, so no terrible loss.\n"},{"id":"157482","messageId":"20101207095818.GB1867@neumann","threadId":"25773","inReplyTo":"alpine.DEB.2.02.1012061159500.23348@dr-wily.mit.edu","subject":"Re: [PATCH] describe: Don’t look up commits with --exact-match","fromName":"SZEDER Gábor","fromEmail":"szeder@ira.uka.de","sentAt":"2010-12-07T09:58:18Z","receivedAt":"2010-12-07T09:58:18Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"Hi,\n\nOn Mon, Dec 06, 2010 at 12:28:59PM -0500, Anders Kaseorg wrote:\n> This makes ‘git describe --exact-match HEAD’ about 15 times faster on\n> a cold cache (2.3s instead of 35s) in a linux-2.6 repository with many\n> packed tags. That’s a huge win for the interactivity of the __git_ps1\n> shell prompt helper.\n\nI wanted to give it a try to see the performance improvements in the\nbash prompt for myself, but couldn't get to it so far. However,\nglancing through the logic finding out the current branch in\n__git_ps1, it seems that git describe is only run when git\nsymbolic-ref HEAD failed, i.e. when on a detached head. So the\nperformance improvement in the shell prompt is only there when on a\ndetached head (and with lots of tags), right? If so, then I'd like to\nhave \"when on a detached head\" appended to the commit message.\n\n\nBest,\nGábor\n"},{"id":"157511","messageId":"alpine.DEB.2.02.1012071320240.23348@dr-wily.mit.edu","threadId":"25773","inReplyTo":"20101207095818.GB1867@neumann","subject":"[PATCH 1/2] describe: Use for_each_rawref","fromName":"Anders Kaseorg","fromEmail":"andersk@ksplice.com","sentAt":"2010-12-07T18:22:00Z","receivedAt":"2010-12-07T18:22:00Z","isPatch":true,"sender":{"key":"andersk@mit.edu","avatar":"https://avatars.githubusercontent.com/u/26471?v=4"},"body":"Don’t waste time checking for dangling refs; they wouldn’t affect the\noutput of ‘git describe’ anyway. Although this doesn’t gain much\nperformance by itself, it does in conjunction with the next commit.\n\nSigned-off-by: Anders Kaseorg \n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 43caff2..700f740 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -418,7 +418,7 @@ int cmd_describe(int argc, const char **argv, const char *prefix)\n \t\treturn cmd_name_rev(i + argc, args, prefix);\n \t}\n \n-\tfor_each_ref(get_name, NULL);\n+\tfor_each_rawref(get_name, NULL);\n \tif (!found_names && !always)\n \t\tdie(\"No names found, cannot describe anything.\");\n \n-- \n1.7.3.3\n"},{"id":"157512","messageId":"alpine.DEB.2.02.1012071322120.23348@dr-wily.mit.edu","threadId":"25773","inReplyTo":"alpine.DEB.2.02.1012071320240.23348@dr-wily.mit.edu","subject":"[PATCH 2/2] describe: Don’t look up commits with --exact-match","fromName":"Anders Kaseorg","fromEmail":"andersk@ksplice.com","sentAt":"2010-12-07T18:22:53Z","receivedAt":"2010-12-07T18:22:53Z","isPatch":true,"sender":{"key":"andersk@mit.edu","avatar":"https://avatars.githubusercontent.com/u/26471?v=4"},"body":"This makes ‘git describe --exact-match HEAD’ about 15 times faster on\na cold cache (2.3s instead of 35s) in a linux-2.6 repository with many\npacked tags. That’s a huge win for the interactivity of the __git_ps1\nshell prompt helper when on a detached head.\n\nSigned-off-by: Anders Kaseorg \n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 700f740..0cddef1 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -22,7 +22,7 @@ static int tags;\t/* Allow lightweight tags */\n static int longformat;\n static int abbrev = DEFAULT_ABBREV;\n static int max_candidates = 10;\n-static int found_names;\n+static struct commit_name *names;\n static const char *pattern;\n static int always;\n static const char *dirty;\n@@ -34,6 +34,8 @@ static const char *diff_index_args[] = {\n \n \n struct commit_name {\n+\tstruct commit_name *next;\n+\tunsigned char peeled[20];\n \tstruct tag *tag;\n \tunsigned prio:2; /* annotated tag = 2, tag = 1, head = 0 */\n \tunsigned name_checked:1;\n@@ -78,31 +80,26 @@ static int replace_name(struct commit_name *e,\n }\n \n static void add_to_known_names(const char *path,\n-\t\t\t struct commit *commit,\n+\t\t\t const unsigned char *peeled,\n \t\t\t int prio,\n \t\t\t const unsigned char *sha1)\n {\n-\tstruct commit_name *e = commit->util;\n \tstruct tag *tag = NULL;\n-\tif (replace_name(e, prio, sha1, &tag)) {\n-\t\tsize_t len = strlen(path)+1;\n-\t\tfree(e);\n-\t\te = xmalloc(sizeof(struct commit_name) + len);\n-\t\te->tag = tag;\n-\t\te->prio = prio;\n-\t\te->name_checked = 0;\n-\t\thashcpy(e->sha1, sha1);\n-\t\tmemcpy(e->path, path, len);\n-\t\tcommit->util = e;\n-\t}\n-\tfound_names = 1;\n+\tsize_t len = strlen(path)+1;\n+\tstruct commit_name *e = xmalloc(sizeof(struct commit_name) + len);\n+\thashcpy(e->peeled, peeled);\n+\te->tag = tag;\n+\te->prio = prio;\n+\te->name_checked = 0;\n+\thashcpy(e->sha1, sha1);\n+\tmemcpy(e->path, path, len);\n+\te->next = names;\n+\tnames = e;\n }\n \n static int get_name(const char *path, const unsigned char *sha1, int flag, void *cb_data)\n {\n \tint might_be_tag = !prefixcmp(path, \"refs/tags/\");\n-\tstruct commit *commit;\n-\tstruct object *object;\n \tunsigned char peeled[20];\n \tint is_tag, prio;\n \n@@ -110,16 +107,10 @@ static int get_name(const char *path, const unsigned char *sha1, int flag, void\n \t\treturn 0;\n \n \tif (!peel_ref(path, peeled) && !is_null_sha1(peeled)) {\n-\t\tcommit = lookup_commit_reference_gently(peeled, 1);\n-\t\tif (!commit)\n-\t\t\treturn 0;\n-\t\tis_tag = !!hashcmp(sha1, commit->object.sha1);\n+\t\tis_tag = !!hashcmp(sha1, peeled);\n \t} else {\n-\t\tcommit = lookup_commit_reference_gently(sha1, 1);\n-\t\tobject = parse_object(sha1);\n-\t\tif (!commit || !object)\n-\t\t\treturn 0;\n-\t\tis_tag = object->type == OBJ_TAG;\n+\t\thashcpy(peeled, sha1);\n+\t\tis_tag = 0;\n \t}\n \n \t/* If --all, then any refs are used.\n@@ -142,7 +133,7 @@ static int get_name(const char *path, const unsigned char *sha1, int flag, void\n \t\tif (!prio)\n \t\t\treturn 0;\n \t}\n-\tadd_to_known_names(all ? path + 5 : path + 10, commit, prio, sha1);\n+\tadd_to_known_names(all ? path + 5 : path + 10, peeled, prio, sha1);\n \treturn 0;\n }\n \n@@ -228,7 +219,7 @@ static void describe(const char *arg, int last_one)\n \tunsigned char sha1[20];\n \tstruct commit *cmit, *gave_up_on = NULL;\n \tstruct commit_list *list;\n-\tstruct commit_name *n;\n+\tstruct commit_name *n, *e;\n \tstruct possible_tag all_matches[MAX_TAGS];\n \tunsigned int match_cnt = 0, annotated_cnt = 0, cur_match;\n \tunsigned long seen_commits = 0;\n@@ -240,7 +231,12 @@ static void describe(const char *arg, int last_one)\n \tif (!cmit)\n \t\tdie(\"%s is not a valid '%s' object\", arg, commit_type);\n \n-\tn = cmit->util;\n+\tn = NULL;\n+\tfor (e = names; e; e = e->next) {\n+\t\tif (!hashcmp(e->peeled, cmit->object.sha1) &&\n+\t\t replace_name(n, e->prio, e->sha1, &e->tag))\n+\t\t\tn = e;\n+\t}\n \tif (n && (tags || all || n->prio == 2)) {\n \t\t/*\n \t\t * Exact match to an existing ref.\n@@ -259,6 +255,12 @@ static void describe(const char *arg, int last_one)\n \tif (debug)\n \t\tfprintf(stderr, \"searching to describe %s\\n\", arg);\n \n+\tfor (e = names; e; e = e->next) {\n+\t\tstruct commit *c = lookup_commit_reference_gently(e->peeled, 1);\n+\t\tif (c && replace_name(c->util, e->prio, e->sha1, &e->tag))\n+\t\t\tc->util = e;\n+\t}\n+\n \tlist = NULL;\n \tcmit->object.flags = SEEN;\n \tcommit_list_insert(cmit, &list);\n@@ -419,7 +421,7 @@ int cmd_describe(int argc, const char **argv, const char *prefix)\n \t}\n \n \tfor_each_rawref(get_name, NULL);\n-\tif (!found_names && !always)\n+\tif (!names && !always)\n \t\tdie(\"No names found, cannot describe anything.\");\n \n \tif (argc == 0) {\n-- \n1.7.3.3\n"},{"id":"157515","messageId":"alpine.DEB.2.02.1012071325100.23348@dr-wily.mit.edu","threadId":"25773","inReplyTo":"alpine.DEB.2.02.1012071320240.23348@dr-wily.mit.edu","subject":"Re: [PATCH 1/2] describe: Use for_each_rawref","fromName":"Anders Kaseorg","fromEmail":"andersk@ksplice.com","sentAt":"2010-12-07T18:26:45Z","receivedAt":"2010-12-07T18:26:45Z","isPatch":true,"sender":{"key":"andersk@mit.edu","avatar":"https://avatars.githubusercontent.com/u/26471?v=4"},"body":"On Tue, 7 Dec 2010, Anders Kaseorg wrote:\n> Signed-off-by: Anders Kaseorg \n> \n> diff --git a/builtin/describe.c b/builtin/describe.c\n\n(Gaaah, sorry, I accidentally used format-patch -p here. Won’t happen \nagain. :-) )\n\nAnders\n"},{"id":"157518","messageId":"7vfwu9qvew.fsf@alter.siamese.dyndns.org","threadId":"25773","inReplyTo":"alpine.DEB.2.02.1012061159500.23348@dr-wily.mit.edu","subject":"Re: [PATCH] describe: Don’t look up commits with --exact-match","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2010-12-07T18:39:51Z","receivedAt":"2010-12-07T18:39:51Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Anders Kaseorg writes:\n\n> From 2ad1e58b8f6e9c117c77748b6e8b85227d9d5412 Mon Sep 17 00:00:00 2001\n> From: Anders Kaseorg \n> Subject: [PATCH 1/2] describe: Use for_each_rawref\n>\n> Don’t waste time checking for dangling refs; they wouldn’t affect the\n> output of ‘git describe’ anyway. Although this doesn’t gain much\n> performance by itself, it does in conjunction with the next commit.\n>\n> Signed-off-by: Anders Kaseorg \n> ---\n> builtin/describe.c | 2 +-\n> 1 files changed, 1 insertions(+), 1 deletions(-)\n>\n> diff --git a/builtin/describe.c b/builtin/describe.c\n> index 43caff2..700f740 100644\n> --- a/builtin/describe.c\n> +++ b/builtin/describe.c\n> @@ -418,7 +418,7 @@ int cmd_describe(int argc, const char **argv, const char *prefix)\n> \t\treturn cmd_name_rev(i + argc, args, prefix);\n> \t}\n> \n> -\tfor_each_ref(get_name, NULL);\n> +\tfor_each_rawref(get_name, NULL);\n> \tif (!found_names && !always)\n> \t\tdie(\"No names found, cannot describe anything.\");\n\nIt is Ok during a review cycle that is not meant as the final submission,\nbut please follow Documentation/SubmittingPatches for the final round\n(i.e. not multiple-changes in a single mail), as mentioned by Jonathan.\n\n> From ce8a2ab9cf80247c2834d21f36f63cedb794e62f Mon Sep 17 00:00:00 2001\n> From: Anders Kaseorg \n> Subject: describe: Don’t look up commits with --exact-match\n>\n> This makes ‘git describe --exact-match HEAD’ about 15 times faster on\n> a cold cache (2.3s instead of 35s) in a linux-2.6 repository with many\n> packed tags. That’s a huge win for the interactivity of the __git_ps1\n> shell prompt helper.\n\nGood description of the motivation. Care to describe how it is achieved?\n\nI may be misreading your intention, but my understanding of the thinking\nbehind what the new code does is...\n\n - When the object name given from the command line happens to match one\n of the tags exactly (either a lightweight tag in which case we can just\n compare the object names to detect the match, or an annotated tag in\n which case we only need to parse the tag but not the underlying commit\n to do the comparison), we do not have to parse any commit object.\n\n - Other cases we would need to parse commit objects and traverse the\n history.\n\n - Hence, the code can be optimized for the case to describe an exact\n match by trying exact object name match first and then loading commit\n objects only when no exact matches found.\n\n - When we are only looking for exact matches (which is _not_ a rare\n corner case), we won't ever fall back to the \"parse commit objects and\n traverse the history\" codepath. So it is important to lazily parse\n commit objects in order to optimize for this special case.\n\nI however think this may hurt when more than one objects are asked to be\ndescribed and there is no exact match. The fallback codepath that lazily\nruns lookup_commit_reference_gently() and uses replace_name() to compute\nthe best name needs to run only once, but this part of the code seems to\nrun it for the elements on the names list once per describe() invocation\nthat needs to fall back to this codepath. Would it remove this regression\nif we make it run only once?\n\nI don't think this affects correctness, though.\n\n> @@ -259,6 +255,12 @@ static void describe(const char *arg, int last_one)\n> \tif (debug)\n> \t\tfprintf(stderr, \"searching to describe %s\\n\", arg);\n> \n> +\tfor (e = names; e; e = e->next) {\n> +\t\tstruct commit *c = lookup_commit_reference_gently(e->peeled, 1);\n> +\t\tif (c && replace_name(c->util, e->prio, e->sha1, &e->tag))\n> +\t\t\tc->util = e;\n> +\t}\n> +\n> \tlist = NULL;\n> \tcmit->object.flags = SEEN;\n> \tcommit_list_insert(cmit, &list);\n\nAs you can see from its \"if (!e->tag)\" codepath, replace_name() is not\ndesigned to be called excessively (e.g. we will end up running the\ncodepath for an annotated tag that we should know we won't find a tag).\n\nAlso, \"struct tag *tag\" does not need to exist in add_to_known_names()\nanymore; a NULL is assigned to it and its only use is to get assigned\nto e->tag.\n"},{"id":"157528","messageId":"7vsjy9pdmg.fsf@alter.siamese.dyndns.org","threadId":"25773","inReplyTo":"alpine.DEB.2.02.1012071325100.23348@dr-wily.mit.edu","subject":"Re: [PATCH 1/2] describe: Use for_each_rawref","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2010-12-07T19:49:27Z","receivedAt":"2010-12-07T19:49:27Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Anders Kaseorg writes:\n\n> On Tue, 7 Dec 2010, Anders Kaseorg wrote:\n>> Signed-off-by: Anders Kaseorg \n>> \n>> diff --git a/builtin/describe.c b/builtin/describe.c\n>\n> (Gaaah, sorry, I accidentally used format-patch -p here. Won’t happen \n> again. :-) )\n\nThe default will work just fine, no?\n\nAlso labelling them like \"[PATCH v2 1/2]\" would have been nicer to spot\nthe progress of the series.\n\nThanks.\n"},{"id":"157549","messageId":"7vr5dtnt0h.fsf@alter.siamese.dyndns.org","threadId":"25773","inReplyTo":"7vsjy9pdmg.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 1/2] describe: Use for_each_rawref","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2010-12-07T21:59:58Z","receivedAt":"2010-12-07T21:59:58Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> Anders Kaseorg writes:\n>\n>> On Tue, 7 Dec 2010, Anders Kaseorg wrote:\n>>> Signed-off-by: Anders Kaseorg \n>>> \n>>> diff --git a/builtin/describe.c b/builtin/describe.c\n>>\n>> (Gaaah, sorry, I accidentally used format-patch -p here. Won’t happen \n>> again. :-) )\n>\n> The default will work just fine, no?\n>\n> Also labelling them like \"[PATCH v2 1/2]\" would have been nicer to spot\n> the progress of the series.\n\nTwo more requests.\n\n * Please describe what was changed since earlier interations after \"---\"\n lines;\n\n * Please run tests before submitting patches. It appears to break t7407.\n\nWhat breaks in t7407 is \"git submodule status --recursive\" output. In my\nenvironment, it used to describe the tip as heads/master but after the\npatch it says remotes/origin/master. The output from \"describe --all\"\ndoes not tiebreak between one branch from another, even though it does\nfavor tags over branches (and tries to use annotated ones), so it is not a\nreal regression in that sense, but then the test needs to be fixed not to\ncare about which equally good branches are shown.\n\nSome might even argue that it is more relevant to show how the commit\nrelates to remote-tracking branch heads. That is a separate issue (if\nthis position is widely supported, we would introduce another \"prio\"\nbetween \"all others (0)\" and \"lightweight tags (1)\" for remote-tracking\nbranches), though.\n"},{"id":"157573","messageId":"alpine.DEB.2.02.1012072204371.23348@dr-wily.mit.edu","threadId":"25773","inReplyTo":"7vfwu9qvew.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] describe: Don’t look up commits with --exact-match","fromName":"Anders Kaseorg","fromEmail":"andersk@ksplice.com","sentAt":"2010-12-08T04:41:39Z","receivedAt":"2010-12-08T04:41:39Z","isPatch":true,"sender":{"key":"andersk@mit.edu","avatar":"https://avatars.githubusercontent.com/u/26471?v=4"},"body":"On Tue, 7 Dec 2010, Junio C Hamano wrote:\n> I however think this may hurt when more than one objects are asked to be\n> described and there is no exact match.\n\nYeah, that turns out to be true. So I rewrote the patch to put the \ncommit_names into a hash table instead of a linked list, run \nreplace_name() only once per tag, and run the lookup code only once per \ndescribe(). I also tried to split things up a bit more and explain more \nin the commit messages.\n\n> * Please run tests before submitting patches. It appears to break t7407.\n\nOops, I was lazy and only ran the tests that (directly) use describe; I’ll \nbe more careful in the future. The new series doesn’t have this problem \nbecause it does the replace_name()s in the same order as the old code, and \nit passes all tests.\n\nfixed 1\nsuccess 6426\nfailed 0\nbroken 39\ntotal 6496\n\nAnders\n"},{"id":"157574","messageId":"alpine.DEB.2.02.1012072341570.23348@dr-wily.mit.edu","threadId":"25773","inReplyTo":"alpine.DEB.2.02.1012072204371.23348@dr-wily.mit.edu","subject":"[PATCH v2 1/4] describe: Use for_each_rawref","fromName":"Anders Kaseorg","fromEmail":"andersk@ksplice.com","sentAt":"2010-12-08T04:42:35Z","receivedAt":"2010-12-08T04:42:35Z","isPatch":true,"sender":{"key":"andersk@mit.edu","avatar":"https://avatars.githubusercontent.com/u/26471?v=4"},"body":"Don’t waste time checking for dangling refs; they wouldn’t affect the\noutput of ‘git describe’ anyway. Although this doesn’t gain much\nperformance by itself, it does in conjunction with the next commits.\n\nSigned-off-by: Anders Kaseorg \n---\n builtin/describe.c | 2 +-\n 1 files changed, 1 insertions(+), 1 deletions(-)\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 43caff2..700f740 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -418,7 +418,7 @@ int cmd_describe(int argc, const char **argv, const char *prefix)\n \t\treturn cmd_name_rev(i + argc, args, prefix);\n \t}\n \n-\tfor_each_ref(get_name, NULL);\n+\tfor_each_rawref(get_name, NULL);\n \tif (!found_names && !always)\n \t\tdie(\"No names found, cannot describe anything.\");\n \n-- \n1.7.3.3\n"},{"id":"157575","messageId":"alpine.DEB.2.02.1012072342480.23348@dr-wily.mit.edu","threadId":"25773","inReplyTo":"alpine.DEB.2.02.1012072341570.23348@dr-wily.mit.edu","subject":"[PATCH v2 2/4] describe: Don’t use a flex array in struct commit_name","fromName":"Anders Kaseorg","fromEmail":"andersk@ksplice.com","sentAt":"2010-12-08T04:43:18Z","receivedAt":"2010-12-08T04:43:18Z","isPatch":true,"sender":{"key":"andersk@mit.edu","avatar":"https://avatars.githubusercontent.com/u/26471?v=4"},"body":"Now add_to_known_names overwrites commit_names in place when multiple\ntags point to the same commit. This will make it easier to store\ncommit_names in a hash table.\n\nSigned-off-by: Anders Kaseorg \n---\n builtin/describe.c | 12 ++++++------\n 1 files changed, 6 insertions(+), 6 deletions(-)\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 700f740..5b8461d 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -38,7 +38,7 @@ struct commit_name {\n \tunsigned prio:2; /* annotated tag = 2, tag = 1, head = 0 */\n \tunsigned name_checked:1;\n \tunsigned char sha1[20];\n-\tchar path[FLEX_ARRAY]; /* more */\n+\tconst char *path;\n };\n static const char *prio_names[] = {\n \t\"head\", \"lightweight\", \"annotated\",\n@@ -85,15 +85,15 @@ static void add_to_known_names(const char *path,\n \tstruct commit_name *e = commit->util;\n \tstruct tag *tag = NULL;\n \tif (replace_name(e, prio, sha1, &tag)) {\n-\t\tsize_t len = strlen(path)+1;\n-\t\tfree(e);\n-\t\te = xmalloc(sizeof(struct commit_name) + len);\n+\t\tif (!e) {\n+\t\t\te = xmalloc(sizeof(struct commit_name));\n+\t\t\tcommit->util = e;\n+\t\t}\n \t\te->tag = tag;\n \t\te->prio = prio;\n \t\te->name_checked = 0;\n \t\thashcpy(e->sha1, sha1);\n-\t\tmemcpy(e->path, path, len);\n-\t\tcommit->util = e;\n+\t\te->path = path;\n \t}\n \tfound_names = 1;\n }\n-- \n1.7.3.3\n"},{"id":"157576","messageId":"alpine.DEB.2.02.1012072343300.23348@dr-wily.mit.edu","threadId":"25773","inReplyTo":"alpine.DEB.2.02.1012072341570.23348@dr-wily.mit.edu","subject":"[PATCH v2 3/4] describe: Store commit_names in a hash table by commit SHA1","fromName":"Anders Kaseorg","fromEmail":"andersk@ksplice.com","sentAt":"2010-12-08T04:43:54Z","receivedAt":"2010-12-08T04:43:54Z","isPatch":true,"sender":{"key":"andersk@mit.edu","avatar":"https://avatars.githubusercontent.com/u/26471?v=4"},"body":"describe is currently forced to look up the commit at each tag in\norder to store the struct commit_name pointers in struct commit.util.\nFor --exact-match queries, those lookups are wasteful. In preparation\nfor removing them, put the commit_names into a hash table, indexed by\ncommit SHA1, that can be used to quickly check for exact matches.\n\nSigned-off-by: Anders Kaseorg \n---\n builtin/describe.c | 36 +++++++++++++++++++++++++++++++-----\n 1 files changed, 31 insertions(+), 5 deletions(-)\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 5b8461d..afc50c0 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -6,6 +6,7 @@\n #include \"exec_cmd.h\"\n #include \"parse-options.h\"\n #include \"diff.h\"\n+#include \"hash.h\"\n \n #define SEEN\t\t(1u<<0)\n #define MAX_TAGS\t(FLAG_BITS - 1)\n@@ -22,7 +23,7 @@ static int tags;\t/* Allow lightweight tags */\n static int longformat;\n static int abbrev = DEFAULT_ABBREV;\n static int max_candidates = 10;\n-static int found_names;\n+struct hash_table names;\n static const char *pattern;\n static int always;\n static const char *dirty;\n@@ -34,6 +35,8 @@ static const char *diff_index_args[] = {\n \n \n struct commit_name {\n+\tstruct commit_name *next;\n+\tunsigned char peeled[20];\n \tstruct tag *tag;\n \tunsigned prio:2; /* annotated tag = 2, tag = 1, head = 0 */\n \tunsigned name_checked:1;\n@@ -44,6 +47,19 @@ static const char *prio_names[] = {\n \t\"head\", \"lightweight\", \"annotated\",\n };\n \n+static inline unsigned int hash_sha1(const unsigned char *sha1)\n+{\n+\treturn *(unsigned int *)sha1;\n+}\n+\n+static inline struct commit_name *find_commit_name(const unsigned char *peeled)\n+{\n+\tstruct commit_name *n = lookup_hash(hash_sha1(peeled), &names);\n+\twhile (n && !!hashcmp(peeled, n->peeled))\n+\t\tn = n->next;\n+\treturn n;\n+}\n+\n static int replace_name(struct commit_name *e,\n \t\t\t int prio,\n \t\t\t const unsigned char *sha1,\n@@ -82,12 +98,22 @@ static void add_to_known_names(const char *path,\n \t\t\t int prio,\n \t\t\t const unsigned char *sha1)\n {\n-\tstruct commit_name *e = commit->util;\n+\tconst unsigned char *peeled = commit->object.sha1;\n+\tstruct commit_name *e = find_commit_name(peeled);\n \tstruct tag *tag = NULL;\n \tif (replace_name(e, prio, sha1, &tag)) {\n \t\tif (!e) {\n+\t\t\tvoid **pos;\n \t\t\te = xmalloc(sizeof(struct commit_name));\n \t\t\tcommit->util = e;\n+\t\t\thashcpy(e->peeled, peeled);\n+\t\t\tpos = insert_hash(hash_sha1(peeled), e, &names);\n+\t\t\tif (pos) {\n+\t\t\t\te->next = *pos;\n+\t\t\t\t*pos = e;\n+\t\t\t} else {\n+\t\t\t\te->next = NULL;\n+\t\t\t}\n \t\t}\n \t\te->tag = tag;\n \t\te->prio = prio;\n@@ -95,7 +121,6 @@ static void add_to_known_names(const char *path,\n \t\thashcpy(e->sha1, sha1);\n \t\te->path = path;\n \t}\n-\tfound_names = 1;\n }\n \n static int get_name(const char *path, const unsigned char *sha1, int flag, void *cb_data)\n@@ -240,7 +265,7 @@ static void describe(const char *arg, int last_one)\n \tif (!cmit)\n \t\tdie(\"%s is not a valid '%s' object\", arg, commit_type);\n \n-\tn = cmit->util;\n+\tn = find_commit_name(cmit->object.sha1);\n \tif (n && (tags || all || n->prio == 2)) {\n \t\t/*\n \t\t * Exact match to an existing ref.\n@@ -418,8 +443,9 @@ int cmd_describe(int argc, const char **argv, const char *prefix)\n \t\treturn cmd_name_rev(i + argc, args, prefix);\n \t}\n \n+\tinit_hash(&names);\n \tfor_each_rawref(get_name, NULL);\n-\tif (!found_names && !always)\n+\tif (!names.nr && !always)\n \t\tdie(\"No names found, cannot describe anything.\");\n \n \tif (argc == 0) {\n-- \n1.7.3.3\n"},{"id":"157577","messageId":"alpine.DEB.2.02.1012072344000.23348@dr-wily.mit.edu","threadId":"25773","inReplyTo":"alpine.DEB.2.02.1012072341570.23348@dr-wily.mit.edu","subject":"[PATCH v2 4/4] describe: Delay looking up commits until searching for an inexact match","fromName":"Anders Kaseorg","fromEmail":"andersk@ksplice.com","sentAt":"2010-12-08T04:46:16Z","receivedAt":"2010-12-08T04:46:16Z","isPatch":true,"sender":{"key":"andersk@mit.edu","avatar":"https://avatars.githubusercontent.com/u/26471?v=4"},"body":"Now that struct commit.util is not used until after we’ve checked that\nthe argument doesn’t exactly match a tag, we can wait until then to\nlook up the commits for each tag.\n\nThis avoids a lot of I/O on --exact-match queries in repositories with\nmany tags. For example, ‘git describe --exact-match HEAD’ becomes\nabout 12 times faster on a cold cache (3.2s instead of 39s) in a\nlinux-2.6 repository with 2000 packed tags. That’s a huge win for the\ninteractivity of the __git_ps1 shell prompt helper when on a detached\nHEAD.\n\nSigned-off-by: Anders Kaseorg \n---\n\n(The benchmark numbers are different because my linux-2.6 repository has \nchanged; I don’t think this version is actually slower.)\n\n builtin/describe.c | 35 ++++++++++++++++++++---------------\n 1 files changed, 20 insertions(+), 15 deletions(-)\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex afc50c0..2633371 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -24,6 +24,7 @@ static int longformat;\n static int abbrev = DEFAULT_ABBREV;\n static int max_candidates = 10;\n struct hash_table names;\n+static int have_util;\n static const char *pattern;\n static int always;\n static const char *dirty;\n@@ -60,6 +61,15 @@ static inline struct commit_name *find_commit_name(const unsigned char *peeled)\n \treturn n;\n }\n \n+static int set_util(void *vn)\n+{\n+\tstruct commit_name *n = vn;\n+\tstruct commit *c = lookup_commit_reference_gently(n->peeled, 1);\n+\tif (c)\n+\t\tc->util = n;\n+\treturn 0;\n+}\n+\n static int replace_name(struct commit_name *e,\n \t\t\t int prio,\n \t\t\t const unsigned char *sha1,\n@@ -94,18 +104,16 @@ static int replace_name(struct commit_name *e,\n }\n \n static void add_to_known_names(const char *path,\n-\t\t\t struct commit *commit,\n+\t\t\t const unsigned char *peeled,\n \t\t\t int prio,\n \t\t\t const unsigned char *sha1)\n {\n-\tconst unsigned char *peeled = commit->object.sha1;\n \tstruct commit_name *e = find_commit_name(peeled);\n \tstruct tag *tag = NULL;\n \tif (replace_name(e, prio, sha1, &tag)) {\n \t\tif (!e) {\n \t\t\tvoid **pos;\n \t\t\te = xmalloc(sizeof(struct commit_name));\n-\t\t\tcommit->util = e;\n \t\t\thashcpy(e->peeled, peeled);\n \t\t\tpos = insert_hash(hash_sha1(peeled), e, &names);\n \t\t\tif (pos) {\n@@ -126,8 +134,6 @@ static void add_to_known_names(const char *path,\n static int get_name(const char *path, const unsigned char *sha1, int flag, void *cb_data)\n {\n \tint might_be_tag = !prefixcmp(path, \"refs/tags/\");\n-\tstruct commit *commit;\n-\tstruct object *object;\n \tunsigned char peeled[20];\n \tint is_tag, prio;\n \n@@ -135,16 +141,10 @@ static int get_name(const char *path, const unsigned char *sha1, int flag, void\n \t\treturn 0;\n \n \tif (!peel_ref(path, peeled) && !is_null_sha1(peeled)) {\n-\t\tcommit = lookup_commit_reference_gently(peeled, 1);\n-\t\tif (!commit)\n-\t\t\treturn 0;\n-\t\tis_tag = !!hashcmp(sha1, commit->object.sha1);\n+\t\tis_tag = !!hashcmp(sha1, peeled);\n \t} else {\n-\t\tcommit = lookup_commit_reference_gently(sha1, 1);\n-\t\tobject = parse_object(sha1);\n-\t\tif (!commit || !object)\n-\t\t\treturn 0;\n-\t\tis_tag = object->type == OBJ_TAG;\n+\t\thashcpy(peeled, sha1);\n+\t\tis_tag = 0;\n \t}\n \n \t/* If --all, then any refs are used.\n@@ -167,7 +167,7 @@ static int get_name(const char *path, const unsigned char *sha1, int flag, void\n \t\tif (!prio)\n \t\t\treturn 0;\n \t}\n-\tadd_to_known_names(all ? path + 5 : path + 10, commit, prio, sha1);\n+\tadd_to_known_names(all ? path + 5 : path + 10, peeled, prio, sha1);\n \treturn 0;\n }\n \n@@ -284,6 +284,11 @@ static void describe(const char *arg, int last_one)\n \tif (debug)\n \t\tfprintf(stderr, \"searching to describe %s\\n\", arg);\n \n+\tif (!have_util) {\n+\t\tfor_each_hash(&names, set_util);\n+\t\thave_util = 1;\n+\t}\n+\n \tlist = NULL;\n \tcmit->object.flags = SEEN;\n \tcommit_list_insert(cmit, &list);\n-- \n1.7.3.3\n"},{"id":"157618","messageId":"alpine.DEB.2.02.1012081319320.23348@dr-wily.mit.edu","threadId":"25773","inReplyTo":"alpine.DEB.2.02.1012072343300.23348@dr-wily.mit.edu","subject":"[PATCH v2.1 3/4] describe: Store commit_names in a hash table by commit SHA1","fromName":"Anders Kaseorg","fromEmail":"andersk@ksplice.com","sentAt":"2010-12-08T18:23:24Z","receivedAt":"2010-12-08T18:23:24Z","isPatch":true,"sender":{"key":"andersk@mit.edu","avatar":"https://avatars.githubusercontent.com/u/26471?v=4"},"body":"describe is currently forced to look up the commit at each tag in\norder to store the struct commit_name pointers in struct commit.util.\nFor --exact-match queries, those lookups are wasteful. In preparation\nfor removing them, put the commit_names into a hash table, indexed by\ncommit SHA1, that can be used to quickly check for exact matches.\n\nSigned-off-by: Anders Kaseorg \n---\nChange from v2: I had forgotten to make ‘names’ static again (thanks \nJonathan).\n\n builtin/describe.c | 36 +++++++++++++++++++++++++++++++-----\n 1 files changed, 31 insertions(+), 5 deletions(-)\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 5b8461d..5d709b6 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -6,6 +6,7 @@\n #include \"exec_cmd.h\"\n #include \"parse-options.h\"\n #include \"diff.h\"\n+#include \"hash.h\"\n \n #define SEEN\t\t(1u<<0)\n #define MAX_TAGS\t(FLAG_BITS - 1)\n@@ -22,7 +23,7 @@ static int tags;\t/* Allow lightweight tags */\n static int longformat;\n static int abbrev = DEFAULT_ABBREV;\n static int max_candidates = 10;\n-static int found_names;\n+static struct hash_table names;\n static const char *pattern;\n static int always;\n static const char *dirty;\n@@ -34,6 +35,8 @@ static const char *diff_index_args[] = {\n \n \n struct commit_name {\n+\tstruct commit_name *next;\n+\tunsigned char peeled[20];\n \tstruct tag *tag;\n \tunsigned prio:2; /* annotated tag = 2, tag = 1, head = 0 */\n \tunsigned name_checked:1;\n@@ -44,6 +47,19 @@ static const char *prio_names[] = {\n \t\"head\", \"lightweight\", \"annotated\",\n };\n \n+static inline unsigned int hash_sha1(const unsigned char *sha1)\n+{\n+\treturn *(unsigned int *)sha1;\n+}\n+\n+static inline struct commit_name *find_commit_name(const unsigned char *peeled)\n+{\n+\tstruct commit_name *n = lookup_hash(hash_sha1(peeled), &names);\n+\twhile (n && !!hashcmp(peeled, n->peeled))\n+\t\tn = n->next;\n+\treturn n;\n+}\n+\n static int replace_name(struct commit_name *e,\n \t\t\t int prio,\n \t\t\t const unsigned char *sha1,\n@@ -82,12 +98,22 @@ static void add_to_known_names(const char *path,\n \t\t\t int prio,\n \t\t\t const unsigned char *sha1)\n {\n-\tstruct commit_name *e = commit->util;\n+\tconst unsigned char *peeled = commit->object.sha1;\n+\tstruct commit_name *e = find_commit_name(peeled);\n \tstruct tag *tag = NULL;\n \tif (replace_name(e, prio, sha1, &tag)) {\n \t\tif (!e) {\n+\t\t\tvoid **pos;\n \t\t\te = xmalloc(sizeof(struct commit_name));\n \t\t\tcommit->util = e;\n+\t\t\thashcpy(e->peeled, peeled);\n+\t\t\tpos = insert_hash(hash_sha1(peeled), e, &names);\n+\t\t\tif (pos) {\n+\t\t\t\te->next = *pos;\n+\t\t\t\t*pos = e;\n+\t\t\t} else {\n+\t\t\t\te->next = NULL;\n+\t\t\t}\n \t\t}\n \t\te->tag = tag;\n \t\te->prio = prio;\n@@ -95,7 +121,6 @@ static void add_to_known_names(const char *path,\n \t\thashcpy(e->sha1, sha1);\n \t\te->path = path;\n \t}\n-\tfound_names = 1;\n }\n \n static int get_name(const char *path, const unsigned char *sha1, int flag, void *cb_data)\n@@ -240,7 +265,7 @@ static void describe(const char *arg, int last_one)\n \tif (!cmit)\n \t\tdie(\"%s is not a valid '%s' object\", arg, commit_type);\n \n-\tn = cmit->util;\n+\tn = find_commit_name(cmit->object.sha1);\n \tif (n && (tags || all || n->prio == 2)) {\n \t\t/*\n \t\t * Exact match to an existing ref.\n@@ -418,8 +443,9 @@ int cmd_describe(int argc, const char **argv, const char *prefix)\n \t\treturn cmd_name_rev(i + argc, args, prefix);\n \t}\n \n+\tinit_hash(&names);\n \tfor_each_rawref(get_name, NULL);\n-\tif (!found_names && !always)\n+\tif (!names.nr && !always)\n \t\tdie(\"No names found, cannot describe anything.\");\n \n \tif (argc == 0) {\n-- \n1.7.3.3\n"},{"id":"157635","messageId":"7v7hfjkhfm.fsf@alter.siamese.dyndns.org","threadId":"25773","inReplyTo":"alpine.DEB.2.02.1012072344000.23348@dr-wily.mit.edu","subject":"Re: [PATCH v2 4/4] describe: Delay looking up commits until searching for an inexact match","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2010-12-08T22:50:37Z","receivedAt":"2010-12-08T22:50:37Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Anders Kaseorg writes:\n\n> Now that struct commit.util is not used until after we’ve checked that\n> the argument doesn’t exactly match a tag, we can wait until then to\n> look up the commits for each tag.\n>\n> This avoids a lot of I/O on --exact-match queries in repositories with\n> many tags. For example, ‘git describe --exact-match HEAD’ becomes\n> about 12 times faster on a cold cache (3.2s instead of 39s) in a\n> linux-2.6 repository with 2000 packed tags. That’s a huge win for the\n> interactivity of the __git_ps1 shell prompt helper when on a detached\n> HEAD.\n\nYou seem to have gone in a slightly different direction with this reroll.\nI am not sure if use of hash_table in this code would actually improve\nanything (aside from the general readability and \"reusing code from a good\ninfrastructure is a good thing\" principle), though, no matter how many\ntags you have in your repository. In the code from the earlier round,\nlookup_commit_reference_gently call in the fallback codepath to populate\ncommit->util used the *obj_hash[] to quickly look up the commits with the\nsame object name already.\n\n> @@ -60,6 +61,15 @@ static inline struct commit_name *find_commit_name(const unsigned char *peeled)\n> \treturn n;\n> }\n> \n> +static int set_util(void *vn)\n> +{\n> +\tstruct commit_name *n = vn;\n> +\tstruct commit *c = lookup_commit_reference_gently(n->peeled, 1);\n> +\tif (c)\n> +\t\tc->util = n;\n> +\treturn 0;\n> +}\n\nI don't know how the above would work in the face of hash collisions.\n\nThis is a callback for for_each_hash(), which visits each populated entry\nin the underlying hash table. The semantics of the hash table hash.c\ngives you is \"here is a flat hash table. We insert only to an empty\nfield, and otherwise we will tell you where your new element would have\nhashed into, so that you can implement linear overflow or chained buckets\nyourself on top of this\", and you chose to implement bucket chaining in\nadd_to_known_names(), so don't you need to walk the chain here for commits\nthat share the same first four bytes in their object names?\n"},{"id":"157636","messageId":"7v1v5rkhfb.fsf@alter.siamese.dyndns.org","threadId":"25773","inReplyTo":"alpine.DEB.2.02.1012081319320.23348@dr-wily.mit.edu","subject":"Re: [PATCH v2.1 3/4] describe: Store commit_names in a hash table by commit SHA1","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2010-12-08T22:50:48Z","receivedAt":"2010-12-08T22:50:48Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Anders Kaseorg writes:\n\n> @@ -44,6 +47,19 @@ static const char *prio_names[] = {\n> \t\"head\", \"lightweight\", \"annotated\",\n> };\n> \n> +static inline unsigned int hash_sha1(const unsigned char *sha1)\n> +{\n> +\treturn *(unsigned int *)sha1;\n> +}\n\nDo we know that all the archs we will be compiled on will be happy with\nthis potentially unaligned access? hash_filespec() in diffcore-rename.c\nis written in a way to avoid such an issue, and I would feel safer to see\nthis do the same.\n"},{"id":"157653","messageId":"alpine.DEB.2.02.1012081800540.23348@dr-wily.mit.edu","threadId":"25773","inReplyTo":"7v7hfjkhfm.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH v2 4/4] describe: Delay looking up commits until searching for an inexact match","fromName":"Anders Kaseorg","fromEmail":"andersk@ksplice.com","sentAt":"2010-12-08T23:47:36Z","receivedAt":"2010-12-08T23:47:36Z","isPatch":true,"sender":{"key":"andersk@mit.edu","avatar":"https://avatars.githubusercontent.com/u/26471?v=4"},"body":"On Wed, 8 Dec 2010, Junio C Hamano wrote:\n> You seem to have gone in a slightly different direction with this reroll.\n> I am not sure if use of hash_table in this code would actually improve\n> anything (aside from the general readability and \"reusing code from a good\n> infrastructure is a good thing\" principle), though, no matter how many\n> tags you have in your repository. In the code from the earlier round,\n> lookup_commit_reference_gently call in the fallback codepath to populate\n> commit->util used the *obj_hash[] to quickly look up the commits with the\n> same object name already.\n\nYes; the problem now is that, in order to avoid calling replace_name() \nexcessively, I need to resolve all multiply-tagged commits in one pass, \nbefore I have those commits in the obj_hash. This could have been done \nwith the linked list by deleting any commit_name from the linked list the \nfirst time replace_name() decides it should be superseded by a different \ncommit_name, but the hash table approach seems less fragile to me. The \nhash table also has the advantage of avoiding the O(#tags * #arguments) \ncomplexity when describe is given many arguments.\n\nLet me know if you’d like me to try it the other way.\n\n> I don't know how the above would work in the face of hash collisions.\n\nOh right. I’ll fix that.\n\nstatic int set_util(void *chain)\n{\n\tstruct commit_name *n;\n\tfor (n = chain; n; n = n->next) {\n\t\tstruct commit *c = lookup_commit_reference_gently(n->peeled, 1);\n\t\tif (c)\n\t\t\tc->util = n;\n\t}\n\treturn 0;\n}\n\n> Do we know that all the archs we will be compiled on will be happy with\n> this potentially unaligned access? hash_filespec() in diffcore-rename.c\n> is written in a way to avoid such an issue, and I would feel safer to \n> see this do the same.\n\nI’ll fix that too.\n\nstatic inline unsigned int hash_sha1(const unsigned char *sha1)\n{\n\tunsigned int hash;\n\tmemcpy(&hash, sha1, sizeof(hash));\n\treturn hash;\n}\n\nAnders\n"},{"id":"157673","messageId":"alpine.DEB.2.02.1012090140390.23348@dr-wily.mit.edu","threadId":"25773","inReplyTo":"alpine.DEB.2.02.1012081800540.23348@dr-wily.mit.edu","subject":"[PATCH v3 1/4] describe: Use for_each_rawref","fromName":"Anders Kaseorg","fromEmail":"andersk@ksplice.com","sentAt":"2010-12-09T06:42:25Z","receivedAt":"2010-12-09T06:42:25Z","isPatch":true,"sender":{"key":"andersk@mit.edu","avatar":"https://avatars.githubusercontent.com/u/26471?v=4"},"body":"Don’t waste time checking for dangling refs; they wouldn’t affect the\noutput of ‘git describe’ anyway. Although this doesn’t gain much\nperformance by itself, it does in conjunction with the next commits.\n\nSigned-off-by: Anders Kaseorg \n---\n builtin/describe.c | 2 +-\n 1 files changed, 1 insertions(+), 1 deletions(-)\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 43caff2..700f740 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -418,7 +418,7 @@ int cmd_describe(int argc, const char **argv, const char *prefix)\n \t\treturn cmd_name_rev(i + argc, args, prefix);\n \t}\n \n-\tfor_each_ref(get_name, NULL);\n+\tfor_each_rawref(get_name, NULL);\n \tif (!found_names && !always)\n \t\tdie(\"No names found, cannot describe anything.\");\n \n-- \n1.7.3.3\n"},{"id":"157674","messageId":"alpine.DEB.2.02.1012090142560.23348@dr-wily.mit.edu","threadId":"25773","inReplyTo":"alpine.DEB.2.02.1012090140390.23348@dr-wily.mit.edu","subject":"[PATCH v3 2/4] describe: Don’t use a flex array in struct commit_name","fromName":"Anders Kaseorg","fromEmail":"andersk@ksplice.com","sentAt":"2010-12-09T06:43:32Z","receivedAt":"2010-12-09T06:43:32Z","isPatch":true,"sender":{"key":"andersk@mit.edu","avatar":"https://avatars.githubusercontent.com/u/26471?v=4"},"body":"Now add_to_known_names overwrites commit_names in place when multiple\ntags point to the same commit. This will make it easier to store\ncommit_names in a hash table.\n\nSigned-off-by: Anders Kaseorg \n---\n builtin/describe.c | 12 ++++++------\n 1 files changed, 6 insertions(+), 6 deletions(-)\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 700f740..5b8461d 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -38,7 +38,7 @@ struct commit_name {\n \tunsigned prio:2; /* annotated tag = 2, tag = 1, head = 0 */\n \tunsigned name_checked:1;\n \tunsigned char sha1[20];\n-\tchar path[FLEX_ARRAY]; /* more */\n+\tconst char *path;\n };\n static const char *prio_names[] = {\n \t\"head\", \"lightweight\", \"annotated\",\n@@ -85,15 +85,15 @@ static void add_to_known_names(const char *path,\n \tstruct commit_name *e = commit->util;\n \tstruct tag *tag = NULL;\n \tif (replace_name(e, prio, sha1, &tag)) {\n-\t\tsize_t len = strlen(path)+1;\n-\t\tfree(e);\n-\t\te = xmalloc(sizeof(struct commit_name) + len);\n+\t\tif (!e) {\n+\t\t\te = xmalloc(sizeof(struct commit_name));\n+\t\t\tcommit->util = e;\n+\t\t}\n \t\te->tag = tag;\n \t\te->prio = prio;\n \t\te->name_checked = 0;\n \t\thashcpy(e->sha1, sha1);\n-\t\tmemcpy(e->path, path, len);\n-\t\tcommit->util = e;\n+\t\te->path = path;\n \t}\n \tfound_names = 1;\n }\n-- \n1.7.3.3\n"},{"id":"157676","messageId":"alpine.DEB.2.02.1012090143440.23348@dr-wily.mit.edu","threadId":"25773","inReplyTo":"alpine.DEB.2.02.1012090140390.23348@dr-wily.mit.edu","subject":"[PATCH v3 3/4] describe: Store commit_names in a hash table by commit SHA1","fromName":"Anders Kaseorg","fromEmail":"andersk@ksplice.com","sentAt":"2010-12-09T06:46:08Z","receivedAt":"2010-12-09T06:46:08Z","isPatch":true,"sender":{"key":"andersk@mit.edu","avatar":"https://avatars.githubusercontent.com/u/26471?v=4"},"body":"describe is currently forced to look up the commit at each tag in\norder to store the struct commit_name pointers in struct commit.util.\nFor --exact-match queries, those lookups are wasteful. In preparation\nfor removing them, put the commit_names into a hash table, indexed by\ncommit SHA1, that can be used to quickly check for exact matches.\n\nSigned-off-by: Anders Kaseorg \n---\n\nChange from v2.1: Use memcpy to avoid unaligned accesses in hash_sha1().\n\n builtin/describe.c | 38 +++++++++++++++++++++++++++++++++-----\n 1 files changed, 33 insertions(+), 5 deletions(-)\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 5b8461d..8149233 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -6,6 +6,7 @@\n #include \"exec_cmd.h\"\n #include \"parse-options.h\"\n #include \"diff.h\"\n+#include \"hash.h\"\n \n #define SEEN\t\t(1u<<0)\n #define MAX_TAGS\t(FLAG_BITS - 1)\n@@ -22,7 +23,7 @@ static int tags;\t/* Allow lightweight tags */\n static int longformat;\n static int abbrev = DEFAULT_ABBREV;\n static int max_candidates = 10;\n-static int found_names;\n+static struct hash_table names;\n static const char *pattern;\n static int always;\n static const char *dirty;\n@@ -34,6 +35,8 @@ static const char *diff_index_args[] = {\n \n \n struct commit_name {\n+\tstruct commit_name *next;\n+\tunsigned char peeled[20];\n \tstruct tag *tag;\n \tunsigned prio:2; /* annotated tag = 2, tag = 1, head = 0 */\n \tunsigned name_checked:1;\n@@ -44,6 +47,21 @@ static const char *prio_names[] = {\n \t\"head\", \"lightweight\", \"annotated\",\n };\n \n+static inline unsigned int hash_sha1(const unsigned char *sha1)\n+{\n+\tunsigned int hash;\n+\tmemcpy(&hash, sha1, sizeof(hash));\n+\treturn hash;\n+}\n+\n+static inline struct commit_name *find_commit_name(const unsigned char *peeled)\n+{\n+\tstruct commit_name *n = lookup_hash(hash_sha1(peeled), &names);\n+\twhile (n && !!hashcmp(peeled, n->peeled))\n+\t\tn = n->next;\n+\treturn n;\n+}\n+\n static int replace_name(struct commit_name *e,\n \t\t\t int prio,\n \t\t\t const unsigned char *sha1,\n@@ -82,12 +100,22 @@ static void add_to_known_names(const char *path,\n \t\t\t int prio,\n \t\t\t const unsigned char *sha1)\n {\n-\tstruct commit_name *e = commit->util;\n+\tconst unsigned char *peeled = commit->object.sha1;\n+\tstruct commit_name *e = find_commit_name(peeled);\n \tstruct tag *tag = NULL;\n \tif (replace_name(e, prio, sha1, &tag)) {\n \t\tif (!e) {\n+\t\t\tvoid **pos;\n \t\t\te = xmalloc(sizeof(struct commit_name));\n \t\t\tcommit->util = e;\n+\t\t\thashcpy(e->peeled, peeled);\n+\t\t\tpos = insert_hash(hash_sha1(peeled), e, &names);\n+\t\t\tif (pos) {\n+\t\t\t\te->next = *pos;\n+\t\t\t\t*pos = e;\n+\t\t\t} else {\n+\t\t\t\te->next = NULL;\n+\t\t\t}\n \t\t}\n \t\te->tag = tag;\n \t\te->prio = prio;\n@@ -95,7 +123,6 @@ static void add_to_known_names(const char *path,\n \t\thashcpy(e->sha1, sha1);\n \t\te->path = path;\n \t}\n-\tfound_names = 1;\n }\n \n static int get_name(const char *path, const unsigned char *sha1, int flag, void *cb_data)\n@@ -240,7 +267,7 @@ static void describe(const char *arg, int last_one)\n \tif (!cmit)\n \t\tdie(\"%s is not a valid '%s' object\", arg, commit_type);\n \n-\tn = cmit->util;\n+\tn = find_commit_name(cmit->object.sha1);\n \tif (n && (tags || all || n->prio == 2)) {\n \t\t/*\n \t\t * Exact match to an existing ref.\n@@ -418,8 +445,9 @@ int cmd_describe(int argc, const char **argv, const char *prefix)\n \t\treturn cmd_name_rev(i + argc, args, prefix);\n \t}\n \n+\tinit_hash(&names);\n \tfor_each_rawref(get_name, NULL);\n-\tif (!found_names && !always)\n+\tif (!names.nr && !always)\n \t\tdie(\"No names found, cannot describe anything.\");\n \n \tif (argc == 0) {\n-- \n1.7.3.3\n"},{"id":"157677","messageId":"alpine.DEB.2.02.1012090146160.23348@dr-wily.mit.edu","threadId":"25773","inReplyTo":"alpine.DEB.2.02.1012090140390.23348@dr-wily.mit.edu","subject":"[PATCH v3 4/4] describe: Delay looking up commits until searching for an inexact match","fromName":"Anders Kaseorg","fromEmail":"andersk@ksplice.com","sentAt":"2010-12-09T06:47:29Z","receivedAt":"2010-12-09T06:47:29Z","isPatch":true,"sender":{"key":"andersk@mit.edu","avatar":"https://avatars.githubusercontent.com/u/26471?v=4"},"body":"Now that struct commit.util is not used until after we’ve checked that\nthe argument doesn’t exactly match a tag, we can wait until then to\nlook up the commits for each tag.\n\nThis avoids a lot of I/O on --exact-match queries in repositories with\nmany tags. For example, ‘git describe --exact-match HEAD’ becomes\nabout 12 times faster on a cold cache (3.2s instead of 39s) in a\nlinux-2.6 repository with 2000 packed tags. That’s a huge win for the\ninteractivity of the __git_ps1 shell prompt helper when on a detached\nHEAD.\n\nSigned-off-by: Anders Kaseorg \n---\n\nChange from v2: Process the entire hash chain in set_util().\n\n builtin/describe.c | 37 ++++++++++++++++++++++---------------\n 1 files changed, 22 insertions(+), 15 deletions(-)\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 8149233..a0f52c1 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -24,6 +24,7 @@ static int longformat;\n static int abbrev = DEFAULT_ABBREV;\n static int max_candidates = 10;\n static struct hash_table names;\n+static int have_util;\n static const char *pattern;\n static int always;\n static const char *dirty;\n@@ -62,6 +63,17 @@ static inline struct commit_name *find_commit_name(const unsigned char *peeled)\n \treturn n;\n }\n \n+static int set_util(void *chain)\n+{\n+\tstruct commit_name *n;\n+\tfor (n = chain; n; n = n->next) {\n+\t\tstruct commit *c = lookup_commit_reference_gently(n->peeled, 1);\n+\t\tif (c)\n+\t\t\tc->util = n;\n+\t}\n+\treturn 0;\n+}\n+\n static int replace_name(struct commit_name *e,\n \t\t\t int prio,\n \t\t\t const unsigned char *sha1,\n@@ -96,18 +108,16 @@ static int replace_name(struct commit_name *e,\n }\n \n static void add_to_known_names(const char *path,\n-\t\t\t struct commit *commit,\n+\t\t\t const unsigned char *peeled,\n \t\t\t int prio,\n \t\t\t const unsigned char *sha1)\n {\n-\tconst unsigned char *peeled = commit->object.sha1;\n \tstruct commit_name *e = find_commit_name(peeled);\n \tstruct tag *tag = NULL;\n \tif (replace_name(e, prio, sha1, &tag)) {\n \t\tif (!e) {\n \t\t\tvoid **pos;\n \t\t\te = xmalloc(sizeof(struct commit_name));\n-\t\t\tcommit->util = e;\n \t\t\thashcpy(e->peeled, peeled);\n \t\t\tpos = insert_hash(hash_sha1(peeled), e, &names);\n \t\t\tif (pos) {\n@@ -128,8 +138,6 @@ static void add_to_known_names(const char *path,\n static int get_name(const char *path, const unsigned char *sha1, int flag, void *cb_data)\n {\n \tint might_be_tag = !prefixcmp(path, \"refs/tags/\");\n-\tstruct commit *commit;\n-\tstruct object *object;\n \tunsigned char peeled[20];\n \tint is_tag, prio;\n \n@@ -137,16 +145,10 @@ static int get_name(const char *path, const unsigned char *sha1, int flag, void\n \t\treturn 0;\n \n \tif (!peel_ref(path, peeled) && !is_null_sha1(peeled)) {\n-\t\tcommit = lookup_commit_reference_gently(peeled, 1);\n-\t\tif (!commit)\n-\t\t\treturn 0;\n-\t\tis_tag = !!hashcmp(sha1, commit->object.sha1);\n+\t\tis_tag = !!hashcmp(sha1, peeled);\n \t} else {\n-\t\tcommit = lookup_commit_reference_gently(sha1, 1);\n-\t\tobject = parse_object(sha1);\n-\t\tif (!commit || !object)\n-\t\t\treturn 0;\n-\t\tis_tag = object->type == OBJ_TAG;\n+\t\thashcpy(peeled, sha1);\n+\t\tis_tag = 0;\n \t}\n \n \t/* If --all, then any refs are used.\n@@ -169,7 +171,7 @@ static int get_name(const char *path, const unsigned char *sha1, int flag, void\n \t\tif (!prio)\n \t\t\treturn 0;\n \t}\n-\tadd_to_known_names(all ? path + 5 : path + 10, commit, prio, sha1);\n+\tadd_to_known_names(all ? path + 5 : path + 10, peeled, prio, sha1);\n \treturn 0;\n }\n \n@@ -286,6 +288,11 @@ static void describe(const char *arg, int last_one)\n \tif (debug)\n \t\tfprintf(stderr, \"searching to describe %s\\n\", arg);\n \n+\tif (!have_util) {\n+\t\tfor_each_hash(&names, set_util);\n+\t\thave_util = 1;\n+\t}\n+\n \tlist = NULL;\n \tcmit->object.flags = SEEN;\n \tcommit_list_insert(cmit, &list);\n-- \n1.7.3.3\n"}]}