Re: cleaner/better zlib sources?

From: Nicolas Pitre <nico@cam.org>
Date: Mar 17, 2007, 03:28 UTC
Message-ID: <alpine.LFD.0.83.0703162257560.18328@xanadu.home>
In-Reply-To: <Pine.LNX.4.64.0703161722360.3910@woody.linux-foundation.org>

On Fri, 16 Mar 2007, Linus Torvalds wrote:

Show 12 quoted lines

> The way we unpack delta chains is that we do
> 
>  - find a delta
>  - we apply it to "recursively unpack the thing it's a delta to"
> 
> which sounds totally obvious and straightforward, right?
> 
> EXCEPT it's actually O(n**2) in the delta depth, because we never save the 
> intermediate results, so when we have a delta depth of 10 (our default), 
> and we decode a lot of these things, we basically will look up the base 
> object 10 times, apply the first delta 9 times, apply the second delta 8 
> times, etc etc..

In the worst case, yes. And if you're walking history then the probability of hitting the worst case eventually is rather high.

Show 8 quoted lines

> I also didn't worry about it, because I felt that if it became a problem, 
> it would be easy to just add a cache of base objects (we probably do *not* 
> want to keep the whole unpacked object info in memory all the time just 
> because of memory pressure issues, so "cache of base objects" is better). 
> However, the "pack file + offset" thing makes it harder to do, since we 
> now don't even have the SHA1 of the base object before we unpack it.
> 
> But I guess we could just index this by a <packfile, offset> tuple.

Right. Should be really trivial to hook into unpack_delta_entry() actually replacing the call to unpack_entry() with a wrapper function that returns cached data, or populates the cache with unpack_entry() when no match is found.

Then it would only be a matter of coming up with a clever cache eviction algorithm.

> Anyway, I bet that this is a much bigger issue than the pack format 
> itself (and is largely independent).

Well, I think the pack format issue is significant too. But because those are independent issues the gain in performance will be additive.

Nicolas