Re: [RFC] Cache negative delta pairs

From: Nicolas Pitre <nico@cam.org>
Date: Jun 29, 2006, 16:39 UTC
Message-ID: <Pine.LNX.4.64.0606291154510.1213@localhost.localdomain>
In-Reply-To: <20060629035849.GA30749@coredump.intra.peff.net>

On Wed, 28 Jun 2006, Jeff King wrote:

Show 5 quoted lines

> >From repack to repack, we end up trying to delta many of the same object
> pairs, which is computationally expensive.  This patch makes a
> persistent cache, $GIT_DIR/delta-cache, which contains pairs of sha1
> hashes (the presence of a pair indicates that it's not worth trying to
> delta those two objects).

I think this could be done differently to be even more space efficient as I suggested earlier.

Show 5 quoted lines

> Here are some of my thoughts:
> 
>  - speed. The implementation is quite fast. The sha1 pairs are stored
>    sorted, and we mmap and binary search them. Certainly the extra time
>    spent in lookup is justified by avoiding the delta attempts.

You do that lookup for every delta match attempt. Instead it could be done once for the whole window attempt, potentially reducing the cache size by a factor of 20, and it might be faster too.

Show 6 quoted lines

>  - size. The cache is a packed sequence of binary sha1 pairs. I was
>    concerned that it would grow too large (obviously for n blobs you can
>    end up with n^2/2 entries), but it doesn't seem unreasonable for most
>    repos (either you don't have a lot of files, or if you do, they delta
>    reasonably well). My test repo's cache is only 144K. The git cache is
>    about 2.7M. The linux-2.6 cache is 22M.

See my previous email for comments about this.

>    Theoretically, I could bound the cache size and boot old entries.
>    However, that means storing age information, which increases the
>    required size. I think keeping it simple is best.

You could simply recreate the cache on each run. Or just keep a bitmap of referenced cache entries, and a list of new entries. At the end if the new entry list is empty and the bitmap is all set (or clear) then you just keep the current cache. ONce, say, more than 10% of cache entries are not used anymore then you regenerate the cache. But since you need to regenerate it when new entries are added then the 10% unused entry criteria might not be used that often anyway, unless packs shrink with time which might not be the case really often.

Show 6 quoted lines

>  - 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
>    delta negative (I believe right now hitting the depth limit will
>    cause a negative mark; we should perhaps only do so if the content
>    itself makes the delta unpalatable).

Like I said earlier I think this should be moved up a bit i.e. outside the delta loop. In find_deltas() right before the ...

		j = window;
		while (--j > 0) {

loop, just insert another loop that compute the sha1 of the current target object and window:

		SHA1_Init(&c);
		j = window;
		while (j-- > 0) { /* postdec include the current object as well */
			unsigned int other_idx = idx + j;
			struct unpacked *m;
			if (other_idx >= window)
				other_idx -= window;
			m = array + other_idx;
			if (!m->entry)
				break;
			SHA1_Update(&c, m->entry.sha1, 20);
		}
		SHA1_Final(negative_delta_hash, &c);

Then you can skip over the whole of the delta loop right away if that negative_delta_hash matches one entry in the cache since you already know that this object with this window doesn't produce any delta result.

Otherwise, after the delta loop has proceeded, if there is no delta found then you can add negative_delta_hash to the cache.

Show 8 quoted lines

>  - optionalness. Currently the delta-cache is always used. Since it is a
>    space-time tradeoff, maybe it should be optional (it will have
>    negligible performance and horrible size impact on a repo that
>    consists of many very small but unrelated objects).  Possible methods
>    include:
>      - enable cache saves only if .git/delta-cache is present; turn it
>        on initially with 'touch .git/delta-cache'
>      - config variable

First, I think it should be ignored (but still created) when --no-reuse-delta is passed. Then, it should not be created (but still looked up if it exists and --no-reuse-delta is not provided) when the pack index file is also not created. I don't think it is worth making this further configurable, and given the suggested strategy above the cache should remain fairly small.

Nicolas