using xdl_merge(), was Re: Resolving conflicts

From: Johannes Schindelin <johannes.schindelin@gmx.de>
Date: Dec 2, 2006, 10:49 UTC
Message-ID: <Pine.LNX.4.63.0612021131140.28348@wbgn013.biozentrum.uni-wuerzburg.de>
In-Reply-To: <7vejri20mf.fsf@assigned-by-dhcp.cox.net>

Hi,

On Fri, 1 Dec 2006, Junio C Hamano wrote:

Show 17 quoted lines

> Linus Torvalds <torvalds@osdl.org> writes:
> 
> > [ Tangentially related.. ]
> >
> > On Thu, 30 Nov 2006, Wink Saville wrote:
> >> 
> >> Earlier had a problem with git wanting merge but didn't have it and
> >> couldn't figure out which package it was in Ubuntu:( So I symlinked merge
> >> to kdiff3 which worked at the time:
> >
> > Btw, what's the status of the xdl_merge() thing in "pu"?
> 
> I haven't looked at the code any further than minimally checking
> its external interface to be able to interface it with
> merge-recursive and no more.  Namely:
> 
>  - I haven't read the algorithm to judge its correctness;

With my track record of blamable patches, that should be done by somebody else than me.

>  - I haven't looked for leaks;

Neither have I.

>  - I haven't used the resulting merge-recursive in any real
>    merge; some of our tests do rely on a correctly working
>    merge-recursive, so it is not like the algorithm is always
>    emitting "boo ha ha" and returning no conflicts ;-).

I have. There is a subtle difference to merge, but it might be serious enough:

diff --just-made-up orig new1
 Hello world
+This conflicts
 Bye bye world
+This does not conflict

diff --just-made-up orig new2
 Hello world
+This is different in new2
 Bye bye world

If my interpretation of the test is correct, then the last line of new1 will _not_ conflict with xdl_merg( as is, but with RCS merge. I will fix that shortly.

>  - I haven't benched it to see how much performance is gained
>    by bypassing an extra fork+exec.

There is room for improvement, but I get shaky numbers betwen 31% and 118% (runtime git-merge-recursive xdl_merge() / RCS merge). These are extremely ad-hoc generated numbers, so handle with care. My gut feeling is that a few improvements in the code will give a rough 30%-50% in the average case.

These improvements include not parsing orig twice, and compacting the merge script before applying it.

> Among the four patches Johannes sent out to the list and Davide,
> one was already in his original patch I have in 'pu', another
> makes the same return value change I did myself when interfacing
> the code with merge-recursive.

Yeah, sorry. When I sent the patches, I did not see xdl_merge() in pu.

Show 12 quoted lines

> I have queued the remaining two in 'pu', so there should be nothing 
> missing.
> 
> One of them is marked as "fix off by one error" but it was about
> more than off by one (the code walks two arrays using one index
> for each, but the original code incorrectly used the same index
> to access both arrays at one point, which was also fixed).  I
> did mind the lack of explanation and wanted to reword the log
> message, but as I said, I haven't read the algorithm to
> understand what the code is doing enough, so I cannot write
> anything useful there yet X-<, which is one of the reasons why
> it is still queued in 'pu'.

Sorry again. I fixed that bug in the middle of the night, and committed the next day, trying to deduct what I fixed.

Again, I do not see the patches in pu, though. I will concoct a nice commit message later today, okay?

Linus, you raised the concern that git-cvsserer still relies on external merge. I'd just bastardize git-merge-one-file to work as a replacement of RCS merge (just like git apply works as a replacement of patch), in addition to its original function.

Ciao, Dscho