{"thread":{"id":"27604","subject":"[PATCH 0/4] Speed up git tag --contains","startedAt":"2011-06-11T19:04:07Z","lastAt":"2018-03-12T23:59:14Z","messageCount":28,"participants":["Ævar Arnfjörð Bjarmason","Jeff King","Jonathan Nieder","Jakub Narebski","Ted Ts'o","Clemens Buchacher","Junio C Hamano","A Large Angry SCM","csilvers","Derrick Stolee"],"isPatch":true,"patchVersion":1,"patchTotal":4},"messages":[{"id":"169878","messageId":"1307819051-25748-1-git-send-email-avarab@gmail.com","threadId":"27604","inReplyTo":null,"subject":"[PATCH 0/4] Speed up git tag --contains","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2011-06-11T19:04:07Z","receivedAt":"2011-06-11T19:04:07Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"This is a resubmission of Jeff King's patch series to speed up git tag\n--contains with some changes. It's been cooking for a while as:\n\n * jk/tag-contains (2010-07-05) 4 commits\n - Why is \"git tag --contains\" so slow?\n - default core.clockskew variable to one day\n - limit \"contains\" traversals based on commit timestamp\n - tag: speed up --contains calculation\n \n The idea of the bottom one is probably Ok, except that the use of object\n flags needs to be rethought, or at least the helper needs to be moved to\n builtin/tag.c to make it clear that it should not be used outside the\n current usage context.\n\nI've moved the relevant code from commit.[ch] to builtin/tag.c as\nJunio's comment suggested. So IMO the \"tag: speed up --contains\ncalculation\" patch is ready to be applied.\n\nThe next two patches look OK to me, but they need some documentation\nfor the core.clockskew variable, which perhaps should be renamed to\ntag.clockskew, or was the plan to use it for other things in the\nfuture?\n\nIs the \"Why is \"git tag --contains\" so slow?\" utility something we\nwant? We'd need some documentation for it, which I could\nwrite. However I couldn't find the magic that turns --all into a\ntraversal of all revisions, and how that would work with supporting\nanother --verbose command-line option, to print out the revisions that\nhave high clock skew. I monkeypatched that in locally and found it\nvery useful to find the worst-case revisions, which in my case were on\ntopic branches that could simply be deleted.\n\nIn any case I've been running git with this series for a while, and\nit's really helpful for a repository I work on with ~10k tags. I'm\nwilling to help get it accepted into the core.\n\nJeff King (4):\n tag: speed up --contains calculation\n limit \"contains\" traversals based on commit timestamp\n default core.clockskew variable to one day\n Why is \"git tag --contains\" so slow?\n\n .gitignore | 1 +\n Makefile | 1 +\n builtin.h | 1 +\n builtin/skew.c | 50 ++++++++++++++++++++++++++++++++++++\n builtin/tag.c | 76 +++++++++++++++++++++++++++++++++++++++++++++++++++++++-\n git.c | 1 +\n 6 files changed, 129 insertions(+), 1 deletions(-)\n create mode 100644 builtin/skew.c\n\n-- \n1.7.5.3\n"},{"id":"169879","messageId":"1307819051-25748-2-git-send-email-avarab@gmail.com","threadId":"27604","inReplyTo":"1307819051-25748-1-git-send-email-avarab@gmail.com","subject":"[PATCH 1/4] tag: speed up --contains calculation","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2011-06-11T19:04:08Z","receivedAt":"2011-06-11T19:04:08Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"From: Jeff King \n\nWhen we want to know if commit A contains commit B (or any\none of a set of commits, B through Z), we generally\ncalculate the merge bases and see if B is a merge base of A\n(or for a set, if any of the commits B through Z have that\nproperty).\n\nWhen we are going to check a series of commits A1 through An\nto see whether each contains B (e.g., because we are\ndeciding which tags to show with \"git tag --contains\"), we\ndo a series of merge base calculations. This can be very\nexpensive, as we repeat a lot of traversal work.\n\nInstead, let's leverage the fact that we are going to use\nthe same --contains list for each tag, and mark areas of the\ncommit graph is definitely containing those commits, or\ndefinitely not containing those commits. Later tags can then\nstop traversing as soon as they see a previously calculated\nanswer.\n\nThis sped up \"git tag --contains HEAD~200\" in the linux-2.6\nrepository from:\n\n real 0m15.417s\n user 0m15.197s\n sys 0m0.220s\n\nto:\n\n real 0m5.329s\n user 0m5.144s\n sys 0m0.184s\n\nSigned-off-by: Jeff King \nSigned-off-by: Junio C Hamano \nSigned-off-by: Ævar Arnfjörð Bjarmason \n---\n builtin/tag.c | 46 +++++++++++++++++++++++++++++++++++++++++++++-\n 1 files changed, 45 insertions(+), 1 deletions(-)\n\ndiff --git a/builtin/tag.c b/builtin/tag.c\nindex ec926fc..575a03c 100644\n--- a/builtin/tag.c\n+++ b/builtin/tag.c\n@@ -12,6 +12,8 @@\n #include \"tag.h\"\n #include \"run-command.h\"\n #include \"parse-options.h\"\n+#include \"diff.h\"\n+#include \"revision.h\"\n \n static const char * const git_tag_usage[] = {\n \t\"git tag [-a|-s|-u ] [-f] [-m |-F ] []\",\n@@ -29,6 +31,48 @@ struct tag_filter {\n \tstruct commit_list *with_commit;\n };\n \n+static int in_commit_list(const struct commit_list *want, struct commit *c)\n+{\n+\tfor (; want; want = want->next)\n+\t\tif (!hashcmp(want->item->object.sha1, c->object.sha1))\n+\t\t\treturn 1;\n+\treturn 0;\n+}\n+\n+static int contains_recurse(struct commit *candidate,\n+\t\t\t const struct commit_list *want)\n+{\n+\tstruct commit_list *p;\n+\n+\t/* was it previously marked as containing a want commit? */\n+\tif (candidate->object.flags & TMP_MARK)\n+\t\treturn 1;\n+\t/* or marked as not possibly containing a want commit? */\n+\tif (candidate->object.flags & UNINTERESTING)\n+\t\treturn 0;\n+\t/* or are we it? */\n+\tif (in_commit_list(want, candidate))\n+\t\treturn 1;\n+\n+\tif (parse_commit(candidate) < 0)\n+\t\treturn 0;\n+\n+\t/* Otherwise recurse and mark ourselves for future traversals. */\n+\tfor (p = candidate->parents; p; p = p->next) {\n+\t\tif (contains_recurse(p->item, want)) {\n+\t\t\tcandidate->object.flags |= TMP_MARK;\n+\t\t\treturn 1;\n+\t\t}\n+\t}\n+\tcandidate->object.flags |= UNINTERESTING;\n+\treturn 0;\n+}\n+\n+int contains(struct commit *candidate, const struct commit_list *want)\n+{\n+\treturn contains_recurse(candidate, want);\n+}\n+\n static int show_reference(const char *refname, const unsigned char *sha1,\n \t\t\t int flag, void *cb_data)\n {\n@@ -47,7 +91,7 @@ static int show_reference(const char *refname, const unsigned char *sha1,\n \t\t\tcommit = lookup_commit_reference_gently(sha1, 1);\n \t\t\tif (!commit)\n \t\t\t\treturn 0;\n-\t\t\tif (!is_descendant_of(commit, filter->with_commit))\n+\t\t\tif (!contains(commit, filter->with_commit))\n \t\t\t\treturn 0;\n \t\t}\n \n-- \n1.7.5.3\n"},{"id":"169880","messageId":"1307819051-25748-3-git-send-email-avarab@gmail.com","threadId":"27604","inReplyTo":"1307819051-25748-1-git-send-email-avarab@gmail.com","subject":"[PATCH 2/4] limit \"contains\" traversals based on commit timestamp","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2011-06-11T19:04:09Z","receivedAt":"2011-06-11T19:04:09Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"From: Jeff King \n\nWhen looking for commits that contain other commits (e.g.,\nvia \"git tag --contains\"), we can end up traversing useless\nportions of the graph. For example, if I am looking for a\ntag that contains a commit made last week, there is not much\npoint in traversing portions of the history graph made five\nyears ago.\n\nThis optimization can provide massive speedups. For example,\ndoing \"git tag --contains HEAD~200\" in the linux-2.6\nrepository goes from:\n\n real 0m5.302s\n user 0m5.116s\n sys 0m0.184s\n\nto:\n\n real 0m0.030s\n user 0m0.020s\n sys 0m0.008s\n\nThe downside is that we will no longer find some answers in\nthe face of extreme clock skew, as we will stop the\ntraversal early when seeing commits skewed too far into the\npast.\n\nName-rev already implements a similar optimization, using a\n\"slop\" of one day to allow for a certain amount of clock\nskew in commit timestamps. This patch introduces a\n\"core.clockskew\" variable, which allows specifying the\nallowable amount of clock skew in seconds. For safety, it\ndefaults to \"none\", causing a full traversal (i.e., no\nchange in behavior from previous versions).\n\nSigned-off-by: Jeff King \nSigned-off-by: Junio C Hamano \nSigned-off-by: Ævar Arnfjörð Bjarmason \n---\n builtin/tag.c | 36 +++++++++++++++++++++++++++++++++---\n 1 files changed, 33 insertions(+), 3 deletions(-)\n\ndiff --git a/builtin/tag.c b/builtin/tag.c\nindex 575a03c..0f0d784 100644\n--- a/builtin/tag.c\n+++ b/builtin/tag.c\n@@ -25,6 +25,8 @@ static const char * const git_tag_usage[] = {\n \n static char signingkey[1000];\n \n+static int core_clock_skew = -1;\n+\n struct tag_filter {\n \tconst char *pattern;\n \tint lines;\n@@ -40,7 +42,8 @@ static int in_commit_list(const struct commit_list *want, struct commit *c)\n }\n \n static int contains_recurse(struct commit *candidate,\n-\t\t\t const struct commit_list *want)\n+\t\t\t const struct commit_list *want,\n+\t\t\t unsigned long cutoff)\n {\n \tstruct commit_list *p;\n \n@@ -57,9 +60,13 @@ static int contains_recurse(struct commit *candidate,\n \tif (parse_commit(candidate) < 0)\n \t\treturn 0;\n \n+\t/* stop searching if we go too far back in time */\n+\tif (candidate->date < cutoff)\n+\t\treturn 0;\n+\n \t/* Otherwise recurse and mark ourselves for future traversals. */\n \tfor (p = candidate->parents; p; p = p->next) {\n-\t\tif (contains_recurse(p->item, want)) {\n+\t\tif (contains_recurse(p->item, want, cutoff)) {\n \t\t\tcandidate->object.flags |= TMP_MARK;\n \t\t\treturn 1;\n \t\t}\n@@ -70,7 +77,22 @@ static int contains_recurse(struct commit *candidate,\n \n int contains(struct commit *candidate, const struct commit_list *want)\n {\n-\treturn contains_recurse(candidate, want);\n+\tunsigned long cutoff = 0;\n+\n+\tif (core_clock_skew >= 0) {\n+\t\tconst struct commit_list *c;\n+\t\tunsigned long min_date = ULONG_MAX;\n+\t\tfor (c = want; c; c = c->next) {\n+\t\t\tif (parse_commit(c->item) < 0)\n+\t\t\t\tcontinue;\n+\t\t\tif (c->item->date < min_date)\n+\t\t\t\tmin_date = c->item->date;\n+\t\t}\n+\t\tif (min_date > core_clock_skew)\n+\t\t\tcutoff = min_date - core_clock_skew;\n+\t}\n+\n+\treturn contains_recurse(candidate, want, cutoff);\n }\n \n static int show_reference(const char *refname, const unsigned char *sha1,\n@@ -277,6 +299,14 @@ static int git_tag_config(const char *var, const char *value, void *cb)\n \t\treturn 0;\n \t}\n \n+\tif (!strcmp(var, \"core.clockskew\")) {\n+\t\tif (!value || !strcmp(value, \"none\"))\n+\t\t\tcore_clock_skew = -1;\n+\t\telse\n+\t\t\tcore_clock_skew = git_config_int(var, value);\n+\t\treturn 0;\n+\t}\n+\n \treturn git_default_config(var, value, cb);\n }\n \n-- \n1.7.5.3\n"},{"id":"169881","messageId":"1307819051-25748-4-git-send-email-avarab@gmail.com","threadId":"27604","inReplyTo":"1307819051-25748-1-git-send-email-avarab@gmail.com","subject":"[PATCH 3/4] default core.clockskew variable to one day","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2011-06-11T19:04:10Z","receivedAt":"2011-06-11T19:04:10Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"From: Jeff King \n\nThis is the slop value used by name-rev, so presumably is a\nreasonable default.\n\nSigned-off-by: Jeff King \nSigned-off-by: Junio C Hamano \nSigned-off-by: Ævar Arnfjörð Bjarmason \n---\n builtin/tag.c | 2 +-\n 1 files changed, 1 insertions(+), 1 deletions(-)\n\ndiff --git a/builtin/tag.c b/builtin/tag.c\nindex 0f0d784..1468813 100644\n--- a/builtin/tag.c\n+++ b/builtin/tag.c\n@@ -25,7 +25,7 @@ static const char * const git_tag_usage[] = {\n \n static char signingkey[1000];\n \n-static int core_clock_skew = -1;\n+static int core_clock_skew = 86400;\n \n struct tag_filter {\n \tconst char *pattern;\n-- \n1.7.5.3\n"},{"id":"169882","messageId":"1307819051-25748-5-git-send-email-avarab@gmail.com","threadId":"27604","inReplyTo":"1307819051-25748-1-git-send-email-avarab@gmail.com","subject":"[PATCH 4/4] Why is \"git tag --contains\" so slow?","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2011-06-11T19:04:11Z","receivedAt":"2011-06-11T19:04:11Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"From: Jeff King \n\nOn Mon, Jul 05, 2010 at 08:27:23AM -0400, Jeff King wrote:\n\n> As you probably guessed from the specificity of the number, I wrote a\n> short program to actually traverse and find the worst skew. It takes\n> about 5 seconds to run (unsurprisingly, since it is doing the same full\n> traversal that we end up doing in the above numbers). So we could\n> \"autoskew\" by setting up the configuration on clone, and then\n> periodically updating it as part of \"git gc\".\n\nThis patch doesn't implement auto-detection of skew, but is the program\nI used to calculate, and would provide the basis for such\nauto-detection. It would be interesting to see average skew numbers for\npopular repositories. You can run it as \"git skew --all\".\n\nSigned-off-by: Junio C Hamano \nSigned-off-by: Ævar Arnfjörð Bjarmason \n---\n .gitignore | 1 +\n Makefile | 1 +\n builtin.h | 1 +\n builtin/skew.c | 50 ++++++++++++++++++++++++++++++++++++++++++++++++++\n git.c | 1 +\n 5 files changed, 54 insertions(+), 0 deletions(-)\n create mode 100644 builtin/skew.c\n\ndiff --git a/.gitignore b/.gitignore\nindex acffdfa..503ef8b 100644\n--- a/.gitignore\n+++ b/.gitignore\n@@ -137,6 +137,7 @@\n /git-show-branch\n /git-show-index\n /git-show-ref\n+/git-skew\n /git-stage\n /git-stash\n /git-status\ndiff --git a/Makefile b/Makefile\nindex e40ac0c..4ba5542 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -763,6 +763,7 @@ BUILTIN_OBJS += builtin/send-pack.o\n BUILTIN_OBJS += builtin/shortlog.o\n BUILTIN_OBJS += builtin/show-branch.o\n BUILTIN_OBJS += builtin/show-ref.o\n+BUILTIN_OBJS += builtin/skew.o\n BUILTIN_OBJS += builtin/stripspace.o\n BUILTIN_OBJS += builtin/symbolic-ref.o\n BUILTIN_OBJS += builtin/tag.o\ndiff --git a/builtin.h b/builtin.h\nindex 0e9da90..0be47ca 100644\n--- a/builtin.h\n+++ b/builtin.h\n@@ -143,5 +143,6 @@ extern int cmd_verify_pack(int argc, const char **argv, const char *prefix);\n extern int cmd_show_ref(int argc, const char **argv, const char *prefix);\n extern int cmd_pack_refs(int argc, const char **argv, const char *prefix);\n extern int cmd_replace(int argc, const char **argv, const char *prefix);\n+extern int cmd_skew(int argc, const char **argv, const char *prefix);\n \n #endif\ndiff --git a/builtin/skew.c b/builtin/skew.c\nnew file mode 100644\nindex 0000000..1046f5f\n--- /dev/null\n+++ b/builtin/skew.c\n@@ -0,0 +1,50 @@\n+#include \"cache.h\"\n+#include \"commit.h\"\n+#include \"diff.h\"\n+#include \"revision.h\"\n+\n+unsigned long worst_skew = 0;\n+\n+static void check_skew_recurse(struct commit *c, unsigned long when)\n+{\n+\tstruct commit_list *p;\n+\n+\tif (c->object.flags & SEEN)\n+\t\treturn;\n+\tc->object.flags |= SEEN;\n+\n+\tif (parse_commit(c) < 0)\n+\t\treturn;\n+\n+\tif (c->date > when) {\n+\t\tunsigned long skew = c->date - when;\n+\t\tif (skew > worst_skew)\n+\t\t\tworst_skew = skew;\n+\t}\n+\n+\tfor (p = c->parents; p; p = p->next)\n+\t\tcheck_skew_recurse(p->item, c->date < when ? c->date : when);\n+}\n+\n+static void check_skew(struct commit *c)\n+{\n+\tcheck_skew_recurse(c, time(NULL));\n+}\n+\n+int cmd_skew(int argc, const char **argv, const char *prefix) {\n+\tstruct rev_info revs;\n+\tint i;\n+\n+\tgit_config(git_default_config, NULL);\n+\tinit_revisions(&revs, prefix);\n+\targc = setup_revisions(argc, argv, &revs, NULL);\n+\n+\tfor (i = 0; i < revs.pending.nr; i++) {\n+\t\tstruct object *o = revs.pending.objects[i].item;\n+\t\tif (o->type == OBJ_COMMIT)\n+\t\t\tcheck_skew((struct commit *)o);\n+\t}\n+\n+\tprintf(\"%lu\\n\", worst_skew);\n+\treturn 0;\n+}\ndiff --git a/git.c b/git.c\nindex 89721d4..2404bf3 100644\n--- a/git.c\n+++ b/git.c\n@@ -434,6 +434,7 @@ static void handle_internal_command(int argc, const char **argv)\n \t\t{ \"version\", cmd_version },\n \t\t{ \"whatchanged\", cmd_whatchanged, RUN_SETUP },\n \t\t{ \"write-tree\", cmd_write_tree, RUN_SETUP },\n+\t\t{ \"skew\", cmd_skew, RUN_SETUP },\n \t};\n \tint i;\n \tstatic const char ext[] = STRIP_EXTENSION;\n-- \n1.7.5.3\n"},{"id":"170857","messageId":"20110706064012.GA927@sigill.intra.peff.net","threadId":"27604","inReplyTo":"1307819051-25748-1-git-send-email-avarab@gmail.com","subject":"Re: [PATCH 0/4] Speed up git tag --contains","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-06T06:40:12Z","receivedAt":"2011-07-06T06:40:12Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"[+cc people who were interested in earlier iterations of this topic]\n\nOn Sat, Jun 11, 2011 at 07:04:07PM +0000, Ævar Arnfjörð Bjarmason wrote:\n\n> This is a resubmission of Jeff King's patch series to speed up git tag\n> --contains with some changes. It's been cooking for a while as:\n\nThanks for resurrecting this. I've been meaning to look at it again, and\nsomehow an entire year has passed. I've tried to refresh my memory on\nthe issues, so hopefully I can make coherent comments.\n\nThere have been a few responses in the meantime, and one I want to\naddress is Junio's:\n\n http://article.gmane.org/gmane.comp.version-control.git/152765\n\nThe major points in it are (I'm paraphrasing for brevity, but please\ncorrect me if I'm misrepresenting):\n\n 1. A depth-first algorithm has the problem of going down to the roots\n unnecessarily.\n\nYes, and that's why with my initial patch, \"tag --contains\" is on the\nsame order of time as \"git rev-list --tags >/dev/null\" (in the worst\ncase). But with the early return based on commit timestamp, we stop\nlooking down uninteresting paths early. So the downside isn't speed, but\ntrusting commit timestamps.\n\n 2. One solution is to use merge-bases to find earlier cutoff points.\n\nIt's possible. But doesn't the merge bases algorithm, like all of the\ncommit walking, rely somewhat on commit timestamps, too? For example,\nthis thread shows issues with revision limiting:\n\n http://thread.gmane.org/gmane.comp.version-control.git/72274\n\nI'm not sure about the merge bases algorithm, though. In the face of\nskew, I think it can go down a non-optimal path (e.g., going all the way\nto the root because one branch has commits skewed to look much older\nthan they really are, which pushes them to the back of the commit_list\npriority queue). But I think it will still find the correct answer.\n\nTwo problems with doing a merge-base solution are:\n\n a. It can still end up hitting the roots, or close to them. The\n merge-base of something recent and a tag from years ago is going\n to have to go through years of history. So using a timestamp cutoff\n is really nice to know that there's no point in digging (on the\n other hand, searching for something from years ago with respect to\n recent tags will always have to dig through all of that history;\n however, I think this is less common than the other way around).\n\n b. If you are doing the merge-base over many tags at once, it's hard\n to figure out which source tag is actually responsible for hitting\n the merge base.\n\nWhich leads us to Junio's final point:\n\n 3. You can do something like show-branch does, and smudge each commit\n with a bitfield that has one bit per tag (e.g., using the object\n flags).\n\nMy problem with this is that it doesn't scale algorithmically with many\ntags. If we have a constant number of bits, then that reduces the number\nof merge-base traversals we have to do by a constant number. Our\nconstant using the flags field would be 27. And reducing the time by a\nfactor of 27 is nice, but I suspect something like the 10K-tags example\nis still going to be painful, if even one out of the 27 in each\ntraversal has dig far into history.\n\nAnother option is to trade space for time. Do one traversal, but\nactually keep a large enough bitfield. For 10K tags, that's about 1K per\ncommit. So for git.git, that's 30M. For linux-2.6, it's 250M. Which is\ngetting pretty big. But remember that's an insane number of tags, and we\ncan also move the slider between time and space (e.g., 5 traversals of\n50M each).\n\n> I've moved the relevant code from commit.[ch] to builtin/tag.c as\n> Junio's comment suggested. So IMO the \"tag: speed up --contains\n> calculation\" patch is ready to be applied.\n\nThe only downside to that is that the code is harder to reuse in \"branch\n--contains\", which could also benefit. I think the multiple merge-base\ntraversals tend not to be as bad, because branch tips tend to stay\nrecent, and you tend to ask for recent commits. So even though we dig\nthrough the same commits multiple times, it all stays in recent history.\nWhereas tags tend to point to very old things.\n\nStill, that is dependent on your repo setup, including numbers of\nbranches and how stale they tend to be. It would be nice if we could\nalways be fast.\n\n> The next two patches look OK to me, but they need some documentation\n> for the core.clockskew variable, which perhaps should be renamed to\n> tag.clockskew, or was the plan to use it for other things in the\n> future?\n\nIt was intended to be used elsewhere. I have a patch to use it in\nname-rev, which currently just has a hard-coded skew.\n\nThe problem with a skew variable like this is that you really don't want\nto set it higher than a day or so. Because it affects all parts of the\ntraversal, not just the parts near the skewed commits. In linux-2.6, for\nexample, the worst skew is about 100 days. Here are timings for \"git tag\n--contains HEAD~200\" with various core.clockskew values:\n\n - no clock skew tolerated: .035s\n - 1 day: .034s\n - 100 days of clock: .252s\n - infinite: 5.373s\n\nSo we are almost an order of magnitude slower by having set an\nappropriate clockskew value. And that's only for 100 days. Some of the\nprojects have skew on the order of years.\n\nIf we can assume that the skewed commits are relatively rare[1], we\nmight do better to mark individual skewed commits via notes or the\nreplace mechanism. A simple test shows that doing notes lookups is not\ntoo expensive:\n\n # pretend we have some fake timestamps\n for i in 20 40 60; do\n git notes add -m \"fake timestamp\" HEAD~$i\n done\n\n (best of 5)\n $ time git log --pretty=raw --no-notes >/dev/null\n real 0m3.868s\n user 0m3.796s\n sys 0m0.060s\n\n (best of 5)\n $ time git log --pretty=raw --show-notes >/dev/null\n real 0m3.878s\n user 0m3.812s\n sys 0m0.052s\n\nAnd then any code wanting to limit traversal would have to check the\nnotes to see if the timestamp was valid (in fact, we would do even fewer\nlookups, since we only need to check for a bogus timestamp at the edges\nof our traversal).\n\nThe replace mechanism could be used instead; it has the advantage that\nwe wouldn't even need to change the traversal code; it would just see\nthe corrected objects with the right timestamp, and has similar\nperformance characteristics.\n\n[1] The numbers from Jonathan and Clemens show that in most repos, the\nnumbers of skewed commits tend to be small (single-digits usually, or\neven in the dozens; but much fewer than the total number of commits).\n\n> Is the \"Why is \"git tag --contains\" so slow?\" utility something we\n> want?\n\nAs it is now, I don't think so. Tweaking core.clockskew is slow, as\nshown above. And it's not something people should have to do manually. I\nhave a version, which I'll post in a minute, which actually fills in a\nnotes tree with the sha1 of commits with bogus timestamps. And then\nthat tree can be consulted accurately and automatically.\n\nHowever, if we're going to have a look-aside cache of metadata on each\ncommit, maybe it is really time to stop thinking about commit timestamps\nand start thinking about \"generation numbers\". This concept has been\nbrought up before on the list; it's basically:\n\n 1. Root commits have generation = 0.\n\n 2. Other commits have generation = 1 + max(generations of parents).\n\nSo it's a strictly increasing number, and you know that, given X > Y, X\ncannot possibly be an ancestor of Y.\n\nIf this were stored in the commit object, we could use it for all\ntraversals instead of the commit timestamp, and it would presumably be\nmore reliable (you could still have a bogus repo, of course, but it\nwould come from a bug in git, not from importing old history or having\nyour clock set wrong).\n\nThe problem is that existing objects don't have this generation number.\nIt's easy to calculate, though, and we could in theory use a notes-cache\nto store it externally. Obviously the complexity and performance aren't\ngoing to be as good as if it were just in the commit object, but we're\nsadly 6 years too late to make that decision.\n\n-Peff\n"},{"id":"170858","messageId":"20110706065452.GB927@sigill.intra.peff.net","threadId":"27604","inReplyTo":"20110706064012.GA927@sigill.intra.peff.net","subject":"Re: [PATCH 0/4] Speed up git tag --contains","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-06T06:54:52Z","receivedAt":"2011-07-06T06:54:52Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jul 06, 2011 at 02:40:12AM -0400, Jeff King wrote:\n\n> As it is now, I don't think so. Tweaking core.clockskew is slow, as\n> shown above. And it's not something people should have to do manually. I\n> have a version, which I'll post in a minute, which actually fills in a\n> notes tree with the sha1 of commits with bogus timestamps. And then\n> that tree can be consulted accurately and automatically.\n\nHere's that patch. I think I did this after our discussion at\nGitTogether 2010, and haven't looked at it since. So beware.\n\nClemens mentioned elsewhere that my skew-detection programs only find\nskew in one direction. And I think that may be a problem here. We are\nbasically finding commits which have a timestamp in the past from their\nmost recent parent. So that means in a history like this:\n\n A---B---C--D--E--F\n\n timestamp(A) = 1\n timestamp(B) = 2\n timestamp(C) = 1\n timestamp(D) = 4\n timestamp(E) = 5\n\nWe will see that commit C is bogus, since it is in the past from its\nparent. But if a commit skews to the future:\n\n timestamp(A) = 1\n timestamp(B) = 2\n timestamp(C) = 6\n timestamp(D) = 4\n timestamp(E) = 5\n\nthen everything _after_ it will look bogus (D and E, in this case).\n\n>From what we've seen, it seems like skewing into the past is more\ncommon. It seems to come from importing old commits and using their\ntimestamps as the commit timestamps. It would be nice to find a more\naccurate set (I _think_ with future skew like the second example above,\nthe patch below will not give wrong answers; it will just be overly\npessimal and traverse more commits than it needs to).\n\n---\n .gitignore | 1 +\n Makefile | 1 +\n builtin.h | 1 +\n builtin/skew.c | 56 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n commit.c | 20 +++++++++++++++++---\n git.c | 1 +\n 6 files changed, 77 insertions(+), 3 deletions(-)\n create mode 100644 builtin/skew.c\n\ndiff --git a/.gitignore b/.gitignore\nindex acffdfa..503ef8b 100644\n--- a/.gitignore\n+++ b/.gitignore\n@@ -137,6 +137,7 @@\n /git-show-branch\n /git-show-index\n /git-show-ref\n+/git-skew\n /git-stage\n /git-stash\n /git-status\ndiff --git a/Makefile b/Makefile\nindex f8c72e1..f6ecc27 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -765,6 +765,7 @@ BUILTIN_OBJS += builtin/send-pack.o\n BUILTIN_OBJS += builtin/shortlog.o\n BUILTIN_OBJS += builtin/show-branch.o\n BUILTIN_OBJS += builtin/show-ref.o\n+BUILTIN_OBJS += builtin/skew.o\n BUILTIN_OBJS += builtin/stripspace.o\n BUILTIN_OBJS += builtin/symbolic-ref.o\n BUILTIN_OBJS += builtin/tag.o\ndiff --git a/builtin.h b/builtin.h\nindex 0e9da90..0be47ca 100644\n--- a/builtin.h\n+++ b/builtin.h\n@@ -143,5 +143,6 @@ extern int cmd_verify_pack(int argc, const char **argv, const char *prefix);\n extern int cmd_show_ref(int argc, const char **argv, const char *prefix);\n extern int cmd_pack_refs(int argc, const char **argv, const char *prefix);\n extern int cmd_replace(int argc, const char **argv, const char *prefix);\n+extern int cmd_skew(int argc, const char **argv, const char *prefix);\n \n #endif\ndiff --git a/builtin/skew.c b/builtin/skew.c\nnew file mode 100644\nindex 0000000..796b02a\n--- /dev/null\n+++ b/builtin/skew.c\n@@ -0,0 +1,56 @@\n+#include \"cache.h\"\n+#include \"commit.h\"\n+#include \"diff.h\"\n+#include \"revision.h\"\n+#include \"notes-cache.h\"\n+\n+struct notes_cache bogus_timestamps;\n+\n+static unsigned long check_skew(struct commit *c)\n+{\n+\tstruct commit_list *p;\n+\tunsigned long most_recent;\n+\n+\tif (c->util)\n+\t\treturn (unsigned long)c->util;\n+\n+\tif (parse_commit(c) < 0)\n+\t\tdie(\"unable to parse commit: %s\", sha1_to_hex(c->object.sha1));\n+\n+\tmost_recent = 0;\n+\tfor (p = c->parents; p; p = p->next) {\n+\t\tunsigned long timestamp = check_skew(p->item);\n+\t\tif (timestamp > most_recent)\n+\t\t\tmost_recent = timestamp;\n+\t}\n+\n+\tif (c->date + 86400 < most_recent)\n+\t\tnotes_cache_put(&bogus_timestamps, c->object.sha1, \"\", 0);\n+\telse\n+\t\tmost_recent = c->date;\n+\n+\tc->util = (void *)most_recent;\n+\treturn most_recent;\n+}\n+\n+int cmd_skew(int argc, const char **argv, const char *prefix) {\n+\tstruct rev_info revs;\n+\tint i;\n+\n+\tgit_config(git_default_config, NULL);\n+\tinit_revisions(&revs, prefix);\n+\targc = setup_revisions(argc, argv, &revs, NULL);\n+\n+\tnotes_cache_init(&bogus_timestamps, \"traversal-cutoff-ignore\", \"v1\");\n+\n+\tfor (i = 0; i < revs.pending.nr; i++) {\n+\t\tstruct object *o = revs.pending.objects[i].item;\n+\t\tif (o->type == OBJ_COMMIT)\n+\t\t\tcheck_skew((struct commit *)o);\n+\t}\n+\n+\tif (notes_cache_write(&bogus_timestamps) < 0)\n+\t\tdie_errno(\"unable to write notes tree\");\n+\n+\treturn 0;\n+}\ndiff --git a/commit.c b/commit.c\nindex 6647609..1bec48b 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -5,7 +5,7 @@\n #include \"utf8.h\"\n #include \"diff.h\"\n #include \"revision.h\"\n-#include \"notes.h\"\n+#include \"notes-cache.h\"\n \n int core_clock_skew = 86400;\n int save_commit_buffer = 1;\n@@ -888,6 +888,19 @@ static int in_commit_list(const struct commit_list *want, struct commit *c)\n \treturn 0;\n }\n \n+static int has_bogus_timestamp(unsigned char sha1[20])\n+{\n+\tstatic int initialized;\n+\tstatic struct notes_cache bogus;\n+\n+\tif (!initialized) {\n+\t\tnotes_cache_init(&bogus, \"traversal-cutoff-ignore\", \"v1\");\n+\t\tinitialized = 1;\n+\t}\n+\n+\treturn get_note(&bogus.tree, sha1) != NULL;\n+}\n+\n static int contains_recurse(struct commit *candidate,\n \t\t\t const struct commit_list *want,\n \t\t\t unsigned long cutoff)\n@@ -908,8 +921,9 @@ static int contains_recurse(struct commit *candidate,\n \t\treturn 0;\n \n \t/* stop searching if we go too far back in time */\n-\tif (candidate->date < cutoff)\n-\t\treturn 0;\n+\tif (candidate->date < cutoff &&\n+\t !has_bogus_timestamp(candidate->object.sha1))\n+\t\t\treturn 0;\n \n \t/* Otherwise recurse and mark ourselves for future traversals. */\n \tfor (p = candidate->parents; p; p = p->next) {\ndiff --git a/git.c b/git.c\nindex 8828c18..7adeba7 100644\n--- a/git.c\n+++ b/git.c\n@@ -408,6 +408,7 @@ static void handle_internal_command(int argc, const char **argv)\n \t\t{ \"show\", cmd_show, RUN_SETUP },\n \t\t{ \"show-branch\", cmd_show_branch, RUN_SETUP },\n \t\t{ \"show-ref\", cmd_show_ref, RUN_SETUP },\n+\t\t{ \"skew\", cmd_skew, RUN_SETUP },\n \t\t{ \"stage\", cmd_add, RUN_SETUP | NEED_WORK_TREE },\n \t\t{ \"status\", cmd_status, RUN_SETUP | NEED_WORK_TREE },\n \t\t{ \"stripspace\", cmd_stripspace },\n-- \n1.7.6.20.g45f3f.dirty\n"},{"id":"170859","messageId":"20110706065623.GB14164@elie","threadId":"27604","inReplyTo":"20110706064012.GA927@sigill.intra.peff.net","subject":"Re: [PATCH 0/4] Speed up git tag --contains","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2011-07-06T06:56:23Z","receivedAt":"2011-07-06T06:56:23Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Jeff King wrote:\n\n> The problem is that existing objects don't have this generation number.\n> It's easy to calculate, though, and we could in theory use a notes-cache\n> to store it externally. Obviously the complexity and performance aren't\n> going to be as good as if it were just in the commit object, but we're\n> sadly 6 years too late to make that decision.\n\nI am still digesting the rest of what you wrote, but wouldn't this be\neasy to do today? One could just use a notes-cache while prototyping\nand if it seems to work well, introduce new loose and packed object\nformats that include a field for the cached generation number.\n"},{"id":"170860","messageId":"20110706070311.GA3790@sigill.intra.peff.net","threadId":"27604","inReplyTo":"20110706065623.GB14164@elie","subject":"Re: [PATCH 0/4] Speed up git tag --contains","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-06T07:03:11Z","receivedAt":"2011-07-06T07:03:11Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jul 06, 2011 at 01:56:23AM -0500, Jonathan Nieder wrote:\n\n> Jeff King wrote:\n> \n> > The problem is that existing objects don't have this generation number.\n> > It's easy to calculate, though, and we could in theory use a notes-cache\n> > to store it externally. Obviously the complexity and performance aren't\n> > going to be as good as if it were just in the commit object, but we're\n> > sadly 6 years too late to make that decision.\n> \n> I am still digesting the rest of what you wrote, but wouldn't this be\n> easy to do today? One could just use a notes-cache while prototyping\n> and if it seems to work well, introduce new loose and packed object\n> formats that include a field for the cached generation number.\n\nYes, that's exactly how to do it. I'm just not sure \"introduce new loose\nand packed object formats\" is \"easy to do\". Though I'm not sure we need\nnew formats. It is really just a new header in the commit object. And if\nwe write the code carefully, we should be able to transparently use\nnewly-generated objects with the field, and fall back to a notes-cache\n(with autogeneration) when it isn't there.\n\nExisting git will ignore the new generation field. It does mean that old\nand new git will generate different sha1s for the exact same commit. I\ndon't know how big a deal this is in practice. It matters a lot more for\nblobs and trees. But for commits, even if you are replaying a commit,\nyou should be updating the commit timestamp, which is going to give a\nnew sha1.\n\nThe other thing I worry about is performance. You are building a full\nnotes tree and looking up every commit in the traversal. I don't know\nhow bad that will be (though from my other back-of-the-envelope tests,\nit may not actually be that bad; notes were designed to be fast for\nexactly this case).\n\n-Peff\n"},{"id":"170921","messageId":"m3mxgr4has.fsf_-_@localhost.localdomain","threadId":"27604","inReplyTo":"20110706070311.GA3790@sigill.intra.peff.net","subject":"Re: generation numbers (was: [PATCH 0/4] Speed up git tag --contains)","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2011-07-06T14:26:53Z","receivedAt":"2011-07-06T14:26:53Z","isPatch":true,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Jeff King writes:\n> On Wed, Jul 06, 2011 at 01:56:23AM -0500, Jonathan Nieder wrote:\n> > Jeff King wrote:\n> > \n> > > The problem is that existing objects don't have this generation number.\n> > > It's easy to calculate, though, and we could in theory use a notes-cache\n> > > to store it externally. Obviously the complexity and performance aren't\n> > > going to be as good as if it were just in the commit object, but we're\n> > > sadly 6 years too late to make that decision.\n> > \n> > I am still digesting the rest of what you wrote, but wouldn't this be\n> > easy to do today? One could just use a notes-cache while prototyping\n> > and if it seems to work well, introduce new loose and packed object\n> > formats that include a field for the cached generation number.\n> \n> Yes, that's exactly how to do it. I'm just not sure \"introduce new loose\n> and packed object formats\" is \"easy to do\". Though I'm not sure we need\n> new formats. It is really just a new header in the commit object. And if\n> we write the code carefully, we should be able to transparently use\n> newly-generated objects with the field, and fall back to a notes-cache\n> (with autogeneration) when it isn't there.\n\nI understand that you would do autogeneration at least when you create\na commit, and at least one of parents does not have generation number.\n\nYou can also autogenerate notes-cache when following commits, and\nencountering commit object without generation number. \n\nOr make \"git gc\" autogenerate cache-notes for generation number,\nperhaps with an option (i.e. probably not for \"git gc --auto\").\n \n> Existing git will ignore the new generation field. It does mean that old\n> and new git will generate different sha1s for the exact same commit. I\n> don't know how big a deal this is in practice. It matters a lot more for\n> blobs and trees. But for commits, even if you are replaying a commit,\n> you should be updating the commit timestamp, which is going to give a\n> new sha1.\n> \n> The other thing I worry about is performance. You are building a full\n> notes tree and looking up every commit in the traversal. I don't know\n> how bad that will be (though from my other back-of-the-envelope tests,\n> it may not actually be that bad; notes were designed to be fast for\n> exactly this case).\n\nWell, one thing that it would test our notes infrastructure...\n\n-- \nJakub Narebski\nPoland\nShadeHawk on #git\n"},{"id":"170923","messageId":"20110706150103.GA2693@thunk.org","threadId":"27604","inReplyTo":"m3mxgr4has.fsf_-_@localhost.localdomain","subject":"Re: generation numbers (was: [PATCH 0/4] Speed up git tag --contains)","fromName":"Ted Ts'o","fromEmail":"tytso@mit.edu","sentAt":"2011-07-06T15:01:03Z","receivedAt":"2011-07-06T15:01:03Z","isPatch":true,"sender":{"key":"tytso@mit.edu","avatar":"https://avatars.githubusercontent.com/u/51416?v=4"},"body":"Is it worth it to try to replicate this information across repositories?\n\nWhy not just simply have a cache file in the git directory which is\nmanaged somewhat like gitk.cache; call it generation.cache?\n\n\t\t\t\t\t\t- Ted\n"},{"id":"170938","messageId":"20110706181200.GD17978@sigill.intra.peff.net","threadId":"27604","inReplyTo":"20110706150103.GA2693@thunk.org","subject":"Re: generation numbers (was: [PATCH 0/4] Speed up git tag --contains)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-06T18:12:00Z","receivedAt":"2011-07-06T18:12:00Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jul 06, 2011 at 11:01:03AM -0400, Ted Ts'o wrote:\n\n> Is it worth it to try to replicate this information across repositories?\n\nProbably not. I suggested notes-cache just because the amount of code is\nvery trivial.\n\nOne problem with notes storage is that it's not well optimized for tiny\npieces of data like this (e.g., the generation number should fit in a\n32-bit unsigned int, as its max is the size of the longest single path\nin the history graph). But notes are much more general; we will actually\nmap each commit to a blob object containing the generation number, which\nis pretty wasteful.\n\n> Why not just simply have a cache file in the git directory which is\n> managed somewhat like gitk.cache; call it generation.cache?\n\nYeah, that would be fine. With a sorted list of binary sha1s and 32-bit\ngeneration numbers, you're talking about 24 bytes per commit. Or a 6\nmegabyte cache for linux-2.6.\n\nYou'd probably want to be a little clever with updates. If I have\ncalculated the generation number of every commit, and then do \"git\ncommit; git tag --contains HEAD\", you probably don't want to rewrite the\nentire cache. You could probably journal a fixed number of entries in an\nunsorted file (or even in a parallel directory structure to loose\nobjects), and then periodically write out the whole sorted list when the\njournal gets too big. Or choose a more clever data structure that can do\nin-place updates.\n\n-Peff\n"},{"id":"170939","messageId":"201107062046.43820.jnareb@gmail.com","threadId":"27604","inReplyTo":"20110706181200.GD17978@sigill.intra.peff.net","subject":"Re: generation numbers (was: [PATCH 0/4] Speed up git tag --contains)","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2011-07-06T18:46:42Z","receivedAt":"2011-07-06T18:46:42Z","isPatch":true,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"On Wed, 6 Jul 2011, Jeff King wrote:\n> On Wed, Jul 06, 2011 at 11:01:03AM -0400, Ted Ts'o wrote:\n> \n> > Is it worth it to try to replicate this information across repositories?\n> \n> Probably not. I suggested notes-cache just because the amount of code is\n> very trivial.\n\nWell, generation numbers are universal and would help everybody. For\nnew commits with 'generation' header those would be always replicated,\nfor old commits with 'generation' notes / notes-cache the can be\nreplicated.\n \n> One problem with notes storage is that it's not well optimized for tiny\n> pieces of data like this (e.g., the generation number should fit in a\n> 32-bit unsigned int, as its max is the size of the longest single path\n> in the history graph). But notes are much more general; we will actually\n> map each commit to a blob object containing the generation number, which\n> is pretty wasteful.\n\nWasn't textconv-cache using commit-less notes? The same can be done\nfor generation notes-cache. Though it is still wasteful... By the\nway, would we be using text representation (like in 'generation'\ncommit header) or 32-bit integer binary representation in some\nordering, or variable-length integer (I think git uses them somewhere)?\n\nNb. I wonder if 32-bit unsigned int would always be enough, for example\nLinux kernel + history.\n\n> > Why not just simply have a cache file in the git directory which is\n> > managed somewhat like gitk.cache; call it generation.cache?\n> \n> Yeah, that would be fine. With a sorted list of binary sha1s and 32-bit\n> generation numbers, you're talking about 24 bytes per commit. Or a 6\n> megabyte cache for linux-2.6.\n> \n> You'd probably want to be a little clever with updates. If I have\n> calculated the generation number of every commit, and then do \"git\n> commit; git tag --contains HEAD\", you probably don't want to rewrite the\n> entire cache. You could probably journal a fixed number of entries in an\n> unsorted file (or even in a parallel directory structure to loose\n> objects), and then periodically write out the whole sorted list when the\n> journal gets too big. Or choose a more clever data structure that can do\n> in-place updates.\n\nAnd that is the difference between gitk.cache (generated _once_ when starting\ngitk, and regenerated on request), and idea of generation.cache\n\nI think it would be simpler to use generation header + generation notes.\nOr start with generation notes only.\n\n-- \nJakub Narebski\nPoland\n"},{"id":"170943","messageId":"20110706190621.GA3937@toss","threadId":"27604","inReplyTo":"20110706065452.GB927@sigill.intra.peff.net","subject":"Re: [PATCH 0/4] Speed up git tag --contains","fromName":"Clemens Buchacher","fromEmail":"drizzd@aon.at","sentAt":"2011-07-06T19:06:21Z","receivedAt":"2011-07-06T19:06:21Z","isPatch":true,"sender":{"key":"drizzd@gmx.net","avatar":"https://avatars.githubusercontent.com/u/59082?v=4"},"body":"On Wed, Jul 06, 2011 at 02:54:52AM -0400, Jeff King wrote:\n>\n> From what we've seen, it seems like skewing into the past is more\n> common. It seems to come from importing old commits and using their\n> timestamps as the commit timestamps. It would be nice to find a more\n> accurate set (I _think_ with future skew like the second example above,\n> the patch below will not give wrong answers; it will just be overly\n> pessimal and traverse more commits than it needs to).\n\nYes, and that was indeed my only concern. Since we cannot tell with\ncertainty if we have skew into the past or into the future, it's\nnot wrong to always assume skew into the past. It just does not\nalways produce the shortest run of skewed commits, as you said. And\nif skews into the future are rare, then that should not be an\nissue.\n\nBut considering the complexity behind the timestamp based approach,\nwhich you have demonstrated in your analysis, the generation number\nconcept looks very attractive to me.\n\nIt even has potential for the push/pull transport protocol.\n(Unreliable) commit timestamps are currently used while searching\nfor common commits. And there is still the problem of searching\ndown the wrong branch, which can be especially bad for repos with\nmultiple disjoint histories. For example, we shouldn't send any\nHAVEs for commits with generation numbers greater than the\ngeneration number of the wanted ref. Or smaller than half that (in\nwhich case downloading the complete pack would probably be faster).\n\nThomas, IIRC you were working on this. Do you think this could\nhelp?\n\nClemens\n"},{"id":"170951","messageId":"7viprfhu4w.fsf@alter.siamese.dyndns.org","threadId":"27604","inReplyTo":"20110706181200.GD17978@sigill.intra.peff.net","subject":"Re: generation numbers","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-07-06T23:22:23Z","receivedAt":"2011-07-06T23:22:23Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> Yeah, that would be fine. With a sorted list of binary sha1s and 32-bit\n> generation numbers, you're talking about 24 bytes per commit. Or a 6\n> megabyte cache for linux-2.6.\n>\n> You'd probably want to be a little clever with updates. If I have\n> calculated the generation number of every commit, and then do \"git\n> commit; git tag --contains HEAD\", you probably don't want to rewrite the\n> entire cache. You could probably journal a fixed number of entries in an\n> unsorted file (or even in a parallel directory structure to loose\n> objects), and then periodically write out the whole sorted list when the\n> journal gets too big. Or choose a more clever data structure that can do\n> in-place updates.\n\nAs to the low level implementation detail I agree everything you said, but\nI have been wondering how the generation number should intereact with\ngrafts and replaces. It certainly would be safest whenever you change\ngrafts (which should be a rare event anyway).\n"},{"id":"170985","messageId":"20110707185908.GB12044@sigill.intra.peff.net","threadId":"27604","inReplyTo":"201107062046.43820.jnareb@gmail.com","subject":"Re: generation numbers (was: [PATCH 0/4] Speed up git tag --contains)","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-07T18:59:08Z","receivedAt":"2011-07-07T18:59:08Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jul 06, 2011 at 08:46:42PM +0200, Jakub Narebski wrote:\n\n> > > Is it worth it to try to replicate this information across repositories?\n> > \n> > Probably not. I suggested notes-cache just because the amount of code is\n> > very trivial.\n> \n> Well, generation numbers are universal and would help everybody. For\n> new commits with 'generation' header those would be always replicated,\n> for old commits with 'generation' notes / notes-cache the can be\n> replicated.\n\nSure. But it's not worth trying to transfer them between repositories,\nwhen it only takes a few seconds to generate them locally (approximately\nthe same amount of time that \"git rev-list --all >/dev/null\" takes).\n\n> > One problem with notes storage is that it's not well optimized for tiny\n> > pieces of data like this (e.g., the generation number should fit in a\n> > 32-bit unsigned int, as its max is the size of the longest single path\n> > in the history graph). But notes are much more general; we will actually\n> > map each commit to a blob object containing the generation number, which\n> > is pretty wasteful.\n> \n> Wasn't textconv-cache using commit-less notes? The same can be done\n> for generation notes-cache.\n\nNo, textconv actually uses parentless commits. But the issue I'm talking\nabout is not the history storage. It's the value storage. Instead of\npointing to a 32-bit int, we point to a 160-bit sha1 that references an\nobject containing the value (and the object header is going to be as big\nas the value itself). So it's wasteful in storage, and it's wasteful in\nthe amount of work to do a lookup.\n\nYou could \"cheat\" and instead of storing the sha1 of a blob object in\nthe notes tree, use the lower 32 bits to store an actual value. I don't\nthink that currently breaks any assumptions in the notes code, but it\ndefinitely is against the intent of it.\n\nI wrote a patch to calculate and cache commit generation numbers on the\nfly, and output them via the \"%G\" format placeholder. So we can get some\ntimings (these are from git.git):\n\n # baseline to compare against; print the commiter timestamp of every\n # commit, which is about how expensive it would be to parse and print\n # an embedded generation number\n $ time git log --format=%ct >/dev/null\n real 0m0.388s\n user 0m0.380s\n sys 0m0.004s\n\n # and the baseline amount of storage used (fully packed)\n $ du -s .git/objects\n 47072 .git/objects\n\n # now the cost to generate the whole cache; slower, obviously, but it\n # only needs to happen once\n $ time git log --format=%G >/dev/null\n real 0m2.180s\n user 0m1.204s\n sys 0m0.960s\n\n # at which point everything is loose, and we are wasting tons of space\n $ du -s .git/objects\n 171692 .git/objects\n\n # and traversing with generation lookup is still a bit slower than\n # without it\n $ time git log --format=%G >/dev/null\n real 0m0.822s\n user 0m0.544s\n sys 0m0.272s\n\n # but repacking helps with the space; now we're using only ~3M\n $ git gc\n $ du -s .git/objects\n 50236 .git/objects\n\n # and traversal is faster, but still about 33% slower than our\n # baseline\n real 0m0.490s\n user 0m0.468s\n sys 0m0.020s\n\nSo I suspect we could do better with a data structure optimized for this\ntype of storage.\n\n> Though it is still wasteful... By the way, would we be using text\n> representation (like in 'generation' commit header) or 32-bit integer\n> binary representation in some ordering, or variable-length integer (I\n> think git uses them somewhere)?\n\nFor a local lookup cache, I would use a fixed-size binary integer just\nto keep the lookup data structure simple (then you know the width of\neach record ahead of time). For a generation commit header, obviously we\nwould go with the ascii representation as we do for other headers.\n\n> Nb. I wonder if 32-bit unsigned int would always be enough, for example\n> Linux kernel + history.\n\nYeah, it should be plenty. There are only 250K commits in linux-2.6, and\nthe absolute worst case generation number is 250K (if they are all\nlinear). But the history is an n-ary tree, and the highest generation is\nactually the height of the tree. So the more branchy the history, the\nsmaller the height.\n\nThe generation of v3.0-rc6, representing 6 years of history, is 79044.\nAt that rate, the linux-2.6 repository will overflow in a mere 320,000\nyears.\n\n> I think it would be simpler to use generation header + generation notes.\n> Or start with generation notes only.\n\nThe patch implementing generation notes is below. The implementation is\nquite simple, but it would be nice if it were faster.\n\n---\n commit.c | 81 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n commit.h | 2 +\n pretty.c | 3 ++\n 3 files changed, 86 insertions(+), 0 deletions(-)\n\ndiff --git a/commit.c b/commit.c\nindex ac337c7..493517c 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -6,6 +6,7 @@\n #include \"diff.h\"\n #include \"revision.h\"\n #include \"notes.h\"\n+#include \"notes-cache.h\"\n \n int save_commit_buffer = 1;\n \n@@ -878,3 +879,83 @@ int commit_tree(const char *msg, unsigned char *tree,\n \tstrbuf_release(&buffer);\n \treturn result;\n }\n+\n+static struct notes_cache generations;\n+\n+static int generation_from_cache(struct commit *c, unsigned long *g)\n+{\n+\tchar *buf, *end;\n+\tsize_t len;\n+\n+\tbuf = notes_cache_get(&generations, c->object.sha1, &len);\n+\tif (!buf)\n+\t\treturn -1;\n+\n+\terrno = 0;\n+\t*g = strtoul(buf, &end, 10);\n+\tif (errno == ERANGE || *end != '\\0') {\n+\t\tfree(buf);\n+\t\treturn -1;\n+\t}\n+\n+\tfree(buf);\n+\treturn 0;\n+}\n+\n+static void generation_to_cache(struct commit *c, unsigned long g)\n+{\n+\tchar buf[64];\n+\tint len;\n+\n+\tlen = snprintf(buf, sizeof(buf), \"%lu\", g);\n+\tnotes_cache_put(&generations, c->object.sha1, buf, len);\n+}\n+\n+static unsigned long commit_generation_recurse(struct commit *c)\n+{\n+\tstruct commit_list *p;\n+\tunsigned long r;\n+\n+\tif (!generation_from_cache(c, &r))\n+\t\treturn r;\n+\n+\tif (parse_commit(c) < 0)\n+\t\tdie(\"unable to parse commit: %s\", sha1_to_hex(c->object.sha1));\n+\n+\tif (!c->parents)\n+\t\treturn 0;\n+\n+\tr = 0;\n+\tfor (p = c->parents; p; p = p->next) {\n+\t\tunsigned long pgen = commit_generation_recurse(p->item);\n+\t\tif (pgen > r)\n+\t\t\tr = pgen;\n+\t}\n+\tr++;\n+\n+\tgeneration_to_cache(c, r);\n+\treturn r;\n+}\n+\n+int installed_generation_writer;\n+static void write_generation_cache(void)\n+{\n+\tnotes_cache_write(&generations);\n+}\n+\n+unsigned long commit_generation(const struct commit *commit)\n+{\n+\tunsigned long r;\n+\n+\tif (!generations.tree.initialized)\n+\t\tnotes_cache_init(&generations, \"generations\", \"v1\");\n+\n+\tr = commit_generation_recurse((struct commit *)commit);\n+\n+\tif (!installed_generation_writer) {\n+\t\tatexit(write_generation_cache);\n+\t\tinstalled_generation_writer = 1;\n+\t}\n+\n+\treturn r;\n+}\ndiff --git a/commit.h b/commit.h\nindex a2d571b..bff6b36 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -176,4 +176,6 @@ extern int commit_tree(const char *msg, unsigned char *tree,\n \t\tstruct commit_list *parents, unsigned char *ret,\n \t\tconst char *author);\n \n+unsigned long commit_generation(const struct commit *commit);\n+\n #endif /* COMMIT_H */\ndiff --git a/pretty.c b/pretty.c\nindex f45eb54..8f1b321 100644\n--- a/pretty.c\n+++ b/pretty.c\n@@ -965,6 +965,9 @@ static size_t format_commit_one(struct strbuf *sb, const char *placeholder,\n \t\t\treturn 2;\n \t\t}\n \t\treturn 0;\t/* unknown %g placeholder */\n+\tcase 'G':\n+\t\tstrbuf_addf(sb, \"%lu\", commit_generation(commit));\n+\t\treturn 1;\n \tcase 'N':\n \t\tif (c->pretty_ctx->show_notes) {\n \t\t\tformat_display_notes(commit->object.sha1, sb,\n-- \n1.7.6.7.ge7132.dirty\n"},{"id":"170986","messageId":"20110707190828.GC12044@sigill.intra.peff.net","threadId":"27604","inReplyTo":"7viprfhu4w.fsf@alter.siamese.dyndns.org","subject":"Re: generation numbers","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-07T19:08:28Z","receivedAt":"2011-07-07T19:08:28Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jul 06, 2011 at 04:22:23PM -0700, Junio C Hamano wrote:\n\n> As to the low level implementation detail I agree everything you said, but\n> I have been wondering how the generation number should intereact with\n> grafts and replaces. It certainly would be safest whenever you change\n> grafts (which should be a rare event anyway).\n\nUgh. I hadn't even considered grafting. Yeah, grafting or replacing\ncould make the generation numbers totally wrong. And not just for the\nreplaced commit, but for everything that builds on top. That's perhaps\nan argument against putting them into the commit header at all; once you\ngraft, everything after will have bogus generation numbers.\n\nSo yeah, you would want to clear the cache any time you tweak\nreplacements or grafts (which I think is what you were saying in your\nfinal sentence).\n\nYou could do a hybrid solution, in which you have generation numbers in\nthe commit header, and an external cache. You need the cache anyway to\nsupport older commits without the header. And then you could use the\nbuilt-in generation numbers when there's no grafting or replacing going\non, and the cache otherwise. That keeps the common case (no grafts)\nfaster.\n\nStill, if we can get the external lookup to be faster than my initial\nnotes attempt (which really should not be that hard), the performance\ndifference may not end up that big, and it won't even be worth putting\nthem into the header at all.\n\n-Peff\n"},{"id":"170990","messageId":"7vliw9hoky.fsf@alter.siamese.dyndns.org","threadId":"27604","inReplyTo":"20110707185908.GB12044@sigill.intra.peff.net","subject":"Re: generation numbers","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-07-07T19:34:37Z","receivedAt":"2011-07-07T19:34:37Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> You could \"cheat\" and instead of storing the sha1 of a blob object in\n> the notes tree, use the lower 32 bits to store an actual value. I don't\n> think that currently breaks any assumptions in the notes code, but it\n> definitely is against the intent of it.\n\nI highly suspect that it would break fsck rather badly. You may not even\nbe able to repack a repository with such a notes tree.\n\n> For a local lookup cache, I would use a fixed-size binary integer just\n> to keep the lookup data structure simple (then you know the width of\n> each record ahead of time). For a generation commit header, obviously we\n> would go with the ascii representation as we do for other headers.\n\nYes.\n"},{"id":"170991","messageId":"201107072210.13254.jnareb@gmail.com","threadId":"27604","inReplyTo":"20110707190828.GC12044@sigill.intra.peff.net","subject":"Re: generation numbers","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2011-07-07T20:10:12Z","receivedAt":"2011-07-07T20:10:12Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"On Thu, 7 Jul 2011, Jeff King wrote:\n> On Wed, Jul 06, 2011 at 04:22:23PM -0700, Junio C Hamano wrote:\n> \n> > As to the low level implementation detail I agree everything you said, but\n> > I have been wondering how the generation number should intereact with\n> > grafts and replaces. It certainly would be safest whenever you change\n> > grafts (which should be a rare event anyway).\n> \n> Ugh. I hadn't even considered grafting. Yeah, grafting or replacing\n> could make the generation numbers totally wrong. And not just for the\n> replaced commit, but for everything that builds on top. That's perhaps\n> an argument against putting them into the commit header at all; once you\n> graft, everything after will have bogus generation numbers.\n> \n> So yeah, you would want to clear the cache any time you tweak\n> replacements or grafts (which I think is what you were saying in your\n> final sentence).\n> \n> You could do a hybrid solution, in which you have generation numbers in\n> the commit header, and an external cache. You need the cache anyway to\n> support older commits without the header. And then you could use the\n> built-in generation numbers when there's no grafting or replacing going\n> on, and the cache otherwise. That keeps the common case (no grafts)\n> faster.\n\nOr we could enhance pack protocol (new capability) to send generation\nnotes cache as a separate stream perhaps.\n\nOr make generation notes cache part of post-downloading work, after\n(or while) generating pack index.\n\n> Still, if we can get the external lookup to be faster than my initial\n> notes attempt (which really should not be that hard), the performance\n> difference may not end up that big, and it won't even be worth putting\n> them into the header at all.\n\nI wonder if we can reuse pack index code / format somewhat.\n\nOr perhaps some kind of on-disk hash table; we need O(1) fast lookup,\nand ability to update structure 'in place'.\n\n-- \nJakub Narebski\nPoland\n"},{"id":"170993","messageId":"201107072231.13181.jnareb@gmail.com","threadId":"27604","inReplyTo":"7vliw9hoky.fsf@alter.siamese.dyndns.org","subject":"Re: generation numbers","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2011-07-07T20:31:12Z","receivedAt":"2011-07-07T20:31:12Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"On Thu, 7 Jul 2011, Junio C Hamano wrote:\n> Jeff King writes:\n> \n> > You could \"cheat\" and instead of storing the sha1 of a blob object in\n> > the notes tree, use the lower 32 bits to store an actual value. I don't\n> > think that currently breaks any assumptions in the notes code, but it\n> > definitely is against the intent of it.\n> \n> I highly suspect that it would break fsck rather badly. You may not even\n> be able to repack a repository with such a notes tree.\n\nWell, we could (ab)use file mode to mark that what would be sha1 actually\nstores fixed-width content of a file, like we do with submodules.\n\nThis technique is I think quite similar in idea to filesystems storing\ncontents of small files in file inode, isn't it?\n\n-- \nJakub Narebski\nPoland\n"},{"id":"170996","messageId":"4E161CA3.2050001@gmail.com","threadId":"27604","inReplyTo":"201107072231.13181.jnareb@gmail.com","subject":"Re: generation numbers","fromName":"A Large Angry SCM","fromEmail":"gitzilla@gmail.com","sentAt":"2011-07-07T20:52:51Z","receivedAt":"2011-07-07T20:52:51Z","isPatch":false,"sender":{"key":"gitzilla@gmail.com","avatar":"https://gravatar.com/avatar/354625c442439908ff3dd99757dee330e29e9df7847472384faf7a00add247fb?d=mp&s=160"},"body":"On 07/07/2011 04:31 PM, Jakub Narebski wrote:\n> On Thu, 7 Jul 2011, Junio C Hamano wrote:\n>> Jeff King writes:\n>>\n>>> You could \"cheat\" and instead of storing the sha1 of a blob object in\n>>> the notes tree, use the lower 32 bits to store an actual value. I don't\n>>> think that currently breaks any assumptions in the notes code, but it\n>>> definitely is against the intent of it.\n>>\n>> I highly suspect that it would break fsck rather badly. You may not even\n>> be able to repack a repository with such a notes tree.\n>\n> Well, we could (ab)use file mode to mark that what would be sha1 actually\n> stores fixed-width content of a file, like we do with submodules.\n>\n> This technique is I think quite similar in idea to filesystems storing\n> contents of small files in file inode, isn't it?\n>\n\nAre the benefits really worth all these hacks?\n"},{"id":"171007","messageId":"7vei21haxv.fsf@alter.siamese.dyndns.org","threadId":"27604","inReplyTo":"4E161CA3.2050001@gmail.com","subject":"Re: generation numbers","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2011-07-08T00:29:16Z","receivedAt":"2011-07-08T00:29:16Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"A Large Angry SCM writes:\n\n> On 07/07/2011 04:31 PM, Jakub Narebski wrote:\n>> On Thu, 7 Jul 2011, Junio C Hamano wrote:\n>>> Jeff King writes:\n>>>\n>>>> You could \"cheat\" and instead of storing the sha1 of a blob object in\n>>>> the notes tree, use the lower 32 bits to store an actual value. I don't\n>>>> think that currently breaks any assumptions in the notes code, but it\n>>>> definitely is against the intent of it.\n>>>\n>>> I highly suspect that it would break fsck rather badly. You may not even\n>>> be able to repack a repository with such a notes tree.\n>>\n>> Well, we could (ab)use file mode to mark that what would be sha1 actually\n>> stores fixed-width content of a file, like we do with submodules.\n>>\n>> This technique is I think quite similar in idea to filesystems storing\n>> contents of small files in file inode, isn't it?\n>\n> Are the benefits really worth all these hacks?\n\nNot at all. Don't take everything everybody says about low level\nimplementation too seriously. Most people do not know what they are\ntalking about ;-).\n"},{"id":"171021","messageId":"20110708225725.GA16047@sigill.intra.peff.net","threadId":"27604","inReplyTo":"7vliw9hoky.fsf@alter.siamese.dyndns.org","subject":"Re: generation numbers","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-07-08T22:57:25Z","receivedAt":"2011-07-08T22:57:25Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jul 07, 2011 at 12:34:37PM -0700, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > You could \"cheat\" and instead of storing the sha1 of a blob object in\n> > the notes tree, use the lower 32 bits to store an actual value. I don't\n> > think that currently breaks any assumptions in the notes code, but it\n> > definitely is against the intent of it.\n> \n> I highly suspect that it would break fsck rather badly. You may not even\n> be able to repack a repository with such a notes tree.\n\nTrue. I think you would have to do the file-mode hack that Jakub\nsuggested. But that's getting pretty gross. If something isn't big\nenough to be in a blob, and especially if we are just caching, it would\nbe nice to have some lighter-weight caching mechanism.\n\n> > For a local lookup cache, I would use a fixed-size binary integer just\n> > to keep the lookup data structure simple (then you know the width of\n> > each record ahead of time). For a generation commit header, obviously we\n> > would go with the ascii representation as we do for other headers.\n\nSo I implemented something like this today. In fact, it's a generic[1]\nfast persistent object-data mapping for data of a fixed size. The\non-disk representation is a stream of pairs: binary sha1s followed by\ntheir fixed-size data. Lookup is by binary search (using sha1_entry_pos,\nwhich makes this more or less the same as pack-index lookups).\n\nThere's a separate in-memory lookaside table that receives updates.\nThese are stored as a hash[2] because except for the first run, this\nwill typically be much smaller than the disk version, and we care more\nabout insertion speed here. When git exits, the memory and disk versions\nare merged into a new cache which atomically replaces the old version\nvia rename().\n\nHere are the timings I came up with using it on top of my depth-first\ncontains algorithm. All runs are for \"git tag --contains HEAD~1000\" in\nthe linux-2.6 repo. All times are best-of-five unless otherwise noted.\n\nTo get a baseline, I measured the algorithm with no cutoff at all (i.e.,\nffc4b80 in pu), and then with a cutoff based on timestamp with one day\nof slop (i.e., de9f14e in pu):\n\n none:\n real 0m3.139s\n user 0m3.044s\n sys 0m0.092s\n\n timestamp:\n real 0m0.027s\n user 0m0.024s\n sys 0m0.000s\n\nWe can use the \"timestamp\" value as our goal; it's fast, but not\nnecessarily correct in the face of skew (and it's about as fast as we\nwould expect a generation header inside the commit to perform). We can\nuse \"none\" as a lower goalpost. It's correct, but slow. If we're slower\nthan it, then we have totally failed.\n\nThen I tried doing a generation-based cutoff, caching the generations\nvia notes-cache. Here are those timings:\n\n notes (1st run):\n real 0m14.153s\n user 0m7.868s\n sys 0m5.392s\n\n notes (before repack):\n real 0m0.102s\n user 0m0.076s\n sys 0m0.024s\n\n notes (after repack):\n real 0m0.090s\n user 0m0.072s\n sys 0m0.016s\n\nIt's pretty painful to actually generate the cache, mostly because we\nend up writing a ton of tree and blob objects. The objects directory\nballoons from 503M to 1.1G after that run. Repacking brings that down to\na mere 524M, or 21M spent on the cache. Not shown in these timings is\nthe painfully slow \"git gc\" it took to get there.\n\nSo there's a nice speedup over the no-cutoff case, but we're still 3\ntimes as slow as the timestamp case. And the sheer amount of object\ncruft (both in terms of wasted space, and wasted time writing and\nrepacking) is ugly.\n\nNext up is the custom object-cache code:\n\n custom (1st run):\n real 0m3.769s\n user 0m3.404s\n sys 0m0.360s\n\n custom:\n real 0m0.035s\n user 0m0.028s\n sys 0m0.004s\n\nYou can see that the first run is a bit slower, as we have to touch\nevery commit to figure out the generations. But it also highlights how\nmuch of the notes-cache version is spent not actually figuring out the\ngenerations, but rather just writing the notes tree.\n\nSubsequent runs are pretty darn fast. It's a tiny bit slower than using\nthe timestamps, but it's within the noise. The resulting cache file is\n5.9M.\n\nSo it seems like a good direction to pursue. The only downside I see is\nthat we may be slower operating in a read-only repository in which\nnobody has generated any cache yet. But that seems like a bit of a crazy\ncase, and even then, it's on par with the no-cutoff-at-all case, so it's\nreally not that bad. And it's guaranteed to be correct in the face of\nskew, as opposed to the fast timestamp case.\n\n-Peff\n\n[1] I intentionally wrote the object caching code in a very generic,\n data-agnostic way. I have a patch series to speed up git-cherry by\n caching patch-ids of commits against their parents. It uses\n notes-cache and already provides some speedup, but I'd like to see\n if I can make it faster with the new code.\n\n[2] Instead of writing my own hash, I hacked decorate.[ch] to have\n \"value\" semantics. I.e., you can now store values of arbitrary size.\n The existing semantics of storing a \"void *\" are easy to do on top\n of that. I noticed that fast-export is already encoding uint32_t's\n inside the pointers. This makes that a little more supported, and\n also means that the same hack will work for data larger than a void\n pointer (e.g., patch-id caching will need 20 bytes).\n"},{"id":"336526","messageId":"E1ea4Ui-0005qJ-3s@theory.stanford.edu","threadId":"27604","inReplyTo":"20110706064012.GA927@sigill.intra.peff.net","subject":"Re: [PATCH 0/4] Speed up git tag --contains","fromName":"csilvers","fromEmail":"csilvers@cs.stanford.edu","sentAt":"2018-01-12T18:56:00Z","receivedAt":"2018-01-12T19:27:44Z","isPatch":true,"sender":{"key":"csilvers@cs.stanford.edu","avatar":null},"body":"> This is a resubmission of Jeff King's patch series to speed up git tag\n> --contains with some changes. It's been cooking for a while as:\n\nReplying to this 6-year-old thread:\n\nIs there any chance this could be resurrected? We are using\nphabricator, which uses `git branch --contains` as part of its\nworkflow. Our repo has ~1000 branches on it, and the contains\noperation is eating up all our CPU (and time). It would be very\nhelpful to us to make this faster!\n\n(The original thread is at\nhttps://public-inbox.org/git/E1OU82h-0001xY-3b@closure.thunk.org/\n)\n\ncraig\n"},{"id":"340869","messageId":"20180303051516.GE27689@sigill.intra.peff.net","threadId":"27604","inReplyTo":"E1ea4Ui-0005qJ-3s@theory.stanford.edu","subject":"Re: [PATCH 0/4] Speed up git tag --contains","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-03-03T05:15:16Z","receivedAt":"2018-03-03T05:15:23Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jan 12, 2018 at 10:56:00AM -0800, csilvers wrote:\n\n> > This is a resubmission of Jeff King's patch series to speed up git tag\n> > --contains with some changes. It's been cooking for a while as:\n> \n> Replying to this 6-year-old thread:\n> \n> Is there any chance this could be resurrected? We are using\n> phabricator, which uses `git branch --contains` as part of its\n> workflow. Our repo has ~1000 branches on it, and the contains\n> operation is eating up all our CPU (and time). It would be very\n> helpful to us to make this faster!\n> \n> (The original thread is at\n> https://public-inbox.org/git/E1OU82h-0001xY-3b@closure.thunk.org/\n\nSorry, this got thrown on my \"to respond\" pile and languished.\n\nThere are actually three things that make \"git branch --contains\" slow.\n\nFirst, if you're filtering 1000 branches, we'll run 1000 merge-base\ntraversals, which may walk over the same commits multiple times.\n\nThese days \"tag --contains\" uses a different algorithm that can look at\nall heads in a single traversal. But the downside is that it's\ndepth-first, so it tends to walk down to the roots. That's generally OK\nfor tags, since you often have ancient tags that mean getting close to\nthe roots anyway.\n\nBut for branches, they're more likely to be recent, and you can get away\nwithout going very deep into the history.\n\nSo it's a tradeoff. There's no run-time switch to flip between them, but\na patch like this:\n\ndiff --git a/builtin/branch.c b/builtin/branch.c\nindex 8dcc2ed058..4d674e86d5 100644\n--- a/builtin/branch.c\n+++ b/builtin/branch.c\n@@ -404,6 +404,7 @@ static void print_ref_list(struct ref_filter *filter, struct ref_sorting *sortin\n \n \tmemset(&array, 0, sizeof(array));\n \n+\tfilter->with_commit_tag_algo = 1;\n \tfilter_refs(&array, filter, filter->kind | FILTER_REFS_INCLUDE_BROKEN);\n \n \tif (filter->verbose)\n\ndrops my run of \"git branch -a --contains HEAD~100\" from 8.6s to\n0.4s on a repo with ~1800 branches. That sounds good, but on a repo with\na smaller number of branches, we may actually end up slower (because we\ndig further down in history, and don't benefit from the multiple-branch\nspeedup).\n\nI tried to do a \"best of both\" algorithm in:\n\n https://public-inbox.org/git/20140625233429.GA20457@sigill.intra.peff.net/\n\nwhich finds arbitrary numbers of merge bases in a single traversal. It\ndid seem to work, but I felt uneasy about some of the corner cases.\nI've been meaning to revisit it, but obviously have never gotten around\nto it.\n\nThe second slow thing is that during the traversal we load each commit\nobject from disk. The solution there is to keep the parent information\nin a faster cache. I had a few proposals over the years, but I won't\neven bother to dig them up, because there's quite recent and promising\nwork in this area from Derrick Stolee:\n\n https://public-inbox.org/git/1519698787-190494-1-git-send-email-dstolee@microsoft.com/\n\nAnd finally, the thing that the patches you linked are referencing is\nabout using commit timestamps as a proxy for generation numbers. And\nStolee's patches actually leave room for real, trustable generation\nnumbers.\n\nOnce we have the serialized commit graph and generation numbers, think\nthe final step would just be to teach the \"tag --contains\" algorithm to\nstop walking down unproductive lines of history. And in fact, I think we\ncan forget about the best-of-both multi-tip merge-base idea entirely.\nBecause if you can use the generation numbers to avoid going too deep,\nthen a depth-first approach is fine. And we'd just want to flip\ngit-branch over to using that algorithm by default.\n\n-Peff\n"},{"id":"341325","messageId":"E1eu4bJ-0007k0-71@theory.stanford.edu","threadId":"27604","inReplyTo":"20180303051516.GE27689@sigill.intra.peff.net","subject":"Re: [PATCH 0/4] Speed up git tag --contains","fromName":"csilvers","fromEmail":"csilvers@cs.stanford.edu","sentAt":"2018-03-08T23:05:29Z","receivedAt":"2018-03-08T23:33:13Z","isPatch":true,"sender":{"key":"csilvers@cs.stanford.edu","avatar":null},"body":"} I had a few proposals over the years, but I won't even bother to dig\n} them up, because there's quite recent and promising work in this\n} area from Derrick Stolee:\n\nIt sounds like the best thing to do is to wait for this, then.\n\nWe managed to convert a bunch of our branches to tags, so our\nimmediate problem has been resolved. But I'm sure it will come up\nagain as more branches are created...\n\ncarig\n"},{"id":"341480","messageId":"63e9c6a8-4efc-6f86-f355-1ec40dd674e4@gmail.com","threadId":"27604","inReplyTo":"20180303051516.GE27689@sigill.intra.peff.net","subject":"Re: [PATCH 0/4] Speed up git tag --contains","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-03-12T13:45:27Z","receivedAt":"2018-03-12T13:45:36Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 3/3/2018 12:15 AM, Jeff King wrote:\n> On Fri, Jan 12, 2018 at 10:56:00AM -0800, csilvers wrote:\n>\n>>> This is a resubmission of Jeff King's patch series to speed up git tag\n>>> --contains with some changes. It's been cooking for a while as:\n>> Replying to this 6-year-old thread:\n>>\n>> Is there any chance this could be resurrected? We are using\n>> phabricator, which uses `git branch --contains` as part of its\n>> workflow. Our repo has ~1000 branches on it, and the contains\n>> operation is eating up all our CPU (and time). It would be very\n>> helpful to us to make this faster!\n>>\n>> (The original thread is at\n>> https://public-inbox.org/git/E1OU82h-0001xY-3b@closure.thunk.org/\n> Sorry, this got thrown on my \"to respond\" pile and languished.\n\nThanks for adding me to the thread. It's good to know the pain point \npeople are having around commit graph walks.\n\n> There are actually three things that make \"git branch --contains\" slow.\n>\n> First, if you're filtering 1000 branches, we'll run 1000 merge-base\n> traversals, which may walk over the same commits multiple times.\n>\n> These days \"tag --contains\" uses a different algorithm that can look at\n> all heads in a single traversal. But the downside is that it's\n> depth-first, so it tends to walk down to the roots. That's generally OK\n> for tags, since you often have ancient tags that mean getting close to\n> the roots anyway.\n>\n> But for branches, they're more likely to be recent, and you can get away\n> without going very deep into the history.\n>\n> So it's a tradeoff. There's no run-time switch to flip between them, but\n> a patch like this:\n>\n> diff --git a/builtin/branch.c b/builtin/branch.c\n> index 8dcc2ed058..4d674e86d5 100644\n> --- a/builtin/branch.c\n> +++ b/builtin/branch.c\n> @@ -404,6 +404,7 @@ static void print_ref_list(struct ref_filter *filter, struct ref_sorting *sortin\n> \n> \tmemset(&array, 0, sizeof(array));\n> \n> +\tfilter->with_commit_tag_algo = 1;\n> \tfilter_refs(&array, filter, filter->kind | FILTER_REFS_INCLUDE_BROKEN);\n> \n> \tif (filter->verbose)\n>\n> drops my run of \"git branch -a --contains HEAD~100\" from 8.6s to\n> 0.4s on a repo with ~1800 branches. That sounds good, but on a repo with\n> a smaller number of branches, we may actually end up slower (because we\n> dig further down in history, and don't benefit from the multiple-branch\n> speedup).\n\nIt's good to know that we already have an algorithm for the multi-head \napproach. Things like `git branch -vv` are harder to tease out because \nthe graph walk is called by the line-format code.\n\n> I tried to do a \"best of both\" algorithm in:\n>\n> https://public-inbox.org/git/20140625233429.GA20457@sigill.intra.peff.net/\n>\n> which finds arbitrary numbers of merge bases in a single traversal. It\n> did seem to work, but I felt uneasy about some of the corner cases.\n> I've been meaning to revisit it, but obviously have never gotten around\n> to it.\n>\n> The second slow thing is that during the traversal we load each commit\n> object from disk. The solution there is to keep the parent information\n> in a faster cache. I had a few proposals over the years, but I won't\n> even bother to dig them up, because there's quite recent and promising\n> work in this area from Derrick Stolee:\n>\n> https://public-inbox.org/git/1519698787-190494-1-git-send-email-dstolee@microsoft.com/\n>\n> And finally, the thing that the patches you linked are referencing is\n> about using commit timestamps as a proxy for generation numbers. And\n> Stolee's patches actually leave room for real, trustable generation\n> numbers.\n>\n> Once we have the serialized commit graph and generation numbers, think\n> the final step would just be to teach the \"tag --contains\" algorithm to\n> stop walking down unproductive lines of history. And in fact, I think we\n> can forget about the best-of-both multi-tip merge-base idea entirely.\n> Because if you can use the generation numbers to avoid going too deep,\n> then a depth-first approach is fine. And we'd just want to flip\n> git-branch over to using that algorithm by default.\n\nI'll keep this in mind as a target for performance measurements in the \nserialized commit graph patch and the following generation number patch.\n\nThanks,\n-Stolee\n"},{"id":"341514","messageId":"20180312235907.GG1968@sigill.intra.peff.net","threadId":"27604","inReplyTo":"63e9c6a8-4efc-6f86-f355-1ec40dd674e4@gmail.com","subject":"Re: [PATCH 0/4] Speed up git tag --contains","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-03-12T23:59:07Z","receivedAt":"2018-03-12T23:59:14Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Mar 12, 2018 at 09:45:27AM -0400, Derrick Stolee wrote:\n\n> > diff --git a/builtin/branch.c b/builtin/branch.c\n> > index 8dcc2ed058..4d674e86d5 100644\n> > --- a/builtin/branch.c\n> > +++ b/builtin/branch.c\n> > @@ -404,6 +404,7 @@ static void print_ref_list(struct ref_filter *filter, struct ref_sorting *sortin\n> > \tmemset(&array, 0, sizeof(array));\n> > +\tfilter->with_commit_tag_algo = 1;\n> > \tfilter_refs(&array, filter, filter->kind | FILTER_REFS_INCLUDE_BROKEN);\n> > \tif (filter->verbose)\n> > \n> > drops my run of \"git branch -a --contains HEAD~100\" from 8.6s to\n> > 0.4s on a repo with ~1800 branches. That sounds good, but on a repo with\n> > a smaller number of branches, we may actually end up slower (because we\n> > dig further down in history, and don't benefit from the multiple-branch\n> > speedup).\n> \n> It's good to know that we already have an algorithm for the multi-head\n> approach. Things like `git branch -vv` are harder to tease out because the\n> graph walk is called by the line-format code.\n\nYeah, the ahead/behind stuff will need some work. Part of it is just\ncode structuring. We know ahead of time which branches (and their\nupstreams) are going to need this ahead/behind computation, so we should\nbe able to do collect them all for a single call.\n\nBut I'm not sure if a general multi-pair ahead/behind is going to be\neasy. I don't have even experimental code for that. :)\n\nWe have a multi-pair ahead/behind command which we use at GitHub, but it\ndoes each pair separately. It leans heavily on reachability bitmaps, so\nthe main advantage is that it's able to amortize the cost of loading the\nbitmaps (both off disk, but also we sometimes have to walk to complete\nthe bitmaps).\n\n-Peff\n"}]}