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

From: Antoine Pelisse <apelisse@gmail.com>
Date: Mar 17, 2013, 20:37 UTC
Message-ID: <CALWbr2yfgA8kvtn4yxzPD5cencAPmwMqx=A6n4ohsjdzfAE1bQ@mail.gmail.com>
In-Reply-To: <7vhak9rdne.fsf@alter.siamese.dyndns.org>

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 <gitster@pobox.com> wrote:

Show 31 quoted lines

> Antoine Pelisse <apelisse@gmail.com> writes:
>
>> 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 <apelisse@gmail.com>
>> ---
>> 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