{"thread":{"id":"24245","subject":"Why is \"git tag --contains\" so slow?","startedAt":"2010-07-01T00:54:15Z","lastAt":"2011-02-23T16:39:38Z","messageCount":46,"participants":["Theodore Ts'o","Shawn O. Pearce","Avery Pennarun","tytso@mit.edu","Jeff King","Sam Vilain","Will Palmer","Theodore Tso","Jakub Narebski","Johan Herland","Nicolas Pitre","Sverre Rabbelier","Jonathan Nieder","Clemens Buchacher","Ævar Arnfjörð Bjarmason"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"144557","messageId":"E1OU82h-0001xY-3b@closure.thunk.org","threadId":"24245","inReplyTo":null,"subject":"Why is \"git tag --contains\" so slow?","fromName":"Theodore Ts'o","fromEmail":"tytso@mit.edu","sentAt":"2010-07-01T00:54:15Z","receivedAt":"2010-07-01T00:54:15Z","isPatch":false,"sender":{"key":"tytso@mit.edu","avatar":"https://avatars.githubusercontent.com/u/51416?v=4"},"body":"\nI'm trying to write a script that can determine the first kernel release\n(i.e., a tag of that matchs v2.6.*) that contains a particular commit.\n\nI can do this using \"git tag --contains <commit-id>\", but it's quite\nslow.  It takes something like 8-9 seconds.  (8.5 seconds of user time,\n8.6 times of wall clock, to be precise).\n\nI can get the information much faster using \"gitk -1 <commit-id>\", which\nfinishes painting the screen in under 2 seconds, but that throws up a\nGUI and then a human has to pull the information out using their eyes.\n(Yeah, or I could figure out where in the 11,631 lines of Tcl script the\n\"preceeds\" line is calculated, but I figured I'd ask here first.)\n\nIs there a better way of calculating what I want from the command line\nusing the built-in native git tools?  And if so, why is git tag\n--contains apparently 4 times slower than gitk at performing this task?\n\nThanks,\n\n\t\t\t\t\t\t- Ted\n"},{"id":"144558","messageId":"20100701005854.GO2337@spearce.org","threadId":"24245","inReplyTo":"E1OU82h-0001xY-3b@closure.thunk.org","subject":"Re: Why is \"git tag --contains\" so slow?","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2010-07-01T00:58:54Z","receivedAt":"2010-07-01T00:58:54Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Theodore Ts'o <tytso@mit.edu> wrote:\n> \n> I'm trying to write a script that can determine the first kernel release\n> (i.e., a tag of that matchs v2.6.*) that contains a particular commit.\n> \n> I can do this using \"git tag --contains <commit-id>\", but it's quite\n> slow.  It takes something like 8-9 seconds.  (8.5 seconds of user time,\n> 8.6 times of wall clock, to be precise).\n> \n> I can get the information much faster using \"gitk -1 <commit-id>\", which\n> finishes painting the screen in under 2 seconds, but that throws up a\n> GUI and then a human has to pull the information out using their eyes.\n> (Yeah, or I could figure out where in the 11,631 lines of Tcl script the\n> \"preceeds\" line is calculated, but I figured I'd ask here first.)\n> \n> Is there a better way of calculating what I want from the command line\n> using the built-in native git tools?  And if so, why is git tag\n> --contains apparently 4 times slower than gitk at performing this task?\n\ngitk keeps a cache of this stuff in .git/gitk.cache.  I'll bet its\npulling from cache here, which is why it snaps so fast.\n\nWithout the cache is expensive, which is what 'git tag --contains'\nis doing.  The code walks back from each tag tracing along the commit\nparent pointers, keeping track of the nearest tag name that can reach\nany given commit.  When it finds your commit, it stops and outputs.\n\nSince this stuff can't change unless the refs change, yes, it can be\ncached easily.  But nobody has done caching for this in Git itself,\nonly in Tcl for gitk.  :-\\\n\n-- \nShawn.\n"},{"id":"144559","messageId":"AANLkTikkLIKm3soF9agXnN34P7Xnq4AiVqGU_qFaaRmZ@mail.gmail.com","threadId":"24245","inReplyTo":"E1OU82h-0001xY-3b@closure.thunk.org","subject":"Re: Why is \"git tag --contains\" so slow?","fromName":"Avery Pennarun","fromEmail":"apenwarr@gmail.com","sentAt":"2010-07-01T01:00:21Z","receivedAt":"2010-07-01T01:00:21Z","isPatch":false,"sender":{"key":"apenwarr@gmail.com","avatar":"https://avatars.githubusercontent.com/u/20592?v=4"},"body":"On Wed, Jun 30, 2010 at 8:54 PM, Theodore Ts'o <tytso@mit.edu> wrote:\n> I'm trying to write a script that can determine the first kernel release\n> (i.e., a tag of that matchs v2.6.*) that contains a particular commit.\n>\n> I can do this using \"git tag --contains <commit-id>\", but it's quite\n> slow.  It takes something like 8-9 seconds.  (8.5 seconds of user time,\n> 8.6 times of wall clock, to be precise).\n>\n> I can get the information much faster using \"gitk -1 <commit-id>\", which\n> finishes painting the screen in under 2 seconds, but that throws up a\n> GUI and then a human has to pull the information out using their eyes.\n\nThere's a big difference between the two: the gitk command you're\nusing only works if the given commit is *itself* named by a tag, while\n'git tag --contains' needs to search the entire history of every tag\nto see if the given commit is *inside* it somewhere.\n\nIf all you want is to see if a given commit exactly matches a tag,\nperhaps you want something like\n\n   git describe --exact-match <commit-id>\n\nHave fun,\n\nAvery\n"},{"id":"144593","messageId":"20100701121711.GF1333@thunk.org","threadId":"24245","inReplyTo":"AANLkTikkLIKm3soF9agXnN34P7Xnq4AiVqGU_qFaaRmZ@mail.gmail.com","subject":"Re: Why is \"git tag --contains\" so slow?","fromName":"","fromEmail":"tytso@mit.edu","sentAt":"2010-07-01T12:17:11Z","receivedAt":"2010-07-01T12:17:11Z","isPatch":false,"sender":{"key":"tytso@mit.edu","avatar":"https://avatars.githubusercontent.com/u/51416?v=4"},"body":"On Wed, Jun 30, 2010 at 09:00:21PM -0400, Avery Pennarun wrote:\n> \n> There's a big difference between the two: the gitk command you're\n> using only works if the given commit is *itself* named by a tag, while\n> 'git tag --contains' needs to search the entire history of every tag\n> to see if the given commit is *inside* it somewhere.\n\nGitk provides both.  What I want is listed on the \"Preceeds\" line in\nthe lower right hand box (the sixth line from the top in the\nper-commit box).\n\n> If all you want is to see if a given commit exactly matches a tag,\n> perhaps you want something like\n> \n>    git describe --exact-match <commit-id>\n\nYeah, I'm not talking about the tag and branch names that show up in\nthe top gitk box (and which you can also get via git log --annotate).\nI'm specifically talking about what you get with:\n\n\tgit tags --contains <commit-id>\n\n\t\t\t\t\t\t\t- Ted\n"},{"id":"144594","messageId":"20100701150331.GA12851@sigill.intra.peff.net","threadId":"24245","inReplyTo":"20100701121711.GF1333@thunk.org","subject":"Re: Why is \"git tag --contains\" so slow?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2010-07-01T15:03:31Z","receivedAt":"2010-07-01T15:03:31Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jul 01, 2010 at 08:17:11AM -0400, tytso@mit.edu wrote:\n\n> Yeah, I'm not talking about the tag and branch names that show up in\n> the top gitk box (and which you can also get via git log --annotate).\n> I'm specifically talking about what you get with:\n> \n> \tgit tags --contains <commit-id>\n\nI think there is room for improving the speed of \"git tag --contains\".\nConsider these two similar operations:\n\n  $ time git name-rev HEAD~200\n  HEAD~200 tags/v1.7.1-rc2~2\n\n  real    0m0.060s\n  user    0m0.048s\n  sys     0m0.012s\n\n  $ time git tag --contains HEAD~200\n  v1.7.1\n  v1.7.1-rc2\n  v1.7.1.1\n  v1.7.2-rc0\n  v1.7.2-rc1\n\n  real    0m2.179s\n  user    0m2.156s\n  sys     0m0.020s\n\nObviously the latter is producing the full list of tags, but both should\nhave to do a traversal starting at each tag ref.\n\nIt looks like \"git tag --contains\" is implemented as something like:\n\n  for ref in `git tag -l`; do\n    if `git merge-base $ref $commit | grep $commit`; then\n      echo $ref\n    fi\n  done\n\nexcept in C. But you can see we'll do a full merge-base calculation for\neach tag. And that merge-base calculation may potentially go quite far\nback in history.\n\nThe name-rev code has a simple heuristic that it stops traversing when\nthe timestamp of the traversed commit gets more than a day behind that\nof $commit. This doesn't do well with clock skew, but can save a lot of\ntime in practice. We should perhaps consider something like that here.\n\nI suspect we could do even better by sharing information between\ntraversals. That is, walk the graph from each ref, but retain marks on\ncommits between each walk. For a commit c, if walking down each parent\ngets us to a root without hitting $commit, then we can mark \"c\" as not\npossibly containing the commit. We can cut short any walk when we hit a\n\"c\" that is already marked. So by traversing from \"v1.7.1\", if we find\nthat we do not contain $commit, we will have already marked v1.7.0,\nv1.6.*, etc, and will not need to traverse them again.\n\nWhen you do find one that contains $commit, you can also mark it as\n\"definitely contains\", and you can stop a traversal that definitely\ncontains. So if we see something is in v1.7.0, then the traversal from\nv1.7.1 only needs to go as far back as v1.7.0.\n\n-Peff\n"},{"id":"144604","messageId":"20100701153842.GA15466@sigill.intra.peff.net","threadId":"24245","inReplyTo":"20100701150331.GA12851@sigill.intra.peff.net","subject":"Re: Why is \"git tag --contains\" so slow?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2010-07-01T15:38:42Z","receivedAt":"2010-07-01T15:38:42Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jul 01, 2010 at 11:03:31AM -0400, Jeff King wrote:\n\n>   $ time git tag --contains HEAD~200\n>   v1.7.1\n>   v1.7.1-rc2\n>   v1.7.1.1\n>   v1.7.2-rc0\n>   v1.7.2-rc1\n> \n>   real    0m2.179s\n>   user    0m2.156s\n>   sys     0m0.020s\n>\n> [...]\n>\n> I suspect we could do even better by sharing information between\n> traversals. That is, walk the graph from each ref, but retain marks on\n\nHere is a quick and dirty patch to implement what I suggested. With it,\nI get the same results as above, but it runs between 3 and 4 times as\nfast:\n\n  real    0m0.621s\n  user    0m0.588s\n  sys     0m0.032s\n\nImplementing the timestamp-checking thing that name-rev does would\nprobably drop it even more (at the expense of less accuracy in the\nface of clock skew).\n\ndiff --git a/builtin/tag.c b/builtin/tag.c\nindex d311491..d18c3ed 100644\n--- a/builtin/tag.c\n+++ b/builtin/tag.c\n@@ -10,6 +10,8 @@\n #include \"builtin.h\"\n #include \"refs.h\"\n #include \"tag.h\"\n+#include \"diff.h\"\n+#include \"revision.h\"\n #include \"run-command.h\"\n #include \"parse-options.h\"\n \n@@ -31,6 +33,42 @@ struct tag_filter {\n \n #define PGP_SIGNATURE \"-----BEGIN PGP SIGNATURE-----\"\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(const struct commit_list *want, struct commit *candidate)\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+\t/* If not, then try parents, and be sure to mark ourselves\n+\t * for future traversals. */\n+\tparse_commit(candidate);\n+\tfor (p = candidate->parents; p; p = p->next) {\n+\t\tif (contains(want, p->item)) {\n+\t\t\tcandidate->object.flags |= TMP_MARK;\n+\t\t\treturn 1;\n+\t\t}\n+\t}\n+\n+\tcandidate->object.flags |= UNINTERESTING;\n+\treturn 0;\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@@ -49,7 +87,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(filter->with_commit, commit))\n \t\t\t\treturn 0;\n \t\t}\n \n"},{"id":"144710","messageId":"20100702192612.GM1333@thunk.org","threadId":"24245","inReplyTo":"20100701153842.GA15466@sigill.intra.peff.net","subject":"Re: Why is \"git tag --contains\" so slow?","fromName":"","fromEmail":"tytso@mit.edu","sentAt":"2010-07-02T19:26:12Z","receivedAt":"2010-07-02T19:26:12Z","isPatch":false,"sender":{"key":"tytso@mit.edu","avatar":"https://avatars.githubusercontent.com/u/51416?v=4"},"body":"On Thu, Jul 01, 2010 at 11:38:42AM -0400, Jeff King wrote:\n> \n> Here is a quick and dirty patch to implement what I suggested. With it,\n> I get the same results as above, but it runs between 3 and 4 times as\n> fast:\n> \n>   real    0m0.621s\n>   user    0m0.588s\n>   sys     0m0.032s\n\nI just tried your patch, and with a large number of tags (198 tags,\nfrom v2.6.11 to v2.6.34 with all of the -rc releases of the linux\nkernel), it is indeed faster: 8.5 seconds without the patch versus 2.3\nseconds with the patch.\n\nHowever, if I remove a large number of tags (since I know this is\nsomething that was introduced since 2.6.33, so I made a shared clone\nof the repository but then I removed all of the tags from 2.6.11\nthrough 2.6.33, so there was only 19 tags in play), the time to\nexecute the git tag --contains became 1.3 seconds without the patch,\nversus 2.9 seconds without the patch.\n\nSo with the oldest tags removed, your patch actually made things run\n*slower* (2.3 vs 2.9 seconds, which was counter-intuitive to me), and\nfastest way to speed things up was to restrict the tags that would be\nsearched.\n\nWhich gives me the technique I should use to solve my immediate\nproblem, but if the user knows that the patch was merged into mainline\nwithin the last 4 months, maybe what would be better is either a way\nto specify a regexp (or list) of tags that the user finds\n\"interesting\" as --contains candidate, or a \"--since=4 months\"\nargument.\n\n\t   \t      \t   \t      \t      - Ted\n"},{"id":"144734","messageId":"20100703080618.GA10483@sigill.intra.peff.net","threadId":"24245","inReplyTo":"20100702192612.GM1333@thunk.org","subject":"Re: Why is \"git tag --contains\" so slow?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2010-07-03T08:06:19Z","receivedAt":"2010-07-03T08:06:19Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Jul 02, 2010 at 03:26:12PM -0400, tytso@mit.edu wrote:\n\n> I just tried your patch, and with a large number of tags (198 tags,\n> from v2.6.11 to v2.6.34 with all of the -rc releases of the linux\n> kernel), it is indeed faster: 8.5 seconds without the patch versus 2.3\n> seconds with the patch.\n> \n> However, if I remove a large number of tags (since I know this is\n> something that was introduced since 2.6.33, so I made a shared clone\n> of the repository but then I removed all of the tags from 2.6.11\n> through 2.6.33, so there was only 19 tags in play), the time to\n> execute the git tag --contains became 1.3 seconds without the patch,\n> versus 2.9 seconds without the patch.\n> \n> So with the oldest tags removed, your patch actually made things run\n> *slower* (2.3 vs 2.9 seconds, which was counter-intuitive to me), and\n> fastest way to speed things up was to restrict the tags that would be\n> searched.\n\nI'm guessing that it is caused by the depth-first search that my patch\ndoes. If we follow the \"wrong\" parent of a merge (i.e., the one that the\ncommit in question is not on), then we will end up hitting all commits\ndown to the roots before backtracking and looking down the right\nparent.\n\nI noticed that my improved time for \"git tag --contains\" was similar to\nthe total time for \"git rev-list --all >/dev/null\". Can you try timing\nthat? My suspicion is that it is going to be about 2.9 seconds for you.\n\nSo we could potentially improve my patch by doing a breadth-first\nsearch, although that is a bit trickier (since the point is to mark and\nprune whole subgraphs of history). But I'm not sure it is worth it in\npractice. It will make some lookups quicker, but in most cases you will\nend up going to the roots anyway for a negative lookup (in your case it\nwas only faster because you got rid of all the old tags). A better\nstrategy is to prune based on commit date so we _never_ go to the roots,\neven for a negative hit. That should give similar speedups as a\nbreadth-first search would to your case, but also make the normal case\nmuch faster by quickly discarding nonsensical paths (e.g., there is not\nmuch point following a commit made 3 years ago to see if it contains a\ncommit made yesterday).\n\nTry the patch below, which adds a date cutoff similar to the one used in\nname-rev. It's much faster in my tests:\n\n  # stock \"git tag --contains HEAD~200\"\n  real    0m2.179s\n  user    0m2.156s\n  sys     0m0.020s\n\n  # my first patch\n  real    0m0.621s\n  user    0m0.588s\n  sys     0m0.032s\n\n  # this patch\n  real    0m0.041s\n  user    0m0.036s\n  sys     0m0.004s\n\nFor non-pathological cases, I expect it to perform equal to stock git at\nworst, and in practice much better (for pathological cases, its worst\ncase is equivalent to \"git rev-list --all\", which is still not that\nbad). Let me know how it does on your case.\n\nThe obvious downside is that it stops looking down a path in the face of\nextreme clock skew. We could perhaps allow a \"--contains=thorough\" to\nspend a little more time to achieve a better answer (i.e., ignore the\ncutoff date).\n\ndiff --git a/builtin/tag.c b/builtin/tag.c\nindex d311491..5768a44 100644\n--- a/builtin/tag.c\n+++ b/builtin/tag.c\n@@ -10,6 +10,8 @@\n #include \"builtin.h\"\n #include \"refs.h\"\n #include \"tag.h\"\n+#include \"diff.h\"\n+#include \"revision.h\"\n #include \"run-command.h\"\n #include \"parse-options.h\"\n \n@@ -31,6 +33,61 @@ struct tag_filter {\n \n #define PGP_SIGNATURE \"-----BEGIN PGP SIGNATURE-----\"\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(const struct commit_list *want,\n+\t\t\t    struct commit *candidate,\n+\t\t\t    unsigned long cutoff)\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+\t/* stop searching if we go too far back in time */\n+\tparse_commit(candidate);\n+\tif (candidate->date < cutoff)\n+\t\treturn 0;\n+\n+\t/* If not, then try parents, and be sure to mark ourselves\n+\t * for future traversals. */\n+\tfor (p = candidate->parents; p; p = p->next) {\n+\t\tif (contains_recurse(want, p->item, cutoff)) {\n+\t\t\tcandidate->object.flags |= TMP_MARK;\n+\t\t\treturn 1;\n+\t\t}\n+\t}\n+\n+\tcandidate->object.flags |= UNINTERESTING;\n+\treturn 0;\n+}\n+\n+static int contains(const struct commit_list *want, struct commit *candidate)\n+{\n+\tconst struct commit_list *c;\n+\tunsigned long min_date = ULONG_MAX;\n+\tfor (c = want; c; c = c->next) {\n+\t\tparse_commit(c->item);\n+\t\tif (c->item->date < min_date)\n+\t\t\tmin_date = c->item->date;\n+\t}\n+\t/* give a full day of clock skew slop */\n+\treturn contains_recurse(want, candidate, min_date - 86400);\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@@ -49,7 +106,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(filter->with_commit, commit))\n \t\t\t\treturn 0;\n \t\t}\n \n"},{"id":"144765","messageId":"1278199649.9701.6.camel@denix","threadId":"24245","inReplyTo":"20100701005854.GO2337@spearce.org","subject":"Re: Why is \"git tag --contains\" so slow?","fromName":"Sam Vilain","fromEmail":"sam@vilain.net","sentAt":"2010-07-03T23:27:29Z","receivedAt":"2010-07-03T23:27:29Z","isPatch":false,"sender":{"key":"sam@vilain.net","avatar":"https://gravatar.com/avatar/8fc840ca854dbf6f7065b4335e3b934951c1dca3b11db688e95e471901f8f4a8?d=mp&s=160"},"body":"On Wed, 2010-06-30 at 17:58 -0700, Shawn O. Pearce wrote:\n> > I can do this using \"git tag --contains <commit-id>\", but it's quite\n> > slow.  It takes something like 8-9 seconds.  (8.5 seconds of user time,\n> > 8.6 times of wall clock, to be precise).\n> > \n> > I can get the information much faster using \"gitk -1 <commit-id>\", which\n> > [...]\n> > using the built-in native git tools?  And if so, why is git tag\n> > --contains apparently 4 times slower than gitk at performing this task?\n> \n> gitk keeps a cache of this stuff in .git/gitk.cache.  I'll bet its\n> pulling from cache here, which is why it snaps so fast.\n> \n> Without the cache is expensive, which is what 'git tag --contains'\n> is doing.  The code walks back from each tag tracing along the commit\n> parent pointers, keeping track of the nearest tag name that can reach\n> any given commit.  When it finds your commit, it stops and outputs.\n> \n> Since this stuff can't change unless the refs change, yes, it can be\n> cached easily.  But nobody has done caching for this in Git itself,\n> only in Tcl for gitk.  :-\\\n\nI think possibly rev-cache would improve this case.  Maybe it could also\nbe used for gitk.  Perhaps Nick you might like to say more, and comment\non what the outstanding work is to do?\n\nSam\n"},{"id":"144769","messageId":"20100704005543.GB6384@thunk.org","threadId":"24245","inReplyTo":"20100703080618.GA10483@sigill.intra.peff.net","subject":"Re: Why is \"git tag --contains\" so slow?","fromName":"","fromEmail":"tytso@mit.edu","sentAt":"2010-07-04T00:55:43Z","receivedAt":"2010-07-04T00:55:43Z","isPatch":false,"sender":{"key":"tytso@mit.edu","avatar":"https://avatars.githubusercontent.com/u/51416?v=4"},"body":"On Sat, Jul 03, 2010 at 04:06:19AM -0400, Jeff King wrote:\n> \n> I noticed that my improved time for \"git tag --contains\" was similar to\n> the total time for \"git rev-list --all >/dev/null\". Can you try timing\n> that? My suspicion is that it is going to be about 2.9 seconds for you.\n\nI'm at home, so getting access to my work machine is a bit of a pain,\nso I replicated the experiment at home.\n\n% time /tmp/git.1.7.2-rc1 tag --contains 307ae18 | wc -l\n13\n\nreal\t0m13.706s\nuser\t0m13.542s\nsys\t0m0.150s\n\n% time /tmp/git.patch.1 tag --contains 307ae18 | wc -l\n13\n\nreal\t0m2.869s\nuser\t0m2.703s\nsys\t0m0.163s\n\n% time /tmp/git.patch.1 rev-list --all  > /dev/null\n\nreal   0m3.074s\nuser   0m2.920s\nsys    0m0.147s\n\n\n> Try the patch below, which adds a date cutoff similar to the one used in\n> name-rev. It's much faster in my tests:\n\nYep, much faster indeed:\n\n% time /tmp/git.patch.2 tag --contains 307ae18 | wc -l\n13\n\nreal\t0m0.054s\nuser\t0m0.030s\nsys\t0m0.023s\n\n> The obvious downside is that it stops looking down a path in the face of\n> extreme clock skew. We could perhaps allow a \"--contains=thorough\" to\n> spend a little more time to achieve a better answer (i.e., ignore the\n> cutoff date).\n\nYep, it does blow up in the face of the extreme clock skew in some of\nthe ext4 commits in the Linux kernel tree.  (Sorry about that; mea\nculpa, I didn't realize at the time this was a problem, and it was my\nworkflow using the guilt program which happened to introduce them.)\n\nIn any case, because of the ext4 commits, I can show a test case which\ndoesn't work well with your date cutoff patch:\n\n#!/bin/sh\n\nfor i in $(git log --reverse --oneline v2.6.32..v2.6.35-rc3 fs/ext4 fs/jbd2 |\n      \t       awk '{print $1}')\ndo\n    echo -n \"$i \"\n    /tmp/git.patch.2 tag --contains $i | head -1\ndone\n\nYou won't see any problems after v2.6.34; I fixed my workflow once I\nwas told it was causing git problems.\n\nIf you replace this with the unpatched git, or with git with your\nfirst patch, it will be of course much slower, but it will print out\nall of the tags that would be expected given a topographical\nexamination of the commit graph.  Whether this is a bug in git or a bug\nthat I introduced into the Linux kernel git tree is of course an open\nquestion.  However, if we do want to allow git operations to work\nquickly --- and I agree this is a good thing; the speedups that this\ncan allow are quite significant --- maybe we should teach \"git commit\"\nto either print a warning or outright refuse to introduce clock skews\nin the first place.\n\n(Or maybe we have git config options that can enable or disable\noptimizations that depend on the lack of clock skews; but I could\nunderstand people not wanting to maintian the extra code paths.)\n\n\t   \t      \t      \t \t  - Ted\n"},{"id":"144813","messageId":"20100705122723.GB21146@sigill.intra.peff.net","threadId":"24245","inReplyTo":"20100704005543.GB6384@thunk.org","subject":"Re: Why is \"git tag --contains\" so slow?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2010-07-05T12:27:23Z","receivedAt":"2010-07-05T12:27:23Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Jul 03, 2010 at 08:55:43PM -0400, tytso@mit.edu wrote:\n\n> > I noticed that my improved time for \"git tag --contains\" was similar to\n> > the total time for \"git rev-list --all >/dev/null\". Can you try timing\n> > that? My suspicion is that it is going to be about 2.9 seconds for you.\n> \n> I'm at home, so getting access to my work machine is a bit of a pain,\n> so I replicated the experiment at home.\n\nThanks. Those numbers confirm what I had been thinking.\n\n> Yep, it does blow up in the face of the extreme clock skew in some of\n> the ext4 commits in the Linux kernel tree.  (Sorry about that; mea\n> culpa, I didn't realize at the time this was a problem, and it was my\n> workflow using the guilt program which happened to introduce them.)\n\nYes, I was thinking specifically of those commits when I warned about\nclock skew. :)\n\n> In any case, because of the ext4 commits, I can show a test case which\n> doesn't work well with your date cutoff patch:\n\nNot surprising. I think you will find that \"git name-rev\" (or \"git\ndescribe --contains\", which simply calls name-rev) will have similar\nproblems.\n\n> (Or maybe we have git config options that can enable or disable\n> optimizations that depend on the lack of clock skews; but I could\n> understand people not wanting to maintian the extra code paths.)\n\nI think the best thing we can do is provide a \"how much clock skew to\ntolerate\" variable, and give it a sane default. Then people who know\nthey have skewed repositories can make the correctness-optimization\ntradeoff as they see fit.\n\nThe extra code is very minor. It's really only a line or two of code\nwhen calculating the cutoff date to convert \"be thorough\" into a cutoff\ndate of 0.\n\nThe real question is what that default should be. Name-rev already uses\n86400 seconds. The worst skew in git.git is 8 seconds. The worst skew in\nlinux-2.6.git is 8622098 (about 100 days). For reference, here are my\ntimings on \"git tag --contains HEAD~200\" for various allowable clock\nskew values:\n\n  0 (don't allow even a second of clock skew): .035s\n  86400 (one day of clock skew allowed): .034s\n  8622098 (the worst skew in linux-2.6): .252s\n  infinite (never cutoff for clock skew): 5.373s\n\nSo anything below a day is pointless and lost in the noise. Even 100\ndays yields quite a satisfactory speedup from the current code, but\nobviously that number is totally arbitrary based on one repo.\n\nAs you probably guessed from the specificity of the number, I wrote a\nshort program to actually traverse and find the worst skew. It takes\nabout 5 seconds to run (unsurprisingly, since it is doing the same full\ntraversal that we end up doing in the above numbers). So we could\n\"autoskew\" by setting up the configuration on clone, and then\nperiodically updating it as part of \"git gc\".\n\nThat is perhaps over-engineering (and would add a few seconds to a\nclone), but I like that it would Just Work without the user doing\nanything.\n\nI'll follow this mail up with a series that implements a cleaned-up\nversion of the previous patches in this thread, and we'll see what\nothers think.\n\n-Peff\n"},{"id":"144814","messageId":"20100705123335.GA25699@sigill.intra.peff.net","threadId":"24245","inReplyTo":"20100705122723.GB21146@sigill.intra.peff.net","subject":"[RFC/PATCH 1/4] tag: speed up --contains calculation","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2010-07-05T12:33:36Z","receivedAt":"2010-07-05T12:33:36Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When 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 <peff@peff.net>\n---\nNote that this is a depth first search, whereas we generally traverse in\na more breadth-first way. So it can actually make things slightly slower\nthan the current merge-base code, if:\n\n  1. You don't have any merge base calculations that involve going very\n     far back in history.\n\n  2. We depth-first down the wrong side of a merge.\n\nHowever, in the usual cases, I think it will perform much better.\nComparing an old tag with a recent commit means we have to look at a lot\nof the commit graph, anyway.\n\nIf anybody has a clever idea for making it breadth-first, I would be\nhappy to hear it.\n\nOther caveats:\n\n  1. This can probably be a one-liner change to use in \"git branch\n     --contains\", as well. I didn't measure it, as that already tends to\n     be reasonably fast.\n\n  2. It uses commit marks, which means it doesn't behave well with other\n     traversals. I have no idea if I should be using alternate marks or\n     not.\n\n  3. We never clear the marks, or check them against the \"want\" list. So\n     we just assume that repeated calls to contains will have the same\n     \"want\" list.\n\n builtin/tag.c |    2 +-\n commit.c      |   42 ++++++++++++++++++++++++++++++++++++++++++\n commit.h      |    2 ++\n 3 files changed, 45 insertions(+), 1 deletions(-)\n\ndiff --git a/builtin/tag.c b/builtin/tag.c\nindex d311491..c200e1e 100644\n--- a/builtin/tag.c\n+++ b/builtin/tag.c\n@@ -49,7 +49,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 \ndiff --git a/commit.c b/commit.c\nindex e9b0750..20354c6 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -845,3 +845,45 @@ int commit_tree(const char *msg, unsigned char *tree,\n \tstrbuf_release(&buffer);\n \treturn result;\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+}\ndiff --git a/commit.h b/commit.h\nindex eb2b8ac..1a7299e 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -153,6 +153,8 @@ extern struct commit_list *get_shallow_commits(struct object_array *heads,\n int is_descendant_of(struct commit *, struct commit_list *);\n int in_merge_bases(struct commit *, struct commit **, int);\n \n+int contains(struct commit *, const struct commit_list *);\n+\n extern int interactive_add(int argc, const char **argv, const char *prefix);\n extern int run_add_interactive(const char *revision, const char *patch_mode,\n \t\t\t       const char **pathspec);\n-- \n1.7.2.rc1.209.g2a36c\n"},{"id":"144815","messageId":"20100705123419.GB25699@sigill.intra.peff.net","threadId":"24245","inReplyTo":"20100705122723.GB21146@sigill.intra.peff.net","subject":"[RFC/PATCH 2/4] limit \"contains\" traversals based on commit timestamp","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2010-07-05T12:34:19Z","receivedAt":"2010-07-05T12:34:19Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"When 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 <peff@peff.net>\n---\n cache.h  |    1 +\n commit.c |   27 ++++++++++++++++++++++++---\n config.c |    8 ++++++++\n 3 files changed, 33 insertions(+), 3 deletions(-)\n\ndiff --git a/cache.h b/cache.h\nindex c9fa3df..2dfb636 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -551,6 +551,7 @@ extern int read_replace_refs;\n extern int fsync_object_files;\n extern int core_preload_index;\n extern int core_apply_sparse_checkout;\n+extern int core_clock_skew;\n \n enum safe_crlf {\n \tSAFE_CRLF_FALSE = 0,\ndiff --git a/commit.c b/commit.c\nindex 20354c6..c849b50 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -7,6 +7,7 @@\n #include \"revision.h\"\n #include \"notes.h\"\n \n+int core_clock_skew = -1;\n int save_commit_buffer = 1;\n \n const char *commit_type = \"commit\";\n@@ -855,7 +856,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@@ -872,9 +874,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@@ -885,5 +891,20 @@ 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 }\ndiff --git a/config.c b/config.c\nindex cdcf583..7a18bc9 100644\n--- a/config.c\n+++ b/config.c\n@@ -595,6 +595,14 @@ static int git_default_core_config(const char *var, const char *value)\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 \t/* Add other config variables here and to Documentation/config.txt. */\n \treturn 0;\n }\n-- \n1.7.2.rc1.209.g2a36c\n"},{"id":"144817","messageId":"20100705123533.GC25699@sigill.intra.peff.net","threadId":"24245","inReplyTo":"20100705122723.GB21146@sigill.intra.peff.net","subject":"[RFC/PATCH 3/4] default core.clockskew variable to one day","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2010-07-05T12:35:34Z","receivedAt":"2010-07-05T12:35:34Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"This is the slop value used by name-rev, so presumably is a\nreasonable default.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nActually, I think auto-detecting the skew in a repo during \"gc\" might be\nan even better default. See:\n\n  http://article.gmane.org/gmane.comp.version-control.git/150260\n\nearlier in this thread for some numbers and discussion.\n\n commit.c |    2 +-\n 1 files changed, 1 insertions(+), 1 deletions(-)\n\ndiff --git a/commit.c b/commit.c\nindex c849b50..4cbe756 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -7,7 +7,7 @@\n #include \"revision.h\"\n #include \"notes.h\"\n \n-int core_clock_skew = -1;\n+int core_clock_skew = 86400;\n int save_commit_buffer = 1;\n \n const char *commit_type = \"commit\";\n-- \n1.7.2.rc1.209.g2a36c\n"},{"id":"144818","messageId":"20100705123653.GD25699@sigill.intra.peff.net","threadId":"24245","inReplyTo":"20100705122723.GB21146@sigill.intra.peff.net","subject":"[RFC/PATCH 4/4] name-rev: respect core.clockskew","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2010-07-05T12:36:53Z","receivedAt":"2010-07-05T12:36:53Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Before core.clockskew existed, we were just hard-coded to\n86400 seconds. This allows users to tweak the value as\nappropriate.\n\nSigned-off-by: Jeff King <peff@peff.net>\n---\nI think it makes sense to adapt this to core.clockskew. Especially if\nour default stays at 86400, then there is no change in behavior. But\neven if it does change, I think having it tweakable (and especially if\nwe automatically calculate per-repo skew) makes sense.\n\n builtin/name-rev.c |    8 ++++----\n 1 files changed, 4 insertions(+), 4 deletions(-)\n\ndiff --git a/builtin/name-rev.c b/builtin/name-rev.c\nindex 06a38ac..5c6d712 100644\n--- a/builtin/name-rev.c\n+++ b/builtin/name-rev.c\n@@ -5,8 +5,6 @@\n #include \"refs.h\"\n #include \"parse-options.h\"\n \n-#define CUTOFF_DATE_SLOP 86400 /* one day */\n-\n typedef struct rev_name {\n \tconst char *tip_name;\n \tint generation;\n@@ -270,8 +268,10 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)\n \t\tadd_object_array((struct object *)commit, *argv, &revs);\n \t}\n \n-\tif (cutoff)\n-\t\tcutoff = cutoff - CUTOFF_DATE_SLOP;\n+\tif (cutoff && core_clock_skew >= 0)\n+\t\tcutoff = cutoff - core_clock_skew;\n+\telse\n+\t\tcutoff = 0;\n \tfor_each_ref(name_ref, &data);\n \n \tif (transform_stdin) {\n-- \n1.7.2.rc1.209.g2a36c\n"},{"id":"144819","messageId":"20100705123923.GC21146@sigill.intra.peff.net","threadId":"24245","inReplyTo":"20100705122723.GB21146@sigill.intra.peff.net","subject":"Re: Why is \"git tag --contains\" so slow?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2010-07-05T12:39:23Z","receivedAt":"2010-07-05T12:39:23Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On 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\ndiff --git a/.gitignore b/.gitignore\nindex 14e2b6b..90aff17 100644\n--- a/.gitignore\n+++ b/.gitignore\n@@ -132,6 +132,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 9aca8a1..e673bdf 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -725,6 +725,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 ed6ee26..5f5dc0a 100644\n--- a/builtin.h\n+++ b/builtin.h\n@@ -141,5 +141,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 265fa09..8a77fe3 100644\n--- a/git.c\n+++ b/git.c\n@@ -399,6 +399,7 @@ static void handle_internal_command(int argc, const char **argv)\n \t\t{ \"verify-pack\", cmd_verify_pack },\n \t\t{ \"show-ref\", cmd_show_ref, RUN_SETUP },\n \t\t{ \"pack-refs\", cmd_pack_refs, RUN_SETUP },\n+\t\t{ \"skew\", cmd_skew, RUN_SETUP },\n \t};\n \tint i;\n \tstatic const char ext[] = STRIP_EXTENSION;\n"},{"id":"144822","messageId":"20100705141012.GA25518@thunk.org","threadId":"24245","inReplyTo":"20100705122723.GB21146@sigill.intra.peff.net","subject":"Re: Why is \"git tag --contains\" so slow?","fromName":"","fromEmail":"tytso@mit.edu","sentAt":"2010-07-05T14:10:12Z","receivedAt":"2010-07-05T14:10:12Z","isPatch":false,"sender":{"key":"tytso@mit.edu","avatar":"https://avatars.githubusercontent.com/u/51416?v=4"},"body":"On Mon, Jul 05, 2010 at 08:27:23AM -0400, Jeff King wrote:\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> \n> That is perhaps over-engineering (and would add a few seconds to a\n> clone), but I like that it would Just Work without the user doing\n> anything.\n\nAs time progresses, the clock skew breakage should be less likely to\nbe hit by a typical developer, right?  That is, unless you are\nspecifically referencing one of the commits which were skewed, two\nyears from now, the chances of someone (who isn't doing code\narcheology) of getting hit by a problem should be small, right?  This\nseems to be definitely the case with \"git tag --contains\"; would it be\ntrue for git name-rev and the other places that depend on (roughly)\nincreasing commit times?\n\nIf so, I could imagine the automagic scheme choosing a default that\nonly finds the worst skew in the past N months.  This would speed up\nthings up for users who are using repositories that have skews in the\ndistant past, at the cost of introducing potentially confusuing edge\ncases for people doing code archeology.\n\nI'm not sure this is a good tradeoff, but given in practice how rarely\nmost developers go back in time more than say, 12-24 months, maybe\nit's worth doing.  What do you think?\n\n     \t   \t   \t\t\t\t- Ted\n"},{"id":"144896","messageId":"20100706115826.GA15413@sigill.intra.peff.net","threadId":"24245","inReplyTo":"20100705141012.GA25518@thunk.org","subject":"Re: Why is \"git tag --contains\" so slow?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2010-07-06T11:58:28Z","receivedAt":"2010-07-06T11:58:28Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Jul 05, 2010 at 10:10:12AM -0400, tytso@mit.edu wrote:\n\n> As time progresses, the clock skew breakage should be less likely to\n> be hit by a typical developer, right?  That is, unless you are\n> specifically referencing one of the commits which were skewed, two\n> years from now, the chances of someone (who isn't doing code\n> archeology) of getting hit by a problem should be small, right?  This\n\nIt's not about directly referencing skewed commits. It's about\ntraversing history that contains skewed commits. So if I have a history\nlike:\n\n  A -- B -- C -- D\n\nand \"B\" is skewed, then I will generally give up on finding \"A\" when\nsearching backwards from \"C\" or \"D\", or their descendants. So as time\nmoves forward, you will continue to have your old tags pointing to \"C\"\nor \"D\", but also tags pointing to their descendants. Doing \"git tag\n--contains A\" will continue to be inaccurate, since it will continue to\nlook for \"A\" from \"C\" and \"D\", but also from newer tags, all of which\ninvolve traversing the skewed \"B\".\n\nWhat I think is true is that people will be less likely to look at \"A\"\nas time goes on, as code it introduced presumably becomes less relevant\n(either bugs are shaken out, or it gets replaced, or whatever). And\nobviously looking at \"C\" from \"D\", the skew in \"B\" will be irrelevant.\n\nSo I think typical developers become less likely to hit the issue as\ntime goes on, but software archaeologists will hit it forever.\n\n> If so, I could imagine the automagic scheme choosing a default that\n> only finds the worst skew in the past N months.  This would speed up\n> things up for users who are using repositories that have skews in the\n> distant past, at the cost of introducing potentially confusuing edge\n> cases for people doing code archeology.\n\nHow do you decide, when looking for commits that have bogus timestamps,\nwhich ones happened in the past N months? Certainly you can do some\nstatistical analysis to pick out anomalous ones. And you could perhaps\nfavor future skewing over past skewing, since that skew doesn't tend to\nimpact traversal cutoffs (and large past skewing seems to be more\ncommon). But that is getting kind of complex.\n\n> I'm not sure this is a good tradeoff, but given in practice how rarely\n> most developers go back in time more than say, 12-24 months, maybe\n> it's worth doing.  What do you think?\n\nI'm not sure. I am tempted to just default it to 86400 and go no\nfurther.  People who care about archaeology can turn off traversal\ncutoffs if they like, and as the skewed history ages, people get less\nlikely to look at it. We could also pick half a year or some high number\nas the default allowable. The performance increase is still quite\nnoticeable there, and it covers the only large skew we know about. I'd\nbe curious to see if other projects have skew, and how much.\n\n-Peff\n"},{"id":"144916","messageId":"1278430303.32094.15.camel@wpalmer.simply-domain","threadId":"24245","inReplyTo":"20100706115826.GA15413@sigill.intra.peff.net","subject":"Re: Why is \"git tag --contains\" so slow?","fromName":"Will Palmer","fromEmail":"wmpalmer@gmail.com","sentAt":"2010-07-06T15:31:43Z","receivedAt":"2010-07-06T15:31:43Z","isPatch":false,"sender":{"key":"wmpalmer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/357044?v=4"},"body":"On Tue, 2010-07-06 at 07:58 -0400, Jeff King wrote:\n> On Mon, Jul 05, 2010 at 10:10:12AM -0400, tytso@mit.edu wrote:\n> > I'm not sure this is a good tradeoff, but given in practice how rarely\n> > most developers go back in time more than say, 12-24 months, maybe\n> > it's worth doing.  What do you think?\n> \n> I'm not sure. I am tempted to just default it to 86400 and go no\n> further.  People who care about archaeology can turn off traversal\n> cutoffs if they like, and as the skewed history ages, people get less\n> likely to look at it. We could also pick half a year or some high number\n> as the default allowable. The performance increase is still quite\n> noticeable there, and it covers the only large skew we know about. I'd\n> be curious to see if other projects have skew, and how much.\n> \n> -Peff\n\nIs it wrong to expect that git perform poorly in the edge-cases (hugely\nskewed timestamps), but that it perform /correctly/ in all cases?\n\nClearly, marking already-traversed histories was the right thing to do,\nand if I read correctly, made a good improvement on its own. But you\nseem to have crossed a line at some point between \"optimization\" and\n\"potentially giving the wrong answer because it's faster\"\n\nOr am I just misunderstanding here?\n"},{"id":"144920","messageId":"20100706165336.GJ25518@thunk.org","threadId":"24245","inReplyTo":"1278430303.32094.15.camel@wpalmer.simply-domain","subject":"Re: Why is \"git tag --contains\" so slow?","fromName":"","fromEmail":"tytso@mit.edu","sentAt":"2010-07-06T16:53:36Z","receivedAt":"2010-07-06T16:53:36Z","isPatch":false,"sender":{"key":"tytso@mit.edu","avatar":"https://avatars.githubusercontent.com/u/51416?v=4"},"body":"On Tue, Jul 06, 2010 at 04:31:43PM +0100, Will Palmer wrote:\n> Is it wrong to expect that git perform poorly in the edge-cases (hugely\n> skewed timestamps), but that it perform /correctly/ in all cases?\n> \n> Clearly, marking already-traversed histories was the right thing to do,\n> and if I read correctly, made a good improvement on its own. But you\n> seem to have crossed a line at some point between \"optimization\" and\n> \"potentially giving the wrong answer because it's faster\"\n\nWhen \"it's faster\" is between 100-1000 times faster, I think we have\nto look at things a bit more closely.  That's the difference between a\ncommand being usable and not usable.\n\nWe would be much better off if our tools enforced the fact that\ncommitter times were always increasing.  If from the beginning, we had\nintroduced checks so that \"git commit\" refused to create new commits\nwhere the committer time was before its parent commit(s), and\ngit-receive-pack refused to accept packs that contained\nnon-monotonically increasing commits or commits that occurred in the\nfuture according to its system clock, then these optimizations would\nbe completely valid.\n\nBut we didn't, and we do have skew in some repositories.  So the\nquestion is what to do going forward?  One solution might be to\nenforce this moving forward, and to have varying levels of strictness\nin enforcing this constraint.  So for completely new repositories,\nthis becomes a non-brainer.  For older repositories, Jeff's idea of\nhaving a tunable parameter so that results are correct given a maximum\nclock skew --- which can be determined --- will allow us to have\ncorrectness _and_ performance.\n\n\t\t\t\t\t\t- Ted\n"},{"id":"145036","messageId":"20100707174546.GA4979@coredump.intra.peff.net","threadId":"24245","inReplyTo":"1278430303.32094.15.camel@wpalmer.simply-domain","subject":"Re: Why is \"git tag --contains\" so slow?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2010-07-07T17:45:46Z","receivedAt":"2010-07-07T17:45:46Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jul 06, 2010 at 04:31:43PM +0100, Will Palmer wrote:\n\n> Is it wrong to expect that git perform poorly in the edge-cases (hugely\n> skewed timestamps), but that it perform /correctly/ in all cases?\n\nWhen you put it that way, yes, I think the ideal behavior is that we are\nalways correct, fast in the common case, and slow for edge cases.\n\nBut there are some fuzzy areas here:\n\n  1. Is clock skew more than a day (or some number of seconds, whatever\n     it may be) an edge case, or is it simply breakage in the repo? In\n     an ideal world, it would simply be an edge case that causes\n     slowdown. But git already implements traversal-cutoff based on\n     date, at least in \"git name-rev\", so this is not a new issue. I\n     know we also look at the date for some other traversals (in fact, I\n     see lots of other cutoffs that don't even seem to have the one-day\n     slop). But I haven't looked closely enough to see just what will\n     break with a huge skew.\n\n  2. Not implementing traversal-cutoff based on date doesn't slow just\n     edge cases. It slows _all_ cases, by a factor of a hundred, on the\n     off chance that you might have an edge case.\n\n     By pre-calculating the per-repo max skew during clone and gc, you\n     can turn it into your \"always correct, slower for edge cases\". But:\n\n       a. It makes clone and gc a bit slower, even for non-edge cases.\n\n       b. It is not _always_ correct, as you have a lag period between\n          when skew is introduced into your repo (either by commit or by\n          fetch) and when you gc it. But it's closer.\n\n     And of course it's just complex, and I tend to shy away from\n     complexity when I can. The question to me comes back to (1) above.\n     Is massive clock skew a breakage that should produce a few\n     incorrect results, or is it something we should always handle?\n\n-Peff\n"},{"id":"145037","messageId":"20100707175037.GB4979@coredump.intra.peff.net","threadId":"24245","inReplyTo":"1278430303.32094.15.camel@wpalmer.simply-domain","subject":"Re: Why is \"git tag --contains\" so slow?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2010-07-07T17:50:37Z","receivedAt":"2010-07-07T17:50:37Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jul 06, 2010 at 04:31:43PM +0100, Will Palmer wrote:\n\n> Clearly, marking already-traversed histories was the right thing to do,\n> and if I read correctly, made a good improvement on its own. But you\n> seem to have crossed a line at some point between \"optimization\" and\n> \"potentially giving the wrong answer because it's faster\"\n\nAs a side-note to what I said in my other email, the sinful thing here\nis not this optimization (my patch 2/4). It's _defaulting_ the\noptimization to on (my patch 3/4). With just 2/4, it's something that a\nuser can enable to get better speed if they feel confident there is no\nlarge skew in their repo.\n\n-Peff\n"},{"id":"145107","messageId":"11D5771D-EB47-42E9-BCC3-69C8FE1999EC@MIT.EDU","threadId":"24245","inReplyTo":"20100707174546.GA4979@coredump.intra.peff.net","subject":"Re: Why is \"git tag --contains\" so slow?","fromName":"Theodore Tso","fromEmail":"tytso@mit.edu","sentAt":"2010-07-08T10:29:04Z","receivedAt":"2010-07-08T10:29:04Z","isPatch":false,"sender":{"key":"tytso@mit.edu","avatar":"https://avatars.githubusercontent.com/u/51416?v=4"},"body":"\nOn Jul 7, 2010, at 1:45 PM, Jeff King wrote:\n\n>     And of course it's just complex, and I tend to shy away from\n>     complexity when I can. The question to me comes back to (1) above.\n>     Is massive clock skew a breakage that should produce a few\n>     incorrect results, or is it something we should always handle?\n\nGoing back to the question that kicked off this thread, I wonder if there\nis some way that cacheing could be used to speed up the all cases,\nor at lest the edge cases, without imposing as much latency as tracking\nthe max skew?   i.e., some thing like gitk's gitk.cache file.  For bonus\npoints, it could be a cache file that is used by both gitk and git tag\n--contains, git branch --contains, and git name-rev.\n\nDoes that sound like reasonable idea?\n\n--Ted\n"},{"id":"145111","messageId":"m37hl6mdnb.fsf@localhost.localdomain","threadId":"24245","inReplyTo":"11D5771D-EB47-42E9-BCC3-69C8FE1999EC@MIT.EDU","subject":"Re: Why is \"git tag --contains\" so slow?","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2010-07-08T11:12:36Z","receivedAt":"2010-07-08T11:12:36Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Theodore Tso <tytso@MIT.EDU> writes:\n> On Jul 7, 2010, at 1:45 PM, Jeff King wrote:\n> \n> >     And of course it's just complex, and I tend to shy away from\n> >     complexity when I can. The question to me comes back to (1) above.\n> >     Is massive clock skew a breakage that should produce a few\n> >     incorrect results, or is it something we should always handle?\n> \n> Going back to the question that kicked off this thread, I wonder if there\n> is some way that cacheing could be used to speed up the all cases,\n> or at lest the edge cases, without imposing as much latency as tracking\n> the max skew?   i.e., some thing like gitk's gitk.cache file.  For bonus\n> points, it could be a cache file that is used by both gitk and git tag\n> --contains, git branch --contains, and git name-rev.\n> \n> Does that sound like reasonable idea?\n\nBy the way, what had happened to the rev-cache project from GSoC 2009?\n\n-- \nJakub Narebski\nPoland\nShadeHawk on #git\n"},{"id":"145113","messageId":"20100708112802.GA2294@sigill.intra.peff.net","threadId":"24245","inReplyTo":"20100706165336.GJ25518@thunk.org","subject":"Re: Why is \"git tag --contains\" so slow?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2010-07-08T11:28:02Z","receivedAt":"2010-07-08T11:28:02Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jul 06, 2010 at 12:53:36PM -0400, tytso@mit.edu wrote:\n\n> We would be much better off if our tools enforced the fact that\n> committer times were always increasing.  If from the beginning, we had\n> introduced checks so that \"git commit\" refused to create new commits\n> where the committer time was before its parent commit(s), and\n> git-receive-pack refused to accept packs that contained\n> non-monotonically increasing commits or commits that occurred in the\n> future according to its system clock, then these optimizations would\n> be completely valid.\n> \n> But we didn't, and we do have skew in some repositories.  So the\n> question is what to do going forward?  One solution might be to\n> enforce this moving forward, and to have varying levels of strictness\n> in enforcing this constraint.  So for completely new repositories,\n\nWhatever we do with the optimization, I do agree with your suggestion at\nleast for \"git commit\" to avoid making such commits.  Rejecting them\nduring fetchs and pushes would be a nice, too, but should probably just\nbe a warning at first, in case you have to pull from somebody with an\nolder git. You would also have to consider whether some small skew is\nacceptable during a pull. Something like a 5-second skew is not a big\ndeal. If you had thousands of such skews in a row, yes, it would be bad,\nbut that is not likely to happen (and I can't think of some way to\nmaliciously create such a history that would not otherwise be\nunusable).\n\n> this becomes a non-brainer.  For older repositories, Jeff's idea of\n> having a tunable parameter so that results are correct given a maximum\n> clock skew --- which can be determined --- will allow us to have\n> correctness _and_ performance.\n\nYeah. I think the real question is what the default for that parameter\nshould be: pessimistic but always correct, optimistic but possibly\nincorrect in the face of skew, or auto-tuned per-repository.\n\n-Peff\n"},{"id":"145114","messageId":"20100708113151.GB2294@sigill.intra.peff.net","threadId":"24245","inReplyTo":"11D5771D-EB47-42E9-BCC3-69C8FE1999EC@MIT.EDU","subject":"Re: Why is \"git tag --contains\" so slow?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2010-07-08T11:31:51Z","receivedAt":"2010-07-08T11:31:51Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Jul 08, 2010 at 06:29:04AM -0400, Theodore Tso wrote:\n\n> On Jul 7, 2010, at 1:45 PM, Jeff King wrote:\n> \n> >     And of course it's just complex, and I tend to shy away from\n> >     complexity when I can. The question to me comes back to (1) above.\n> >     Is massive clock skew a breakage that should produce a few\n> >     incorrect results, or is it something we should always handle?\n> \n> Going back to the question that kicked off this thread, I wonder if there\n> is some way that cacheing could be used to speed up the all cases,\n> or at lest the edge cases, without imposing as much latency as tracking\n> the max skew?   i.e., some thing like gitk's gitk.cache file.  For bonus\n> points, it could be a cache file that is used by both gitk and git tag\n> --contains, git branch --contains, and git name-rev.\n> \n> Does that sound like reasonable idea?\n\nIt sounds reasonable to me. It just needs somebody to design and\nimplement it. :)\n\nI don't know anything about how gitk.cache works. Caching tag refs is\nnot that hard, because the refs tend not to change. Doing arbitrary \"X\ncontains Y\" caching is much harder, and I think you would have to build\nit on Nick's rev-cache work. Maybe he (cc'd) has some ideas.\n\n-Peff\n"},{"id":"145123","messageId":"1278595295.2668.10.camel@wpalmer.simply-domain","threadId":"24245","inReplyTo":"20100708112802.GA2294@sigill.intra.peff.net","subject":"Re: Why is \"git tag --contains\" so slow?","fromName":"Will Palmer","fromEmail":"wmpalmer@gmail.com","sentAt":"2010-07-08T13:21:35Z","receivedAt":"2010-07-08T13:21:35Z","isPatch":false,"sender":{"key":"wmpalmer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/357044?v=4"},"body":"On Thu, 2010-07-08 at 07:28 -0400, Jeff King wrote:\n> On Tue, Jul 06, 2010 at 12:53:36PM -0400, tytso@mit.edu wrote:\n> Whatever we do with the optimization, I do agree with your suggestion at\n> least for \"git commit\" to avoid making such commits.  Rejecting them\n> during fetchs and pushes would be a nice, too, but should probably just\n> be a warning at first, in case you have to pull from somebody with an\n> older git...[snip]\n> Yeah. I think the real question is what the default for that parameter\n> should be: pessimistic but always correct, optimistic but possibly\n> incorrect in the face of skew, or auto-tuned per-repository.\n> -Peff\n\nI think these two go hand-in-hand, and would resolve most of my issues\nwith it. Auto-tune, starting pessimistically, but then using something\nmore-optimized after something like gc has detected that it's okay. On\npull from an older repository (which I see as happening very frequently,\nI add remotes much more often than I do a straight \"clone\"), a warning\nand an auto-tune to something which would account for the newly-fetched\nbad data.\n\nMy only other objection is more wishy-washy and/or lazy: currently a\n\"commit\" doesn't need to know anything at all about what it references\nin order to be considered a valid object, but saying \"the time of commit\nneeds to be equal to or greater than the parent commit\" means that a\ntool.. and by \"tool\" I mean \"wretched abuse of cat-file and sed\", which\nis sometimes just faster to throw-together than filter-branch ..needs to\nbe more aware of what it's doing. Yes, it's a horrible abuse, but I was\nalways under the impression that low-level abuse of the system is\nsomething which git supports, by virtue of having such a simple model.\n"},{"id":"145126","messageId":"20100708135442.GA7549@thunk.org","threadId":"24245","inReplyTo":"1278595295.2668.10.camel@wpalmer.simply-domain","subject":"Re: Why is \"git tag --contains\" so slow?","fromName":"","fromEmail":"tytso@mit.edu","sentAt":"2010-07-08T13:54:42Z","receivedAt":"2010-07-08T13:54:42Z","isPatch":false,"sender":{"key":"tytso@mit.edu","avatar":"https://avatars.githubusercontent.com/u/51416?v=4"},"body":"On Thu, Jul 08, 2010 at 02:21:35PM +0100, Will Palmer wrote:\n> I think these two go hand-in-hand, and would resolve most of my issues\n> with it. Auto-tune, starting pessimistically, but then using something\n> more-optimized after something like gc has detected that it's okay. On\n> pull from an older repository (which I see as happening very frequently,\n> I add remotes much more often than I do a straight \"clone\"), a warning\n> and an auto-tune to something which would account for the newly-fetched\n> bad data.\n\nWell, keep in mind that we've been using a one-day \"maximum clock skew\nor you start getting incorrect results\" for quite a while.  We just\nhaven't necessarily publicized this fact or added enforcement to \"git\ncommit\" and git-receive-pack.  And I've been introducing clock skews\nof about 3 months (roughly equal to the time between Linux stable\nreleases) into the Linux kernel repository for some 1-2 years (because\nI just didn't know about the clock skew dependency and there was no\nenforcement of the same), and the number of times people have noticed,\nor at least complained, has been relatively small.  So like it or not,\nthe default of \"one day clock skew or you get incorrect results\" is\nthe status quo.\n\nYour idea of being utterly pessimistic until the next \"git gc\" is\ninteresting, since it doesn't slow down the \"git clone step\".\nUnfortunately, it also means that commands like \"git name-rev\" will be\nseveral hundred times slower than they currently are (which probably\nmakes them unusable) until the first \"git gc\" --- this is the fact\nthat we've been depending on the clock skew being less than one day\nfor quite some time already; again, it _is_ the status quo.\n\nAnd, \"git gc\" takes quite a bit longer than scanning for the maximum\nskew after doing a \"git clone\".  Given that \"git clone\" generally\ntakes a good long time anyway, adding 1-3 seconds after a clone seems\nto be the better way to go.  I think the biggest issue with it is the\ncomplexity concern which Jeff has raised.\n\nGiven that, it would seem to me that (a) auto-tuning when cloning, (b)\ndefaulting to one-day and then auto-tuning on \"git gc\", or (c)\ndefaulting to one-day and not auto-tuning at all (the status quo) seem\nto be the three most reasonable, listed in order of my preference.\n\nAs far as enforcement is concerned, we have choices of (a) add\nwarnings, which later become hard errors if the skew is greater than\nsome configurable window, (b) scan for skews during commits and\nreceive-packs, and update the auto-tune based on the skews found, or\n(c) do nothing (the status quo).  (b) is the most user friendly, but\nit adds more complexity, which is why I think (a) edges it out as a\nbetter choice, but fortunately, I'm not the one who's paid the big\nbucks to make these sorts of decisions.  :-)\n\n> My only other objection is more wishy-washy and/or lazy: currently a\n> \"commit\" doesn't need to know anything at all about what it references\n> in order to be considered a valid object, but saying \"the time of commit\n> needs to be equal to or greater than the parent commit\" means that a\n> tool.. and by \"tool\" I mean \"wretched abuse of cat-file and sed\", which\n> is sometimes just faster to throw-together than filter-branch ..needs to\n> be more aware of what it's doing. Yes, it's a horrible abuse, but I was\n> always under the impression that low-level abuse of the system is\n> something which git supports, by virtue of having such a simple model.\n\nI don't know that it's that much more difficult.  See the patch I\nproposed for \"guilt\"; it was a ten line patch, and if you were willing\nto be even more \"quick and wretched\", I could have made it a 3 or 4\nline patch.\n\n\t\t\t\t\t\t- Ted\n"},{"id":"145130","messageId":"201007081635.25381.johan@herland.net","threadId":"24245","inReplyTo":"11D5771D-EB47-42E9-BCC3-69C8FE1999EC@MIT.EDU","subject":"Re: Why is \"git tag --contains\" so slow?","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2010-07-08T14:35:25Z","receivedAt":"2010-07-08T14:35:25Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"On Thursday 08 July 2010, Theodore Tso wrote:\n> On Jul 7, 2010, at 1:45 PM, Jeff King wrote:\n> >     And of course it's just complex, and I tend to shy away from\n> >     complexity when I can. The question to me comes back to (1)\n> > above. Is massive clock skew a breakage that should produce a few\n> > incorrect results, or is it something we should always handle?\n>\n> Going back to the question that kicked off this thread, I wonder if\n> there is some way that cacheing could be used to speed up the all\n> cases, or at lest the edge cases, without imposing as much latency as\n> tracking the max skew?   i.e., some thing like gitk's gitk.cache\n> file.  For bonus points, it could be a cache file that is used by\n> both gitk and git tag --contains, git branch --contains, and git\n> name-rev.\n>\n> Does that sound like reasonable idea?\n\nHere's a quick-and-dirty POC which builds a mapping from commits to \ntheir children and stores it using git notes [1], and then uses that to \nimplement 'git tag --contains <commit>' by traversing _forwards_ from \n<commit> and printing all tags we encounter along the way [2].\n\n\n[1]: The attached \"build_childnotes.py\" script builds this mapping. \nInvoke as follows:\n\n\tgit log --all --format=\"%H,%P\" |\n\t./build_childnotes.py |\n\tgit fast-import\n\n[2]: The attached \"git_tag_contains.py\" script traverses the notes \nprinting out tags along the way. Invoke it as follows:\n\n\tgit_tag_contains.py <commit>\n\nThe second script is way too slow, and really needs to use \"git \ncat-file --batch\" to not fork a process for every commit in history...\n\n\n...Johan\n\n-- \nJohan Herland, <johan@herland.net>\nwww.herland.net\n"},{"id":"145149","messageId":"alpine.LFD.2.00.1007081443040.6020@xanadu.home","threadId":"24245","inReplyTo":"11D5771D-EB47-42E9-BCC3-69C8FE1999EC@MIT.EDU","subject":"Re: Why is \"git tag --contains\" so slow?","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2010-07-08T19:06:34Z","receivedAt":"2010-07-08T19:06:34Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 8 Jul 2010, Theodore Tso wrote:\n\n> \n> On Jul 7, 2010, at 1:45 PM, Jeff King wrote:\n> \n> >     And of course it's just complex, and I tend to shy away from\n> >     complexity when I can. The question to me comes back to (1) above.\n> >     Is massive clock skew a breakage that should produce a few\n> >     incorrect results, or is it something we should always handle?\n> \n> Going back to the question that kicked off this thread, I wonder if there\n> is some way that cacheing could be used to speed up the all cases,\n> or at lest the edge cases, without imposing as much latency as tracking\n> the max skew?   i.e., some thing like gitk's gitk.cache file.  For bonus\n> points, it could be a cache file that is used by both gitk and git tag\n> --contains, git branch --contains, and git name-rev.\n> \n> Does that sound like reasonable idea?\n\nI don't think any caching would be as good as fixing the fundamental \nissue.\n\nGit is fast, sure.  But it could be way faster yet in its graph \ntraversal.  And my pack v4 format is meant to overcome all those \nobstacles that Git currently has to work through in order to walk its \ncommit graph.  Once one realize that most of the commit object headers \nare SHA1 reference which need no be compressed with zlib as it is done \nnow, and that the author and committer info can be factored out in a \ndictionary table, and that even those SHA1 references can be substituted \nwith an index value into the pack index file (a bit like the OFS variant \nof the delta object), meaning that even the object lookup could be \nbypassed, then it would be possible to make graph traversal a magnitude \ncheaper in terms of computing cycles and memory touched.\n\nThe pack format v4 has been brewing in my head for... well... years now.  \nAnd that is good because I've improved on the original v4 design even \nmore since then. And I even found some time to write more code lately.  \nI have the new object encoding code almost working for trees and \ncommits.  My Git hacking time is still limited so this is progressing \nslowly though.\n\nJust to say that I don't think any kind of caching might be necessary in \nthe end, as it is possible to encode object data in a pack in a way that \nought to be about as fast to access as a separate cache would.  So if \nsomeone is pondering about working on a cache layer, then I'd have one \nalternate suggestion or two for that person.  ;-)\n\n\nNicolas\n"},{"id":"145152","messageId":"alpine.LFD.2.00.1007081515030.6020@xanadu.home","threadId":"24245","inReplyTo":"m37hl6mdnb.fsf@localhost.localdomain","subject":"Re: Why is \"git tag --contains\" so slow?","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2010-07-08T19:29:49Z","receivedAt":"2010-07-08T19:29:49Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 8 Jul 2010, Jakub Narebski wrote:\n\n> Theodore Tso <tytso@MIT.EDU> writes:\n> > On Jul 7, 2010, at 1:45 PM, Jeff King wrote:\n> > \n> > >     And of course it's just complex, and I tend to shy away from\n> > >     complexity when I can. The question to me comes back to (1) above.\n> > >     Is massive clock skew a breakage that should produce a few\n> > >     incorrect results, or is it something we should always handle?\n> > \n> > Going back to the question that kicked off this thread, I wonder if there\n> > is some way that cacheing could be used to speed up the all cases,\n> > or at lest the edge cases, without imposing as much latency as tracking\n> > the max skew?   i.e., some thing like gitk's gitk.cache file.  For bonus\n> > points, it could be a cache file that is used by both gitk and git tag\n> > --contains, git branch --contains, and git name-rev.\n> > \n> > Does that sound like reasonable idea?\n> \n> By the way, what had happened to the rev-cache project from GSoC 2009?\n\nI think the person who worked on it did so in good faith, and that the \nresult is well done.\n\nBut I personally cannot convince myself this is fundamentally the right \nsolution to the issue.  Maintaining another data structure to work \naround defficiencies in the primary data structure doesn't sound right \nto me.\n\nI might be looking at this from my own perspective as one of the few \npeople who hacked extensively on the Git pack format from the very \nbeginning.  But I do see a way for the pack format to encode commit and \ntree objects so that walking them would be a simple lookup in the pack \nindex file where both the SHA1 and offset in the pack for each parent \ncan be immediately retrieved.  Same for tree references.  No deflating \nrequired, no binary search, just simple dereferences.  And the pack size \nwould even shrink as a side effect.\n\n\nNicolas\n"},{"id":"145155","messageId":"AANLkTikVNkObOxGQhDJ5Qau-vYn2YcomHQW2p2zsMof9@mail.gmail.com","threadId":"24245","inReplyTo":"alpine.LFD.2.00.1007081515030.6020@xanadu.home","subject":"Re: Why is \"git tag --contains\" so slow?","fromName":"Avery Pennarun","fromEmail":"apenwarr@gmail.com","sentAt":"2010-07-08T19:39:39Z","receivedAt":"2010-07-08T19:39:39Z","isPatch":false,"sender":{"key":"apenwarr@gmail.com","avatar":"https://avatars.githubusercontent.com/u/20592?v=4"},"body":"On Thu, Jul 8, 2010 at 3:29 PM, Nicolas Pitre <nico@fluxnic.net> wrote:\n> On Thu, 8 Jul 2010, Jakub Narebski wrote:\n>> By the way, what had happened to the rev-cache project from GSoC 2009?\n>\n> I think the person who worked on it did so in good faith, and that the\n> result is well done.\n>\n> But I personally cannot convince myself this is fundamentally the right\n> solution to the issue.  Maintaining another data structure to work\n> around defficiencies in the primary data structure doesn't sound right\n> to me.\n>\n> I might be looking at this from my own perspective as one of the few\n> people who hacked extensively on the Git pack format from the very\n> beginning.  But I do see a way for the pack format to encode commit and\n> tree objects so that walking them would be a simple lookup in the pack\n> index file where both the SHA1 and offset in the pack for each parent\n> can be immediately retrieved.  Same for tree references.  No deflating\n> required, no binary search, just simple dereferences.  And the pack size\n> would even shrink as a side effect.\n\nOne trick that bup uses is an additional file that sits alongside the\npack and acts as an index.  In bup's case, this is to work around\ndeficiencies in the .idx file format when using ridiculously huge\nnumbers of objects (hundreds of millions) across a large number of\npackfiles.  But the same concept could apply here: instead of doing\nsomething like rev-cache, you could just construct the \"efficient\"\npart of the packv4 format (which I gather is entirely related to\ncommit messages), and store it alongside each pack.\n\nThis would allow people to incrementally modify git to use the new,\nefficient commit object storage, without breaking backward\ncompatibility with earlier versions of git.  (Just as bup can index\nhuge numbers of packed objects but still stores them in the plain git\npack format.)\n\nJust a thought.  Thinking of it this way might make it easier to get\nover the inertia of an entirely new packfile format.\n\nHave fun,\n\nAvery\n"},{"id":"145161","messageId":"alpine.LFD.2.00.1007081559300.6020@xanadu.home","threadId":"24245","inReplyTo":"AANLkTikVNkObOxGQhDJ5Qau-vYn2YcomHQW2p2zsMof9@mail.gmail.com","subject":"Re: Why is \"git tag --contains\" so slow?","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2010-07-08T20:13:21Z","receivedAt":"2010-07-08T20:13:21Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 8 Jul 2010, Avery Pennarun wrote:\n\n> On Thu, Jul 8, 2010 at 3:29 PM, Nicolas Pitre <nico@fluxnic.net> wrote:\n> > I might be looking at this from my own perspective as one of the few\n> > people who hacked extensively on the Git pack format from the very\n> > beginning.  But I do see a way for the pack format to encode commit and\n> > tree objects so that walking them would be a simple lookup in the pack\n> > index file where both the SHA1 and offset in the pack for each parent\n> > can be immediately retrieved.  Same for tree references.  No deflating\n> > required, no binary search, just simple dereferences.  And the pack size\n> > would even shrink as a side effect.\n> \n> One trick that bup uses is an additional file that sits alongside the\n> pack and acts as an index.  In bup's case, this is to work around\n> deficiencies in the .idx file format when using ridiculously huge\n> numbers of objects (hundreds of millions) across a large number of\n> packfiles.  But the same concept could apply here: instead of doing\n> something like rev-cache, you could just construct the \"efficient\"\n> part of the packv4 format (which I gather is entirely related to\n> commit messages), and store it alongside each pack.\n\nNo.  I want the essential information in an efficient encoding _inside_ \nthe pack, actually replacing the existing encoding.  One of the goal is \nalso to reduce repository size, not to grow it.\n\n> This would allow people to incrementally modify git to use the new,\n> efficient commit object storage, without breaking backward\n> compatibility with earlier versions of git.  (Just as bup can index\n> huge numbers of packed objects but still stores them in the plain git\n> pack format.)\n\nInitially, what I'm aiming for is for pack-objects to produce the new \nformat, for index-pack to grok it, and for sha1_file:unpack_entry() to \nsimply regenerate the canonical object format whenever a pack v4 object \nis encountered.  Also pack-objects would be able to revert the object \nencoding to the current format on the fly when it is serving a fetch \nrequest to a client which is not pack v4 aware, just like we do now with \nthe ofs-delta capability.\n\nOnce that stage is reached, I'll submit the lot and hope that other \npeople will help incrementally converting part of Git to benefit from \nnative access to the pack v4 data.  The tree object walk code would be \nthe first obvious candidate.  And so on.\n\n\nNicolas\n"},{"id":"145164","messageId":"201007082320.05017.jnareb@gmail.com","threadId":"24245","inReplyTo":"alpine.LFD.2.00.1007081559300.6020@xanadu.home","subject":"Re: Why is \"git tag --contains\" so slow?","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2010-07-08T21:20:03Z","receivedAt":"2010-07-08T21:20:03Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Dnia czwartek 8. lipca 2010 22:13, Nicolas Pitre napisał:\n> On Thu, 8 Jul 2010, Avery Pennarun wrote:\n> > On Thu, Jul 8, 2010 at 3:29 PM, Nicolas Pitre <nico@fluxnic.net> wrote:\n\n> > > I might be looking at this from my own perspective as one of the few\n> > > people who hacked extensively on the Git pack format from the very\n> > > beginning.  But I do see a way for the pack format to encode commit and\n> > > tree objects so that walking them would be a simple lookup in the pack\n> > > index file where both the SHA1 and offset in the pack for each parent\n> > > can be immediately retrieved.  Same for tree references.  No deflating\n> > > required, no binary search, just simple dereferences.  And the pack size\n> > > would even shrink as a side effect.\n> > \n> > One trick that bup uses is an additional file that sits alongside the\n> > pack and acts as an index.  In bup's case, this is to work around\n> > deficiencies in the .idx file format when using ridiculously huge\n> > numbers of objects (hundreds of millions) across a large number of\n> > packfiles.  But the same concept could apply here: instead of doing\n> > something like rev-cache, you could just construct the \"efficient\"\n> > part of the packv4 format (which I gather is entirely related to\n> > commit messages), and store it alongside each pack.\n> \n> No.  I want the essential information in an efficient encoding _inside_ \n> the pack, actually replacing the existing encoding.  One of the goal is \n> also to reduce repository size, not to grow it.\n\nThat's a good idea.\n \n> > This would allow people to incrementally modify git to use the new,\n> > efficient commit object storage, without breaking backward\n> > compatibility with earlier versions of git.  (Just as bup can index\n> > huge numbers of packed objects but still stores them in the plain git\n> > pack format.)\n> \n> Initially, what I'm aiming for is for pack-objects to produce the new \n> format, for index-pack to grok it, and for sha1_file:unpack_entry() to \n> simply regenerate the canonical object format whenever a pack v4 object \n> is encountered.  Also pack-objects would be able to revert the object \n> encoding to the current format on the fly when it is serving a fetch \n> request to a client which is not pack v4 aware, just like we do now with \n> the ofs-delta capability.\n> \n> Once that stage is reached, I'll submit the lot and hope that other \n> people will help incrementally converting part of Git to benefit from \n> native access to the pack v4 data.  The tree object walk code would be \n> the first obvious candidate.  And so on.\n\nIf I remember correctly with pack v4 some operations like getting size\nof tree object needs encoding to current format, so they are slower than\nthey should be (and perhaps a bit slower than current implementation).\nBut that should be I think rare (well, unless one streams to \n'git cat-file --batch / --batch-check').\n\nWould pack v4 need index v4?\n\nBy the way, rev-cache project was started mainly to make \"counting\nobjects\" part of clone / fetch faster.  Would pack v4 offer the same\nwithout rev-cache?\n\n-- \nJakub Narebski\nPoland\n"},{"id":"145165","messageId":"AANLkTik3Cp8W5wrWhL7DW736QPt7-2V-E8EAWJB5JYd1@mail.gmail.com","threadId":"24245","inReplyTo":"201007082320.05017.jnareb@gmail.com","subject":"Re: Why is \"git tag --contains\" so slow?","fromName":"Sverre Rabbelier","fromEmail":"srabbelier@gmail.com","sentAt":"2010-07-08T21:30:57Z","receivedAt":"2010-07-08T21:30:57Z","isPatch":false,"sender":{"key":"srabbelier@gmail.com","avatar":"https://avatars.githubusercontent.com/u/3098?v=4"},"body":"Heya,\n\n2010/7/8 Jakub Narebski <jnareb@gmail.com>:\n> By the way, rev-cache project was started mainly to make \"counting\n> objects\" part of clone / fetch faster.  Would pack v4 offer the same\n> without rev-cache?\n\nSpeaking of pack v4 features...\n\nI remember from GitTogether08 that one hope was that the metadata\nwould be in a different file, such that it could be retrieved\nseparately (allowing shallow clones to create and push new commits).\nIs this not something that is part of the design goals for packv4?\n\n-- \nCheers,\n\nSverre Rabbelier\n"},{"id":"145169","messageId":"alpine.LFD.2.00.1007081909540.6020@xanadu.home","threadId":"24245","inReplyTo":"AANLkTik3Cp8W5wrWhL7DW736QPt7-2V-E8EAWJB5JYd1@mail.gmail.com","subject":"Re: Why is \"git tag --contains\" so slow?","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2010-07-08T23:10:39Z","receivedAt":"2010-07-08T23:10:39Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 8 Jul 2010, Sverre Rabbelier wrote:\n\n> Heya,\n> \n> 2010/7/8 Jakub Narebski <jnareb@gmail.com>:\n> > By the way, rev-cache project was started mainly to make \"counting\n> > objects\" part of clone / fetch faster.  Would pack v4 offer the same\n> > without rev-cache?\n> \n> Speaking of pack v4 features...\n> \n> I remember from GitTogether08 that one hope was that the metadata\n> would be in a different file, such that it could be retrieved\n> separately (allowing shallow clones to create and push new commits).\n> Is this not something that is part of the design goals for packv4?\n\nNo.  And I don't see why a pack format change would need to be involved \neither.\n\n\nNicolas\n"},{"id":"145170","messageId":"alpine.LFD.2.00.1007081910480.6020@xanadu.home","threadId":"24245","inReplyTo":"201007082320.05017.jnareb@gmail.com","subject":"Re: Why is \"git tag --contains\" so slow?","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2010-07-08T23:15:09Z","receivedAt":"2010-07-08T23:15:09Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 8 Jul 2010, Jakub Narebski wrote:\n\n> If I remember correctly with pack v4 some operations like getting size\n> of tree object needs encoding to current format, so they are slower than\n> they should be (and perhaps a bit slower than current implementation).\n> But that should be I think rare (well, unless one streams to \n> 'git cat-file --batch / --batch-check').\n\nI didn't write the code to recreate canonical object format yet, but I \nsuspect that the pack v4 object encoding will have to carry the size for \nthe canonical version.\n\n> Would pack v4 need index v4?\n\nSo far, no.\n\n> By the way, rev-cache project was started mainly to make \"counting\n> objects\" part of clone / fetch faster.  Would pack v4 offer the same\n> without rev-cache?\n\nThat's indeed the main goal.\n\n\nNicolas\n"},{"id":"153459","messageId":"20101013220753.GA8674@burratino","threadId":"24245","inReplyTo":"20100705123335.GA25699@sigill.intra.peff.net","subject":"Re: [RFC/PATCH 1/4] tag: speed up --contains calculation","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2010-10-13T22:07:53Z","receivedAt":"2010-10-13T22:07:53Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Hi,\n\nJeff King wrote:\n\n> When we want to know if commit A contains commit B (or any\n> one of a set of commits, B through Z),\n\nLet's revive this old thread.  Sorry for the long silence (the last\ntime this topic was visited was a couple months ago [1] afaict).\n\n> Instead, let's leverage the fact that we are going to use\n> the same --contains list for each tag, and mark areas of the\n> commit graph is definitely containing those commits, or\n> definitely not containing those commits. Later tags can then\n> stop traversing as soon as they see a previously calculated\n> answer.\n\nMakes sense.  And the resulting timings are exciting.\n\n> ---\n> Note that this is a depth first search, whereas we generally traverse in\n> a more breadth-first way. So it can actually make things slightly slower\n> than the current merge-base code, if:\n> \n>   1. You don't have any merge base calculations that involve going very\n>      far back in history.\n> \n>   2. We depth-first down the wrong side of a merge.\n> \n> However, in the usual cases, I think it will perform much better.\n\nNit: Wouldn't this (or a summary of it) belong in the log message, too,\nto avoid headscratching when a person tries to bisect a performance\nregression down the line?\n\n>   1. This can probably be a one-liner change to use in \"git branch\n>      --contains\", as well. I didn't measure it, as that already tends to\n>      be reasonably fast.\n\nThese days \"branch -r --contains\" has been _sloow_ for me.  So once\nthis is tuned, that wouldn't be a bad idea, methinks.\n\n>   2. It uses commit marks, which means it doesn't behave well with other\n>      traversals. I have no idea if I should be using alternate marks or\n>      not.\n\nThis is what Junio was referring to with \"the use of TMP_MARK smelled\nsomewhat bad to me\", right?\n\n>   3. We never clear the marks, or check them against the \"want\" list.\n\nThis too, I suppose.\n\n> So\n>      we just assume that repeated calls to contains will have the same\n>      \"want\" list.\n\nAs long as this is advertised, I think it is fine.  If someone needs\nto use --contains for multiple purposes in a builtin, that can be\ndealt with then (maybe with a separate function to reset the marks).\n\nMaybe it would make sense to keep this static in builtin/tag.c for\nnow, and defer cleaning up the interface to a separate patch.\n\n> --- a/commit.c\n> +++ b/commit.c\n\nNow the meat of the patch.  git has a few algorithms for checking if\none commit is an ancestor of another.\n\nis_descendant_of::\n\n\t1. find merge bases.  This is breadth-first search in\n\t   date order, but it walks through all ancestors as far\n\t   as I can tell.\n\t2. make them independent (seems pointless...).\n\t3. check if ancestor is one of them.\n\nget_revision after setting UNINTERESTING (i.e., rev-list -1 ^tag cmit)::\n\n\t1. find interesting and uninteresting commits.  This is\n\t   breadth-first search in date order.\n\t2. when the first interesting commit is found, emit it\n\t   and stop.\n\nNeither is optimized to check a batch of commits to find which contain\nthe commit of interest.\n\njoin_revs of show-branch::\n\n\t1. color the tag and cmit.\n\t2. let colors propagate back to all their ancestors, stopping\n\t   propagation along a given path when a commit has all colors.\n\t   This is breadth-first traversal in date order.\n\t3. for each commit with all colors, propagate that knowledge\n\t   to all parents we've encountered before.\n\t4. check what colors cmit has.\n\nlimit_to_ancestry::\n\n\t1. compute rev-list ^cmit tag in the usual way.\n\t2. reverse the revision list.\n\t3. color cmit with TMP_MARK and let that color permeate\n\t   up the backwards revision list.\n\t4. repeat! until no progress is made.\n\t4. check what color tag has.\n\nNone of these seem to tolerate timestamp skew. :(\n\nAm I understanding correctly?\n\nIf so, just making is_descendant_of less stupid (e.g., not traversing\nall history) would presumably help a lot.  Another approach would be\nto try the show-branch tactic repeatedly with small enough batches of\ntags to fit in the flag bitfield.  Yet another approach would be to\ntake the limit_to_ancestry one, but if the revision list is not\ntopologically sorted, it could be slow.\n\nHopefully your approach will be even better...\n\n> @@ -845,3 +845,45 @@ int commit_tree(const char *msg, unsigned char *tree,\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\nNice.  We cache the \"is wanted\" result using TMP_MARK and\nUNINTERESTING.  It cannot be slower than is_descendant_of if I\nunderstood correctly because the latter is a little crazy.\n\nPossible unprincipled approach:\n\n 1. Mark the wanted commits with TMP_MARK.\n 2. Perform a breadth-first, date-order search starting at\n    candidate to find a commit with TMP_MARK.\n    a. If not found, mark the commits involved as UNINTERESTING\n    b. If found, let the TMP_MARK permeate up using the\n       limit_to_ancestry algorithm.\n 3. Repeat with each other candidate.\n 4. (If needed) walk starting at each candidate to clear the\n    temporary flags.\n\nI am not sure if that would be any faster, though.  What do you think?\n\n[...]\n> +int contains(struct commit *, const struct commit_list *);\n\nThanks for a pleasant read.\n\n[1] http://thread.gmane.org/gmane.comp.version-control.git/152607/focus=152701\n"},{"id":"153469","messageId":"20101013225601.GC2558@localhost","threadId":"24245","inReplyTo":"20100705123335.GA25699@sigill.intra.peff.net","subject":"Re: [RFC/PATCH 1/4] tag: speed up --contains calculation","fromName":"Clemens Buchacher","fromEmail":"drizzd@aon.at","sentAt":"2010-10-13T22:56:01Z","receivedAt":"2010-10-13T22:56:01Z","isPatch":true,"sender":{"key":"drizzd@gmx.net","avatar":"https://avatars.githubusercontent.com/u/59082?v=4"},"body":"On Mon, Jul 05, 2010 at 08:33:36AM -0400, Jeff King wrote:\n> \n> This sped up \"git tag --contains HEAD~200\" in the linux-2.6\n> repository from:\n> \n>   real    0m15.417s\n>   user    0m15.197s\n>   sys     0m0.220s\n\nFWIW, in the staging tree they have a new tag for almost every day.\nMy linux repo currently has 677 tags. This same command would\nprobably take hours. I have not had the patience yet to let it\nfinish.\n\nWith your patch I get this.\n\n$ time git tag --contains HEAD~200\nv2.6.36-rc3\nv2.6.36-rc4\nv2.6.36-rc5\n\nreal\t0m8.047s\nuser\t0m7.755s\nsys\t0m0.268s\n\nClemens\n"},{"id":"153471","messageId":"20101013232153.GC11793@burratino","threadId":"24245","inReplyTo":"20100705123419.GB25699@sigill.intra.peff.net","subject":"Re: [RFC/PATCH 2/4] limit \"contains\" traversals based on commit timestamp","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2010-10-13T23:21:53Z","receivedAt":"2010-10-13T23:21:53Z","isPatch":true,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Jeff King wrote:\n\n> Name-rev already implements a similar optimization, using a\n> \"slop\" of one day to allow for a certain amount of clock\n> skew in commit timestamps. This patch introduces a\n> \"core.clockskew\" variable, which allows specifying the\n> allowable amount of clock skew in seconds.  For safety, it\n> defaults to \"none\", causing a full traversal (i.e., no\n> change in behavior from previous versions).\n\nTests?\n\nActually just a short example script to try would be helpful,\nif anyone has one handy (yes, I am terribly lazy).  Such a script\nwould be useful for figuring out which commands ought to be\nupdated to respect core_clock_skew.  rev-list is one.\n\n> --- a/commit.c\n> +++ b/commit.c\n[...]\n> @@ -872,9 +874,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\nNice idea.\n\n> @@ -885,5 +891,20 @@ 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\nWhy ignore these errors?  Will they be noticed later?\n\nThe rest of the patch looks good to me.  I am not thrilled with\nmaking the user figure out an acceptable \"[core] clockskew\" value\n(and am not sure it makes much sense as a tunable setting), but\nit is better than the status quo, so...\n"},{"id":"153530","messageId":"20101014185945.GA14634@burratino","threadId":"24245","inReplyTo":"20100705123923.GC21146@sigill.intra.peff.net","subject":"Re: Why is \"git tag --contains\" so slow?","fromName":"Jonathan Nieder","fromEmail":"jrnieder@gmail.com","sentAt":"2010-10-14T18:59:45Z","receivedAt":"2010-10-14T18:59:45Z","isPatch":false,"sender":{"key":"jrnieder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/281595?v=4"},"body":"Jeff King wrote:\n\n> This patch doesn't implement auto-detection of skew, but is the program\n> I used to calculate, and would provide the basis for such\n> auto-detection. It would be interesting to see average skew numbers for\n> popular repositories. You can run it as \"git skew --all\".\n\nFun.  The story this tells me is that most repositories would benefit\nmore from special-casing a few commits than from a \"[core] clockskew\"\nsetting.\n\nCaveat: the repos mentioned below are not canonical at all.  They are\njust some repos I happened to have around, some tracking multiple upstreams.\n\nproject # skewed        maximum skew    notes\n------- --------        ------------    -----\ngtk+    13              13 hrs          worst example seems to be tz related\n\nsystemd 3               1 hr            all three come from a single 65min\n                                        jump.  Same committer before+after.\n\ndpkg    2               76 days         automatic import from manually\n                                        written changelog\n\nglibc   2               31 months       (tag) commits imported to wrong\n                                        branches by \"git cvsimport\", I think\n\ngit     4               7 minutes       all four come from a single merge\n                                        commit, parents have same committer\n                                        as the merge.  probably clock drift\n                                        corrected with something like ntp.\n\nguilt   22              96 minutes      from the known (fixed) bug, I assume\n\nlinux-2.6 1226          99 days         probably the old guilt bug (e.g., in\n                                        ext4, blackfin trees)\n\nsed     0\n"},{"id":"153628","messageId":"20101016143226.GA20515@localhost","threadId":"24245","inReplyTo":"20101014185945.GA14634@burratino","subject":"Re: Why is \"git tag --contains\" so slow?","fromName":"Clemens Buchacher","fromEmail":"drizzd@aon.at","sentAt":"2010-10-16T14:32:26Z","receivedAt":"2010-10-16T14:32:26Z","isPatch":false,"sender":{"key":"drizzd@gmx.net","avatar":"https://avatars.githubusercontent.com/u/59082?v=4"},"body":"On Thu, Oct 14, 2010 at 01:59:45PM -0500, Jonathan Nieder wrote:\n> \n> project # skewed        maximum skew    notes\n> ------- --------        ------------    -----\n> gtk+    13              13 hrs          worst example seems to be tz related\n\nIt really is kind of fun.\n\nwine                    1       14 days\nmesa                    4930    150 days\n\nxf86-video-ati          13      ~2.5 hrs\nxf86-video-intel        26      8 hrs\nxf86-video-nouveau      12       10 hrs\n\nfluxbox                 0       0\nmetacity                0       0\nopenbox                 8       4 hrs\n\ngiggle                  2       21 min\nglibc                   2       931 days\n"},{"id":"154555","messageId":"20101027171145.GA6921@sigill.intra.peff.net","threadId":"24245","inReplyTo":"20101016143226.GA20515@localhost","subject":"Re: Why is \"git tag --contains\" so slow?","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2010-10-27T17:11:45Z","receivedAt":"2010-10-27T17:11:45Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Oct 16, 2010 at 04:32:26PM +0200, Clemens Buchacher wrote:\n\n> On Thu, Oct 14, 2010 at 01:59:45PM -0500, Jonathan Nieder wrote:\n> > \n> > project # skewed        maximum skew    notes\n> > ------- --------        ------------    -----\n> > gtk+    13              13 hrs          worst example seems to be tz related\n> \n> It really is kind of fun.\n> \n> wine                    1       14 days\n\nThanks both of you for the extra data points. If you don't mind, would\nyou consider running my updated git-skew below on your test cases (or\ntweaking your skew detectors, since you both seem to be getting a '#\nskewed' column that mine didn't output). Specifically, I am interested\nin long runs of skewed commits, since one potential solution would be to\njust accept a fixed number of slop commits (rather than accepting\ncommits within a certain slop time).\n\nFor the kernel the longest run looks to be about 80 commits. This should\nyield much better performance than handling the worst skew by time\n(which was 100 days, during which many more than 80 commits are usually\nused).\n\nPatch below. NB: thinking on this more, I think my program's results are\nslightly inaccurate. There are corner skew cases we can miss by the use\nof marking commits SEEN (i.e., skew you would see if you got to a commit\nby another path). However, the problem gets intractably large if you\ndon't mark commits (you end up traversing every possible path through\nthe graph).\n\n---\n .gitignore     |    1 +\n Makefile       |    1 +\n builtin.h      |    1 +\n builtin/skew.c |   62 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n git.c          |    1 +\n 5 files changed, 66 insertions(+), 0 deletions(-)\n create mode 100644 builtin/skew.c\n\ndiff --git a/.gitignore b/.gitignore\nindex 20560b8..d696c78 100644\n--- a/.gitignore\n+++ b/.gitignore\n@@ -132,6 +132,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 1f1ce04..25f94b0 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -739,6 +739,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 f2a25a0..e01ac4c 100644\n--- a/builtin.h\n+++ b/builtin.h\n@@ -140,5 +140,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..169a9f4\n--- /dev/null\n+++ b/builtin/skew.c\n@@ -0,0 +1,62 @@\n+#include \"cache.h\"\n+#include \"commit.h\"\n+#include \"diff.h\"\n+#include \"revision.h\"\n+\n+unsigned long worst_skew = 0;\n+unsigned char worst_skew_sha1[20];\n+unsigned long worst_run = 0;\n+unsigned char worst_run_sha1[20];\n+\n+static void check_skew_recurse(struct commit *c, unsigned long when, int counter)\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\t\thashcpy(worst_skew_sha1, c->object.sha1);\n+\t\t}\n+\t\tif (++counter > worst_run) {\n+\t\t\tworst_run = counter;\n+\t\t\thashcpy(worst_run_sha1, c->object.sha1);\n+\t\t}\n+\t}\n+\telse\n+\t\tcounter = 0;\n+\n+\tfor (p = c->parents; p; p = p->next)\n+\t\tcheck_skew_recurse(p->item, c->date < when ? c->date : when, counter);\n+}\n+\n+static void check_skew(struct commit *c)\n+{\n+\tcheck_skew_recurse(c, time(NULL), 0);\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(\"worst skew: %lu (%s)\\n\", worst_skew, sha1_to_hex(worst_skew_sha1));\n+\tprintf(\"longest run: %lu (%s)\\n\", worst_run, sha1_to_hex(worst_run_sha1));\n+\treturn 0;\n+}\ndiff --git a/git.c b/git.c\nindex 0409ac9..1041858 100644\n--- a/git.c\n+++ b/git.c\n@@ -405,6 +405,7 @@ static void handle_internal_command(int argc, const char **argv)\n \t\t{ \"verify-pack\", cmd_verify_pack },\n \t\t{ \"show-ref\", cmd_show_ref, RUN_SETUP },\n \t\t{ \"pack-refs\", cmd_pack_refs, 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.3.2.216.g61ab7.dirty\n"},{"id":"154616","messageId":"20101028080739.GA3953@localhost","threadId":"24245","inReplyTo":"20101027171145.GA6921@sigill.intra.peff.net","subject":"Re: Why is \"git tag --contains\" so slow?","fromName":"Clemens Buchacher","fromEmail":"drizzd@aon.at","sentAt":"2010-10-28T08:07:39Z","receivedAt":"2010-10-28T08:07:39Z","isPatch":false,"sender":{"key":"drizzd@gmx.net","avatar":"https://avatars.githubusercontent.com/u/59082?v=4"},"body":"Hi Jeff,\n\nOn Wed, Oct 27, 2010 at 10:11:45AM -0700, Jeff King wrote:\n> \n> Thanks both of you for the extra data points. If you don't mind, would\n> you consider running my updated git-skew below on your test cases (or\n> tweaking your skew detectors, since you both seem to be getting a '#\n> skewed' column that mine didn't output).\n\nI think this works well for small skews and for positive skews,\ni.e., if the date goes back to the future. But if the date goes\ninto the past, that time is used as the new reference, and all\nsubsequently traversed commits are considered skewed. So for\nexample, if I add the following commit to git.git's current master,\nthe longest run becomes 1092 commits.\n\n$ GIT_COMMITTER_DATE=$(date -d \"now-1 year\") git commit --allow-empty -m add-skew\n\nTo solve this, we could keep track of a window of the last n\ncommits traversed and take as a new time reference the largest date\nwithin that window which is smaller than the previous reference.\nThat way we would fail to detect skew only if all of the commits in\nthat window are skewed into the past or into the future.\n\nThis particular scenario does not seem to occur in any of the repos\nI tested, except maybe for the mesa repo. But manual inspection\nshows that that repo has very long runs of skewed commits anyways.\n\nlinux                           99 days         80\nwine                    1       14 days         1\nmesa                    4930    150 days        1520\n                                                                                \nxf86-video-ati          13      ~2.5 hrs        4\nxf86-video-intel        26      8 hrs           4\nxf86-video-nouveau      12       10 hrs         9\n                                                                                \nfluxbox                 0       0               0\nmetacity                0       0               0\nopenbox                 8       4 hrs           4                               \n                                                                                \ngiggle                  2       21 min          2                               \nglibc                   2       931 days        1\n\nClemens\n"},{"id":"162029","messageId":"AANLkTinL-gN3sCkUzzsBbzwxo1AYx1NURjKaE8D4TgvU@mail.gmail.com","threadId":"24245","inReplyTo":"20100705123335.GA25699@sigill.intra.peff.net","subject":"Re: [RFC/PATCH 1/4] tag: speed up --contains calculation","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2011-02-23T15:51:02Z","receivedAt":"2011-02-23T15:51:02Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"On Mon, Jul 5, 2010 at 14:33, Jeff King <peff@peff.net> wrote:\n> When we want to know if commit A contains commit B (or any\n> one of a set of commits, B through Z), we generally\n> calculate 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\n> property).\n\nOn a work repo with around 10k tags after and before this patch:\n\n    $ time ~/g/git/git tag --contains HEAD~200 | wc -l\n    113\n\n    real    0m0.421s\n    user    0m0.380s\n    sys     0m0.042s\n\n    $ time git tag --contains HEAD~200 | wc -l\n    113\n\n    real    2m18.861s\n    user    2m18.750s\n    sys     0m0.092s\n\nI'd love to have this merged downwards from pu. It's the single\nbiggest usability improvement in my Git workflow for as long as I can\nremember.\n"},{"id":"162031","messageId":"20110223163938.GB10042@sigill.intra.peff.net","threadId":"24245","inReplyTo":"AANLkTinL-gN3sCkUzzsBbzwxo1AYx1NURjKaE8D4TgvU@mail.gmail.com","subject":"Re: [RFC/PATCH 1/4] tag: speed up --contains calculation","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2011-02-23T16:39:38Z","receivedAt":"2011-02-23T16:39:38Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Feb 23, 2011 at 04:51:02PM +0100, Ævar Arnfjörð Bjarmason wrote:\n\n> On Mon, Jul 5, 2010 at 14:33, Jeff King <peff@peff.net> wrote:\n> > When we want to know if commit A contains commit B (or any\n> > one of a set of commits, B through Z), we generally\n> > calculate 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\n> > property).\n> \n> On a work repo with around 10k tags after and before this patch:\n> [...much speed improvement...]\n> I'd love to have this merged downwards from pu. It's the single\n> biggest usability improvement in my Git workflow for as long as I can\n> remember.\n\nYeah, I have been meaning to revisit the topic. I got sidetracked by\nlooking at clock skew issues, and there was some debate over whether the\nstrict depth-first traversal was the best way to do it (although if you\ntrust the commit timestamps, I think you stop going down dead-ends\npretty quickly in practice; and I think we do implicitly trust the\ncommit timestamps in the regular merge base traversals). If we can do a\nmulti-headed merge base, that would be better, but I'll have to think on\nit.\n\nI'll try to take a look this week and see what I can come up with.\n\n-Peff\n"}]}