Re: git annotate runs out of memory

From: Jeff King <peff@peff.net>
Date: Dec 12, 2007, 07:57 UTC
Message-ID: <20071212075725.GA7676@coredump.intra.peff.net>
In-Reply-To: <alpine.LFD.0.9999.0712111146200.25032@woody.linux-foundation.org>

On Tue, Dec 11, 2007 at 11:50:08AM -0800, Linus Torvalds wrote:

Show 10 quoted lines

> And, btw: the diff is totally different from the xdelta we have, so even 
> if we have an already prepared nice xdelta between the two versions, we'll 
> end up re-generating the files in full, and then do a diff on the end 
> result.
> 
> Of course, part of that is that git logically *never* works with deltas, 
> except in the actual code-paths that generate objects (or generate packs, 
> of course). So even if we had used a delta algorithm that would be 
> amenable to be turned into a diff directly, it would have been a layering 
> violation to actually do that.

That doesn't mean we can't opportunistically jump layers when available, and fall back on the regular behavior otherwise. The nice thing about clean and simple layers is that you can always add optimizations later by poking sane holes.

Let's assume for the sake of argument that we can convert an xdelta into a diff fairly cheaply. Using the patch below, we can count the places where we are diffing two blobs, and one blob is a delta base of the other (assuming our magical conversion function can also reverse diffs. ;) ).

For a "git log -p" on git.git, I get:

   9951 diffs could be optimized
  10958 diffs could not be optimized

or about 48%. It would be nice if we could drop the cost by almost 50% (if our magical function is free to call, too!).

Of course, I haven't even looked at whether converting xdeltas to unified diffs is possible. I suspect in some cases it is (e.g., pure addition of text) and in some cases it isn't (I assume xdelta doesn't have any context lines, which might hurt). And it's possible that a specialized diff user like git-blame can just learn to use the xdeltas by itself (I didn't get a "could optimize" count for git-blame since it seems to follow a different codepath for its diffs).

---

diff --git a/cache.h b/cache.h
index 27d90fe..0d672be 100644
--- a/cache.h
+++ b/cache.h
@@ -569,6 +569,7 @@ extern void *unpack_entry(struct packed_git *, off_t, enum object_type *, unsign
 extern unsigned long unpack_object_header_gently(const unsigned char *buf, unsigned long len, enum object_type *type, unsigned long *sizep);
 extern unsigned long get_size_from_delta(struct packed_git *, struct pack_window **, off_t);
 extern const char *packed_object_info_detail(struct packed_git *, off_t, unsigned long *, unsigned long *, unsigned int *, unsigned char *);
+extern int have_xdelta(unsigned char from[20], unsigned char to[20]);
 extern int matches_pack_name(struct packed_git *p, const char *name);
 
 /* Dumb servers support */
diff --git a/diff.c b/diff.c
index f780e3e..5402900 100644
--- a/diff.c
+++ b/diff.c
@@ -1299,6 +1299,10 @@ static void builtin_diff(const char *name_a,
 		}
 	}
 
+	fprintf(stderr, "could optimize: %s\n",
+			(have_xdelta(one->sha1, two->sha1) ||
+			have_xdelta(two->sha1, one->sha1)) ? "yes" : "no");
+
 	if (fill_mmfile(&mf1, one) < 0 || fill_mmfile(&mf2, two) < 0)
 		die("unable to read files to diff");
 
diff --git a/sha1_file.c b/sha1_file.c
index b0c2435..f811ddc 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -2422,3 +2422,20 @@ int read_pack_header(int fd, struct pack_header *header)
 		return PH_ERROR_PROTOCOL;
 	return 0;
 }
+
+int have_xdelta(unsigned char from[20], unsigned char to[20])
+{
+	struct pack_entry e;
+	unsigned char base_sha1[20];
+	const char *type;
+	unsigned long size;
+	unsigned long store_size;
+	unsigned int delta_chain_length;
+
+	if (!find_pack_entry(to, &e, NULL))
+		return 0;
+
+	type = packed_object_info_detail(e.p, e.offset, &size, &store_size,
+					 &delta_chain_length, base_sha1);
+	return !hashcmp(base_sha1, from);
+}