Re: git annotate runs out of memory

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Dec 12, 2007, 00:02 UTC
Message-ID: <alpine.LFD.0.9999.0712111548200.25032@woody.linux-foundation.org>
In-Reply-To: <alpine.LFD.0.9999.0712111523210.25032@woody.linux-foundation.org>

On Tue, 11 Dec 2007, Linus Torvalds wrote:

> 
> and while I suspect xdiff could be optimized a bit more for the cases 
> where we have no changes at the end, that's beyond my skills.

Ok, I lied.

Nothing is beyond my skills. My mad k0der skillz are unbeatable.

This speeds up git-blame on ChangeLog-style files by a big amount, by just ignoring the common end that we don't care about, since we don't want any context anyway at that point. So I now get:

	[torvalds@woody gcc]$ time git blame gcc/ChangeLog > /dev/null

	real    0m7.031s
	user    0m6.852s
	sys     0m0.180s

which seems quite reasonable, and is about three times faster than trying to diff those big files.

Davide: this really _does_ make a huge difference. Maybe xdiff itself 
should do this optimization on its own, rather than have the caller hack 
around the fact that xdiff doesn't handle this common case all that well?

The same thing obviously works for the beginning-of-file too, but then you have to play games with line numbers being affected etc, so the end is the rather much easier case and is the case that a ChangeLog-style file cares about.

Daniel, this is obviously on top of the patches that fix the memory leak.

			Linus

---

diff --git a/builtin-blame.c b/builtin-blame.c
index c158d31..677188c 100644
--- a/builtin-blame.c
+++ b/builtin-blame.c
@@ -543,6 +551,20 @@ static struct patch *compare_buffer(mmfile_t *file_p, mmfile_t *file_o,
 	return state.ret;
 }
 
+#define BLOCK 1024
+
+static void truncate_common_data(mmfile_t *a, mmfile_t *b)
+{
+	long l1 = a->size, l2 = b->size;
+
+	while ((l1 -= BLOCK) > 0 && (l2 -= BLOCK) > 0) {
+		if (memcmp(a->ptr + l1, b->ptr + l2, BLOCK))
+			break;
+		a->size = l1;
+		b->size = l2;
+	}
+}
+
 /*
  * Run diff between two origins and grab the patch output, so that
  * we can pass blame for lines origin is currently suspected for
@@ -557,6 +579,7 @@ static struct patch *get_patch(struct origin *parent, struct origin *origin)
 	fill_origin_blob(origin, &file_o);
 	if (!file_p.ptr || !file_o.ptr)
 		return NULL;
+	truncate_common_data(&file_p, &file_o);
 	patch = compare_buffer(&file_p, &file_o, 0);
 	num_get_patch++;
 	return patch;