{"thread":{"id":"31330","subject":"in_merge_bases() is too expensive for recent \"pu\" update","startedAt":"2012-08-23T12:32:33Z","lastAt":"2012-08-28T16:03:09Z","messageCount":16,"participants":["Nguyen Thai Ngoc Duy","Thomas Rast","Junio C Hamano","Jeff King"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"197712","messageId":"CACsJy8C-VxzwigyUDHnUkXN7vhB+93X96pH9MvgB0ps7v-_NmQ@mail.gmail.com","threadId":"31330","inReplyTo":null,"subject":"in_merge_bases() is too expensive for recent \"pu\" update","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-08-23T12:32:33Z","receivedAt":"2012-08-23T12:32:33Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"I just did a \"git fetch\". It took 19 seconds (measured with\ngettimeofday) to finish in_merge_bases() in update_local_ref() in\nfetch.c, just to print this line\n\n + a4f2db3...b95a282 pu -> origin/pu (forced update)\n\nIt's partly my fault because I'm on gcc -O0. But should it not take\nthat much time for one line? As a grumpy user, I'd be perfectly ok\nwith git saying \"probably forced update, check it yourself\" if the\nspent time exceeds half a second. On the same token, if diffstat takes\ntoo long for git-pull, then perhaps just stop and print \"do it\nyourself\".\n-- \nDuy\n"},{"id":"197713","messageId":"878vd5k7uu.fsf@thomas.inf.ethz.ch","threadId":"31330","inReplyTo":"CACsJy8C-VxzwigyUDHnUkXN7vhB+93X96pH9MvgB0ps7v-_NmQ@mail.gmail.com","subject":"Re: in_merge_bases() is too expensive for recent \"pu\" update","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2012-08-23T14:20:41Z","receivedAt":"2012-08-23T14:20:41Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Nguyen Thai Ngoc Duy writes:\n\n> I just did a \"git fetch\". It took 19 seconds (measured with\n> gettimeofday) to finish in_merge_bases() in update_local_ref() in\n> fetch.c, just to print this line\n>\n> + a4f2db3...b95a282 pu -> origin/pu (forced update)\n>\n> It's partly my fault because I'm on gcc -O0. But should it not take\n> that much time for one line? As a grumpy user, I'd be perfectly ok\n> with git saying \"probably forced update, check it yourself\" if the\n> spent time exceeds half a second. On the same token, if diffstat takes\n> too long for git-pull, then perhaps just stop and print \"do it\n> yourself\".\n\nI missed out on the a4f2db3 update, so I can't test exactly this, but my\nreflog tells the I had before b95a282 was d3dd556. Computing all\nmerge-bases takes very long indeed:\n\n $ time git merge-base --all d3dd556 b95a282 | wc -l\n 51\n\n real 0m4.877s\n user 0m4.829s\n sys 0m0.026s\n\nAnd I think the reason is that the algorithm is just doing too much.\nFrom a quick glance, it appears to first compute the result list rslt[]\nof merge bases, then for each pair attempts to eliminate one of them by\ndetermining that rslt[i] or rslt[j] is also a merge base of rslt[j:].\nIt is thus spending quadratic time in the number of merge-bases, times\nthe size of history (ok, I can't actually come up with an example that\ndoes the latter).\n\nAt the very least it should be possible to change in_merge_bases() to\nnot do any of the post-filtering; perhaps like the patch below. It\npasses the test suite. The whole \"merge bases of A and a list of Bs\"\nthing is blowing my overheated mind, though, so I'm not able to convince\nmyself that it is correct in all cases.\n\nEven if this turns out to be flawed, we should also identify uses of\nin_merge_bases() where the real question was is_descendant_of() [I\nsomewhat suspect that's all of them], and then replace is_descendant_of\nwith a much cheaper lookup. This can be as simple as propagating a mark\nfrom the candidate until it either goes beyond all possible ancestors,\nor hits one of them.\n\nBy the way, the internal slowness of git-merge-base also affects the\nA...B syntax. For example,\n\n git rev-list --left-right --count @{upstream}...\n\nis used by the __git_ps1 code to determine the prompt display, which\njust got very slow for me today. Again, it should be easy to figure out\nthe boundary of the symmetric difference simply by propagating two\nmarks. I do not think that the result of A...B actually depends on\nfiguring out exactly what the merge bases are, simply excluding *any*\ncandidate without pruning is enough.\n\n\ndiff --git i/commit.c w/commit.c\nindex 65a8485..70427ab 100644\n--- i/commit.c\n+++ w/commit.c\n@@ -837,10 +837,13 @@ int in_merge_bases(struct commit *commit, struct commit **reference, int num)\n \tstruct commit_list *bases, *b;\n \tint ret = 0;\n \n-\tif (num == 1)\n-\t\tbases = get_merge_bases(commit, *reference, 1);\n-\telse\n+\tif (num != 1)\n \t\tdie(\"not yet\");\n+\n+\tbases = merge_bases_many(commit, 1, reference);\n+\tclear_commit_marks(commit, all_flags);\n+\tclear_commit_marks(*reference, all_flags);\n+\t\n \tfor (b = bases; b; b = b->next) {\n \t\tif (!hashcmp(commit->object.sha1, b->item->object.sha1)) {\n \t\t\tret = 1;\n\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"197727","messageId":"7vd32h4h1t.fsf@alter.siamese.dyndns.org","threadId":"31330","inReplyTo":"878vd5k7uu.fsf@thomas.inf.ethz.ch","subject":"Re: in_merge_bases() is too expensive for recent \"pu\" update","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-23T18:08:46Z","receivedAt":"2012-08-23T18:08:46Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast writes:\n\n> At the very least it should be possible to change in_merge_bases() to\n> not do any of the post-filtering; perhaps like the patch below.\n\nI do not recall the details but the post-filtering was added after\nthe initial naive version without it that was posted to the list did\nnot work correctly in corner cases. I wouldn't doubt that N*(N-1)\nloop can be optimized to something with log(N), but I offhand find\nit hard to believe \"to not do any\" could be correct without seeing\nmore detailed analysis.\n"},{"id":"197733","messageId":"7v393d49xs.fsf@alter.siamese.dyndns.org","threadId":"31330","inReplyTo":"7vd32h4h1t.fsf@alter.siamese.dyndns.org","subject":"Re: in_merge_bases() is too expensive for recent \"pu\" update","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-23T20:42:23Z","receivedAt":"2012-08-23T20:42:23Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> Thomas Rast writes:\n>\n>> At the very least it should be possible to change in_merge_bases() to\n>> not do any of the post-filtering; perhaps like the patch below.\n>\n> I do not recall the details but the post-filtering was added after\n> the initial naive version without it that was posted to the list did\n> not work correctly in corner cases. I wouldn't doubt that N*(N-1)\n> loop can be optimized to something with log(N), but I offhand find\n> it hard to believe \"to not do any\" could be correct without seeing\n> more detailed analysis.\n\nIf \"one on one side, many on the other side\" in merge_bases_many()\nconfuses any of you in the readers, you can just ignore many-ness.\nGetting merge bases for \"one\" against many \"two\"s using\nmerge_bases_many() is exactly the same as getting merge bases for\n\"one\" against a (fictitious) single commit you can make by merging\nall \"two\"s.\n\nSo we can think about the degenerate case of merge base between two\ncommits A and B in the following discussion.\n\nA merge-base between A and B is defined to be a commit that is a\ncommon ancestor of both A and B, and that is not an ancestor of any\nother merge-base between A and B. In the simplest case (illustrated\nbelow), 1 is a merge base between A and B, but 2 is not (even though\nit is an ancestor of both A and B, it is an ancestor of 1 which is a\nmerge base).\n\n y---A\n /\n ---2---o---1---x---B\n\nSo, the thinking goes, in order to find all merge bases, first we\ncan traverse from A and B, following \"parent\" link from children,\nand painting found parents in two colors.\n\nStart from A and B. Follow from B to find 'x' and paint it in blue,\nfollow from A to find 'y' and paint it in amber. Follow from 'x' to\n'1', paint it in blue. Follow from 'y' to '1', paint it in amber\nbut notice that it already is painted in blue. Stop the traversal\nthere and we found a candidate '1' that could be a merge base. We\nknow digging from '1' will not find more merge bases, so we should\nstop there (I do not recall offhand if the current code does stop\nthere, though) [*1*].\n\nThere may be other paths that are not depicted in the above\nillustration that reach '2' from A and B without passing '1'\nthrough.\n\n o-------o\n / \\\n / y---A\n / /\n ---2---z---1---x---B\n \\ /\n o-------o\n\nIn such a history, we may stop after finding '1' and '2' in the\nfirst pass of \"stop when a node is painted in both amber and blue\".\nThis way, the first pass will find _all_ merge bases, but it also\nmay find common ancestors that are not merge bases.\n\nSo we need to notice that '1' and '2' have ancestry relation in\norder to reject '2' as \"common but not merge-base\". One way of\ndoing so is not to stop at '1' and keep digging (and eventually we\nfind that '2' is what we could reach from '1' that already is a\nmerge base), but then we will be susceptible to the same kind of\nclock skew issue as the revision traverser. Instead, merge-base\ntraverser chose to do this by running the same \"stop traversing at\ncommon\" traverser between the candidates (in this case, '1' and\n'2').\n\nThe objective of this second traversal is very different from the\nfirst one, though. We do not need _all_ the merge bases between '1'\nand '2'; we do not even need merge bases.\n\nThe only thing we need to prove that '1' is a merge base (i.e. not\nan ancestor of any other merge base candidates the first round of\ntraversal between A and B found) is to do the first round of the\ntraversal for '1' as \"one\" and all the other ('2' in this case) as\n\"two\"s; if the first round of such traversal finishes without\npainting '1' in both colors, that would mean '1' is not reachable\nfrom any other candidates of merge base between A and B, so we have\nproven that '1' is a merge base.\n\nSo I suspect that the postprocess phase could be made from N*(N-1)\nto N (run merge_bases_many() once for each of the common ancestor\nthe first round found). You might also be able to stop the\ntraversal used in the first phase (i.e. get_merge_bases()) a bit\nearlier, if we are digging through '1' to paint 'z' (and eventually\n'2') in STALE (amber+blue) color, as digging further only to paint\nthings in STALE color is not necessary with the postprocess.\n\n\n[Footnote]\n\n*1* Digging through '2' down may find that other candidate merge\nbases we reach by traversing other paths that may not be depicted in\nthe above illustration, and there may be such paths to reach '1'\nfrom A and B that does not pass '2' through. That is a possible\nalternative way to reject common ancestor that is not merge-base.\n"},{"id":"197735","messageId":"7vy5l52ueg.fsf@alter.siamese.dyndns.org","threadId":"31330","inReplyTo":"7v393d49xs.fsf@alter.siamese.dyndns.org","subject":"Re: in_merge_bases() is too expensive for recent \"pu\" update","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-23T21:03:19Z","receivedAt":"2012-08-23T21:03:19Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> The objective of this second traversal is very different from the\n> first one, though. We do not need _all_ the merge bases between '1'\n> and '2'; we do not even need merge bases.\n>\n> The only thing we need to prove that '1' is a merge base (i.e. not\n> an ancestor of any other merge base candidates the first round of\n> traversal between A and B found) is to do the first round of the\n> traversal for '1' as \"one\" and all the other ('2' in this case) as\n> \"two\"s; if the first round of such traversal finishes without\n> painting '1' in both colors, that would mean '1' is not reachable\n> from any other candidates of merge base between A and B, so we have\n> proven that '1' is a merge base.\n>\n> So I suspect that the postprocess phase could be made from N*(N-1)\n> to N (run merge_bases_many() once for each of the common ancestor\n> the first round found). You might also be able to stop the\n> traversal used in the first phase (i.e. get_merge_bases()) a bit\n> earlier, if we are digging through '1' to paint 'z' (and eventually\n> '2') in STALE (amber+blue) color, as digging further only to paint\n> things in STALE color is not necessary with the postprocess.\n\nAs a corollary, the \"is pu@{0} a fast-forward of pu@{1}?\" check does\nnot need merge base computation at all. The only thing it needs to\ndo is to prove pu@{1} is reachable from pu@{0}, and that can be done\nthe same way in which '1' can be proved unreachable from '2' in the\npost processing phase as described above, i.e. it needs only the\nfirst phase of running merge_bases_many() without postprocessing.\n"},{"id":"197757","messageId":"87sjbceiu9.fsf@thomas.inf.ethz.ch","threadId":"31330","inReplyTo":"7vy5l52ueg.fsf@alter.siamese.dyndns.org","subject":"Re: in_merge_bases() is too expensive for recent \"pu\" update","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2012-08-24T09:32:14Z","receivedAt":"2012-08-24T09:32:14Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Junio C Hamano writes:\n\n> As a corollary, the \"is pu@{0} a fast-forward of pu@{1}?\" check does\n> not need merge base computation at all. The only thing it needs to\n> do is to prove pu@{1} is reachable from pu@{0}, and that can be done\n> the same way in which '1' can be proved unreachable from '2' in the\n> post processing phase as described above, i.e. it needs only the\n> first phase of running merge_bases_many() without postprocessing.\n\nWell, yeah, you snipped this part from my original post :-)\n\n} Even if this turns out to be flawed, we should also identify uses of\n} in_merge_bases() where the real question was is_descendant_of() [I\n} somewhat suspect that's all of them], and then replace is_descendant_of\n} with a much cheaper lookup. This can be as simple as propagating a mark\n} from the candidate until it either goes beyond all possible ancestors,\n} or hits one of them.\n\nAs far as the \"real question\" goes, I'm purely guessing here -- it is\nentirely possible that a bunch of the in_merge_bases() checks really do\nneed the pruned set of merge bases. But this particular check, and I\nsuspect a bunch of others, does not.\n\nThen there's the next bit:\n\n} By the way, the internal slowness of git-merge-base also affects the\n} A...B syntax. For example,\n} \n} git rev-list --left-right --count @{upstream}...\n} \n} is used by the __git_ps1 code to determine the prompt display, which\n} just got very slow for me today. Again, it should be easy to figure out\n} the boundary of the symmetric difference simply by propagating two\n} marks. I do not think that the result of A...B actually depends on\n} figuring out exactly what the merge bases are, simply excluding *any*\n} candidate without pruning is enough.\n\nApart from __git_ps1, this is also used by git-status, git-checkout and\n'git branch -v' to show \"your branch is N behind and M ahead\". Again\nit's a bit of a hunch, but I think figuring out the symmetric difference\nis a simple matter of propagating two marks and including only commits\nthat ended up having exactly one of them. At least the counting case\nshould be easy, rev-list is slightly harder to fix.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"197758","messageId":"87393cbp6b.fsf@thomas.inf.ethz.ch","threadId":"31330","inReplyTo":"7v393d49xs.fsf@alter.siamese.dyndns.org","subject":"Re: in_merge_bases() is too expensive for recent \"pu\" update","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2012-08-24T09:43:40Z","receivedAt":"2012-08-24T09:43:40Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Junio C Hamano writes:\n\n> Junio C Hamano writes:\n>\n>> Thomas Rast writes:\n>>\n>>> At the very least it should be possible to change in_merge_bases() to\n>>> not do any of the post-filtering; perhaps like the patch below.\n>>\n>> I do not recall the details but the post-filtering was added after\n>> the initial naive version without it that was posted to the list did\n>> not work correctly in corner cases. I wouldn't doubt that N*(N-1)\n>> loop can be optimized to something with log(N), but I offhand find\n>> it hard to believe \"to not do any\" could be correct without seeing\n>> more detailed analysis.\n>\n> If \"one on one side, many on the other side\" in merge_bases_many()\n> confuses any of you in the readers, you can just ignore many-ness.\n> Getting merge bases for \"one\" against many \"two\"s using\n> merge_bases_many() is exactly the same as getting merge bases for\n> \"one\" against a (fictitious) single commit you can make by merging\n> all \"two\"s.\n>\n> So we can think about the degenerate case of merge base between two\n> commits A and B in the following discussion.\n>\n> A merge-base between A and B is defined to be a commit that is a\n> common ancestor of both A and B, and that is not an ancestor of any\n> other merge-base between A and B.\n\nOk, under that definition I really do think that it's \"easy\".\n\nYou have all the pieces here but one:\n\n> Start from A and B. Follow from B to find 'x' and paint it in blue,\n> follow from A to find 'y' and paint it in amber. Follow from 'x' to\n> '1', paint it in blue. Follow from 'y' to '1', paint it in amber\n> but notice that it already is painted in blue.\n[...]\n> o-------o\n> / \\\n> / y---A\n> / /\n> ---2---z---1---x---B\n> \\ /\n> o-------o\n[...]\n> So we need to notice that '1' and '2' have ancestry relation in\n> order to reject '2' as \"common but not merge-base\". One way of\n> doing so is not to stop at '1' and keep digging (and eventually we\n> find that '2' is what we could reach from '1' that already is a\n> merge base), but then we will be susceptible to the same kind of\n> clock skew issue as the revision traverser.\n\nI think that is *the* way to do it.\n\nAnd the way to fix the clock skew issue (also in the revision traversal)\nis Peff's generation number cache. Just keep propagating marks, digging\nin generation order, until the generations prove that nothing new can\nhappen.\n\n [Side note, in reply to an earlier comment in the rev-list thread: I\n agree with Peff's reasoning that a cache is better than a commit\n header.]\n\nThe precise termination condition should be:\n\n There are no more one-colored commits to walk, and\n\n The maximum generation of the remaining commits in the walk is less\n than the minimum generation of the merge base candidates\n\nThen the generation numbers ensure that no commit in the walk (which by\nthen only propagates STALE marks) can possibly be a descendant of any of\nthe candidates. At that point, the candidates are the true set of merge\nbases.\n\n\nI conjecture that every history walking problem can be solved in time\nlinear in the number of commits once we properly use the generation\nnumbers ;-)\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"197767","messageId":"CACsJy8DJLmNWDNhGczk_0qDngHxDgQMh7zskxJXTqLGQ8gwugw@mail.gmail.com","threadId":"31330","inReplyTo":"878vd5k7uu.fsf@thomas.inf.ethz.ch","subject":"Re: in_merge_bases() is too expensive for recent \"pu\" update","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-08-24T11:42:19Z","receivedAt":"2012-08-24T11:42:19Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Thu, Aug 23, 2012 at 9:20 PM, Thomas Rast wrote:\n> At the very least it should be possible to change in_merge_bases() to\n> not do any of the post-filtering; perhaps like the patch below. It\n> passes the test suite. The whole \"merge bases of A and a list of Bs\"\n> thing is blowing my overheated mind, though, so I'm not able to convince\n> myself that it is correct in all cases.\n>\n> diff --git i/commit.c w/commit.c\n> index 65a8485..70427ab 100644\n> --- i/commit.c\n> +++ w/commit.c\n> @@ -837,10 +837,13 @@ int in_merge_bases(struct commit *commit, struct commit **reference, int num)\n> struct commit_list *bases, *b;\n> int ret = 0;\n>\n> - if (num == 1)\n> - bases = get_merge_bases(commit, *reference, 1);\n> - else\n> + if (num != 1)\n> die(\"not yet\");\n> +\n> + bases = merge_bases_many(commit, 1, reference);\n> + clear_commit_marks(commit, all_flags);\n> + clear_commit_marks(*reference, all_flags);\n> +\n> for (b = bases; b; b = b->next) {\n> if (!hashcmp(commit->object.sha1, b->item->object.sha1)) {\n> ret = 1;\n\nWithout looking into detail (as I'm not familiar with this code), this\npatch does not help much. Without the patch:\n\n$ time ./git merge-base a4f2db3 b95a282\ned36e5bd41f7192e42e9b4c573875a343a9daf48\n\nreal 0m19.988s\nuser 0m19.797s\nsys 0m0.082s\n\nWith the patch:\n\n$ time ./git merge-base a4f2db3 b95a282\ned36e5bd41f7192e42e9b4c573875a343a9daf48\n\nreal 0m19.560s\nuser 0m19.448s\nsys 0m0.037s\n-- \nDuy\n"},{"id":"197768","messageId":"CACsJy8Ap-T-5KPK1HdGVM3Eyr7LqgsLuc7jvXLZJrtsmiRUSFw@mail.gmail.com","threadId":"31330","inReplyTo":"CACsJy8DJLmNWDNhGczk_0qDngHxDgQMh7zskxJXTqLGQ8gwugw@mail.gmail.com","subject":"Re: in_merge_bases() is too expensive for recent \"pu\" update","fromName":"Nguyen Thai Ngoc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2012-08-24T11:51:21Z","receivedAt":"2012-08-24T11:51:21Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Fri, Aug 24, 2012 at 6:42 PM, Nguyen Thai Ngoc Duy wrote:\n> Without looking into detail (as I'm not familiar with this code), this\n> patch does not help much.\n\nAnd I should have looked. git merge-base does not use that function.\nWith your patch, git fetch is instant again for same 'pu' update.\n-- \nDuy\n"},{"id":"197776","messageId":"20120824151511.GB15162@sigill.intra.peff.net","threadId":"31330","inReplyTo":"87393cbp6b.fsf@thomas.inf.ethz.ch","subject":"Re: in_merge_bases() is too expensive for recent \"pu\" update","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-08-24T15:15:11Z","receivedAt":"2012-08-24T15:15:11Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Aug 24, 2012 at 11:43:40AM +0200, Thomas Rast wrote:\n\n> > Start from A and B. Follow from B to find 'x' and paint it in blue,\n> > follow from A to find 'y' and paint it in amber. Follow from 'x' to\n> > '1', paint it in blue. Follow from 'y' to '1', paint it in amber\n> > but notice that it already is painted in blue.\n> [...]\n> > o-------o\n> > / \\\n> > / y---A\n> > / /\n> > ---2---z---1---x---B\n> > \\ /\n> > o-------o\n> [...]\n> > So we need to notice that '1' and '2' have ancestry relation in\n> > order to reject '2' as \"common but not merge-base\". One way of\n> > doing so is not to stop at '1' and keep digging (and eventually we\n> > find that '2' is what we could reach from '1' that already is a\n> > merge base), but then we will be susceptible to the same kind of\n> > clock skew issue as the revision traverser.\n> \n> I think that is *the* way to do it.\n> \n> And the way to fix the clock skew issue (also in the revision traversal)\n> is Peff's generation number cache. Just keep propagating marks, digging\n> in generation order, until the generations prove that nothing new can\n> happen.\n\nI thought you were just interested in speeding up is_descendent_of. You\nshould be able to do that without a generation number. Just start from A\nand B as above, do the two-color painting, and do not add the parents of\nany two-color commits (because you know they are ancestors of both, and\ntherefore you cannot find either by looking backwards). If you paint \"B\"\namber, then it is a descendent of \"A\" (and vice versa if you paint \"A\"\nblue).\n\nClock skew may make you take longer (because you may go depth-first down\nan uninteresting chain of commits), but it should never give you the\nwrong answer. It's not as fast as using a generation-based cutoff\n(because you have to keep walking to the actual shared ancestor), but in\npractice it's usually fine.\n\nThe reason I did not do that for \"tag --contains\" is that I wanted to\ndo a simultaneous walk for all tags. That would require N color bits for\nN tags, and we have a limited space in each commit object. I didn't time\nusing a separate hash table to store those bits outside of the commit\nobjects. That would have a higher constant, but should still yield good\nbig-O complexity.\n\n> [Side note, in reply to an earlier comment in the rev-list thread: I\n> agree with Peff's reasoning that a cache is better than a commit\n> header.]\n\nI still think it's a good idea to keep it out of the commit header. But\nI think I might lean towards tying it to the pack index (i.e.,\ngenerating it when we generate the index, and depending on the sha1\ntable in the index). That would be smaller, and gets rid of any\ncomplexity or performance issues with making incremental updates to the\ncache. Loose objects wouldn't have a cached version number, but that's\nOK; in practice you can quickly walk backwards to a commit that _is_\ncached.\n\n-Peff\n"},{"id":"197777","messageId":"7v62882srk.fsf@alter.siamese.dyndns.org","threadId":"31330","inReplyTo":"87sjbceiu9.fsf@thomas.inf.ethz.ch","subject":"Re: in_merge_bases() is too expensive for recent \"pu\" update","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-24T15:50:55Z","receivedAt":"2012-08-24T15:50:55Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast writes:\n\n> Well, yeah, you snipped this part from my original post :-)\n>\n> } Even if this turns out to be flawed, we should also identify uses of\n> } in_merge_bases() where the real question was is_descendant_of() [I\n> } somewhat suspect that's all of them], and then replace is_descendant_of\n> } with a much cheaper lookup. This can be as simple as propagating a mark\n> } from the candidate until it either goes beyond all possible ancestors,\n> } or hits one of them.\n\nYeah, I agree with the above, and the \"cheaper lookup\" would\nprobably be merge-bases-many() without postprocess.\n"},{"id":"197778","messageId":"7v1uiw2spo.fsf@alter.siamese.dyndns.org","threadId":"31330","inReplyTo":"87393cbp6b.fsf@thomas.inf.ethz.ch","subject":"Re: in_merge_bases() is too expensive for recent \"pu\" update","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-24T15:52:03Z","receivedAt":"2012-08-24T15:52:03Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast writes:\n\n> Junio C Hamano writes:\n> ...\n>> Start from A and B. Follow from B to find 'x' and paint it in blue,\n>> follow from A to find 'y' and paint it in amber. Follow from 'x' to\n>> '1', paint it in blue. Follow from 'y' to '1', paint it in amber\n>> but notice that it already is painted in blue.\n> [...]\n>> o-------o\n>> / \\\n>> / y---A\n>> / /\n>> ---2---z---1---x---B\n>> \\ /\n>> o-------o\n> [...]\n>> So we need to notice that '1' and '2' have ancestry relation in\n>> order to reject '2' as \"common but not merge-base\". One way of\n>> doing so is not to stop at '1' and keep digging (and eventually we\n>> find that '2' is what we could reach from '1' that already is a\n>> merge base), but then we will be susceptible to the same kind of\n>> clock skew issue as the revision traverser.\n>\n> I think that is *the* way to do it.\n\nBut we do not live in *that* world. At least not yet.\n\n> I conjecture that every history walking problem can be solved in time\n> linear in the number of commits once we properly use the generation\n> numbers ;-)\n\nI would conjecture that too, but we do not live in that world yet.\n"},{"id":"197781","messageId":"7vobm01d1f.fsf@alter.siamese.dyndns.org","threadId":"31330","inReplyTo":"20120824151511.GB15162@sigill.intra.peff.net","subject":"Re: in_merge_bases() is too expensive for recent \"pu\" update","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-24T16:15:56Z","receivedAt":"2012-08-24T16:15:56Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> I thought you were just interested in speeding up is_descendent_of. You\n> should be able to do that without a generation number. Just start from A\n> and B as above, do the two-color painting, and do not add the parents of\n> any two-color commits (because you know they are ancestors of both, and\n> therefore you cannot find either by looking backwards). If you paint \"B\"\n> amber, then it is a descendent of \"A\" (and vice versa if you paint \"A\"\n> blue).\n\nYes, that is what merge_bases_many() (the one without the post\nprocessing to cull candidates) is primarily doing. The function\nalso does the \"STALE\" bit processing that aims to reduce the number\nof candidates in \"no clock skew\" cases with minimum effort, to\nmimimize the cost of get_merge_bases_many() in the post-processing\nphase, but removing the \"STALE\" bit processing shouldn't affect the\ncorrectness of get_merge_bases_many() and would help performance of\nmerge_bases_many() proper, which is useful for is_descendant_of().\n\n> The reason I did not do that for \"tag --contains\" is that I wanted to\n> do a simultaneous walk for all tags. That would require N color bits for\n> N tags, and we have a limited space in each commit object. I didn't time\n> using a separate hash table to store those bits outside of the commit\n> objects. That would have a higher constant, but should still yield good\n> big-O complexity.\n\nIt may not be a bad idea to at least try and see the performance\nimplications of moving many users of object->flags to a new\nimplementation of per-purpose flag bits based on the decoration\ninfrastracture.\n"},{"id":"197958","messageId":"7va9xfpyyf.fsf@alter.siamese.dyndns.org","threadId":"31330","inReplyTo":"878vd5k7uu.fsf@thomas.inf.ethz.ch","subject":"Re: in_merge_bases() is too expensive for recent \"pu\" update","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-28T01:50:00Z","receivedAt":"2012-08-28T01:50:00Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast writes:\n\n> diff --git i/commit.c w/commit.c\n> index 65a8485..70427ab 100644\n> --- i/commit.c\n> +++ w/commit.c\n> @@ -837,10 +837,13 @@ int in_merge_bases(struct commit *commit, struct commit **reference, int num)\n> \tstruct commit_list *bases, *b;\n> \tint ret = 0;\n> \n> -\tif (num == 1)\n> -\t\tbases = get_merge_bases(commit, *reference, 1);\n> -\telse\n> +\tif (num != 1)\n> \t\tdie(\"not yet\");\n> +\n> +\tbases = merge_bases_many(commit, 1, reference);\n> +\tclear_commit_marks(commit, all_flags);\n> +\tclear_commit_marks(*reference, all_flags);\n> +\t\n> \tfor (b = bases; b; b = b->next) {\n> \t\tif (!hashcmp(commit->object.sha1, b->item->object.sha1)) {\n> \t\t\tret = 1;\n\nThis ended up being part of the series I sent earlier, and I want to\nassign authorship to you. As you did this as part of the discussion,\nnaturally the patch came without a sign-off. Can we consider it\nsigned off? Just saying \"ok\" is fine.\n\nThanks.\n"},{"id":"197962","messageId":"877gsjmo3a.fsf@thomas.inf.ethz.ch","threadId":"31330","inReplyTo":"7va9xfpyyf.fsf@alter.siamese.dyndns.org","subject":"Re: in_merge_bases() is too expensive for recent \"pu\" update","fromName":"Thomas Rast","fromEmail":"trast@inf.ethz.ch","sentAt":"2012-08-28T08:12:57Z","receivedAt":"2012-08-28T08:12:57Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Junio C Hamano writes:\n\n> Thomas Rast writes:\n>\n>> diff --git i/commit.c w/commit.c\n>> index 65a8485..70427ab 100644\n>> --- i/commit.c\n>> +++ w/commit.c\n>> @@ -837,10 +837,13 @@ int in_merge_bases(struct commit *commit, struct commit **reference, int num)\n>> \tstruct commit_list *bases, *b;\n>> \tint ret = 0;\n>> \n>> -\tif (num == 1)\n>> -\t\tbases = get_merge_bases(commit, *reference, 1);\n>> -\telse\n>> +\tif (num != 1)\n>> \t\tdie(\"not yet\");\n>> +\n>> +\tbases = merge_bases_many(commit, 1, reference);\n>> +\tclear_commit_marks(commit, all_flags);\n>> +\tclear_commit_marks(*reference, all_flags);\n>> +\t\n>> \tfor (b = bases; b; b = b->next) {\n>> \t\tif (!hashcmp(commit->object.sha1, b->item->object.sha1)) {\n>> \t\t\tret = 1;\n>\n> This ended up being part of the series I sent earlier, and I want to\n> assign authorship to you. As you did this as part of the discussion,\n> naturally the patch came without a sign-off. Can we consider it\n> signed off? Just saying \"ok\" is fine.\n\nSure:\n\n ok\n\n;-)\n\nI'm also mildly surprised that it ended up being correct, albeit with\nsome extra work from you :-)\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"197991","messageId":"7vehmr57ia.fsf@alter.siamese.dyndns.org","threadId":"31330","inReplyTo":"877gsjmo3a.fsf@thomas.inf.ethz.ch","subject":"Re: in_merge_bases() is too expensive for recent \"pu\" update","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-08-28T16:03:09Z","receivedAt":"2012-08-28T16:03:09Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast writes:\n\n> I'm also mildly surprised that it ended up being correct, albeit with\n> some extra work from you :-)\n\nI actually am not all that surprised. It just shows that the\noriginal code was layered in more or less the right way. At the the\nbottom layer we would want a way to paint graph down to common\nancestors cheaply, and then on top we want to have a way to filter\nout the redundant ones. It is a different story that the\nimplementation of individual layers may still have rooms for\nimprovements (just like the last patch in my series showed for the\nupper layer where we used to do N * (N-1) when we only needed N).\n\nI have a suspicion that the merge_bases_many() at the bottom layer\ncould be built on an even cheaper API. This caller you added does\nnot need \"bases\" list returned; it only wants to see that ancestors\nof \"commit\" and \"reference\" down to their common ancestors are\npainted in two colors PARENT1 and PARENT2. Instead of iterating\nover the returned candidate list, we might be able to do\n\n\tcommon = PARENT1 | PARENT2;\n\tpaint_ancestors(commit, 1, reference);\n commit_is_common = ((commit->object.flags & common) == common);\n clear_commit_marks(commit, all_flags);\n clear_commit_marks(*reference, all_flags);\n\nwhere paint_ancestors() just paints but does not accumlate to return\na commit_list. Note that paint_ancestors() need to always paint its\narguments (merge_bases_many() has an early special case to return a\nlist that only has \"commit\" when it appears in \"reference\" without\npainting anything, and the callers like get_merge_bases_many() know\nthis to avoid calling clear_commit_marks()) if we are to go in this\ndirection, so it is unclear if it will be overall gain.\n"}]}