[svn.haxx.se] · SVN Dev · SVN Users · SVN Org · TSVN Dev · TSVN Users · Subclipse Dev · Subclipse Users · this month's index

Re: Improvements to diff3 (merge) performance

From: Greg Hudson <ghudson_at_MIT.EDU>
Date: Sun, 12 Jun 2011 15:37:06 -0400

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
Received on 2011-06-12 21:37:46 CEST

This is an archived mail posted to the Subversion Dev mailing list.

This site is subject to the Apache Privacy Policy and the Apache Public Forum Archive Policy.