Re: git annotate runs out of memory

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;