Re: [PATCH] combine-diff: coalesce lost lines optimally

Hopefully, my patch takes about the same time as git 1.7.9.5 and
produces the same output on that commit ;)
Unfortunately on a commit that would remove A LOT of lines (10000)
from 7 parents, the times goes from 0.01s to 1.5s... I'm pretty sure
that scenario is quite uncommon though.

On Sun, Mar 17, 2013 at 9:10 PM, Junio C Hamano [off-list ref] wrote:

Antoine Pelisse [off-list ref] writes:

quoted

This replaces the greedy implementation to coalesce lost lines by using
dynamic programming to find the Longest Common Subsequence.

The O(n²) time complexity is obviously bigger than previous
implementation but it can produce shorter diff results (and most likely
easier to read).

List of lost lines is now doubly-linked because we reverse-read it when
reading the direction matrix.

Signed-off-by: Antoine Pelisse <redacted>
---
Hi,
This is a very first draft for improving the way we coalesce lost
lines. It has only been tested with the two scenarios below.

What is left to do:
- Test it more extensively
- Had some tests scenarios

I'm also having a hard time trying it with more than two parents. How I
am supposed to have more than two parents while octopus merge refuses if
there are conflicts ?

9fdb62af92c7 ([ACPI] merge 3549 4320 4485 4588 4980 5483 5651 acpica
asus fops pnpacpi branches into release, 2006-01-24) is one of the
amusing examples ;-)  Cf.

    http://thread.gmane.org/gmane.comp.version-control.git/15486