{"thread":{"id":"35660","subject":"Consistency question","startedAt":"2014-01-15T10:37:08Z","lastAt":"2014-01-18T01:22:22Z","messageCount":8,"participants":["David Kastrup","Jeff King","Andreas Krey","Mike Hommey"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"233140","messageId":"8761pl8raj.fsf@fencepost.gnu.org","threadId":"35660","inReplyTo":null,"subject":"Consistency question","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-01-15T10:37:08Z","receivedAt":"2014-01-15T10:37:08Z","isPatch":false,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"\nHi,\n\nI am in the process of rewriting the core logic of git blame (the\ncurrent speed of which is quite an impediment to some workflows).\nI currently have one question I don't see an answer to right away, and\nthat question arises in doing a reasonably robust traversal of commits\nwithout determining topology first:\n\nThe question is what guarantees I have with regard to the commit date of\na commit in relation to that of its parent commits:\n\na) none\nb) commitdate(child) >= commitdate(parent)\nc) commitdate(child) > commitdate(parent)\n\nObviously, I can rely on c) being true \"almost always\": it's definitely\ngood for a heuristic used for improving performance (meaning as an\nordering criterion for a commit priority queue).  The problem is how\nmuch I should cater for graceful behavior for the cases where it's not.\n\nDoes git do any actual checks before pushing?\n\n-- \nDavid Kastrup\n"},{"id":"233144","messageId":"20140115111330.GH14335@sigill.intra.peff.net","threadId":"35660","inReplyTo":"8761pl8raj.fsf@fencepost.gnu.org","subject":"Re: Consistency question","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-01-15T11:13:30Z","receivedAt":"2014-01-15T11:13:30Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jan 15, 2014 at 11:37:08AM +0100, David Kastrup wrote:\n\n> The question is what guarantees I have with regard to the commit date of\n> a commit in relation to that of its parent commits:\n> \n> a) none\n> b) commitdate(child) >= commitdate(parent)\n> c) commitdate(child) > commitdate(parent)\n\na) none\n\n> Obviously, I can rely on c) being true \"almost always\":\n\nActually, b) is quite often the case in automated processes (e.g., \"git\nam\" or \"git rebase\"). The author dates are different, but the committer\ndates may be in the same second.\n\nAnd of course a) is the result of clock skew and software bugs.\n\n> it's definitely\n> good for a heuristic used for improving performance (meaning as an\n> ordering criterion for a commit priority queue).  The problem is how\n> much I should cater for graceful behavior for the cases where it's not.\n\nYes, this is exactly how git uses it. We generally walk breadth-first\nthrough the graph, relying on commit times for performance but not\ncorrectness.\n\nThere are some parts of the code that will behave badly with clock skew.\nFor example, \"--since\" will stop traversing when we hit a certain point.\nIt requires a fixed number of \"too old\" commits before quitting, though,\nin an attempt to bypass small runs of skewed clocks.\n\nThe \"git describe --contains\" algorithm will also produce wrong results\nin the face of skew. I believe it uses a \"slop\" of 24 hours in its skew.\n\nThe current \"tag --contains\" algorithm is currently correct in the face\nof skew, but it can go much faster if you accept that skew will cause it\nto go wrong. I suspect there are other algorithms that could be sped up,\ntoo, if we had trustworthy generation numbers (I implemented and timed\nthe \"--contains\" algorithm, but haven't done so for other algorithms).\n\nI've played with calculating and caching the generation numbers at\nrepack time, but there aren't any patches currently under consideration.\n\n> Does git do any actual checks before pushing?\n\nNo. One problem with checking the commit relationships is that it may\nnot be the new commit which is broken (by skewing backwards), but rather\nthe commit it builds on (which has skewed forwards). If you are building\non such a fast-forward commit, it is often to late to fix that commit.\nSo you have to fast-forward yourself, propagating the bogus value.\n\nIf the receiving machine checked the incoming commits against its own\ninternal clock, that could work. You would still want to check the\ncommit relationships to catch new commits that erroneously claim to be\nfrom the past, though (that is, before their parents).\n\n-Peff\n"},{"id":"233155","messageId":"871u098ocy.fsf@fencepost.gnu.org","threadId":"35660","inReplyTo":"20140115111330.GH14335@sigill.intra.peff.net","subject":"Re: Consistency question","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-01-15T11:40:29Z","receivedAt":"2014-01-15T11:40:29Z","isPatch":false,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> On Wed, Jan 15, 2014 at 11:37:08AM +0100, David Kastrup wrote:\n>\n>> The question is what guarantees I have with regard to the commit date of\n>> a commit in relation to that of its parent commits:\n>> \n>> a) none\n>> b) commitdate(child) >= commitdate(parent)\n>> c) commitdate(child) > commitdate(parent)\n>\n> a) none\n>\n>> Obviously, I can rely on c) being true \"almost always\":\n>\n> Actually, b) is quite often the case in automated processes (e.g., \"git\n> am\" or \"git rebase\"). The author dates are different, but the committer\n> dates may be in the same second.\n\nOk, thanks.  Assuming that rebases don't happen 1000/s, I should likely\nnot worry too much about O(n^2) for this case (and frankly, clearly\nnobody worried about O(n^2) in the current blame.c anyway).  It's also\nnot really relevant for linear parts of the history like that of \"git\nrebase\" since in that case the parent enters my priority queue when its\nchild is getting processed: nothing to be confused about here.  This is\nmore about sibling rivalries calling a parent to the queue before the\nsibling had a chance to leave.  So it comes into play for my use case\nbasically only when dealing with merge commits.\n\n> I suspect there are other algorithms that could be sped up, too, if we\n> had trustworthy generation numbers (I implemented and timed the\n> \"--contains\" algorithm, but haven't done so for other algorithms).\n\nWith a single root, \"depth\" helps a lot.  When looking for a common\nparent of a number of commits, you first shorten all ancestries to the\nsame size and then you can look for the point of convergence in\nlockstep.\n\nBut didn't git forego the \"single root\" requirement in its commit DAG at\nsome point of time?\n\nThanks for the speedy reply!  I think I'm good with what I need to know\nto go ahead.  The rest is just idle curiosity.\n\n-- \nDavid Kastrup\n"},{"id":"233156","messageId":"87wqi17949.fsf@fencepost.gnu.org","threadId":"35660","inReplyTo":"20140115111330.GH14335@sigill.intra.peff.net","subject":"Re: Consistency question","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-01-15T11:55:02Z","receivedAt":"2014-01-15T11:55:02Z","isPatch":false,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> There are some parts of the code that will behave badly with clock skew.\n> For example, \"--since\" will stop traversing when we hit a certain point.\n> It requires a fixed number of \"too old\" commits before quitting, though,\n> in an attempt to bypass small runs of skewed clocks.\n\nThat actually turns out to be a somewhat sore point for me: I use\nsomething like\n\ngit shortlog -n --since 2013/12/01 --until 2014/01/01 master\n\nfor generating statistics on LilyPond when I am doing my monthly report\nbegging the community for money.\n\nIt turns out that the numbers of commits attributed to me tend to go\n_down_ quite regularly in the time from starting the report to sending\nit out.  Which might also cause me to overlook a particularly\nselfpraiseworthy item.\n\nNot sure how feasible it would be to arrive at a stable and\ncomplementary set of --since/--until.\n\n-- \nDavid Kastrup\n"},{"id":"233157","messageId":"20140115124434.GA27030@inner.h.apk.li","threadId":"35660","inReplyTo":"871u098ocy.fsf@fencepost.gnu.org","subject":"Re: Consistency question","fromName":"Andreas Krey","fromEmail":"a.krey@gmx.de","sentAt":"2014-01-15T12:44:34Z","receivedAt":"2014-01-15T12:44:34Z","isPatch":false,"sender":{"key":"a.krey@gmx.de","avatar":"https://avatars.githubusercontent.com/u/37810?v=4"},"body":"On Wed, 15 Jan 2014 12:40:29 +0000, David Kastrup wrote:\n...\n> With a single root, \"depth\" helps a lot.  When looking for a common\n> parent of a number of commits, you first shorten all ancestries to the\n> same size and then you can look for the point of convergence in\n> lockstep.\n\nHmm, how about traversing from all the start commits downwards\nsimultaneously, noting which start you say each commit from, and stopping\nwhen you have a commit carrying all start labels?\n\nI don't quite see how the same size plus lockstep works out (but the\n'same size' part is possibly the same as my 'concurrent traversal').\n\n> But didn't git forego the \"single root\" requirement in its commit DAG at\n> some point of time?\n\nAbout at the beginning, I guess. Nothing in the data model ever required it?\n\n> ... The rest is just idle curiosity.\n\nMe too, mostly. I may have to do some traversal for tree/dag painting.\n\nAndreas\n\n-- \n\"Totally trivial. Famous last words.\"\nFrom: Linus Torvalds <torvalds@*.org>\nDate: Fri, 22 Jan 2010 07:29:21 -0800\n"},{"id":"233159","messageId":"87ppnt7635.fsf@fencepost.gnu.org","threadId":"35660","inReplyTo":"20140115124434.GA27030@inner.h.apk.li","subject":"Re: Consistency question","fromName":"David Kastrup","fromEmail":"dak@gnu.org","sentAt":"2014-01-15T13:00:30Z","receivedAt":"2014-01-15T13:00:30Z","isPatch":false,"sender":{"key":"dak@gnu.org","avatar":"https://avatars.githubusercontent.com/u/52141349?v=4"},"body":"Andreas Krey <a.krey@gmx.de> writes:\n\n> On Wed, 15 Jan 2014 12:40:29 +0000, David Kastrup wrote:\n> ...\n>> With a single root, \"depth\" helps a lot.  When looking for a common\n>> parent of a number of commits, you first shorten all ancestries to the\n>> same size and then you can look for the point of convergence in\n>> lockstep.\n>\n> Hmm, how about traversing from all the start commits downwards\n> simultaneously, noting which start you say each commit from, and stopping\n> when you have a commit carrying all start labels?\n\nIt means that when the start commits are at considerably different\ndepth, you'll traverse much more material than necessary.\n\nAlso you need labels.\n\n> I don't quite see how the same size plus lockstep works out (but the\n> 'same size' part is possibly the same as my 'concurrent traversal').\n\nIt just equalizes the depth before starting, so you don't need labels:\nany common ancestor is reached at the same time by its descendants.\n\nOf course, I conveniently forgot merge commits.  This scheme works out\nof the box only with single parenting.  And it works fine without a\ncommon ancestor, too: you just run into a NULL pointer at the same time\nwhen there isn't one.\n\nSo, uh, this solution does not really seem to match the problem...\n\n-- \nDavid Kastrup\n"},{"id":"233161","messageId":"20140115134508.GE7102@inner.h.apk.li","threadId":"35660","inReplyTo":"87ppnt7635.fsf@fencepost.gnu.org","subject":"Re: Consistency question","fromName":"Andreas Krey","fromEmail":"a.krey@gmx.de","sentAt":"2014-01-15T13:45:08Z","receivedAt":"2014-01-15T13:45:08Z","isPatch":false,"sender":{"key":"a.krey@gmx.de","avatar":"https://avatars.githubusercontent.com/u/37810?v=4"},"body":"On Wed, 15 Jan 2014 14:00:30 +0000, David Kastrup wrote:\n> Andreas Krey <a.krey@gmx.de> writes:\n...\n> > Hmm, how about traversing from all the start commits downwards\n> > simultaneously, noting which start you say each commit from, and stopping\n> > when you have a commit carrying all start labels?\n> \n> It means that when the start commits are at considerably different\n> depth, you'll traverse much more material than necessary.\n\nBut it has the advantage that you don't need to traverse the DAG\nto the root when the differences are small - the runtimes are roughly\nproportional to the difference between the commits.\n\n> Also you need labels.\n\nYes, I assume that that (marking commits) is not a cost factor.\n\n> > I don't quite see how the same size plus lockstep works out (but the\n> > 'same size' part is possibly the same as my 'concurrent traversal').\n> \n> It just equalizes the depth before starting, so you don't need labels:\n> any common ancestor is reached at the same time by its descendants.\n> \n> Of course, I conveniently forgot merge commits.\n\nI finally noticed but forgot to mention in the last post.\n\nMerges also mean that there is not necessarily a unique common\nancestor between commits.\n\nAndreas\n\n-- \n\"Totally trivial. Famous last words.\"\nFrom: Linus Torvalds <torvalds@*.org>\nDate: Fri, 22 Jan 2010 07:29:21 -0800\n"},{"id":"233332","messageId":"20140118012222.GA4381@glandium.org","threadId":"35660","inReplyTo":"20140115111330.GH14335@sigill.intra.peff.net","subject":"Re: Consistency question","fromName":"Mike Hommey","fromEmail":"mh@glandium.org","sentAt":"2014-01-18T01:22:22Z","receivedAt":"2014-01-18T01:22:22Z","isPatch":false,"sender":{"key":"mh@glandium.org","avatar":"https://avatars.githubusercontent.com/u/1038527?v=4"},"body":"On Wed, Jan 15, 2014 at 06:13:30AM -0500, Jeff King wrote:\n> On Wed, Jan 15, 2014 at 11:37:08AM +0100, David Kastrup wrote:\n> \n> > The question is what guarantees I have with regard to the commit date of\n> > a commit in relation to that of its parent commits:\n> > \n> > a) none\n> > b) commitdate(child) >= commitdate(parent)\n> > c) commitdate(child) > commitdate(parent)\n> \n> a) none\n> \n> > Obviously, I can rely on c) being true \"almost always\":\n> \n> Actually, b) is quite often the case in automated processes (e.g., \"git\n> am\" or \"git rebase\"). The author dates are different, but the committer\n> dates may be in the same second.\n> \n> And of course a) is the result of clock skew and software bugs.\n\n... or importing non-git repositories that don't have commit info\nseparated from author info like git does. In such cases, it's usual to\nduplicate the author info as commit info so that clones of the same\nnon-git repo end up with the same git sha1s. Mercurial easily allows\nauthor dates to be in a non topological order.\n\nMike\n"}]}