Improvements to diff3 (merge) performance

[Morten Kloster <mo...@gmail.com>]

Hi,

I'm not very happy with the current performance of the diff3
algorithm; I think it returns too many and too big conflicts. I have
some ideas on how to improve it, but I'd like to hear other people's
opinions first. Note that the primary purpose is to discuss how we
want merge to behave, not whether it is easy to implement.

I'll use the terms Base (original), Mine (modified) and Theirs (latest)
to refer to the three source files. In the merged file, C indicates a
conflict.

---

First, here's a quick run-though of how diff3 works now: After
running LCS on Base vs. Mine and Base vs. Theirs, it looks for
"sync points" - points where both Mine and Theirs match the Base.
Note that there is no need for an actual overlap: If Mine matches
Base up to a point and Theirs matches Base from that point
onwards, that is a valid sync point. If no two of the three are
identical between two neighboring sync points, that creates a
conflict.

Adjacent changes are accepted:

abcd (Base)
a1cd (Mine)
ab2d (Theirs)
a12d (Merged)

and

abcd (Base)
acd (Mine)
abc (Theirs)
ad (Merged)

while strictly larger changes are not:

abcd (Base)
a1cd (Mine)
a12d (Theirs)
aCd (Merged)

and

abcd (Base)
acd (Mine)
ad (Theirs)
aCd (Merged)

Note that this means that if changed files A and B are merged to
produce C, then attempting to merge A (or B) with C could well
produce a conflict (using the same Base the whole time), whereas
in my opinion, that ought to work fine, yielding C again.

---

My proposed main change is to let diff3 also sync on points where
Mine and Theirs have identical changes relative to Base, if either file
(Mine or Theirs) can also be synced to Base at the same point. This
can happen if either Mine or Theirs is unchanged from Base either
before or after that point, or if either of the changes from Base was a
pure insertion (as there is then no uncertainty as to the position in
the Base file). This would let diff3 incorporate all changes relative to
Base from both Mine and Theirs as long as there is no true conflict.

Some consequences:

Given two changed files A and B that only have deletions relative to
Base, the merged file would only contain the lines that are present
in both A and B.

Different insertions would be merged, not marked as conflict,
unless they truly conflict. There are only true conflicts if the diff2
between the two insertions have actual changes, not just separated
deletions and insertions (or equivalently, if the LCS has gaps in
both files between neighboring segments):

ag (Base)
abcefg (Mine)
acdeg (Theirs)
abcdefg (Merged)

Here, the order of the inserted lines is unambiguously determined;
partially from Mine and partially from Theirs.

Incremental and overlapping changes would merge cleanly:

abcde (Base)
a12de (Mine)
ab23e (Theirs)
a123e (Merged)

Of course there are cases where the merged result might not be
what would be desired, but that is also the case with the current
algorithm - keep in mind that any conflict can be "resolved" by
inserting blank lines in Base, Mine and Theirs to serve as sync
points. Here's an unfortunate case with the current algorithm:

abcbcd (Base)
acbcd (Mine)
abcd (Theirs)
acd (Merged)

- even though Theirs < Mine < Base, in strict subsequence sense,
Merged < Theirs.


As a secondary change, I would like to reduce the sizes of
detected conflicts when the change in one file is a pure deletion.
Example:

abcdef (Base)
abc1ef (Mine
af (Theirs)
aCf (Merged)

Here, only the change d -> 1 is a true conflict, and in a graphical
interface such as TortoiseSVN, I would like to see only that single
line conflicted. However, as was pointed out when I suggested
this on our dev IRC, if can be useful to have the context when
editing the conflict in e.g. vim. One suggestion on IRC was to
split the conflict into 3; two not-really-conflicts around the true
conflict. Ideally, the not-really-conflicts would be marked as such
in the diff, which would require an API change.

An alternate way of handling it, however, would be to merely
improve the resolved_diff result for that conflict (which currently
only contains the whole thing as a conflict). This means that a
resolved_diff could also contain diffs of type
svn_diff__type_diff_modified or svn_diff__type_diff_latest, which
is currently not the case. It might be best to add more display
options for the output functions, so an API change might still be
required. Some or all of the output functions would need to be
adjusted to handle these possibilities.

---

If you know of reasons why these changes would be a bad
idea, please provide examples when possible.


Morten Kloster

Re: Improvements to diff3 (merge) performance

[Greg Hudson <gh...@MIT.EDU>]

On Mon, 2011-06-13 at 07:00 -0400, Morten Kloster wrote:
> I assume he has discussed this elsewhere in more detail? The link
> you provided says very little about it (and the ONLY hit for "implicit
> cherrypicking" on Google was your post :-).

Yes, but I'm not sure where any more, unfortunately.  Possibly here:
http://lists.zooko.com/pipermail/revctrl/ but that's a big archive to
look through.

Complicating matters, Codeville merge operates on the entire history of
the two nodes, rather than just a common base.

> As mentioned above, my original proposal was somewhat more
> aggressive than strictly necessary for my purposes.

I think if you limit the merging to strictly larger changes between sync
points, the false negative rate shouldn't go up too much.

>  Also, I think
> the user should be allowed to specify how aggressive the merge
> algorithm should be as an option.

Perhaps, but most users aren't going to want to fiddle with merge
options, so the onus is still on the system to pick a good default.  (It
does help if the options immediately make sense, which they do in this
proposal.  Options like git's "--patience" and "--strategy octopus" are
especially unlikely to be used productively, I would think.)

Re: Improvements to diff3 (merge) performance

[Morten Kloster <mo...@gmail.com>]

On Sun, Jun 12, 2011 at 9:37 PM, Greg Hudson <gh...@mit.edu> wrote:
> My executive summary of your post is that you want diff3 to try to merge
> related, but not identical, changes occuring between a pair of sync
> points.  I'm wary about this for two reasons.
>
> First, the benefit appears to arise chiefly for what Bram Cohen calls
> "implicit cherrypicking" use cases--that is, cases where a change is
> merged and then merged again together with other changes.  After
> extensive research, Bram eventually concluded that trying to support
> this is a bad idea (http://bramcohen.livejournal.com/52148.html).  I
> tend to think that a merge algorithm should not increase its false
> negative rate for the benefit of implicit cherrypicking.
>

I assume he has discussed this elsewhere in more detail? The link
you provided says very little about it (and the ONLY hit for "implicit
cherrypicking" on Google was your post :-).

> Second, I can see a lot of potential for incorrect merges based on
> superficial similarities.  For instance, if you and I both add code
> between the same two sync points, and the last line of my change is the
> same as the first line of yours (perhaps a blank line), that could be
> enough to unambiguously determine an ordering.  Perhaps both of our code
> additions do the same thing in different ways, and now it gets done
> twice (which is almost never desirable).  Certainly, the existing
> algorithm can produce incorrect merges too, but my intuition says that
> the practical likelihood would become much higher.
>

The blank line case is precisely the kind of problem you're likely to run
into also with the current algorithm, unless the project has a strict policy
on when to have blank lines. I'm not too fond of letting blank lines count
as valid matches for that purpose in the first place - see below. I don't
think my proposal would cause too much of an increase in that kind of
problem, but of course there's a risk. I agree that my original proposal
might be too aggressive, though - that was partially a case of "cool, this
approach will do all I wanted and then some"; see below.

> Of course, I could be off base.  All merge algorithms are heuristic, and
> it would take a lot of research to really compare the efficacy of one
> against another.  You need a cost function to determine the tradeoff
> between the false negative rate and the false positive rate, and you
> also need to measure how any given algorithmic change affects the false
> negative and false positive rates in practice.  Both of these seem
> really hard.
>

I don't suppose there would be a not-horribly-complicated/arduous way of
extracting (LOTS OF) merges (base, both changed files, and committed
merge) from the subversion project history, to serve as a somewhat
representative set of test cases? There must be plenty of them, all told...?

> It would definitely affect my opinion if I learned that the three-way
> merge algorithms in other popular version control systems worked this
> way, or if I learned that Subversion was more restrictive than, say, gnu
> diff3.
>
>

Actually, GNU diff3 (at least version 2.9) is a fair bit MORE restrictive:

1. It requires an actual overlap for sync points - it does not allow
adjacent changes.

2. It does not allow common changes; these are considered conflicts.
Only one of Mine and Theirs can be changed between neighboring
sync points.

Ironically, property 1 would precisely have guaranteed that A or B
could merge cleanly with their merge product C (as long as the LCS
matches stayed the same, of course), since the overlap at the sync
point means it could remain a sync point also in C, IF it were not
for property 2, which pretty explicitly disallows merging with the
merge product...

===

As mentioned above, my original proposal was somewhat more
aggressive than strictly necessary for my purposes. Also, I think
the user should be allowed to specify how aggressive the merge
algorithm should be as an option. Here are some possible levels:

1. Cautious: Only merge changes that are separated by at least
X lines, of which at least Y must be unique matches (since diff3
already has counts for the tokens present in each file, checking
for unique matches is now very cheap and simple).

2. Classic: As now.

3. Aggressive: Sync also on commonly deleted sections, and
merge strictly larger changes (when the changes are easily
identified as such). This is similar to my original proposal,
but doesn't attempt to interleave different insertions or to
merge only partially overlapping changes.

4. Reckless: My original proposal.

I see very little to no risk in allowing the merging of strictly
larger changes; this is a natural extension of allowing both
common and adjacent changes. The only significant risk I
see for syncing on commonly deleted sections is if changes
in one or both files are identified by the LCS algorithm as
fragmented conserved sections, due to a lack of unique
tokens; then the different code from the two files could
end up interleaved. One way to avoid this would be to
require conserved sections to be of a certain quality (at least
X lines, not all identical, or at least one unique line) in order
to qualify as sync points - this could be a good idea also
for the "2. Classic" option, in order to avoid erroneous
syncing on blank lines as discussed above. As mentioned
before, it is easy to put such checks in place now, since the
token counts are already available.

===

At the very least, I think diff3 should return resolved_diff
results that are based on such additional sync points,
since that would give GUI clients far better information
for presenting a good line matching, even if the region as
a whole is still marked as a conflict.

---
Morten

Re: Improvements to diff3 (merge) performance

[Greg Hudson <gh...@MIT.EDU>]

My executive summary of your post is that you want diff3 to try to merge
related, but not identical, changes occuring between a pair of sync
points.  I'm wary about this for two reasons.

First, the benefit appears to arise chiefly for what Bram Cohen calls
"implicit cherrypicking" use cases--that is, cases where a change is
merged and then merged again together with other changes.  After
extensive research, Bram eventually concluded that trying to support
this is a bad idea (http://bramcohen.livejournal.com/52148.html).  I
tend to think that a merge algorithm should not increase its false
negative rate for the benefit of implicit cherrypicking.

Second, I can see a lot of potential for incorrect merges based on
superficial similarities.  For instance, if you and I both add code
between the same two sync points, and the last line of my change is the
same as the first line of yours (perhaps a blank line), that could be
enough to unambiguously determine an ordering.  Perhaps both of our code
additions do the same thing in different ways, and now it gets done
twice (which is almost never desirable).  Certainly, the existing
algorithm can produce incorrect merges too, but my intuition says that
the practical likelihood would become much higher.

Of course, I could be off base.  All merge algorithms are heuristic, and
it would take a lot of research to really compare the efficacy of one
against another.  You need a cost function to determine the tradeoff
between the false negative rate and the false positive rate, and you
also need to measure how any given algorithmic change affects the false
negative and false positive rates in practice.  Both of these seem
really hard.

It would definitely affect my opinion if I learned that the three-way
merge algorithms in other popular version control systems worked this
way, or if I learned that Subversion was more restrictive than, say, gnu
diff3.

Re: Improvements to diff3 (merge) performance

[Morten Kloster <mo...@gmail.com>]

Ugh - using "---" to separate sections of the post was clearly a
really bad idea; sorry about that. :-(

Here it is again, in a hopefully more readable format:

Hi,

I'm not very happy with the current performance of the diff3
algorithm; I think it returns too many and too big conflicts. I have
some ideas on how to improve it, but I'd like to hear other people's
opinions first. Note that the primary purpose is to discuss how we
want merge to behave, not whether it is easy to implement.

I'll use the terms Base (original), Mine (modified) and Theirs (latest)
to refer to the three source files. In the merged file, C indicates a
conflict.

===

First, here's a quick run-though of how diff3 works now: After
running LCS on Base vs. Mine and Base vs. Theirs, it looks for
"sync points" - points where both Mine and Theirs match the Base.
Note that there is no need for an actual overlap: If Mine matches
Base up to a point and Theirs matches Base from that point
onwards, that is a valid sync point. If no two of the three are
identical between two neighboring sync points, that creates a
conflict.

Adjacent changes are accepted:

abcd (Base)
a1cd (Mine)
ab2d (Theirs)
a12d (Merged)

and

abcd (Base)
acd (Mine)
abc (Theirs)
ad (Merged)

while strictly larger changes are not:

abcd (Base)
a1cd (Mine)
a12d (Theirs)
aCd (Merged)

and

abcd (Base)
acd (Mine)
ad (Theirs)
aCd (Merged)

Note that this means that if changed files A and B are merged to
produce C, then attempting to merge A (or B) with C could well
produce a conflict (using the same Base the whole time), whereas
in my opinion, that ought to work fine, yielding C again.

===

My proposed main change is to let diff3 also sync on points where
Mine and Theirs have identical changes relative to Base, if either file
(Mine or Theirs) can also be synced to Base at the same point. This
can happen if either Mine or Theirs is unchanged from Base either
before or after that point, or if either of the changes from Base was a
pure insertion (as there is then no uncertainty as to the position in
the Base file). This would let diff3 incorporate all changes relative to
Base from both Mine and Theirs as long as there is no true conflict.

Some consequences:

Given two changed files A and B that only have deletions relative to
Base, the merged file would only contain the lines that are present
in both A and B.

Different insertions would be merged, not marked as conflict,
unless they truly conflict. There are only true conflicts if the diff2
between the two insertions have actual changes, not just separated
deletions and insertions (or equivalently, if the LCS has gaps in
both files between neighboring segments):

ag (Base)
abcefg (Mine)
acdeg (Theirs)
abcdefg (Merged)

Here, the order of the inserted lines is unambiguously determined;
partially from Mine and partially from Theirs.

Incremental and overlapping changes would merge cleanly:

abcde (Base)
a12de (Mine)
ab23e (Theirs)
a123e (Merged)

Of course there are cases where the merged result might not be
what would be desired, but that is also the case with the current
algorithm - keep in mind that any conflict can be "resolved" by
inserting blank lines in Base, Mine and Theirs to serve as sync
points. Here's an unfortunate case with the current algorithm:

abcbcd (Base)
acbcd (Mine)
abcd (Theirs)
acd (Merged)

- even though Theirs < Mine < Base, in strict subsequence sense,
Merged < Theirs.


As a secondary change, I would like to reduce the sizes of
detected conflicts when the change in one file is a pure deletion.
Example:

abcdef (Base)
abc1ef (Mine
af (Theirs)
aCf (Merged)

Here, only the change d -> 1 is a true conflict, and in a graphical
interface such as TortoiseSVN, I would like to see only that single
line conflicted. However, as was pointed out when I suggested
this on our dev IRC, if can be useful to have the context when
editing the conflict in e.g. vim. One suggestion on IRC was to
split the conflict into 3; two not-really-conflicts around the true
conflict. Ideally, the not-really-conflicts would be marked as such
in the diff, which would require an API change.

An alternate way of handling it, however, would be to merely
improve the resolved_diff result for that conflict (which currently
only contains the whole thing as a conflict). This means that a
resolved_diff could also contain diffs of type
svn_diff__type_diff_modified or svn_diff__type_diff_latest, which
is currently not the case. It might be best to add more display
options for the output functions, so an API change might still be
required. Some or all of the output functions would need to be
adjusted to handle these possibilities.

===

If you know of reasons why these changes would be a bad
idea, please provide examples when possible.


Morten Kloster