# fix git-pack-redundant crashing sometimes 21 messages from 2005-11-15 to 2005-11-18. Participants: Alex Riesen, Timo Hirvonen, Linus Torvalds, Lukas Sandström, Junio C Hamano, Fredrik Kuivinen, Matthias Urlichs. Thread: https://gitlist.dev/t/2527 ## Alex Riesen, 2005-11-15 15:49 Subject: fix git-pack-redundant crashing sometimes Message-ID: <81b0412b0511150749g5672158v7b39c02ffdf13e08@mail.gmail.com> URL: https://gitlist.dev/e/81b0412b0511150749g5672158v7b39c02ffdf13e08%40mail.gmail.com ``` 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. ``` ## Timo Hirvonen, 2005-11-15 16:08 Subject: Re: fix git-pack-redundant crashing sometimes Message-ID: <20051115180848.561a6da5.tihirvon@gmail.com> URL: https://gitlist.dev/e/20051115180848.561a6da5.tihirvon%40gmail.com In-Reply-To: <81b0412b0511150749g5672158v7b39c02ffdf13e08@mail.gmail.com> ``` On Tue, 15 Nov 2005 16:49:30 +0100 Alex Riesen wrote: > 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. I use list.h from Linux when I need double-linked lists. It is very easy to use, efficient and fast. -- http://onion.dynserv.net/~timo/ ``` ## Alex Riesen, 2005-11-15 16:11 Subject: Re: fix git-pack-redundant crashing sometimes Message-ID: <81b0412b0511150811w2a7a2c4ft9a2920ac4f030ee4@mail.gmail.com> URL: https://gitlist.dev/e/81b0412b0511150811w2a7a2c4ft9a2920ac4f030ee4%40mail.gmail.com In-Reply-To: <20051115180848.561a6da5.tihirvon@gmail.com> ``` On 11/15/05, Timo Hirvonen wrote: > > The code could profit from double-linked lists greatly, IMHO. > > I use list.h from Linux when I need double-linked lists. It is very > easy to use, efficient and fast. > Yes, I had it in mind, too. ``` ## Linus Torvalds, 2005-11-15 17:28 Subject: Re: fix git-pack-redundant crashing sometimes Message-ID: URL: https://gitlist.dev/e/Pine.LNX.4.64.0511150921420.3945%40g5.osdl.org In-Reply-To: <81b0412b0511150811w2a7a2c4ft9a2920ac4f030ee4@mail.gmail.com> ``` On Tue, 15 Nov 2005, Alex Riesen wrote: > On 11/15/05, Timo Hirvonen wrote: > > > The code could profit from double-linked lists greatly, IMHO. > > > > I use list.h from Linux when I need double-linked lists. It is very > > easy to use, efficient and fast. > > Yes, I had it in mind, too. 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 ``` ## Lukas Sandström, 2005-11-15 21:24 Subject: [PATCH] Fix llist_sorted_difference_inplace in git-pack-redundant Message-ID: <437A51F2.4000106@etek.chalmers.se> URL: https://gitlist.dev/e/437A51F2.4000106%40etek.chalmers.se In-Reply-To: <81b0412b0511150749g5672158v7b39c02ffdf13e08@mail.gmail.com> ``` 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 --- 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 diff --git a/pack-redundant.c b/pack-redundant.c index 28b82ee..fcb36ff 100644 --- a/pack-redundant.c +++ b/pack-redundant.c @@ -127,38 +127,6 @@ inline struct llist_item * llist_insert_ return llist_insert_back(list, sha1); } -/* computes A\B */ -void llist_sorted_difference_inplace(struct llist *A, - struct llist *B) -{ - struct llist_item *prev, *a, *b, *x; - - prev = a = A->front; - b = B->front; - - while (a != NULL && b != NULL) { - int cmp = memcmp(a->sha1, b->sha1, 20); - if (!cmp) { - x = a; - if (a == A->front) - A->front = a->next; - a = prev->next = a->next; - - if (a == NULL) /* end of list */ - A->back = prev; - A->size--; - free(x); - b = b->next; - } else - if (cmp > 0) - b = b->next; - else { - prev = a; - a = a->next; - } - } -} - /* returns a pointer to an item in front of sha1 */ inline struct llist_item * llist_sorted_remove(struct llist *list, char *sha1, struct llist_item *hint) @@ -194,6 +162,21 @@ redo_from_start: return prev; } +/* computes A\B */ +void llist_sorted_difference_inplace(struct llist *A, + struct llist *B) +{ + struct llist_item *hint, *b; + + hint = NULL; + b = B->front; + + while (b) { + hint = llist_sorted_remove(A, b->sha1, hint); + b = b->next; + } +} + inline struct pack_list * pack_list_insert(struct pack_list **pl, struct pack_list *entry) { --- 0.99.9.GIT ``` ## Alex Riesen, 2005-11-15 21:34 Subject: Re: fix git-pack-redundant crashing sometimes Message-ID: <20051115213442.GA4256@steel.home> URL: https://gitlist.dev/e/20051115213442.GA4256%40steel.home In-Reply-To: <81b0412b0511150749g5672158v7b39c02ffdf13e08@mail.gmail.com> ``` Alex Riesen, Tue, Nov 15, 2005 16:49:30 +0100: > llist_sorted_difference_inplace didn't handle the match in the first > sha1 correctly and the lists went wild everywhere. 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. ``` ## Lukas Sandström, 2005-11-15 21:38 Subject: Re: fix git-pack-redundant crashing sometimes Message-ID: <437A5570.70509@etek.chalmers.se> URL: https://gitlist.dev/e/437A5570.70509%40etek.chalmers.se In-Reply-To: <20051115180848.561a6da5.tihirvon@gmail.com> ``` Timo Hirvonen wrote: > On Tue, 15 Nov 2005 16:49:30 +0100 > Alex Riesen wrote: > > >>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. > > > I use list.h from Linux when I need double-linked lists. It is very > easy to use, efficient and fast. > Well, well. Live and learn I suppose. I have never heard of it before. How portable is it to #include ? (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. ``` ## Lukas Sandström, 2005-11-15 21:41 Subject: Re: fix git-pack-redundant crashing sometimes Message-ID: <437A560E.8020500@etek.chalmers.se> URL: https://gitlist.dev/e/437A560E.8020500%40etek.chalmers.se In-Reply-To: <20051115213442.GA4256@steel.home> ``` Alex Riesen wrote: > Alex Riesen, Tue, Nov 15, 2005 16:49:30 +0100: > >>llist_sorted_difference_inplace didn't handle the match in the first >>sha1 correctly and the lists went wild everywhere. > > > 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. > 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? ``` ## Alex Riesen, 2005-11-15 22:33 Subject: Re: fix git-pack-redundant crashing sometimes Message-ID: <20051115223340.GA3951@steel.home> URL: https://gitlist.dev/e/20051115223340.GA3951%40steel.home In-Reply-To: <437A560E.8020500@etek.chalmers.se> ``` Lukas Sandström, Tue, Nov 15, 2005 22:41:34 +0100: > >>llist_sorted_difference_inplace didn't handle the match in the first > >>sha1 correctly and the lists went wild everywhere. > > > > 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. > > If the patch I just sent out doesn't fix the problem, and you don't 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) > want to debug it yourself, could you please publish the .idx files > so I could have a look at them? Of course: http://home.arcor.de/fork0/download/idx.tar.gz ``` ## Lukas Sandström, 2005-11-15 23:13 Subject: Re: fix git-pack-redundant crashing sometimes Message-ID: <437A6B8A.8060905@etek.chalmers.se> URL: https://gitlist.dev/e/437A6B8A.8060905%40etek.chalmers.se In-Reply-To: <20051115223340.GA3951@steel.home> ``` Alex Riesen wrote: > Lukas Sandström, Tue, Nov 15, 2005 22:41:34 +0100: > >>>>llist_sorted_difference_inplace didn't handle the match in the first >>>>sha1 correctly and the lists went wild everywhere. >>> >>>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. >> >>If the patch I just sent out doesn't fix the problem, and you don't > > > 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) > > > >>want to debug it yourself, could you please publish the .idx files >>so I could have a look at them? > > > Of course: http://home.arcor.de/fork0/download/idx.tar.gz > 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. ``` ## Linus Torvalds, 2005-11-15 23:58 Subject: Re: fix git-pack-redundant crashing sometimes Message-ID: URL: https://gitlist.dev/e/Pine.LNX.4.64.0511151552400.11232%40g5.osdl.org In-Reply-To: <20051115223340.GA3951@steel.home> ``` 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. 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 ``` ## Alex Riesen, 2005-11-16 07:01 Subject: Re: fix git-pack-redundant crashing sometimes Message-ID: <81b0412b0511152301s13944046lb2cbac95f4dab1fd@mail.gmail.com> URL: https://gitlist.dev/e/81b0412b0511152301s13944046lb2cbac95f4dab1fd%40mail.gmail.com In-Reply-To: <437A6B8A.8060905@etek.chalmers.se> ``` On 11/16/05, Lukas Sandström wrote: > 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. 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. ``` ## Junio C Hamano, 2005-11-16 20:13 Subject: Re: fix git-pack-redundant crashing sometimes Message-ID: <7vlkzo73m1.fsf@assigned-by-dhcp.cox.net> URL: https://gitlist.dev/e/7vlkzo73m1.fsf%40assigned-by-dhcp.cox.net In-Reply-To: ``` Linus Torvalds writes: > 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. 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. ``` ## Alex Riesen, 2005-11-16 21:11 Subject: Re: fix git-pack-redundant crashing sometimes Message-ID: <20051116211128.GA13975@steel.home> URL: https://gitlist.dev/e/20051116211128.GA13975%40steel.home In-Reply-To: <437A6B8A.8060905@etek.chalmers.se> ``` Lukas Sandström, Wed, Nov 16, 2005 00:13:14 +0100: > 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. 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? ``` ## Lukas Sandström, 2005-11-16 21:37 Subject: Re: fix git-pack-redundant crashing sometimes Message-ID: <437BA6A6.8080900@etek.chalmers.se> URL: https://gitlist.dev/e/437BA6A6.8080900%40etek.chalmers.se In-Reply-To: ``` 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 ``` ## Lukas Sandström, 2005-11-16 23:59 Subject: Re: fix git-pack-redundant crashing sometimes Message-ID: <437BC7D1.1070605@etek.chalmers.se> URL: https://gitlist.dev/e/437BC7D1.1070605%40etek.chalmers.se In-Reply-To: <437BA6A6.8080900@etek.chalmers.se> ``` Lukas Sandström wrote: > 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. > After doing some maths; actually it is very exponential. 2**n - 1 to be precise. ``` ## Fredrik Kuivinen, 2005-11-17 07:08 Subject: Re: fix git-pack-redundant crashing sometimes Message-ID: <20051117070852.GA4921@c165.ib.student.liu.se> URL: https://gitlist.dev/e/20051117070852.GA4921%40c165.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: > 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. ``` ## Lukas Sandström, 2005-11-17 13:11 Subject: [PATCH] Make git-pack-redundant non-horribly slow on large sets of packs Message-ID: <437C819C.4040507@etek.chalmers.se> URL: https://gitlist.dev/e/437C819C.4040507%40etek.chalmers.se In-Reply-To: <20051115223340.GA3951@steel.home> ``` 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 --- 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 diff --git a/pack-redundant.c b/pack-redundant.c index fcb36ff..51d7341 100644 --- a/pack-redundant.c +++ b/pack-redundant.c @@ -33,6 +33,7 @@ struct pack_list { struct pll { struct pll *next; struct pack_list *pl; + size_t pl_size; }; inline void llist_free(struct llist *list) @@ -249,18 +250,45 @@ void cmp_two_packs(struct pack_list *p1, } } +void pll_insert(struct pll **pll, struct pll **hint_table) +{ + struct pll *prev; + int i = (*pll)->pl_size - 1; + + if (hint_table[i] == NULL) { + hint_table[i--] = *pll; + for (; i >= 0; --i) { + if (hint_table[i] != NULL) + break; + } + if (hint_table[i] == NULL) /* no elements in list */ + die("Why did this happen?"); + } + + prev = hint_table[i]; + while (prev->next && prev->next->pl_size < (*pll)->pl_size) + prev = prev->next; + + (*pll)->next = prev->next; + prev->next = *pll; +} + /* all the permutations have to be free()d at the same time, * since they refer to each other */ struct pll * get_all_permutations(struct pack_list *list) { struct pll *subset, *pll, *new_pll = NULL; /*silence warning*/ - + static struct pll **hint = NULL; + if (hint == NULL) + hint = xcalloc(pack_list_size(list), sizeof(struct pll *)); + if (list == NULL) return NULL; if (list->next == NULL) { new_pll = xmalloc(sizeof(struct pll)); + hint[0] = new_pll; new_pll->next = NULL; new_pll->pl = list; return new_pll; @@ -268,24 +296,30 @@ struct pll * get_all_permutations(struct pll = subset = get_all_permutations(list->next); while (pll) { + if (pll->pl->pack == list->pack) { + pll = pll->next; + continue; + } new_pll = xmalloc(sizeof(struct pll)); - new_pll->next = pll->next; - pll->next = new_pll; new_pll->pl = xmalloc(sizeof(struct pack_list)); memcpy(new_pll->pl, list, sizeof(struct pack_list)); new_pll->pl->next = pll->pl; + new_pll->pl_size = pll->pl_size + 1; + + pll_insert(&new_pll, hint); + + pll = pll->next; + } + /* add ourself */ + new_pll = xmalloc(sizeof(struct pll)); + new_pll->pl = xmalloc(sizeof(struct pack_list)); + memcpy(new_pll->pl, list, sizeof(struct pack_list)); + new_pll->pl->next = NULL; + new_pll->pl_size = 1; + pll_insert(&new_pll, hint); - pll = new_pll->next; - } - /* add ourself to the end */ - new_pll->next = xmalloc(sizeof(struct pll)); - new_pll->next->pl = xmalloc(sizeof(struct pack_list)); - new_pll->next->next = NULL; - memcpy(new_pll->next->pl, list, sizeof(struct pack_list)); - new_pll->next->pl->next = NULL; - - return subset; + return hint[0]; } int is_superset(struct pack_list *pl, struct llist *list) @@ -401,6 +435,8 @@ void minimize(struct pack_list **min) /* find the permutations which contain all missing objects */ perm_all = perm = get_all_permutations(non_unique); while (perm) { + if (perm_ok && perm->pl_size > perm_ok->pl_size) + break; /* ignore all larger permutations */ if (is_superset(perm->pl, missing)) { new_perm = xmalloc(sizeof(struct pll)); new_perm->pl = perm->pl; --- 0.99.9.GIT ``` ## Matthias Urlichs, 2005-11-17 16:56 Subject: Re: fix git-pack-redundant crashing sometimes Message-ID: URL: https://gitlist.dev/e/pan.2005.11.17.16.56.29.833519%40smurf.noris.de In-Reply-To: <437BC7D1.1070605@etek.chalmers.se> ``` Hi, Lukas Sandström wrote: > After doing some maths; actually it is very exponential. 2**n - 1 to be precise. 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. -- Matthias Urlichs | {M:U} IT Design @ m-u-it.de | smurf@smurf.noris.de Disclaimer: The quote was selected randomly. Really. | http://smurf.noris.de - - When was the last time you were drunk? ``` ## Lukas Sandström, 2005-11-18 16:30 Subject: [PATCH] Fix bug introduced by the latest changes to git-pack-redundant Message-ID: <437E01A5.7040501@etek.chalmers.se> URL: https://gitlist.dev/e/437E01A5.7040501%40etek.chalmers.se In-Reply-To: <437C819C.4040507@etek.chalmers.se> ``` I forgot to initialize part of the pll struct when copying it. Found by valgrind. Signed-off-by: Lukas Sandström --- pack-redundant.c | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-) applies-to: 500482a7b3ebb2ebac182136696cb124332feba8 b51be59ab5b323ef148f833976a9c324d6a27404 diff --git a/pack-redundant.c b/pack-redundant.c index 2d7183e..3123f45 100644 --- a/pack-redundant.c +++ b/pack-redundant.c @@ -442,7 +442,7 @@ void minimize(struct pack_list **min) break; /* ignore all larger permutations */ if (is_superset(perm->pl, missing)) { new_perm = xmalloc(sizeof(struct pll)); - new_perm->pl = perm->pl; + memcpy(new_perm, perm, sizeof(struct pll)); new_perm->next = perm_ok; perm_ok = new_perm; } --- 0.99.9.GIT ``` ## Lukas Sandström, 2005-11-18 21:53 Subject: [PATCH] Fix a bug in get_all_permutations. Message-ID: <437E4D54.60901@etek.chalmers.se> URL: https://gitlist.dev/e/437E4D54.60901%40etek.chalmers.se In-Reply-To: <437C819C.4040507@etek.chalmers.se> ``` This line was missing in the previous patch for some reason. Signed-off-by: Lukas Sandström --- pack-redundant.c | 1 + 1 files changed, 1 insertions(+), 0 deletions(-) applies-to: 5b820842ce0afb836ddbeded3a3f9e8d0ba223f9 e65d77b8ece9f6e463de0ceeaf6812a2df6d7d96 diff --git a/pack-redundant.c b/pack-redundant.c index 3655609..3e3f33a 100644 --- a/pack-redundant.c +++ b/pack-redundant.c @@ -291,6 +291,7 @@ struct pll * get_all_permutations(struct hint[0] = new_pll; new_pll->next = NULL; new_pll->pl = list; + new_pll->pl_size = 1; return new_pll; } --- 0.99.9.GIT ```