Re: fix git-pack-redundant crashing sometimes

From: Linus Torvalds <torvalds@osdl.org>
Date: Nov 15, 2005, 23:58 UTC
Message-ID: <Pine.LNX.4.64.0511151552400.11232@g5.osdl.org>
In-Reply-To: <20051115223340.GA3951@steel.home>

On Tue, 15 Nov 2005, Alex Riesen wrote:

Show 5 quoted lines

> 
> Sorry, it doesn't. The code loops here:
> 
> 401             /* find the permutations which contain all missing objects */
> 402             perm_all = perm = get_all_permutations(non_unique);

Looks like the whole thing is exponential.

A good way to do sane pack handling is to keep a _sorted_ list of all objects each pack has. At that point it becomes much easier to see which objects only exist in one particular pack.

The sorting itself is O(nlogn), and the "does this pack have any unique objects" (or "is this pack a superset of all other packs") question should then be O(n).

This is how the packs are generated in the first place - by sorting the objects and limiting the diff generation to the "neighbors" of the objects, you can generate pack-files in O(n logn) rather than O(n**2). Which is pretty important when there are currently 140,000+ objects in the kernel tree.

		Linus