Re: [PATCH] combine-diff: coalesce lost lines optimally
Antoine Pelisse 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)
> +{
Don't you want to pass flags so that you can use match_string_spaces()
at places like this:
> + for (i = 1, baseend = base; i < origbaselen + 1; i++) {
> + for (j = 1, newend = new; j < lennew + 1; j++) {
> + if (baseend->len == newend->len &&
> + !memcmp(baseend->line, newend->line, baseend->len))
> {
IOW, it looks to me that this wants to be rebuilt on top of
fa04ae0be8cc (Allow combined diff to ignore white-spaces,
2013-03-14).
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
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 (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 17, 2013 at 9:10 PM, Junio C Hamano wrote: > Antoine Pelisse 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 >> --- >> 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 -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] combine-diff: coalesce lost lines optimally
Antoine Pelisse 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 > --- > 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 -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] combine-diff: coalesce lost lines optimally
> 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 commit -m all -a git checkout -b side1 HEAD^1 seq 1 2 100 >test git commit -m side1 -a git checkout -b side2 HEAD^1 seq 1 4 100 >test git commit -m side2 -a git checkout -b side3 HEAD^1 seq 1 8 100 >test git commit -m side3 -a git checkout -b side4 HEAD^1 seq 1 16 100 >test git commit -m side4 -a git checkout master >test git add test TREE=$(git write-tree) COMMIT=$(git commit-tree $TREE -p master -p side1 -p side2 -p side3 -p side4 -m merge) git show $COMMIT This will work with the basic greedy implementation if all parents are in this order. But the optimal result will be lost if we change the order of -p parameters in git-commit-tree. The patch seems to be correct, always finding the best result (we always have 100 lines diff) whatever the order of parents. -- To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
