How does Beyo.Comp. 3way-Merge algorithm works?

Collapse
X
 
  • Time
  • Show
Clear All
new posts
  • gghh
    Visitor
    • Nov 2013
    • 3

    How does Beyo.Comp. 3way-Merge algorithm works?

    Hello,

    I am performing a merge and I see a substantially different results between Beyond Compare and another merge tool, p4merge
    http://www.perforce.com/perforce/r12...ref/merge.html

    My work requires me to have absolute confidence in the merging algorithm I use (I merge computer code, as I guess most of us).

    So:
    Can I find bcompare's algorithm described somewhere?
    or is anybody willing to explain me how it works?

    thanks,
  • Aaron
    Team Scooter
    • Oct 2007
    • 15938

    #2
    Hello,

    BC3 expects the Ancestor in the center pane, with Theirs and Yours in the Left or Right panes. Is this how you current have the program configured?

    We have some directions for Perforce here:
    http://www.scootersoftware.com/suppo...b_vcs#perforce
    Aaron P Scooter Software

    Comment

    • gghh
      Visitor
      • Nov 2013
      • 3

      #3
      Hello Aaron,

      > BC3 expects the Ancestor in the center pane,
      > with Theirs and Yours in the Left or Right panes.
      > Is this how you current have the program configured?

      Yes, and I cannot see how the GUI setup has something to do with the merging algorithm.

      > We have some directions for Perforce here: [...]

      I don't use perforce, I use p4merge, which is a graphical merging tool (which happens to be shipped with perforce). And then I run the same merge *again* with BC3, getting different conflicting regions.

      For that matters, my version control tool is mercurial. But that's a totally unrelated fact.
      I perform a 3way merge (base, local, other).
      I do it twice, to evaluate both p4merge and BC3, and pick the best tool for the daily activity of my team.
      They have different behaviours.
      I'd like to know more.

      Comment

      • Zoë
        Team Scooter
        • Oct 2007
        • 2663

        #4
        The two way comparison algorithm is proprietary and not documented anywhere. It's a greedy algorithm and tries to align as it goes, unlike some algorithms which compare the entirety of both files before producing any alignment.

        The three way comparison algorithm runs left<->center and center<->right comparisons and then stitches the results together based on the center file. It doesn't try to use a left<->right comparison until that initial alignment is done, and once it does fills in any gaps in the center with localized left<->right comparisons.

        The merge algorithm takes any left only or right only changes on a line-by-line basis. Any lines that have changes on both sides default to using the ancestor/center file and are marked in red. If a line has an important change on one side and an unimportant change on the other the important change takes precedence.

        If that's not sufficient, let us know what else you need to know.
        Zoë P Scooter Software

        Comment

        • Zoë
          Team Scooter
          • Oct 2007
          • 2663

          #5
          Originally posted by gghh
          My work requires me to have absolute confidence in the merging algorithm I use
          Neither BC nor Perforce should give you that level of confidence, regardless of how well documented the algorithms are. Neither one knows the context of your files and, AFAIK, neither has a language aware logic analyzer. If you rename a variable in one place and add code using the old name in another, neither is going to pick that up as a conflict or automatically pull the new name over.
          Zoë P Scooter Software

          Comment

          • gghh
            Visitor
            • Nov 2013
            • 3

            #6
            Hello Craig,

            > The three way comparison algorithm runs [...]
            > The merge algorithm takes [...]

            thank you very much for your detailed answer.
            This is helping me a lot in understanding what I observe.

            cheers,

            Comment

            • phord
              New User
              • Nov 2012
              • 1

              #7
              The three way comparison algorithm runs left<->center and center<->right comparisons and then stitches the results together based on the center file. It doesn't try to use a left<->right comparison until that initial alignment is done, and once it does fills in any gaps in the center with localized left<->right comparisons.
              I think this explains a problem I run into frequently where BC decides that two "same-change" changes do not align. Is there a reason you do this:

              comparison algorithm runs left<->center and center<->right comparisons and then stitches the results together based on the center file.
              Instead of this?

              comparison algorithm runs left<->center and right<->center comparisons and then stitches the results together based on the center file.
              I think the latter method would result in far fewer misalignments for me.

              Here's an example of this problem:



              Notice both LEFT and RIGHT have the same contents here, but BC3 identifies a conflict at lines 97-99. This is triggered by BC3's decision to alighn the CENTER[93] blank line to LEFT[97] and RIGHT[100]. If it aligned with RIGHT[97] I think this problem would go away. Am I right?

              Sometimes when rebasing in git and resolving with BC3, I end up with sections of code duplicated in my final merge even when BC3 did not see any conflicts (though this may be unrelated to the problem above).

              Comment

              • Aaron
                Team Scooter
                • Oct 2007
                • 15938

                #8
                Improving this is something on our wishlist. We have a set of sample data we work with; the info in your screenshot is very similar to samples we already have, but if you have any other samples you'd like us to look at to add to our test cases, please attach them here or email us at [email protected] (with a link to this forum thread in the email as reference).
                Aaron P Scooter Software

                Comment

                • castro-diephouse
                  New User
                  • Feb 2015
                  • 1

                  #9
                  Originally posted by Aaron
                  Improving this is something on our wishlist. We have a set of sample data we work with; the info in your screenshot is very similar to samples we already have, but if you have any other samples you'd like us to look at to add to our test cases, please attach them here or email us at [email protected] (with a link to this forum thread in the email as reference).
                  Hi Aaron (or whoever is monitoring from Scooter support), is this feature / improvement something that has been done in BC 4? We are evaluating BC 3 for our merge process and this has been flagged as an issue since sometimes both codelines get fixed without the merge being marked in version control. We can work around, but, the process would be less error-prone if BC would correctly identify that the left and right files already have the same change.

                  Comment

                  • Aaron
                    Team Scooter
                    • Oct 2007
                    • 15938

                    #10
                    Hello,

                    We made some improvements to our Alignment and added a new Alignment algorithm option, but have not changed the To Center method of alignment. Our BC4 trial is fully featured and can be tested with your specific files. If you have sample files you would like to email into [email protected], we can add them to our test cases. You can go to the Session Settings, Alignment tab, to alter the settings for your merge.

                    If you email us, please include a link back to this forum thread for our reference.
                    Aaron P Scooter Software

                    Comment

                    Working...