Re: fix git-pack-redundant crashing sometimes

From: Lukas Sandström <lukass@etek.chalmers.se>
Date: Nov 16, 2005, 21:37 UTC
Message-ID: <437BA6A6.8080900@etek.chalmers.se>
In-Reply-To: <Pine.LNX.4.64.0511151552400.11232@g5.osdl.org>

Linus Torvalds wrote:

Show 11 quoted lines

> 
> On Tue, 15 Nov 2005, Alex Riesen wrote:
> 
>>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.
>

Slightly less, but not far from.

> 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.
>

git-pack-redundant already does this.

> 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).
>

Ah, but the question is: "Does this set of packs contain a superset of all objects available in packfiles?" The answer to the question for a certain set is indeed O(n), but the number of sets which have to be tested are ~ O(e**n). (Where n is the number of non-unique packs.)

/Lukas