Re: [RFC] Cache negative delta pairs

From: Jeff King <peff@peff.net>
Date: Jun 29, 2006, 04:30 UTC
Message-ID: <20060629043053.GA32630@coredump.intra.peff.net>
In-Reply-To: <20060629035849.GA30749@coredump.intra.peff.net>

On Wed, Jun 28, 2006 at 11:58:49PM -0400, Jeff King wrote:

Show 5 quoted lines

>    about 2.7M. The linux-2.6 cache is 22M.
>    [...]
>  - correctness. Currently the code uses the output of try_delta for
>    negative caching. Should the cache checking be moved inside try_delta
>    instead? This would give more control over which reasons to mark a

I tried moving the cache check/mark to wrap the call to create_delta in try_delta. The speedup is the same (since all of the CPU time is spent in create_delta anyway), and the linux-2.6 cache size dropped to 18M. I also think this is probably more correct (it ignores every reason not to delta EXCEPT create_delta failing).

The distribution of the window parameter 'j' is similarly uniform:
  44900 j=2
  44907 j=3
  44943 j=1
  45001 j=4
  45014 j=5
  45023 j=6
  45063 j=7
  45158 j=8
  45288 j=9
  45466 j=10

Patch on top of my other one is below.

-Peff

-- >8 -- pack-objects: move delta-cache check/mark closer to create_delta

Signed-off-by: Jeff King <peff@peff.net>
---
 pack-objects.c |   15 ++++++---------
 1 files changed, 6 insertions(+), 9 deletions(-)

diff --git a/pack-objects.c b/pack-objects.c
index 46b9775..83ccc8a 100644
--- a/pack-objects.c
+++ b/pack-objects.c
@@ -1014,9 +1014,13 @@ static int try_delta(struct unpacked *tr
 	if (sizediff >= max_size)
 		return 0;
 
+	if (delta_cache_check(src->entry->sha1, trg->entry->sha1))
+		return 0;
 	delta_buf = create_delta(src_index, trg->data, size, &delta_size, max_size);
-	if (!delta_buf)
+	if (!delta_buf) {
+		delta_cache_mark(src->entry->sha1, trg->entry->sha1);
 		return 0;
+	}
 
 	trg_entry->delta = src_entry;
 	trg_entry->delta_size = delta_size;
@@ -1084,21 +1088,14 @@ static void find_deltas(struct object_en
 		j = window;
 		while (--j > 0) {
 			unsigned int other_idx = idx + j;
-			int r;
 			struct unpacked *m;
 			if (other_idx >= window)
 				other_idx -= window;
 			m = array + other_idx;
 			if (!m->entry)
 				break;
-			if (delta_cache_check(n->entry->sha1, m->entry->sha1))
-				continue;
-			r = try_delta(n, m, m->index, depth);
-			if (r < 0)
+			if (try_delta(n, m, m->index, depth) < 0)
 				break;
-			if (r == 0)
-				delta_cache_mark(n->entry->sha1,
-						 m->entry->sha1);
 		}
 		/* if we made n a delta, and if n is already at max
 		 * depth, leaving it in the window is pointless.  we

-- 
1.4.1.rc1.g0458-dirty