fix git-pack-redundant crashing sometimes

llist_sorted_difference_inplace didn't handle the match in the first sha1 correctly and the lists went wild everywhere.

---

I noticed it on a very big repository (more than 100k files), trying to prune it. The code could profit from double-linked lists greatly, IMHO.

On Tue, 15 Nov 2005 16:49:30 +0100 Alex Riesen <raa.lkml@gmail.com> wrote:

I use list.h from Linux when I need double-linked lists. It is very easy to use, efficient and fast.

On 11/15/05, Timo Hirvonen <tihirvon@gmail.com> wrote:

Yes, I had it in mind, too.

On Tue, 15 Nov 2005, Alex Riesen wrote:

There's a "ptrlist" implementation in sparse, which does a very space-efficient implementation of arbitrary lists of pointers. It's also very CPU-efficient (in fact, thanks to being very cache-friendly, more so than the kernel list.h implementation) for most well-behaved operations (ie it's not hugely friendly to removal, but it's great for "add to end" and "traverse the list").

The ptrlist implementation is optimized for cases where the lists are usually shortish, but not trivial. So they are worthwhile if you expect the list length to be on the order of 5-10 entries rather than just 1-2 (if you have just a couple of entries, the kernel lists are better). But perhaps more importantly, they are very space-efficient when the lists grow bigger (ie they average to just about 5% over the memory cost of a single pointer per list element for long lists).

Sparse in general is under the OSL license, but I'll happily dual-license the ptrlist thing, it's trivial and all my code (and I already checked with the person who did the list sorting code that we can dual-license that too).

			Linus

Timo Hirvonen wrote:

Well, well. Live and learn I suppose. I have never heard of it before.

How portable is it to #include <linux/list.h>? (non-rethorical)

Would there be a performance benefit from doubly-linked list or would it just simplify parts of the code? My first implementation used d-lists, but I dropped the ->prev when I realised it was never used.

Simplify and actually make llist_sorted_difference_inplace work by using llist_sorted_remove instead of duplicating parts of the code.

Signed-off-by: Lukas Sandström <lukass@etek.chalmers.se>

--- Looking at the code; I must have been tired when I wrote llist_sorted_difference_inplace. This should hopefully fix things up nicely. Note that I think the old version got the case "remove last element from list" wrong too.

I think the Signed-off line is in utf8 this time. Tell me if it works better, of if I just should change my name ;)

 pack-redundant.c |   47 +++++++++++++++--------------------------------
 1 files changed, 15 insertions(+), 32 deletions(-)

applies-to: 4b6dbe856a3e63699b299c76f4f1fc5cb34cbe26 560aa97889ef028fed0678389d4bb05ebf3ead62

Alex Riesen, Tue, Nov 15, 2005 16:49:30 +0100:

This wasn't enough. It never (>5 min on 2.4GHz PIV) finishes on my local mirror of git, which has 22 packs by now.

Alex Riesen wrote:

If the patch I just sent out doesn't fix the problem, and you don't want to debug it yourself, could you please publish the .idx files so I could have a look at them?

Lukas Sandström, Tue, Nov 15, 2005 22:41:34 +0100:

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); 403 while (perm) { 404 if (is_superset(perm->pl, missing)) { 405 new_perm = xmalloc(sizeof(struct pll)); 406 new_perm->pl = perm->pl; 407 new_perm->next = perm_ok; 408 perm_ok = new_perm; (gdb) 409 } 410 perm = perm->next; 411 } 412 413 if (perm_ok == NULL)

Of course: http://home.arcor.de/fork0/download/idx.tar.gz

Alex Riesen wrote:

After giving it a quick look, I don't think it locks up. It is just horribly slow. get_all_permutations returns (nice ASCII-art follows)

    ___n___
    \
     \ ____1____
n! * /  k!(n-k)!
    /______
      k=1

permutations, which for your case (22 packs) adds up to 4194303.

I'll look into an optimization so we won't have to call is_superset for every one of them.

OTOH, I might be wrong and it could very well be an infinite loop. Mind running it over the night? I won't look further into this in 20 hours or so anyway.

On 11/16/05, Lukas Sandström <lukass@etek.chalmers.se> wrote:

You missed by some minutes and I fell asleep :) Now, it is some 12 hours until I get to the machine with the lot of packs.

Lukas Sandström, Wed, Nov 16, 2005 00:13:14 +0100:

It doesn't lock up:

$ time git-pack-redundant --all --alt-odb .git/objects/pack/pack-3c5133604508466855453f3e609428f4bbba9131.idx .git/objects/pack/pack-3c5133604508466855453f3e609428f4bbba9131.pack ...

real 24m55.277s user 24m50.778s sys 0m0.582s

Now I shall be called "too impatient", perhaps?

On Tue, 15 Nov 2005, Alex Riesen wrote:

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

Linus Torvalds <torvalds@osdl.org> writes:

This reminds me of one thing I have been meaning to remove.

The $GIT_OBJECT_DIRECTORY/info/pack file produced by update-server-info records not just the packs (P lines), but its dependencies (D lines) and top objects (T lines). If there are more than one packs, D lines are meant to help the downloader to figure out what other packs are needed to complete.

"meant to" is the keyword here. The original heuristics was very bad (still correct but way suboptimal) and it has never been updated. I do not use that information myself in http fetch, and I do not think any Porcelain uses it.

Top objects are tags and commits in the pack that are not reachable from any other object in the same pack. This can be useful if you obtain just a packfile -- you can run server-info to produce info/pack file, and resurrect the branch heads and tags by using them --- you would not know what they are called, though. I have been thinking it may be worthwhile to also record bottom objects (B lines, naturally) --- tags and commits in the pack that refer to tags or commits not present in the same pack. This would help commit walkers to decide which pack is more efficient to slurp when faced with multiple choices. If you see a pack all whose bottom objects you have in your repository, fetching that would complete the commit walking, so the choice would become the matter of choosing such a pack among multiple that has smallest number of objects you do not have locally -- you would have the index file for each pack at that point.

Linus Torvalds wrote:

Slightly less, but not far from.

git-pack-redundant already does this.

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

Lukas Sandström wrote:

After doing some maths; actually it is very exponential. 2**n - 1 to be precise.

Hi, Lukas Sandström wrote:

In the general case, yes. However, you can just sort the packs by date and sequentially drop all that can be dropped. That's not optimal in the general case, but for us it should be close enough.

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

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.

Change the smallest-set detection algortithm so that when we have found a good set, we don't check any larger sets.

Signed-off-by: Lukas Sandström <lukass@etek.chalmers.se>

--- This change might make git-pack-redundant return non-optimal pack-sets in some cases. OTOH, the case which Alex reported completes in 0.6 sec instead of several minutes.

 pack-redundant.c |   62 +++++++++++++++++++++++++++++++++++++++++++-----------
 1 files changed, 49 insertions(+), 13 deletions(-)

applies-to: 1e3fcf60526c196a46433e6947c9104ca236f230 498cc056d758b9e1cd21e984be281d55e24f1117

I forgot to initialize part of the pll struct when copying it. Found by valgrind.

Signed-off-by: Lukas Sandström <lukass@etek.chalmers.se>
---

 pack-redundant.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

applies-to: 500482a7b3ebb2ebac182136696cb124332feba8 b51be59ab5b323ef148f833976a9c324d6a27404

This line was missing in the previous patch for some reason.

Signed-off-by: Lukas Sandström <lukass@etek.chalmers.se>

---

 pack-redundant.c |    1 +
 1 files changed, 1 insertions(+), 0 deletions(-)

applies-to: 5b820842ce0afb836ddbeded3a3f9e8d0ba223f9 e65d77b8ece9f6e463de0ceeaf6812a2df6d7d96