Linus Torvalds <torvalds@xxxxxxxxxxxxxxxxxxxx> writes:
> On Tue, 21 Jul 2009, Junio C Hamano wrote:
>>
>> Here is a patch to do that. I haven't tested it yet though.
>
> Well, it seems to work.
>
> It turned the 85+ minute thing (which I eventually just killed) into
> something that took 1.4 _seconds_. Of course, I didn't check that the end
> result was identical, since I never had the patience to wait for the
> original case.
>
> Now sadly, my fixed test (which took 45 seconds before) didn't much
> improve (it doesn't have nearly as many removed lines, since I checked in
> the _right_ file that is a much closer version to the parent files).
>
> But what is intriguing is that it it gets different results. So I suspect
> this one actually changed behavior some way:
>
> [torvalds@nehalem git-merge]$ time git show --color HEAD | wc
> 22671 63302 672234
>
> real 0m44.024s
> user 0m43.879s
> sys 0m0.148s
>
> [torvalds@nehalem git-merge]$ time ~/git/git show --color HEAD | wc
> 22596 63122 671076
>
> real 0m43.553s
> user 0m43.435s
> sys 0m0.128s
>
> and notice how the git version with your change gives different line
> numbers.
>
> Now, this is a diff, and different answers are possibly _both_ valid, so
> who knows. But I suspect that you _intended_ for the patch to be a
> semantic no-op, and it doesn't seem to be.
I know why. The conversion was wrong. The original found the last_one
that was from the parent we are looking at, and when there is such, it
started the scan from the one _after that_. Otherwise, if lost_head list
had an entry
@@ -l,k +m,n @@
-one
two
three
and the diff with the parent we are currently looking at duplicates
removal:
@@ -l,k +m1,n1 @@
-one
-one
two
three
we will end up losing the second removal, which would be what is happening
with the patch you tried.
I actually was scratching my head wondering why it wasn't happening in the
original code after I sent that faulty patch.
Here is another attempt.
combine-diff.c | 13 +++++--------
1 files changed, 5 insertions(+), 8 deletions(-)
diff --git a/combine-diff.c b/combine-diff.c
index bbf74fc..2438490 100644
--- a/combine-diff.c
+++ b/combine-diff.c
@@ -80,6 +80,7 @@ struct lline {
/* Lines surviving in the merge result */
struct sline {
struct lline *lost_head, **lost_tail;
+ struct lline *next_lost;
char *bol;
int len;
/* bit 0 up to (N-1) are on if the parent has this line (i.e.
@@ -121,18 +122,12 @@ static void append_lost(struct sline *sline, int n, const char *line, int len)
/* Check to see if we can squash things */
if (sline->lost_head) {
- struct lline *last_one = NULL;
- /* We cannot squash it with earlier one */
- for (lline = sline->lost_head;
- lline;
- lline = lline->next)
- if (lline->parent_map & this_mask)
- last_one = lline;
- lline = last_one ? last_one->next : sline->lost_head;
+ lline = sline->next_lost;
while (lline) {
if (lline->len == len &&
!memcmp(lline->line, line, len)) {
lline->parent_map |= this_mask;
+ sline->next_lost = lline->next;
return;
}
lline = lline->next;
@@ -147,6 +142,7 @@ static void append_lost(struct sline *sline, int n, const char *line, int len)
lline->line[len] = 0;
*sline->lost_tail = lline;
sline->lost_tail = &lline->next;
+ sline->next_lost = NULL;
}
struct combine_diff_state {
@@ -187,6 +183,7 @@ static void consume_line(void *state_, char *line, unsigned long len)
xcalloc(state->num_parent,
sizeof(unsigned long));
state->sline[state->nb-1].p_lno[state->n] = state->ob;
+ state->lost_bucket->next_lost = state->lost_bucket->lost_head;
return;
}
if (!state->lost_bucket)
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html