aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJunio C Hamano <gitster@pobox.com>2009-07-22 14:48:28 -0700
committerJunio C Hamano <gitster@pobox.com>2009-07-22 15:37:55 -0700
commit55d5d5bab7c3f9ab6310b9cf436a7935d7d32165 (patch)
treecf01cae48bc434249284890c0fab469504504600
parent78d3b06e0f5e6aaea001ee8e3e7c8e401dc4b244 (diff)
downloadgit-55d5d5bab7c3f9ab6310b9cf436a7935d7d32165.tar.gz
git-55d5d5bab7c3f9ab6310b9cf436a7935d7d32165.tar.xz
combine-diff.c: fix performance problem when folding common deleted lines
For a deleted line in a patch with the parent we are looking at, the append_lost() function finds the same line among a run of lines that were deleted from the same location by patches from parents we previously checked. This is so that patches with two parents @@ -1,4 +1,3 @@ @@ -1,4 +1,3 @@ one one -two -two three three -quatro -fyra +four +four can be coalesced into this sequence, reusing one line that describes the removal of "two" for both parents. @@@ -1,4 -1,4 +1,3 @@@ one --two three - quatro -frya ++four While reading the second patch (that removes "two" and then "fyra"), after finding where removal of the "two" matches, we need to find existing removal of "fyra" (if exists) in the removal list, but the match has to happen after all the existing matches (in this case "two"). The code used a naïve O(n^2) algorithm to compute this by scanning the whole removal list over and over again. This patch remembers where the next scan should be started in the existing removal list to avoid this. Noticed by Linus Torvalds. Signed-off-by: Junio C Hamano <gitster@pobox.com>
-rw-r--r--combine-diff.c13
1 files changed, 5 insertions, 8 deletions
diff --git a/combine-diff.c b/combine-diff.c
index 60d03676b..b82f46cc6 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)