From: Lukas Sandström <lukass@etek.chalmers.se>
Date: Wed, 16 Nov 2005 21:37:42 GMT
Subject: Re: fix git-pack-redundant crashing sometimes
Message-ID: <437BA6A6.8080900@etek.chalmers.se>
In-Reply-To: <Pine.LNX.4.64.0511151552400.11232@g5.osdl.org>

Linus Torvalds wrote:
> 
> 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