{"thread":{"id":"36903","subject":"Our merge bases sometimes suck","startedAt":"2014-06-12T22:12:15Z","lastAt":"2014-06-23T11:43:12Z","messageCount":12,"participants":["Michael Haggerty","Michael J Gruber","Jakub Narębski","Junio C Hamano","Nico Williams"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"244040","messageId":"539A25BF.4060501@alum.mit.edu","threadId":"36903","inReplyTo":null,"subject":"Our merge bases sometimes suck","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2014-06-12T22:12:15Z","receivedAt":"2014-06-12T22:12:15Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"I've been thinking a lot about merge bases lately and think I have\ndiscovered something interesting.\n\ntl;dr:\n\nWhen two branches have multiple merge bases,\n\n    git merge-base $master $branch\n\npicks one merge base more or less arbitrarily.  Here I describe a\ncriterion for picking a \"best\" merge base.  When the best merge base\nis used, the diff output by\n\n    git diff $master...$branch\n\nbecomes shorter and simpler--sometimes dramatically so.  I have\nquantified the improvement by analyzing historical merges from the Git\nproject (see attached image).  Best merge bases might also help reduce\nconflicts when conducting merges.\n\n\nBackground\n==========\n\nA merge base of two or more branches is a common ancestor of those\nbranches that has no descendant that is also a common ancestor (see\n`git-merge-base(1)`).  Merge bases are important when merging\nbranches, and are also used internally to some other commands like\n\"git diff $master...$branch\".\n\nSometimes branches have multiple merge bases, such as in the case of a\ncriss-cross merge:\n\n    o--A--o--o--X--o--Y--o--Z    <- master\n        \\        \\   /\n         \\        \\ /\n          \\        ·\n           \\      / \\\n            \\    /   \\\n             B--C--D--E--F       <- branch\n\nHere, commits X and C are both merge bases for branches master and\nbranch.  You can list all merge bases by running\n\n    git merge-base --all $master $branch\n\nBut if you run\n\n    git merge-base $master $branch\n\nonly one merge base is returned.  *Which* one it returns is not\ndocumented and appears to be pretty arbitrary (probably a side effect\nof the traversal order?)\n\n\nThe \"best\" merge base\n=====================\n\nBut not all merge bases are created equal.  It is possible to define a\n\"best\" merge base that has some nice properties.\n\nLet's focus on the command\n\n    git diff $master...$branch\n\nwhich is equivalent to\n\n    git diff $(git merge-base $master $branch)..$branch\n\nWe want such a diff to have two properties:\n\n1. It must include *all* changes that have been made on the branch but\n   are not yet contained in master.\n\n2. It should contain *as few* changes as possible that are already in\n   master.\n\nThe first property is satisfied automatically if the left end of the\n\"diff\" range is any merge base.  Because a merge base is an ancestor\nof master, it cannot possibly include any changes that were made on\nthe branch but have not yet been merged to master [1].\n\nThe second property requires as a *necessary* condition that the left\nend of the diff is a merge base.  But the property also helps us pick\nthe best among multiple merge bases.  We just need to make the idea of\n\"contains as few changes as possible\" more precise.\n\nI propose that the best merge base is the merge base \"candidate\" that\nminimizes the number of non-merge commits that are in\n\n    git rev-list --no-merges $candidate..$branch\n\nbut are already in master:\n\n    git rev-list --no-merges $master\n\nSince a non-merge commit should embody a single logical change,\ncounting non-merge commits is in some sense counting changes [2].\n\nWe can put this criterion in simpler form.  Because every candidate is\na merge-base,\n\n    git rev-list --no-merges $candidate..$branch\n\nnecessarily includes *all* of the non-merge commits that are on branch\nbut not on master.  This is a fixed number of commits, the same for\nevery candidate.  It *additionally* includes the commits that are on\nmaster but not yet in branch.  This second number varies from one\ncandidate to another.  So if we minimize the number of commits in this\noutput, is is the same as minimizing the number of unwanted commits.\nTherefore, to get the best merge base, all we have to do is pick the\nmerge base that minimizes\n\n    git rev-list --count --no-merges $candidate..$branch\n\nThere can be ties, but in practice they are rare enough that it is\nprobably not worth worrying about them.\n\n\nSymmetry; generalization to more than two branches\n==================================================\n\nInterestingly, minimizing the last criterion is the same as maximizing\n\n    git rev-list --count --no-merges $candidate\n\nbecause there is a fixed number of commits in\n\n    git rev-list --no-merges $branch\n\n, and each of those commits is in exactly one of the two counts above.\nThis formulation shows that the best merge base for computing\n\n    git diff $master...$branch\n\nis also the best merge base for computing\n\n    git diff $branch...$master\n\n; i.e., the best merge base is symmetric in its arguments.  It also\nshows that the concept of \"best merge base\" can trivially be\ngeneralized to more than two branches.\n\n\ngit-best-merge-base script\n===========================\n\nThe best merge base can be computed, for example, using the following\nscript:\n\n    #! /bin/sh\n    # Usage: git-best-merge-base MASTER BRANCH\n\n    set -e\n\n    master=\"$1\"\n    branch=\"$2\"\n\n    count() {\n        git rev-list --no-merges --count \"$1..$branch\"\n    }\n\n    # Note that if $master and $branch have no common ancestors, `git\n    # merge-base` fails with retcode=1, causing the script to exit\n    # with the same error code.\n    merge_bases=$(git merge-base --all \"$master\" \"$branch\")\n\n    case \"${#merge_bases}\" in\n    40)\n        # One merge base -> use it.\n        echo $merge_bases\n        ;;\n    *)\n        # Multiple merge bases -> pick the one for which $base..$branch\n        # has the fewest commits that are already in $master.  To ensure\n        # that the result is repeatable, if there is a tie we choose the\n        # merge base that comes first when sorted by SHA-1:\n        for merge_base in $merge_bases\n        do\n            echo $(count $merge_base) $merge_base\n        done | sort -k1,1n -k2 | sed -ne '1s/^.* //p'\n        ;;\n    esac\n\n\nDo best merge bases really help?\n================================\n\nI analyzed all of the 2-parent merges made in the history of the Git\nproject.  (I limited the analysis to 2-parent merges just for\nsimplicity.)  I computed the size of the asymmetric diffs\n\n    git diff $commit^1...$commit^2\n\nusing the current code and using git-best-merge-base, with the\nfollowing script:\n\n    #! /bin/sh\n\n    old_diff_len() {\n        git diff $1...$2 | wc -l\n    }\n\n    new_diff_len() {\n        git diff $(git-best-merge-base $1 $2)..$2 | wc -l\n    }\n\n    git rev-list --min-parents=2 --max-parents=2 --parents \"$@\" |\n    while read commit p1 p2\n    do\n        echo \"$commit $(git merge-base --all $p1 $p2 | wc -l)\n$(old_diff_len $p1 $p2) $(new_diff_len $p1 $p2)\"\n    done\n\n\nResults:\n\n* Total number of merges: 8263\n\n* Total number of merges with exactly two parents: 8229\n\n  Of which:\n\n  * Number with zero merge bases: 6 (0.07%)\n\n  * Number with one merge base: 7823 (95.1%)\n\n  * Number with multiple merge bases: 400 (4.8%)\n\n    Of which:\n\n    * Number whose diffs shrink: 71 (17.8%)\n\n    * Number whose diffs remain the same length: 323 (80.1%)\n\n    * Number whose diffs grow: 6 (1.5%)\n\nI have attached a graph plotting the diff sizes against each other on\na log-log scale.  The points *under* the red line are diffs that have\nshrunk; the points *over* the red line are the diffs that have grown.\nAs you can see, far more diffs shrank than grew, and by larger\nfactors.  Some of the diffs have shrunk dramatically.  In the most\ndrastic case, the diff shrank from 466602 lines to 81 lines.\n\nA relatively small fraction of all merges are affected, but of merges\nthat have multiple merge bases (which are the most difficult merges to\nhandle), more than one in six would be simplified.\n\nI should mention that I have done a similar analysis of a large\ncommercial software project's history, with broadly similar results.\n\nI wouldn't be surprised if selecting merge bases more intelligently in\n\"git merge\" also helps make more merges go through without conflicts.\n\n\nSuggested next steps\n====================\n\nI don't have time right now to work more on best merge bases, and I am\nnot very familiar with the parts of the code that would be involved.\nSo I'm hoping that somebody else finds this a worthwhile improvement\nand tries implementing best merge bases in git core.  I have the\nfollowing suggestions:\n\n* Add an option\n\n      git merge-base --best <commit> <commit>...\n\n  that computes the best merge base as described above.  Its output\n  can be tested against the git-best-merge-base script that I\n  provided.\n\n* Use the best merge base when computing\n\n      git diff <commit>...<commit>\n\n  This should give shorter differences in many cases.\n\n* Benchmark \"merge-base\" with the \"--best\" option and, if it is not\n  too expensive, perhaps make it the default behavior of \"merge-base\".\n\n* See whether best merge bases can be used to improve other parts of\n  the code, especially the code for the recursive merge strategy.\n\nMichael\n\n[1] I assume that commits make independent changes.  If some commits\n    in fact revert changes made by other commits, or some commits have\n    been cherry-picked across branches, then the correlation between\n    number of commits and size of diff will be a bit weaker but should\n    still be a useful approximation.\n\n[2] There are other ways that \"fewest changes\" could be defined.  We\n    could include merge commits in the count of extra commits.  (This\n    variant could be implemented by omitting `--no-merges` in the\n    `rev-list` commands above.)  Or, when diffing only text files, we\n    could try to minimize the overall textual length of the diff.  The\n    definition used in the main text is chosen for being reasonable,\n    general, symmetric, and not too expensive to compute.\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\n\n"},{"id":"244072","messageId":"539AC690.6000906@drmicha.warpmail.net","threadId":"36903","inReplyTo":"539A25BF.4060501@alum.mit.edu","subject":"Re: Our merge bases sometimes suck","fromName":"Michael J Gruber","fromEmail":"git@drmicha.warpmail.net","sentAt":"2014-06-13T09:38:24Z","receivedAt":"2014-06-13T09:38:24Z","isPatch":false,"sender":{"key":"git@grubix.eu","avatar":"https://avatars.githubusercontent.com/u/233215?v=4"},"body":"Michael Haggerty venit, vidit, dixit 13.06.2014 00:12:\n> I've been thinking a lot about merge bases lately and think I have\n> discovered something interesting.\n> \n> tl;dr:\n> \n> When two branches have multiple merge bases,\n> \n>     git merge-base $master $branch\n> \n> picks one merge base more or less arbitrarily.  Here I describe a\n> criterion for picking a \"best\" merge base.  When the best merge base\n> is used, the diff output by\n> \n>     git diff $master...$branch\n> \n> becomes shorter and simpler--sometimes dramatically so.  I have\n> quantified the improvement by analyzing historical merges from the Git\n> project (see attached image).  Best merge bases might also help reduce\n> conflicts when conducting merges.\n> \n\nEverytime I looked at our merge base code, my head started spinning. So\nit's admirable you even started this endeavor :)\n\nWe use merge bases for several things:\n\n- merging\n- resolving \"A...B\" rev notation (rev-list and friends), aka symmetric\ndifference\n- left/right selection/annotation of commits (rev-list/log)\n- resolving \"diff A...B\", which may be a handy notation, but is horribly\nmisleading because it is a very unsymmetric form of diff\n\nOut of these four, you seemingly picked the one as pivoting example\nwhich is most different from any symmetric notion of \"...\". But in fact,\n\"merging\" is quite unsymmetric, too, because merging branch into master\nis quite different from the other way round.\n\nThis is certainly obvious to you, bit I thought I point it out for the\nconvenience of other readers: You are after optimizing the merge base\nchoice for an unsymmetric use case, which covers \"diff A...B\" as well as\n\"merge B into A\".\n\nIn these two cases, choosing different merge bases can lead to different\nresults. The other two basically use all merge bases anyways.\n\n(I seem to recall that our cherry code could profit from improvements, too.)\n\n> Background\n> ==========\n> \n> A merge base of two or more branches is a common ancestor of those\n> branches that has no descendant that is also a common ancestor (see\n> `git-merge-base(1)`).  Merge bases are important when merging\n> branches, and are also used internally to some other commands like\n> \"git diff $master...$branch\".\n> \n> Sometimes branches have multiple merge bases, such as in the case of a\n> criss-cross merge:\n> \n>     o--A--o--o--X--o--Y--o--Z    <- master\n>         \\        \\   /\n>          \\        \\ /\n>           \\        ·\n>            \\      / \\\n>             \\    /   \\\n>              B--C--D--E--F       <- branch\n> \n> Here, commits X and C are both merge bases for branches master and\n> branch.  You can list all merge bases by running\n> \n>     git merge-base --all $master $branch\n> \n> But if you run\n> \n>     git merge-base $master $branch\n> \n> only one merge base is returned.  *Which* one it returns is not\n> documented and appears to be pretty arbitrary (probably a side effect\n> of the traversal order?)\n> \n> \n> The \"best\" merge base\n> =====================\n> \n> But not all merge bases are created equal.  It is possible to define a\n> \"best\" merge base that has some nice properties.\n> \n> Let's focus on the command\n> \n>     git diff $master...$branch\n> \n> which is equivalent to\n> \n>     git diff $(git merge-base $master $branch)..$branch\n> \n> We want such a diff to have two properties:\n> \n> 1. It must include *all* changes that have been made on the branch but\n>    are not yet contained in master.\n> \n> 2. It should contain *as few* changes as possible that are already in\n>    master.\n> \n> The first property is satisfied automatically if the left end of the\n> \"diff\" range is any merge base.  Because a merge base is an ancestor\n> of master, it cannot possibly include any changes that were made on\n> the branch but have not yet been merged to master [1].\n> \n> The second property requires as a *necessary* condition that the left\n> end of the diff is a merge base.  But the property also helps us pick\n> the best among multiple merge bases.  We just need to make the idea of\n> \"contains as few changes as possible\" more precise.\n> \n> I propose that the best merge base is the merge base \"candidate\" that\n> minimizes the number of non-merge commits that are in\n> \n>     git rev-list --no-merges $candidate..$branch\n> \n> but are already in master:\n> \n>     git rev-list --no-merges $master\n> \n> Since a non-merge commit should embody a single logical change,\n> counting non-merge commits is in some sense counting changes [2].\n> \n> We can put this criterion in simpler form.  Because every candidate is\n> a merge-base,\n> \n>     git rev-list --no-merges $candidate..$branch\n> \n> necessarily includes *all* of the non-merge commits that are on branch\n> but not on master. \n\nThis is actually true for every merge base candidate (i.e. every commit\nwhich is both on master and branch).\n\n[These things are really much easier in set language, A..B being B\n\\setminus A, being B intersected with the complement of A etc.]\n\n> This is a fixed number of commits, the same for\n> every candidate.\n\n\"This\" refers to \"branch minus master\" (commits on branch but not on\nmaster), which is defined indepently of candidate.\n\n>  It *additionally* includes the commits that are on\n> master but not yet in branch.  This second number varies from one\n> candidate to another.\n\n\"master minus branch\" is independent of candidate also.\n\nThe second number is rather those commits on candidate..branch which are\nnot \"branch minus master\", i.e. \"branch minus candidate\" minus \"branch\nminus master\", which is \"branch intersected with master minus\ncandidate\", i.e. those commits on candidate..branch which are also on\nmaster. [Again this is true for every merge base candidate, not just\nevery merge base.]\n\n>  So if we minimize the number of commits in this\n> output, is is the same as minimizing the number of unwanted commits.\n\nNow I understand why this statement is true :)\n\n> Therefore, to get the best merge base, all we have to do is pick the\n> merge base that minimizes\n> \n>     git rev-list --count --no-merges $candidate..$branch\n> \n> There can be ties, but in practice they are rare enough that it is\n> probably not worth worrying about them.\n> \n> \n> Symmetry; generalization to more than two branches\n> ==================================================\n>\n> Interestingly, minimizing the last criterion is the same as maximizing\n> \n>     git rev-list --count --no-merges $candidate\n> \n> because there is a fixed number of commits in\n> \n>     git rev-list --no-merges $branch\n> \n> , and each of those commits is in exactly one of the two counts above.\n\nThat's a cute observation, which in the example above is wrong on first\nglance, but true on second: Visually/subjectively, one easily misses\ncommits B and C when counting \"X..master\", which is not just the commits\n\"extending master beyond X\", etc.\n\n> This formulation shows that the best merge base for computing\n> \n>     git diff $master...$branch\n> \n> is also the best merge base for computing\n> \n>     git diff $branch...$master\n> \n> ; i.e., the best merge base is symmetric in its arguments.  It also\n> shows that the concept of \"best merge base\" can trivially be\n> generalized to more than two branches.\n\nThat symmetry is really surprising, but the argument is convincingly\ncorrect. Alas, that count back to the roots can be really expensive.\n\nGiven that the arguments in the previous argument show that everything\napplies to merge base candidates as well, not just merge bases, I'm\nwondering whether we can weave in the weighing (which one is best) with\nour existing merge base algorithm or maybe an alternative algorithm\nusing generation numbers or such.\n\n> git-best-merge-base script\n> ===========================\n> \n> The best merge base can be computed, for example, using the following\n> script:\n> \n>     #! /bin/sh\n>     # Usage: git-best-merge-base MASTER BRANCH\n> \n>     set -e\n> \n>     master=\"$1\"\n>     branch=\"$2\"\n> \n>     count() {\n>         git rev-list --no-merges --count \"$1..$branch\"\n>     }\n> \n>     # Note that if $master and $branch have no common ancestors, `git\n>     # merge-base` fails with retcode=1, causing the script to exit\n>     # with the same error code.\n>     merge_bases=$(git merge-base --all \"$master\" \"$branch\")\n> \n>     case \"${#merge_bases}\" in\n>     40)\n>         # One merge base -> use it.\n>         echo $merge_bases\n>         ;;\n>     *)\n>         # Multiple merge bases -> pick the one for which $base..$branch\n>         # has the fewest commits that are already in $master.  To ensure\n>         # that the result is repeatable, if there is a tie we choose the\n>         # merge base that comes first when sorted by SHA-1:\n>         for merge_base in $merge_bases\n>         do\n>             echo $(count $merge_base) $merge_base\n>         done | sort -k1,1n -k2 | sed -ne '1s/^.* //p'\n>         ;;\n>     esac\n> \n> \n> Do best merge bases really help?\n> ================================\n> \n> I analyzed all of the 2-parent merges made in the history of the Git\n> project.  (I limited the analysis to 2-parent merges just for\n> simplicity.)  I computed the size of the asymmetric diffs\n> \n>     git diff $commit^1...$commit^2\n> \n> using the current code and using git-best-merge-base, with the\n> following script:\n> \n>     #! /bin/sh\n> \n>     old_diff_len() {\n>         git diff $1...$2 | wc -l\n>     }\n> \n>     new_diff_len() {\n>         git diff $(git-best-merge-base $1 $2)..$2 | wc -l\n>     }\n> \n>     git rev-list --min-parents=2 --max-parents=2 --parents \"$@\" |\n>     while read commit p1 p2\n>     do\n>         echo \"$commit $(git merge-base --all $p1 $p2 | wc -l)\n> $(old_diff_len $p1 $p2) $(new_diff_len $p1 $p2)\"\n>     done\n> \n> \n> Results:\n> \n> * Total number of merges: 8263\n> \n> * Total number of merges with exactly two parents: 8229\n> \n>   Of which:\n> \n>   * Number with zero merge bases: 6 (0.07%)\n> \n>   * Number with one merge base: 7823 (95.1%)\n> \n>   * Number with multiple merge bases: 400 (4.8%)\n\nI guess that shows how well thought out our maintainer's branch and\nmerge workflow is: practically no criss-crossing, everything merged\ndownwards, for almost constant definition of \"down\" ;)\n\n>     Of which:\n> \n>     * Number whose diffs shrink: 71 (17.8%)\n> \n>     * Number whose diffs remain the same length: 323 (80.1%)\n> \n>     * Number whose diffs grow: 6 (1.5%)\n> \n> I have attached a graph plotting the diff sizes against each other on\n> a log-log scale.  The points *under* the red line are diffs that have\n> shrunk; the points *over* the red line are the diffs that have grown.\n> As you can see, far more diffs shrank than grew, and by larger\n> factors.  Some of the diffs have shrunk dramatically.  In the most\n> drastic case, the diff shrank from 466602 lines to 81 lines.\n> \n> A relatively small fraction of all merges are affected, but of merges\n> that have multiple merge bases (which are the most difficult merges to\n> handle), more than one in six would be simplified.\n> \n> I should mention that I have done a similar analysis of a large\n> commercial software project's history, with broadly similar results.\n> \n> I wouldn't be surprised if selecting merge bases more intelligently in\n> \"git merge\" also helps make more merges go through without conflicts.\n> \n> \n> Suggested next steps\n> ====================\n> \n> I don't have time right now to work more on best merge bases, and I am\n> not very familiar with the parts of the code that would be involved.\n> So I'm hoping that somebody else finds this a worthwhile improvement\n> and tries implementing best merge bases in git core.  I have the\n> following suggestions:\n> \n> * Add an option\n> \n>       git merge-base --best <commit> <commit>...\n> \n>   that computes the best merge base as described above.  Its output\n>   can be tested against the git-best-merge-base script that I\n>   provided.\n> \n> * Use the best merge base when computing\n> \n>       git diff <commit>...<commit>\n> \n>   This should give shorter differences in many cases.\n> \n> * Benchmark \"merge-base\" with the \"--best\" option and, if it is not\n>   too expensive, perhaps make it the default behavior of \"merge-base\".\n> \n> * See whether best merge bases can be used to improve other parts of\n>   the code, especially the code for the recursive merge strategy.\n> \n> Michael\n> \n> [1] I assume that commits make independent changes.  If some commits\n>     in fact revert changes made by other commits, or some commits have\n>     been cherry-picked across branches, then the correlation between\n>     number of commits and size of diff will be a bit weaker but should\n>     still be a useful approximation.\n> \n> [2] There are other ways that \"fewest changes\" could be defined.  We\n>     could include merge commits in the count of extra commits.  (This\n>     variant could be implemented by omitting `--no-merges` in the\n>     `rev-list` commands above.)  Or, when diffing only text files, we\n>     could try to minimize the overall textual length of the diff.  The\n>     definition used in the main text is chosen for being reasonable,\n>     general, symmetric, and not too expensive to compute.\n> \n"},{"id":"244075","messageId":"539ACEDE.8040401@alum.mit.edu","threadId":"36903","inReplyTo":"539AC690.6000906@drmicha.warpmail.net","subject":"Re: Our merge bases sometimes suck","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2014-06-13T10:13:50Z","receivedAt":"2014-06-13T10:13:50Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 06/13/2014 11:38 AM, Michael J Gruber wrote:\n> Michael Haggerty venit, vidit, dixit 13.06.2014 00:12:\n>> I've been thinking a lot about merge bases lately and think I have\n>> discovered something interesting.\n>>\n>> tl;dr:\n>>\n>> When two branches have multiple merge bases,\n>>\n>>     git merge-base $master $branch\n>>\n>> picks one merge base more or less arbitrarily.  Here I describe a\n>> criterion for picking a \"best\" merge base.  When the best merge base\n>> is used, the diff output by\n>>\n>>     git diff $master...$branch\n>>\n>> becomes shorter and simpler--sometimes dramatically so.  I have\n>> quantified the improvement by analyzing historical merges from the Git\n>> project (see attached image).  Best merge bases might also help reduce\n>> conflicts when conducting merges.\n>>\n> \n> Everytime I looked at our merge base code, my head started spinning. So\n> it's admirable you even started this endeavor :)\n\nI haven't looked at the code :-)  My email came only out of reading docs\nand experimenting.\n\n> We use merge bases for several things:\n> \n> - merging\n> - resolving \"A...B\" rev notation (rev-list and friends), aka symmetric\n> difference\n> - left/right selection/annotation of commits (rev-list/log)\n> - resolving \"diff A...B\", which may be a handy notation, but is horribly\n> misleading because it is a very unsymmetric form of diff\n> \n> Out of these four, you seemingly picked the one as pivoting example\n> which is most different from any symmetric notion of \"...\". But in fact,\n> \"merging\" is quite unsymmetric, too, because merging branch into master\n> is quite different from the other way round.\n> \n> This is certainly obvious to you, bit I thought I point it out for the\n> convenience of other readers: You are after optimizing the merge base\n> choice for an unsymmetric use case, which covers \"diff A...B\" as well as\n> \"merge B into A\".\n> \n> In these two cases, choosing different merge bases can lead to different\n> results. The other two basically use all merge bases anyways.\n\nCorrect, the scope of my proposal is for cases when there are multiple\nmerge bases but one has to be selected.\n\n> [...]\n>> I propose that the best merge base is the merge base \"candidate\" that\n>> minimizes the number of non-merge commits that are in\n>>\n>>     git rev-list --no-merges $candidate..$branch\n>>\n>> but are already in master:\n>>\n>>     git rev-list --no-merges $master\n>>\n>> Since a non-merge commit should embody a single logical change,\n>> counting non-merge commits is in some sense counting changes [2].\n>>\n>> We can put this criterion in simpler form.  Because every candidate is\n>> a merge-base,\n>>\n>>     git rev-list --no-merges $candidate..$branch\n>>\n>> necessarily includes *all* of the non-merge commits that are on branch\n>> but not on master. \n> \n> This is actually true for every merge base candidate (i.e. every commit\n> which is both on master and branch).\n> \n> [These things are really much easier in set language, A..B being B\n> \\setminus A, being B intersected with the complement of A etc.]\n> \n>> This is a fixed number of commits, the same for\n>> every candidate.\n> \n> \"This\" refers to \"branch minus master\" (commits on branch but not on\n> master), which is defined indepently of candidate.\n> \n>>  It *additionally* includes the commits that are on\n>> master but not yet in branch.  This second number varies from one\n>> candidate to another.\n> \n> \"master minus branch\" is independent of candidate also.\n> \n> The second number is rather those commits on candidate..branch which are\n> not \"branch minus master\", i.e. \"branch minus candidate\" minus \"branch\n> minus master\", which is \"branch intersected with master minus\n> candidate\", i.e. those commits on candidate..branch which are also on\n> master. [Again this is true for every merge base candidate, not just\n> every merge base.]\n> \n>>  So if we minimize the number of commits in this\n>> output, is is the same as minimizing the number of unwanted commits.\n> \n> Now I understand why this statement is true :)\n\nThanks for the translation to set notation.  It is indeed easier to work\nwith.\n\n>> Therefore, to get the best merge base, all we have to do is pick the\n>> merge base that minimizes\n>>\n>>     git rev-list --count --no-merges $candidate..$branch\n>>\n>> There can be ties, but in practice they are rare enough that it is\n>> probably not worth worrying about them.\n>>\n>>\n>> Symmetry; generalization to more than two branches\n>> ==================================================\n>>\n>> Interestingly, minimizing the last criterion is the same as maximizing\n>>\n>>     git rev-list --count --no-merges $candidate\n>>\n>> because there is a fixed number of commits in\n>>\n>>     git rev-list --no-merges $branch\n>>\n>> , and each of those commits is in exactly one of the two counts above.\n> \n> That's a cute observation, which in the example above is wrong on first\n> glance, but true on second: Visually/subjectively, one easily misses\n> commits B and C when counting \"X..master\", which is not just the commits\n> \"extending master beyond X\", etc.\n> \n>> This formulation shows that the best merge base for computing\n>>\n>>     git diff $master...$branch\n>>\n>> is also the best merge base for computing\n>>\n>>     git diff $branch...$master\n>>\n>> ; i.e., the best merge base is symmetric in its arguments.  It also\n>> shows that the concept of \"best merge base\" can trivially be\n>> generalized to more than two branches.\n> \n> That symmetry is really surprising, but the argument is convincingly\n> correct. Alas, that count back to the roots can be really expensive.\n\nI mentioned the formulation\n\n    git rev-list --count --no-merges $candidate\n\nnot because it is necessarily the most efficient way to find the best\nmerge base, but because it is theoretically useful.  For the\nimplementation, any of the formulations can be used, because they are\nall equivalent.\n\n> Given that the arguments in the previous argument show that everything\n> applies to merge base candidates as well, not just merge bases, I'm\n> wondering whether we can weave in the weighing (which one is best) with\n> our existing merge base algorithm or maybe an alternative algorithm\n> using generation numbers or such.\n> [...]\n\nThat's an interesting idea.  I haven't looked at that code at all, so if\nyou want to get involved it would be awesome!\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"244142","messageId":"539B1E59.1030604@gmail.com","threadId":"36903","inReplyTo":"539AC690.6000906@drmicha.warpmail.net","subject":"Re: Our merge bases sometimes suck","fromName":"Jakub Narębski","fromEmail":"jnareb@gmail.com","sentAt":"2014-06-13T15:52:57Z","receivedAt":"2014-06-13T15:52:57Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"W dniu 2014-06-13 11:38, Michael J Gruber pisze:\n> Michael Haggerty venit, vidit, dixit 13.06.2014 00:12:\n>> I've been thinking a lot about merge bases lately and think I have\n>> discovered something interesting.\n>>\n>> tl;dr:\n>>\n>> When two branches have multiple merge bases,\n>>\n>>      git merge-base $master $branch\n>>\n>> picks one merge base more or less arbitrarily.  Here I describe a\n>> criterion for picking a \"best\" merge base.  When the best merge base\n>> is used, the diff output by\n>>\n>>      git diff $master...$branch\n>>\n>> becomes shorter and simpler--sometimes dramatically so.  I have\n>> quantified the improvement by analyzing historical merges from the Git\n>> project (see attached image).  Best merge bases might also help reduce\n>> conflicts when conducting merges.\n>>\n>\n> Everytime I looked at our merge base code, my head started spinning. So\n> it's admirable you even started this endeavor :)\n>\n> We use merge bases for several things:\n>\n> - merging\n> - resolving \"A...B\" rev notation (rev-list and friends), aka symmetric\n> difference\n> - left/right selection/annotation of commits (rev-list/log)\n> - resolving \"diff A...B\", which may be a handy notation, but is horribly\n> misleading because it is a very unsymmetric form of diff\n\nI don't know if it has been fixed, but there is a difference\nbetween \"git diff A...B\" when A and B have one merge base, and\n\"git diff A...B\" when there are more than one merge base.\n\nWhen there is one merge base, \"git diff A...B\" returns simple\nunified diff equivalent to \"git diff $(git merge-base A B) B\".\nIt is unsymmetric.\n\nBut where there are more than one merge base, by design or by\naccident for \"git diff A...B\" git 1.9.2 / 1.7.4 returns\n\n    git diff --cc $(git merge-base --all A B) A B\n\nwhich is *symmetric*, and is combined not unified diff.\n\n-- \nJakub Narębski\n"},{"id":"244180","messageId":"539B77D2.3020307@alum.mit.edu","threadId":"36903","inReplyTo":"539B1E59.1030604@gmail.com","subject":"Re: Our merge bases sometimes suck","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2014-06-13T22:14:42Z","receivedAt":"2014-06-13T22:14:42Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 06/13/2014 05:52 PM, Jakub Narębski wrote:\n> I don't know if it has been fixed, but there is a difference\n> between \"git diff A...B\" when A and B have one merge base, and\n> \"git diff A...B\" when there are more than one merge base.\n> \n> When there is one merge base, \"git diff A...B\" returns simple\n> unified diff equivalent to \"git diff $(git merge-base A B) B\".\n> It is unsymmetric.\n> \n> But where there are more than one merge base, by design or by\n> accident for \"git diff A...B\" git 1.9.2 / 1.7.4 returns\n> \n>    git diff --cc $(git merge-base --all A B) A B\n> \n> which is *symmetric*, and is combined not unified diff.\n\nThanks for the information.  This doesn't seem to be the case in git\n2.0.0.  For example, commit 8c0db2f519 in the git project is a merge\nwith two merge bases:\n\n$ git --version\ngit version 2.0.0\n$ c=8c0db2f5193153ea8a51bb45b0512c5a3889023b\n$ git merge-base --all $c^1 $c^2\na15f43312f6962959e8daa33df0cf5357852a4b8\n9a0e6731c632c841cd2de9dec0b9091b2f10c6fd\n$ git diff $c^1...$c^2 | head -20\ndiff --git a/Documentation/git-rev-parse.txt\nb/Documentation/git-rev-parse.txt\nindex d638bfc..29b5789 100644\n--- a/Documentation/git-rev-parse.txt\n+++ b/Documentation/git-rev-parse.txt\n@@ -77,6 +77,14 @@ OPTIONS\n \tpath of the top-level directory relative to the current\n \tdirectory (typically a sequence of \"../\", or an empty string).\n\n+--git-dir::\n+\tShow `$GIT_DIR` if defined else show the path to the .git directory.\n+\n+--short, --short=number::\n+\tInstead of outputting the full SHA1 values of object names try to\n+\tabbriviate them to a shorter unique name. When no length is specified\n+\t7 is used. The minimum length is 4.\n+\n --since=datestring, --after=datestring::\n \tParses the date string, and outputs corresponding\n \t--max-age= parameter for git-rev-list command.\ndiff --git a/git-archimport.perl b/git-archimport.perl\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\n"},{"id":"244182","messageId":"xmqqbntw1lqx.fsf@gitster.dls.corp.google.com","threadId":"36903","inReplyTo":"539B1E59.1030604@gmail.com","subject":"Re: Our merge bases sometimes suck","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-06-13T22:35:18Z","receivedAt":"2014-06-13T22:35:18Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jakub Narębski <jnareb@gmail.com> writes:\n\n> I don't know if it has been fixed, but there is a difference\n> between \"git diff A...B\" when A and B have one merge base, and\n> \"git diff A...B\" when there are more than one merge base.\n>\n> When there is one merge base, \"git diff A...B\" returns simple\n> unified diff equivalent to \"git diff $(git merge-base A B) B\".\n> It is unsymmetric.\n>\n> But where there are more than one merge base, by design or by\n> accident for \"git diff A...B\" git 1.9.2 / 1.7.4 returns\n>\n>    git diff --cc $(git merge-base --all A B) A B\n>\n> which is *symmetric*, and is combined not unified diff.\n\nHmph, the relevant code has not changed very much since c008c0ff\n(diff A...B: give one possible diff when there are more than one\nmerge-base, 2010-07-12) which has been with us since v1.7.2.\n"},{"id":"244396","messageId":"xmqq8uovo9pa.fsf@gitster.dls.corp.google.com","threadId":"36903","inReplyTo":"539A25BF.4060501@alum.mit.edu","subject":"Re: Our merge bases sometimes suck","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-06-17T15:08:17Z","receivedAt":"2014-06-17T15:08:17Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Michael Haggerty <mhagger@alum.mit.edu> writes:\n\n> The \"best\" merge base\n> =====================\n>\n> But not all merge bases are created equal.  It is possible to define a\n> \"best\" merge base that has some nice properties.\n>\n> Let's focus on the command\n>\n>     git diff $master...$branch\n>\n> which is equivalent to\n>\n>     git diff $(git merge-base $master $branch)..$branch\n> ...\n> I propose that the best merge base is the merge base \"candidate\" that\n> minimizes the number of non-merge commits that are in\n>\n>     git rev-list --no-merges $candidate..$branch\n>\n> but are already in master:\n>\n>     git rev-list --no-merges $master\n\nI welcome this line of thought very much.\n\nThere is one niggle I find somewhat curious but am either too lazy\nor too stupid to think it through myself ;-)\n\nThe \"merge-base\" is a symmetric operation, because the three-way\nmerge, which is the primary customer of its result, fundamentally\nis.  From your description, it sounds like the \"best\" merge base\nhowever may not be symmetric at all.  The merge-base between A and B\nthat makes \"git diff A...B\" the easiest to read by minimizing the\ndistance between it and B may be different from the merge-base\nbetween A and B that makes the other diff \"git diff B...A\" the\neasiest to read.\n\nOr it may not be assymmetric---that is why I said I didn't think it\nthrough.  I am not saying that it is bad if the \"best\" merge-base is\nan asymmetric concept; I am curious if it is asymmetric, and if so\nif that is fundamental.\n"},{"id":"244399","messageId":"53A06264.9080205@alum.mit.edu","threadId":"36903","inReplyTo":"xmqq8uovo9pa.fsf@gitster.dls.corp.google.com","subject":"Re: Our merge bases sometimes suck","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2014-06-17T15:44:36Z","receivedAt":"2014-06-17T15:44:36Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 06/17/2014 05:08 PM, Junio C Hamano wrote:\n> Michael Haggerty <mhagger@alum.mit.edu> writes:\n> \n>> The \"best\" merge base\n>> =====================\n>>\n>> But not all merge bases are created equal.  It is possible to define a\n>> \"best\" merge base that has some nice properties.\n>>\n>> Let's focus on the command\n>>\n>>     git diff $master...$branch\n>>\n>> which is equivalent to\n>>\n>>     git diff $(git merge-base $master $branch)..$branch\n>> ...\n>> I propose that the best merge base is the merge base \"candidate\" that\n>> minimizes the number of non-merge commits that are in\n>>\n>>     git rev-list --no-merges $candidate..$branch\n>>\n>> but are already in master:\n>>\n>>     git rev-list --no-merges $master\n> \n> I welcome this line of thought very much.\n> \n> There is one niggle I find somewhat curious but am either too lazy\n> or too stupid to think it through myself ;-)\n> \n> The \"merge-base\" is a symmetric operation, because the three-way\n> merge, which is the primary customer of its result, fundamentally\n> is.  From your description, it sounds like the \"best\" merge base\n> however may not be symmetric at all.  The merge-base between A and B\n> that makes \"git diff A...B\" the easiest to read by minimizing the\n> distance between it and B may be different from the merge-base\n> between A and B that makes the other diff \"git diff B...A\" the\n> easiest to read.\n> \n> Or it may not be assymmetric---that is why I said I didn't think it\n> through.  I am not saying that it is bad if the \"best\" merge-base is\n> an asymmetric concept; I am curious if it is asymmetric, and if so\n> if that is fundamental.\n\nIt just looks asymmetric, but actually it is symmetric, which was kindof\nsurprising when I realized it.  The argument is in the next section\n\"Symmetry; generalization to more than two branches\".  Michael Gruber\nshowed the same thing upthread using set notation, which is easier to\nfollow.  Here is his argument in symbolic notation.  We want to minimize\n\n    N = |(branch - candidate) ∧ master|\n\nwhere \"branch\" represents the set of all commits in \"branch\" etc, \"|x|\"\nrepresents the number of elements in set \"x\", and \"∧\" is set\nintersection, and candidate is a merge base of branch and master.\n\n    N = |(branch ∧ ∼candidate) ∧ master|\n      = |(branch ∧ master) ∧ ∼candidate|\n\nSince candidate is a common ancestor of branch and master,\n\n    candidate ⊆ branch ∧ master\n\nso we have\n\n    N = |branch ∧ master| - |candidate|\n\nSince \"|branch ∧ master|\" is the same for all candidates, minimizing N\nis the same as maximizing |candidate|, which is the same as\n\n    git rev-list --count --no-merges $candidate\n\n.  This is clearly symmetric in master vs. base.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"244744","messageId":"xmqqtx7gdqbt.fsf@gitster.dls.corp.google.com","threadId":"36903","inReplyTo":"53A06264.9080205@alum.mit.edu","subject":"Re: Our merge bases sometimes suck","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-06-20T06:53:42Z","receivedAt":"2014-06-20T06:53:42Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Michael Haggerty <mhagger@alum.mit.edu> writes:\n\n> It just looks asymmetric, but actually it is symmetric, which was kindof\n> surprising when I realized it....\n>\n> Since \"|branch ∧ master|\" is the same for all candidates, minimizing N\n> is the same as maximizing |candidate|, which is the same as\n>\n>     git rev-list --count --no-merges $candidate\n>\n> This is clearly symmetric in master vs. base.\n\nHmph, but that obviously will become very expensive to compute as\nproject grows.\n\nWhen we (potentially) have multiple merge-bases, after finding all\nthe candidates by traversing from the two commits to be merged, we\nalready make another set of traversals, starting from the candidates\nand painting the ancestors down to their common ancestors.  This is\ndone to discover if each candidate is reachable from any other\ncandidate (in which case the reachable one is not a merge-base).\n\nThe resulting graph of this traversal is currently used only to cull\nnon-merge-bases out of the candidates, but I wonder if you can\n*count* the nodes in it in each color and use that number (which is\nessentially the number of commits that can be reached only from one\ncandidate and not from other candidates) to derive a score for each\ncandidate, and use it to assess the goodness of merge-bases, just\nlike the number you are counting in the above full traversal.\n"},{"id":"244749","messageId":"53A3F67A.80501@alum.mit.edu","threadId":"36903","inReplyTo":"xmqqtx7gdqbt.fsf@gitster.dls.corp.google.com","subject":"Re: Our merge bases sometimes suck","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2014-06-20T08:53:14Z","receivedAt":"2014-06-20T08:53:14Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 06/20/2014 08:53 AM, Junio C Hamano wrote:\n> Michael Haggerty <mhagger@alum.mit.edu> writes:\n> \n>> It just looks asymmetric, but actually it is symmetric, which was kindof\n>> surprising when I realized it....\n>>\n>> Since \"|branch ∧ master|\" is the same for all candidates, minimizing N\n>> is the same as maximizing |candidate|, which is the same as\n>>\n>>     git rev-list --count --no-merges $candidate\n>>\n>> This is clearly symmetric in master vs. base.\n> \n> Hmph, but that obviously will become very expensive to compute as\n> project grows.\n\nThis formulation is theoretically interesting because it shows the\nsymmetry of the criterion, but that doesn't mean it is the most\npractical to use.  Given that multiple formulations are equivalent, any\nof them can be used.\n\n> When we (potentially) have multiple merge-bases, after finding all\n> the candidates by traversing from the two commits to be merged, we\n> already make another set of traversals, starting from the candidates\n> and painting the ancestors down to their common ancestors.  This is\n> done to discover if each candidate is reachable from any other\n> candidate (in which case the reachable one is not a merge-base).\n> \n> The resulting graph of this traversal is currently used only to cull\n> non-merge-bases out of the candidates, but I wonder if you can\n> *count* the nodes in it in each color and use that number (which is\n> essentially the number of commits that can be reached only from one\n> candidate and not from other candidates) to derive a score for each\n> candidate, and use it to assess the goodness of merge-bases, just\n> like the number you are counting in the above full traversal.\n\nIt sounds promising.  Let's see if I correctly understand the algorithm\nthat you described:\n\n\"common_ancestors\" = intersection of all candidates' histories\n\"painting_from($candidate)\" = $candidate - common_ancestors\ndiscard $candidate if $candidate is in painting_from($other_candidate)\n(i.e., it is not a merge base)\n\nIf that is correct, then the candidate with the most commits in\npainting_from($candidate) should be the best merge base, because\ncommon_ancestors is a subset of the candidate's history, so\n\n    |painting_from($candidate)| = |$candidate| - |common_ancestors|\n\nSince |common_ancestors| is the same for all candidates, minimizing\n|painting_from($candidate)| is the same as minimizing |$candidate|.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"244818","messageId":"CAK3OfOjfyrsN47Ho0MFh4VZUg6YMjjwPOa16iuw3xtqyhz16hg@mail.gmail.com","threadId":"36903","inReplyTo":"xmqqtx7gdqbt.fsf@gitster.dls.corp.google.com","subject":"Re: Our merge bases sometimes suck","fromName":"Nico Williams","fromEmail":"nico@cryptonector.com","sentAt":"2014-06-20T21:17:37Z","receivedAt":"2014-06-20T21:17:37Z","isPatch":false,"sender":{"key":"nico@cryptonector.com","avatar":null},"body":"On Fri, Jun 20, 2014 at 1:53 AM, Junio C Hamano <gitster@pobox.com> wrote:\n> Michael Haggerty <mhagger@alum.mit.edu> writes:\n>> [...]\n>\n> Hmph, but that obviously will become very expensive to compute as\n> project grows.\n\nThat's the main reason to like Fossil's approach (namely, the use of\nSQL, specifically SQLite3): you can write declarative queries and let\nthe query planner optimize.\n\n(That's also about the only thing I like about Fossil: the use of\nSQL/SQLite3, and all that that implies.  Fossil is otherwise an\nanti-git, and that makes it useless for me.)\n\nPardon the intrusion,\n\nNico\n--\n"},{"id":"244866","messageId":"53A812D0.1080402@gmail.com","threadId":"36903","inReplyTo":"CAK3OfOjfyrsN47Ho0MFh4VZUg6YMjjwPOa16iuw3xtqyhz16hg@mail.gmail.com","subject":"Re: Our merge bases sometimes suck","fromName":"Jakub Narębski","fromEmail":"jnareb@gmail.com","sentAt":"2014-06-23T11:43:12Z","receivedAt":"2014-06-23T11:43:12Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"W dniu 2014-06-20 23:17, Nico Williams pisze:\n> On Fri, Jun 20, 2014 at 1:53 AM, Junio C Hamano <gitster@pobox.com> wrote:\n>> Michael Haggerty <mhagger@alum.mit.edu> writes:\n>>> [...]\n>>\n>> Hmph, but that obviously will become very expensive to compute as\n>> project grows.\n>\n> That's the main reason to like Fossil's approach (namely, the use of\n> SQL, specifically SQLite3): you can write declarative queries and let\n> the query planner optimize.\n\nI do wonder if using *generic* RDBMS / key-value store would really\nmake Git faster than current filesystem-like approach.\n\nBTW. perhaps caching generation numbers would help here; the idea\nof adding performance-helper generation number header to commit\nobject was rejected.\n\n> (That's also about the only thing I like about Fossil: the use of\n> SQL/SQLite3, and all that that implies.  Fossil is otherwise an\n> anti-git, and that makes it useless for me.)\n\nThere are Bazaar and Veracity that are supposed to have pluggable\nbackends...\n\n-- \nJakub Narębski\n"}]}