[PATCH] combine-diff: coalesce lost lines optimally

2013-03-17 Thread Antoine Pelisse
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

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

2013-03-17 Thread Antoine Pelisse
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 ? OK, creating the merge commit myself solves the issue: git init test git add test git commit -m initial seq 100 test git

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

2013-03-17 Thread Junio C Hamano
Antoine Pelisse apeli...@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

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

2013-03-17 Thread Antoine Pelisse
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 (1) 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

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

2013-03-17 Thread Junio C Hamano
Antoine Pelisse apeli...@gmail.com writes: +/* Coalesce new lines into base by finding LCS */ +static struct lline *coalesce_lines(struct lline *base, int *lenbase, + struct lline *new, int lennew, + unsigned long parent) +{