Re: fix git-pack-redundant crashing sometimes

From: Fredrik Kuivinen <freku045@student.liu.se>
Date: Nov 17, 2005, 07:08 UTC
Message-ID: <20051117070852.GA4921@c165.ib.student.liu.se>
In-Reply-To: <437BA6A6.8080900@etek.chalmers.se>

On Wed, Nov 16, 2005 at 10:37:42PM +0100, Lukas Sandström wrote:

Show 27 quoted lines

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

If haven't looked closely at neither the packing nor the pack redundant code, but the problem looks very similar to Minimum Set Cover (see http://www.nada.kth.se/~viggo/wwwcompendium/node146.html for more information), which is NP-hard. So, if Minimum Set Cover is the problem we are trying to solve we can't hope to find a polynomial time algorithm. However, there is a quite simple greedy approximation algorithm in [1] which is referenced from the URL above.

- Fredrik

[1]: Johnson, D. S. (1974), "Approximation algorithms for
     combinatorial problems", J. Comput. System Sci. 9, 256-278.