Re: [PATCH 2/2] Implement a simple delta_base cache

Linus Torvalds [off-list ref] writes:

ie, we still re-generate some of the objects multiple times, but now, 
rather than generating them (on average) 20+ times each, we now generate 
them an average of just 1.3 times each. Which explains why the wall-time 
goes down by over a factor of two.

This is beautiful.  You only cache what we were about to discard
anyway, and when giving a cached one out, you invalidate the
cached entry, so there is no way the patch can introduce leaks
nor double-frees and it is absolutely safe (as long as we can
pin the packed_git structure, which I think is the case --- even
when we re-read the packs, I do not think we discard old ones).

I've thought about possible ways to improve on it, but came up
almost empty.

When unpacking a depth-3 deltified object A, the code finds the
target object A (which is a delta), ask for its base B and put B
in the cache after using it to reconstitute A.  While doing so,
the first-generation base B is also a delta so its base C (which
is a non-delta) is found and placed in the cache.  When A is
returned, the cache has B and C.  If you ask for B at this
point, we read the delta, pick up its base C from the cache,
apply, and return while putting C back in the cache.  If you ask
for A after that, we do not read from the cache, although it is
available.

Which feels a bit wasteful at first sight, and we *could* make
read_packed_sha1() also steal from the cache, but after thinking
about it a bit, I am not sure if it is worth it.  The contract
between read_packed_sha1() and read_sha1_file() and its callers
is that the returned data belongs to the caller and it is a
responsibility for the caller to free the buffer, and also the
caller is free to modify it, so stealing from the cache from
that codepath means an extra allocation and memcpy.  If the
object stolen from the cache is of sufficient depth, it might be
worth it, but to decide it we somehow need to compute and store
which delta depth the cached one is at.

In any way, your code makes a deeply delitified packfiles a lot
more practical.  As long as the working set of delta chains fits
in the cache, after unpacking the longuest delta, the objects on
the chain can be had by one lookup and one delta application.

Very good job.

In general, this all seems very cool. The patches are simple enough that I 
think this is very safe to merge indeed: the only question I have is that 
somebody should verify that the "struct packed_git *p" is stable over the 
whole lifetime of a process - so that we can use it as a hash key without 
having to invalidate hashes if we unmap a pack (I *think* we just unmap 
the virtual mapping, and "struct packed_git *" stays valid, but Junio 
should ack that for me).

Ack ;-)

On Sat, 17 Mar 2007, Junio C Hamano wrote:

When unpacking a depth-3 deltified object A, the code finds the
target object A (which is a delta), ask for its base B and put B
in the cache after using it to reconstitute A.  While doing so,
the first-generation base B is also a delta so its base C (which
is a non-delta) is found and placed in the cache.  When A is
returned, the cache has B and C.  If you ask for B at this
point, we read the delta, pick up its base C from the cache,
apply, and return while putting C back in the cache.  If you ask
for A after that, we do not read from the cache, although it is
available.

Yes.

I debated that a bit with myself, but decided that:

 (a) it probably doesn't really matter a lot (but I don't have the 
     numbers)

 (b) trying to *also* fill non-delta-base queries from the delta-base 
     cache actually complicates things a lot. Surprisingly much so (the 
     current logic of removing the entry from the cache only to re-insert 
     it after being used made the memory management totally trivial, as 
     you noticed)

 (c) and regardless, we could decide to do a more extensive caching layer 
     later if we really wanted to, and at that point it probably makes 
     more sense to integrate it with the delta-base cache.

     Most git objects are use-once, which is why we really *just* save the 
     flag bits and the SHA1 hash name itself in "struct object", but doing 
     a generic caching layer for object content would likely obviate the 
     need for the current logic to do "save_commit_buffer".

That (c) in particular was what made me think that it's better to keep it 
simple and obvious for now, since even the simple thing largely fixes the 
performance issue.  Almost three seconds I felt bad about, while just over 
a second for something as complex as "git log drivers/usb/" I just cannot 
make myself worry about.

In any way, your code makes a deeply delitified packfiles a lot
more practical.  As long as the working set of delta chains fits
in the cache, after unpacking the longuest delta, the objects on
the chain can be had by one lookup and one delta application.

Yeah. I think it would be good to probably (separately and as "further 
tweaks"):

 - have somebody actually look at hit-rates for different repositories and 
   hash sizes.

 - possibly allow people to set the hash size as a config option, if it 
   turns out that certain repository layouts or usage scenarios end up 
   preferring bigger caches.

   For example, it may be that for historical archives you might want to 
   have deeper delta queues to make the repository smaller, and if they 
   are big anyway maybe they would prefer to have a larger-than-normal 
   cache as a result. On the other hand, if you are memory-constrained, 
   maybe you'd prefer to re-generate the objects and waste a bit of CPU 
   rather than cache the results.

But neither of the above is really an argument against the patch, just a 
"there's certainly room for more work here if anybody cares".

Very good job.

I'm pretty happy with the results myself. Partly because the patches just 
ended up looking so *nice*.

		Linus

On Sat, 17 Mar 2007, Linus Torvalds wrote:

 (a) it probably doesn't really matter a lot (but I don't have the 
     numbers)

Well, to some degree I obviously *do* have the numbers.

I have the numbers that we used to re-generate the object data over five 
*hundred* times per object for some cases, and that I got the average 
such delta-base usage down from 20x to 1.1-1.3x depending on cache size.

In contrast, the "use delta-base also for non-delta queries" fairly 
obviously cannot touch those kinds of numbers. We migth avoid a *few* 
object generation cases, but we're not looking at factors of 20 for any 
kind of sane cases.

So I do think that a higher-level caching approach can work too, but it's 
going to be more effective in other areas:

 - get rid of some ugly hacks (like the "save_commit_buffer" thing I 
   mentioned)
 - possibly help some insane loads (eg cases where we really *do* end up 
   seeing the same object over and over again, perhaps simply because some 
   idiotic automated commit system ends up switching between a few states 
   back-and-forth).

I really think the "insane loads" thing is unlikely, but I could construct 
some crazy usage scenario where a cache of objects in general (and not 
just delta bases) would work. I don't think it's a very realistic case, 
but who knows - people sometimes do really stupid things.

		Linus

On Sat, 17 Mar 2007, Junio C Hamano wrote:

When unpacking a depth-3 deltified object A, the code finds the
target object A (which is a delta), ask for its base B and put B
in the cache after using it to reconstitute A.  While doing so,
the first-generation base B is also a delta so its base C (which
is a non-delta) is found and placed in the cache.  When A is
returned, the cache has B and C.  If you ask for B at this
point, we read the delta, pick up its base C from the cache,
apply, and return while putting C back in the cache.  If you ask
for A after that, we do not read from the cache, although it is
available.

Which feels a bit wasteful at first sight, and we *could* make
read_packed_sha1() also steal from the cache, but after thinking
about it a bit, I am not sure if it is worth it.  The contract
between read_packed_sha1() and read_sha1_file() and its callers
is that the returned data belongs to the caller and it is a
responsibility for the caller to free the buffer, and also the
caller is free to modify it, so stealing from the cache from
that codepath means an extra allocation and memcpy.

So?

A malloc() + memcpy() will always be faster than mmap() + malloc() + 
inflate().  If the data is already there it is certainly better to copy 
it straight away.

With the patch below I can do 'git log drivers/scsi/ > /dev/null' about 
7% faster.  I bet it might be even more on those platforms with bad 
mmap() support.

Signed-off-by: Nicolas Pitre <redacted>
---

diff --git a/sha1_file.c b/sha1_file.c
index a7e3a2a..ee64865 100644
--- a/sha1_file.c
+++ b/sha1_file.c

@@ -1372,7 +1372,7 @@ static unsigned long pack_entry_hash(struct packed_git *p, off_t base_offset)
 }
 
 static void *cache_or_unpack_entry(struct packed_git *p, off_t base_offset,
-	unsigned long *base_size, enum object_type *type)
+	unsigned long *base_size, enum object_type *type, int keep_cache)
 {
 	void *ret;
 	unsigned long hash = pack_entry_hash(p, base_offset);

@@ -1384,7 +1384,13 @@ static void *cache_or_unpack_entry(struct packed_git *p, off_t base_offset,
 	return unpack_entry(p, base_offset, type, base_size);
 
 found_cache_entry:
-	ent->data = NULL;
+	if (!keep_cache)
+		ent->data = NULL;
+	else {
+		ret = xmalloc(ent->size + 1);
+		memcpy(ret, ent->data, ent->size);
+		((char *)ret)[ent->size] = 0;
+	}
 	*type = ent->type;
 	*base_size = ent->size;
 	return ret;

@@ -1418,7 +1424,7 @@ static void *unpack_delta_entry(struct packed_git *p,
 	off_t base_offset;
 
 	base_offset = get_delta_base(p, w_curs, &curpos, *type, obj_offset);
-	base = cache_or_unpack_entry(p, base_offset, &base_size, type);
+	base = cache_or_unpack_entry(p, base_offset, &base_size, type, 0);
 	if (!base)
 		die("failed to read delta base object"
 		    " at %"PRIuMAX" from %s",

@@ -1615,7 +1621,7 @@ static void *read_packed_sha1(const unsigned char *sha1,
 	if (!find_pack_entry(sha1, &e, NULL))
 		return NULL;
 	else
-		return unpack_entry(e.p, e.offset, type, size);
+		return cache_or_unpack_entry(e.p, e.offset, size, type, 1);
 }
 
 /*