{"thread":{"id":"2527","subject":"fix git-pack-redundant crashing sometimes","startedAt":"2005-11-15T15:49:30Z","lastAt":"2005-11-18T21:53:24Z","messageCount":21,"participants":["Alex Riesen","Timo Hirvonen","Linus Torvalds","Lukas Sandström","Junio C Hamano","Fredrik Kuivinen","Matthias Urlichs"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"11901","messageId":"81b0412b0511150749g5672158v7b39c02ffdf13e08@mail.gmail.com","threadId":"2527","inReplyTo":null,"subject":"fix git-pack-redundant crashing sometimes","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2005-11-15T15:49:30Z","receivedAt":"2005-11-15T15:49:30Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"llist_sorted_difference_inplace didn't handle the match in the first\nsha1 correctly and the lists went wild everywhere.\n\n---\n\nI noticed it on a very big repository (more than 100k files), trying\nto prune it.\nThe code could profit from double-linked lists greatly, IMHO.\n"},{"id":"11904","messageId":"20051115180848.561a6da5.tihirvon@gmail.com","threadId":"2527","inReplyTo":"81b0412b0511150749g5672158v7b39c02ffdf13e08@mail.gmail.com","subject":"Re: fix git-pack-redundant crashing sometimes","fromName":"Timo Hirvonen","fromEmail":"tihirvon@gmail.com","sentAt":"2005-11-15T16:08:48Z","receivedAt":"2005-11-15T16:08:48Z","isPatch":false,"sender":{"key":"tihirvon@gmail.com","avatar":null},"body":"On Tue, 15 Nov 2005 16:49:30 +0100\nAlex Riesen <raa.lkml@gmail.com> wrote:\n\n> llist_sorted_difference_inplace didn't handle the match in the first\n> sha1 correctly and the lists went wild everywhere.\n> \n> ---\n> \n> I noticed it on a very big repository (more than 100k files), trying\n> to prune it.\n> The code could profit from double-linked lists greatly, IMHO.\n\nI use list.h from Linux when I need double-linked lists.  It is very\neasy to use, efficient and fast.\n\n-- \nhttp://onion.dynserv.net/~timo/\n"},{"id":"11905","messageId":"81b0412b0511150811w2a7a2c4ft9a2920ac4f030ee4@mail.gmail.com","threadId":"2527","inReplyTo":"20051115180848.561a6da5.tihirvon@gmail.com","subject":"Re: fix git-pack-redundant crashing sometimes","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2005-11-15T16:11:17Z","receivedAt":"2005-11-15T16:11:17Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"On 11/15/05, Timo Hirvonen <tihirvon@gmail.com> wrote:\n> > The code could profit from double-linked lists greatly, IMHO.\n>\n> I use list.h from Linux when I need double-linked lists.  It is very\n> easy to use, efficient and fast.\n>\n\nYes, I had it in mind, too.\n"},{"id":"11914","messageId":"Pine.LNX.4.64.0511150921420.3945@g5.osdl.org","threadId":"2527","inReplyTo":"81b0412b0511150811w2a7a2c4ft9a2920ac4f030ee4@mail.gmail.com","subject":"Re: fix git-pack-redundant crashing sometimes","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-11-15T17:28:25Z","receivedAt":"2005-11-15T17:28:25Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 15 Nov 2005, Alex Riesen wrote:\n\n> On 11/15/05, Timo Hirvonen <tihirvon@gmail.com> wrote:\n> > > The code could profit from double-linked lists greatly, IMHO.\n> >\n> > I use list.h from Linux when I need double-linked lists.  It is very\n> > easy to use, efficient and fast.\n> \n> Yes, I had it in mind, too.\n\nThere's a \"ptrlist\" implementation in sparse, which does a very \nspace-efficient implementation of arbitrary lists of pointers. It's also \nvery CPU-efficient (in fact, thanks to being very cache-friendly, more so \nthan the kernel list.h implementation) for most well-behaved operations \n(ie it's not hugely friendly to removal, but it's great for \"add to end\" \nand \"traverse the list\").\n\nThe ptrlist implementation is optimized for cases where the lists are \nusually shortish, but not trivial. So they are worthwhile if you expect \nthe list length to be on the order of 5-10 entries rather than just 1-2 \n(if you have just a couple of entries, the kernel lists are better). But \nperhaps more importantly, they are very space-efficient when the lists \ngrow bigger (ie they average to just about 5% over the memory cost of a \nsingle pointer per list element for long lists).\n\nSparse in general is under the OSL license, but I'll happily dual-license \nthe ptrlist thing, it's trivial and all my code (and I already checked \nwith the person who did the list sorting code that we can dual-license \nthat too).\n\n\t\t\tLinus\n"},{"id":"11931","messageId":"437A51F2.4000106@etek.chalmers.se","threadId":"2527","inReplyTo":"81b0412b0511150749g5672158v7b39c02ffdf13e08@mail.gmail.com","subject":"[PATCH] Fix llist_sorted_difference_inplace in git-pack-redundant","fromName":"Lukas Sandström","fromEmail":"lukass@etek.chalmers.se","sentAt":"2005-11-15T21:24:02Z","receivedAt":"2005-11-15T21:24:02Z","isPatch":true,"sender":{"key":"luksan@gmail.com","avatar":"https://avatars.githubusercontent.com/u/152281?v=4"},"body":"Simplify and actually make llist_sorted_difference_inplace work\nby using llist_sorted_remove instead of duplicating parts of the\ncode.\n\nSigned-off-by: Lukas Sandström <lukass@etek.chalmers.se>\n\n---\nLooking at the code; I must have been tired when I wrote llist_sorted_difference_inplace.\nThis should hopefully fix things up nicely. Note that I think the old version got the\ncase \"remove last element from list\" wrong too.\n\nI think the Signed-off line is in utf8 this time. Tell me if it works better, of if I \njust should change my name ;)\n\n pack-redundant.c |   47 +++++++++++++++--------------------------------\n 1 files changed, 15 insertions(+), 32 deletions(-)\n\napplies-to: 4b6dbe856a3e63699b299c76f4f1fc5cb34cbe26\n560aa97889ef028fed0678389d4bb05ebf3ead62\ndiff --git a/pack-redundant.c b/pack-redundant.c\nindex 28b82ee..fcb36ff 100644\n--- a/pack-redundant.c\n+++ b/pack-redundant.c\n@@ -127,38 +127,6 @@ inline struct llist_item * llist_insert_\n \treturn llist_insert_back(list, sha1);\n }\n \n-/* computes A\\B */\n-void llist_sorted_difference_inplace(struct llist *A,\n-\t\t\t\t     struct llist *B)\n-{\n-\tstruct llist_item *prev, *a, *b, *x;\n-\n-\tprev = a = A->front;\n-\tb = B->front;\n-\n-\twhile (a != NULL && b != NULL) {\n-\t\tint cmp = memcmp(a->sha1, b->sha1, 20);\n-\t\tif (!cmp) {\n-\t\t\tx = a;\n-\t\t\tif (a == A->front)\n-\t\t\t\tA->front = a->next;\n-\t\t\ta = prev->next = a->next;\n-\n-\t\t\tif (a == NULL) /* end of list */\n-\t\t\t\tA->back = prev;\n-\t\t\tA->size--;\n-\t\t\tfree(x);\n-\t\t\tb = b->next;\n-\t\t} else\n-\t\t\tif (cmp > 0)\n-\t\t\t\tb = b->next;\n-\t\t\telse {\n-\t\t\t\tprev = a;\n-\t\t\t\ta = a->next;\n-\t\t\t}\n-\t}\n-}\n-\n /* returns a pointer to an item in front of sha1 */\n inline struct llist_item * llist_sorted_remove(struct llist *list, char *sha1,\n \t\t\t\t\t       struct llist_item *hint)\n@@ -194,6 +162,21 @@ redo_from_start:\n \treturn prev;\n }\n \n+/* computes A\\B */\n+void llist_sorted_difference_inplace(struct llist *A,\n+\t\t\t\t     struct llist *B)\n+{\n+\tstruct llist_item *hint, *b;\n+\n+\thint = NULL;\n+\tb = B->front;\n+\n+\twhile (b) {\n+\t\thint = llist_sorted_remove(A, b->sha1, hint);\n+\t\tb = b->next;\n+\t}\n+}\n+\n inline struct pack_list * pack_list_insert(struct pack_list **pl,\n \t\t\t\t\t   struct pack_list *entry)\n {\n---\n0.99.9.GIT\n"},{"id":"11936","messageId":"20051115213442.GA4256@steel.home","threadId":"2527","inReplyTo":"81b0412b0511150749g5672158v7b39c02ffdf13e08@mail.gmail.com","subject":"Re: fix git-pack-redundant crashing sometimes","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2005-11-15T21:34:42Z","receivedAt":"2005-11-15T21:34:42Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"Alex Riesen, Tue, Nov 15, 2005 16:49:30 +0100:\n> llist_sorted_difference_inplace didn't handle the match in the first\n> sha1 correctly and the lists went wild everywhere.\n\nThis wasn't enough. It never (>5 min on 2.4GHz PIV) finishes on\nmy local mirror of git, which has 22 packs by now.\n"},{"id":"11937","messageId":"437A5570.70509@etek.chalmers.se","threadId":"2527","inReplyTo":"20051115180848.561a6da5.tihirvon@gmail.com","subject":"Re: fix git-pack-redundant crashing sometimes","fromName":"Lukas Sandström","fromEmail":"lukass@etek.chalmers.se","sentAt":"2005-11-15T21:38:56Z","receivedAt":"2005-11-15T21:38:56Z","isPatch":false,"sender":{"key":"luksan@gmail.com","avatar":"https://avatars.githubusercontent.com/u/152281?v=4"},"body":"Timo Hirvonen wrote:\n> On Tue, 15 Nov 2005 16:49:30 +0100\n> Alex Riesen <raa.lkml@gmail.com> wrote:\n> \n> \n>>llist_sorted_difference_inplace didn't handle the match in the first\n>>sha1 correctly and the lists went wild everywhere.\n>>\n>>---\n>>\n>>I noticed it on a very big repository (more than 100k files), trying\n>>to prune it.\n>>The code could profit from double-linked lists greatly, IMHO.\n> \n> \n> I use list.h from Linux when I need double-linked lists.  It is very\n> easy to use, efficient and fast.\n> \nWell, well. Live and learn I suppose. I have never heard of it before.\n\nHow portable is it to #include <linux/list.h>? (non-rethorical)\n\nWould there be a performance benefit from doubly-linked list or would\nit just simplify parts of the code? My first implementation used d-lists,\nbut I dropped the ->prev when I realised it was never used.\n"},{"id":"11938","messageId":"437A560E.8020500@etek.chalmers.se","threadId":"2527","inReplyTo":"20051115213442.GA4256@steel.home","subject":"Re: fix git-pack-redundant crashing sometimes","fromName":"Lukas Sandström","fromEmail":"lukass@etek.chalmers.se","sentAt":"2005-11-15T21:41:34Z","receivedAt":"2005-11-15T21:41:34Z","isPatch":false,"sender":{"key":"luksan@gmail.com","avatar":"https://avatars.githubusercontent.com/u/152281?v=4"},"body":"Alex Riesen wrote:\n> Alex Riesen, Tue, Nov 15, 2005 16:49:30 +0100:\n> \n>>llist_sorted_difference_inplace didn't handle the match in the first\n>>sha1 correctly and the lists went wild everywhere.\n> \n> \n> This wasn't enough. It never (>5 min on 2.4GHz PIV) finishes on\n> my local mirror of git, which has 22 packs by now.\n> \n\nIf the patch I just sent out doesn't fix the problem, and you don't\nwant to debug it yourself, could you please publish the .idx files\nso I could have a look at them?\n"},{"id":"11946","messageId":"20051115223340.GA3951@steel.home","threadId":"2527","inReplyTo":"437A560E.8020500@etek.chalmers.se","subject":"Re: fix git-pack-redundant crashing sometimes","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2005-11-15T22:33:40Z","receivedAt":"2005-11-15T22:33:40Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"Lukas Sandström, Tue, Nov 15, 2005 22:41:34 +0100:\n> >>llist_sorted_difference_inplace didn't handle the match in the first\n> >>sha1 correctly and the lists went wild everywhere.\n> > \n> > This wasn't enough. It never (>5 min on 2.4GHz PIV) finishes on\n> > my local mirror of git, which has 22 packs by now.\n> \n> If the patch I just sent out doesn't fix the problem, and you don't\n\nSorry, it doesn't. The code loops here:\n\n401             /* find the permutations which contain all missing objects */\n402             perm_all = perm = get_all_permutations(non_unique);\n403             while (perm) {\n404                     if (is_superset(perm->pl, missing)) {\n405                             new_perm = xmalloc(sizeof(struct pll));\n406                             new_perm->pl = perm->pl;\n407                             new_perm->next = perm_ok;\n408                             perm_ok = new_perm;\n(gdb) \n409                     }\n410                     perm = perm->next;\n411             }\n412\n413             if (perm_ok == NULL)\n\n\n> want to debug it yourself, could you please publish the .idx files\n> so I could have a look at them?\n\nOf course: http://home.arcor.de/fork0/download/idx.tar.gz\n"},{"id":"11952","messageId":"437A6B8A.8060905@etek.chalmers.se","threadId":"2527","inReplyTo":"20051115223340.GA3951@steel.home","subject":"Re: fix git-pack-redundant crashing sometimes","fromName":"Lukas Sandström","fromEmail":"lukass@etek.chalmers.se","sentAt":"2005-11-15T23:13:14Z","receivedAt":"2005-11-15T23:13:14Z","isPatch":false,"sender":{"key":"luksan@gmail.com","avatar":"https://avatars.githubusercontent.com/u/152281?v=4"},"body":"Alex Riesen wrote:\n> Lukas Sandström, Tue, Nov 15, 2005 22:41:34 +0100:\n> \n>>>>llist_sorted_difference_inplace didn't handle the match in the first\n>>>>sha1 correctly and the lists went wild everywhere.\n>>>\n>>>This wasn't enough. It never (>5 min on 2.4GHz PIV) finishes on\n>>>my local mirror of git, which has 22 packs by now.\n>>\n>>If the patch I just sent out doesn't fix the problem, and you don't\n> \n> \n> Sorry, it doesn't. The code loops here:\n> \n> 401             /* find the permutations which contain all missing objects */\n> 402             perm_all = perm = get_all_permutations(non_unique);\n> 403             while (perm) {\n> 404                     if (is_superset(perm->pl, missing)) {\n> 405                             new_perm = xmalloc(sizeof(struct pll));\n> 406                             new_perm->pl = perm->pl;\n> 407                             new_perm->next = perm_ok;\n> 408                             perm_ok = new_perm;\n> (gdb) \n> 409                     }\n> 410                     perm = perm->next;\n> 411             }\n> 412\n> 413             if (perm_ok == NULL)\n> \n> \n> \n>>want to debug it yourself, could you please publish the .idx files\n>>so I could have a look at them?\n> \n> \n> Of course: http://home.arcor.de/fork0/download/idx.tar.gz\n> \n\nAfter giving it a quick look, I don't think it locks up. It is just horribly\nslow. get_all_permutations returns (nice ASCII-art follows)\n\n    ___n___\n    \\\n     \\ ____1____\nn! * /  k!(n-k)!\n    /______\n      k=1\n\npermutations, which for your case (22 packs) adds up to 4194303.\n\nI'll look into an optimization so we won't have to call is_superset\nfor every one of them.\n\nOTOH, I might be wrong and it could very well be an infinite loop.\nMind running it over the night? I won't look further into this in\n20 hours or so anyway.\n"},{"id":"11965","messageId":"Pine.LNX.4.64.0511151552400.11232@g5.osdl.org","threadId":"2527","inReplyTo":"20051115223340.GA3951@steel.home","subject":"Re: fix git-pack-redundant crashing sometimes","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-11-15T23:58:02Z","receivedAt":"2005-11-15T23:58:02Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Tue, 15 Nov 2005, Alex Riesen wrote:\n> \n> Sorry, it doesn't. The code loops here:\n> \n> 401             /* find the permutations which contain all missing objects */\n> 402             perm_all = perm = get_all_permutations(non_unique);\n\nLooks like the whole thing is exponential.\n\nA good way to do sane pack handling is to keep a _sorted_ list of all \nobjects each pack has. At that point it becomes much easier to see which \nobjects only exist in one particular pack.\n\nThe sorting itself is O(nlogn), and the \"does this pack have any unique \nobjects\" (or \"is this pack a superset of all other packs\") question should \nthen be O(n).\n\nThis is how the packs are generated in the first place - by sorting the \nobjects and limiting the diff generation to the \"neighbors\" of the \nobjects, you can generate pack-files in O(n logn) rather than O(n**2). \nWhich is pretty important when there are currently 140,000+ objects in the \nkernel tree.\n\n\t\tLinus\n"},{"id":"11997","messageId":"81b0412b0511152301s13944046lb2cbac95f4dab1fd@mail.gmail.com","threadId":"2527","inReplyTo":"437A6B8A.8060905@etek.chalmers.se","subject":"Re: fix git-pack-redundant crashing sometimes","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2005-11-16T07:01:38Z","receivedAt":"2005-11-16T07:01:38Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"On 11/16/05, Lukas Sandström <lukass@etek.chalmers.se> wrote:\n> OTOH, I might be wrong and it could very well be an infinite loop.\n> Mind running it over the night? I won't look further into this in\n> 20 hours or so anyway.\n\nYou missed by some minutes and I fell asleep :) Now, it is some 12\nhours until I get to the machine with the lot of packs.\n"},{"id":"12038","messageId":"7vlkzo73m1.fsf@assigned-by-dhcp.cox.net","threadId":"2527","inReplyTo":"Pine.LNX.4.64.0511151552400.11232@g5.osdl.org","subject":"Re: fix git-pack-redundant crashing sometimes","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-11-16T20:13:42Z","receivedAt":"2005-11-16T20:13:42Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@osdl.org> writes:\n\n> On Tue, 15 Nov 2005, Alex Riesen wrote:\n>> \n>> Sorry, it doesn't. The code loops here:\n>> \n>> 401             /* find the permutations which contain all missing objects */\n>> 402             perm_all = perm = get_all_permutations(non_unique);\n>\n> Looks like the whole thing is exponential.\n\nThis reminds me of one thing I have been meaning to remove.\n\nThe $GIT_OBJECT_DIRECTORY/info/pack file produced by\nupdate-server-info records not just the packs (P lines), but its\ndependencies (D lines) and top objects (T lines).  If there are\nmore than one packs, D lines are meant to help the downloader to\nfigure out what other packs are needed to complete.\n\n\"meant to\" is the keyword here.  The original heuristics was\nvery bad (still correct but way suboptimal) and it has never\nbeen updated.  I do not use that information myself in http\nfetch, and I do not think any Porcelain uses it.\n\nTop objects are tags and commits in the pack that are not\nreachable from any other object in the same pack.  This can be\nuseful if you obtain just a packfile -- you can run server-info\nto produce info/pack file, and resurrect the branch heads and\ntags by using them --- you would not know what they are called,\nthough.  I have been thinking it may be worthwhile to also\nrecord bottom objects (B lines, naturally) --- tags and commits\nin the pack that refer to tags or commits not present in the\nsame pack.  This would help commit walkers to decide which pack\nis more efficient to slurp when faced with multiple choices.  If\nyou see a pack all whose bottom objects you have in your\nrepository, fetching that would complete the commit walking, so\nthe choice would become the matter of choosing such a pack among\nmultiple that has smallest number of objects you do not have\nlocally -- you would have the index file for each pack at that\npoint.\n"},{"id":"12048","messageId":"20051116211128.GA13975@steel.home","threadId":"2527","inReplyTo":"437A6B8A.8060905@etek.chalmers.se","subject":"Re: fix git-pack-redundant crashing sometimes","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2005-11-16T21:11:28Z","receivedAt":"2005-11-16T21:11:28Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"Lukas Sandström, Wed, Nov 16, 2005 00:13:14 +0100:\n> After giving it a quick look, I don't think it locks up. It is just horribly\n> slow. get_all_permutations returns (nice ASCII-art follows)\n> \n>     ___n___\n>     \\\n>      \\ ____1____\n> n! * /  k!(n-k)!\n>     /______\n>       k=1\n> \n> permutations, which for your case (22 packs) adds up to 4194303.\n> \n> I'll look into an optimization so we won't have to call is_superset\n> for every one of them.\n> \n> OTOH, I might be wrong and it could very well be an infinite loop.\n> Mind running it over the night? I won't look further into this in\n> 20 hours or so anyway.\n\nIt doesn't lock up:\n\n$ time git-pack-redundant --all --alt-odb\n.git/objects/pack/pack-3c5133604508466855453f3e609428f4bbba9131.idx\n.git/objects/pack/pack-3c5133604508466855453f3e609428f4bbba9131.pack\n...\n\nreal    24m55.277s\nuser    24m50.778s\nsys     0m0.582s\n\nNow I shall be called \"too impatient\", perhaps?\n"},{"id":"12050","messageId":"437BA6A6.8080900@etek.chalmers.se","threadId":"2527","inReplyTo":"Pine.LNX.4.64.0511151552400.11232@g5.osdl.org","subject":"Re: fix git-pack-redundant crashing sometimes","fromName":"Lukas Sandström","fromEmail":"lukass@etek.chalmers.se","sentAt":"2005-11-16T21:37:42Z","receivedAt":"2005-11-16T21:37:42Z","isPatch":false,"sender":{"key":"luksan@gmail.com","avatar":"https://avatars.githubusercontent.com/u/152281?v=4"},"body":"Linus Torvalds wrote:\n> \n> On Tue, 15 Nov 2005, Alex Riesen wrote:\n> \n>>Sorry, it doesn't. The code loops here:\n>>\n>>401             /* find the permutations which contain all missing objects */\n>>402             perm_all = perm = get_all_permutations(non_unique);\n> \n> \n> Looks like the whole thing is exponential.\n> \nSlightly less, but not far from.\n> A good way to do sane pack handling is to keep a _sorted_ list of all \n> objects each pack has. At that point it becomes much easier to see which \n> objects only exist in one particular pack.\n> \ngit-pack-redundant already does this.\n> The sorting itself is O(nlogn), and the \"does this pack have any unique \n> objects\" (or \"is this pack a superset of all other packs\") question should \n> then be O(n).\n> \nAh, but the question is: \"Does this set of packs contain a superset of\nall objects available in packfiles?\" The answer to the question for a\ncertain set is indeed O(n), but the number of sets which have to be tested\nare ~ O(e**n). (Where n is the number of non-unique packs.)\n\n/Lukas\n"},{"id":"12066","messageId":"437BC7D1.1070605@etek.chalmers.se","threadId":"2527","inReplyTo":"437BA6A6.8080900@etek.chalmers.se","subject":"Re: fix git-pack-redundant crashing sometimes","fromName":"Lukas Sandström","fromEmail":"lukass@etek.chalmers.se","sentAt":"2005-11-16T23:59:13Z","receivedAt":"2005-11-16T23:59:13Z","isPatch":false,"sender":{"key":"luksan@gmail.com","avatar":"https://avatars.githubusercontent.com/u/152281?v=4"},"body":"Lukas Sandström wrote:\n> Linus Torvalds wrote:\n> \n>>On Tue, 15 Nov 2005, Alex Riesen wrote:\n>>\n>>\n>>>Sorry, it doesn't. The code loops here:\n>>>\n>>>401             /* find the permutations which contain all missing objects */\n>>>402             perm_all = perm = get_all_permutations(non_unique);\n>>\n>>\n>>Looks like the whole thing is exponential.\n>>\n> \n> Slightly less, but not far from.\n> \nAfter doing some maths; actually it is very exponential. 2**n - 1 to be precise.\n"},{"id":"12078","messageId":"20051117070852.GA4921@c165.ib.student.liu.se","threadId":"2527","inReplyTo":"437BA6A6.8080900@etek.chalmers.se","subject":"Re: fix git-pack-redundant crashing sometimes","fromName":"Fredrik Kuivinen","fromEmail":"freku045@student.liu.se","sentAt":"2005-11-17T07:08:52Z","receivedAt":"2005-11-17T07:08:52Z","isPatch":false,"sender":{"key":"frekui@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13770967?v=4"},"body":"On Wed, Nov 16, 2005 at 10:37:42PM +0100, Lukas Sandström wrote:\n> Linus Torvalds wrote:\n> > \n> > On Tue, 15 Nov 2005, Alex Riesen wrote:\n> > \n> >>Sorry, it doesn't. The code loops here:\n> >>\n> >>401             /* find the permutations which contain all missing objects */\n> >>402             perm_all = perm = get_all_permutations(non_unique);\n> > \n> > \n> > Looks like the whole thing is exponential.\n> > \n> Slightly less, but not far from.\n> > A good way to do sane pack handling is to keep a _sorted_ list of all \n> > objects each pack has. At that point it becomes much easier to see which \n> > objects only exist in one particular pack.\n> > \n> git-pack-redundant already does this.\n> > The sorting itself is O(nlogn), and the \"does this pack have any unique \n> > objects\" (or \"is this pack a superset of all other packs\") question should \n> > then be O(n).\n> > \n> Ah, but the question is: \"Does this set of packs contain a superset of\n> all objects available in packfiles?\" The answer to the question for a\n> certain set is indeed O(n), but the number of sets which have to be tested\n> are ~ O(e**n). (Where n is the number of non-unique packs.)\n> \n\nIf haven't looked closely at neither the packing nor the pack\nredundant code, but the problem looks very similar to Minimum Set\nCover (see http://www.nada.kth.se/~viggo/wwwcompendium/node146.html\nfor more information), which is NP-hard. So, if Minimum Set Cover is\nthe problem we are trying to solve we can't hope to find a polynomial\ntime algorithm. However, there is a quite simple greedy approximation\nalgorithm in [1] which is referenced from the URL above.\n\n\n- Fredrik\n\n[1]: Johnson, D. S. (1974), \"Approximation algorithms for\n     combinatorial problems\", J. Comput. System Sci. 9, 256-278.\n"},{"id":"12099","messageId":"437C819C.4040507@etek.chalmers.se","threadId":"2527","inReplyTo":"20051115223340.GA3951@steel.home","subject":"[PATCH] Make git-pack-redundant non-horribly slow on large sets of packs","fromName":"Lukas Sandström","fromEmail":"lukass@etek.chalmers.se","sentAt":"2005-11-17T13:11:56Z","receivedAt":"2005-11-17T13:11:56Z","isPatch":true,"sender":{"key":"luksan@gmail.com","avatar":"https://avatars.githubusercontent.com/u/152281?v=4"},"body":"Change the smallest-set detection algortithm so that when\nwe have found a good set, we don't check any larger sets.\n\nSigned-off-by: Lukas Sandström <lukass@etek.chalmers.se>\n\n---\nThis change might make git-pack-redundant return non-optimal\npack-sets in some cases. OTOH, the case which Alex reported\ncompletes in 0.6 sec instead of several minutes.\n\n pack-redundant.c |   62 +++++++++++++++++++++++++++++++++++++++++++-----------\n 1 files changed, 49 insertions(+), 13 deletions(-)\n\napplies-to: 1e3fcf60526c196a46433e6947c9104ca236f230\n498cc056d758b9e1cd21e984be281d55e24f1117\ndiff --git a/pack-redundant.c b/pack-redundant.c\nindex fcb36ff..51d7341 100644\n--- a/pack-redundant.c\n+++ b/pack-redundant.c\n@@ -33,6 +33,7 @@ struct pack_list {\n struct pll {\n \tstruct pll *next;\n \tstruct pack_list *pl;\n+\tsize_t pl_size;\n };\n \n inline void llist_free(struct llist *list)\n@@ -249,18 +250,45 @@ void cmp_two_packs(struct pack_list *p1,\n \t}\n }\n \n+void pll_insert(struct pll **pll, struct pll **hint_table)\n+{\n+\tstruct pll *prev;\n+\tint i = (*pll)->pl_size - 1;\n+\n+\tif (hint_table[i] == NULL) {\n+\t\thint_table[i--] = *pll;\n+\t\tfor (; i >= 0; --i) {\n+\t\t\tif (hint_table[i] != NULL)\n+\t\t\t\tbreak;\n+\t\t}\n+\t\tif (hint_table[i] == NULL) /* no elements in list */\n+\t\t\tdie(\"Why did this happen?\");\n+\t}\n+\n+\tprev = hint_table[i];\n+\twhile (prev->next && prev->next->pl_size < (*pll)->pl_size)\n+\t\tprev = prev->next;\n+\n+\t(*pll)->next = prev->next;\n+\tprev->next = *pll;\n+}\n+\n /* all the permutations have to be free()d at the same time,\n  * since they refer to each other\n  */\n struct pll * get_all_permutations(struct pack_list *list)\n {\n \tstruct pll *subset, *pll, *new_pll = NULL; /*silence warning*/\n-\n+\tstatic struct pll **hint = NULL;\n+\tif (hint == NULL)\n+\t\thint = xcalloc(pack_list_size(list), sizeof(struct pll *));\n+\t\t\n \tif (list == NULL)\n \t\treturn NULL;\n \n \tif (list->next == NULL) {\n \t\tnew_pll = xmalloc(sizeof(struct pll));\n+\t\thint[0] = new_pll;\n \t\tnew_pll->next = NULL;\n \t\tnew_pll->pl = list;\n \t\treturn new_pll;\n@@ -268,24 +296,30 @@ struct pll * get_all_permutations(struct\n \n \tpll = subset = get_all_permutations(list->next);\n \twhile (pll) {\n+\t\tif (pll->pl->pack == list->pack) {\n+\t\t\tpll = pll->next;\n+\t\t\tcontinue;\n+\t\t}\n \t\tnew_pll = xmalloc(sizeof(struct pll));\n-\t\tnew_pll->next = pll->next;\n-\t\tpll->next = new_pll;\n \n \t\tnew_pll->pl = xmalloc(sizeof(struct pack_list));\n \t\tmemcpy(new_pll->pl, list, sizeof(struct pack_list));\n \t\tnew_pll->pl->next = pll->pl;\n+\t\tnew_pll->pl_size = pll->pl_size + 1;\n+\t\t\n+\t\tpll_insert(&new_pll, hint);\n+\n+\t\tpll = pll->next;\n+\t}\n+\t/* add ourself */\n+\tnew_pll = xmalloc(sizeof(struct pll));\n+\tnew_pll->pl = xmalloc(sizeof(struct pack_list));\n+\tmemcpy(new_pll->pl, list, sizeof(struct pack_list));\n+\tnew_pll->pl->next = NULL;\n+\tnew_pll->pl_size = 1;\n+\tpll_insert(&new_pll, hint);\n \n-\t\tpll = new_pll->next;\n-\t}\n-\t/* add ourself to the end */\n-\tnew_pll->next = xmalloc(sizeof(struct pll));\n-\tnew_pll->next->pl = xmalloc(sizeof(struct pack_list));\n-\tnew_pll->next->next = NULL;\n-\tmemcpy(new_pll->next->pl, list, sizeof(struct pack_list));\n-\tnew_pll->next->pl->next = NULL;\n-\n-\treturn subset;\n+\treturn hint[0];\n }\n \n int is_superset(struct pack_list *pl, struct llist *list)\n@@ -401,6 +435,8 @@ void minimize(struct pack_list **min)\n \t/* find the permutations which contain all missing objects */\n \tperm_all = perm = get_all_permutations(non_unique);\n \twhile (perm) {\n+\t\tif (perm_ok && perm->pl_size > perm_ok->pl_size)\n+\t\t\tbreak; /* ignore all larger permutations */\n \t\tif (is_superset(perm->pl, missing)) {\n \t\t\tnew_perm = xmalloc(sizeof(struct pll));\n \t\t\tnew_perm->pl = perm->pl;\n---\n0.99.9.GIT\n"},{"id":"12124","messageId":"pan.2005.11.17.16.56.29.833519@smurf.noris.de","threadId":"2527","inReplyTo":"437BC7D1.1070605@etek.chalmers.se","subject":"Re: fix git-pack-redundant crashing sometimes","fromName":"Matthias Urlichs","fromEmail":"smurf@smurf.noris.de","sentAt":"2005-11-17T16:56:31Z","receivedAt":"2005-11-17T16:56:31Z","isPatch":false,"sender":{"key":"matthias@urlichs.de","avatar":"https://gravatar.com/avatar/2708905af227313eba6f2b2ae0f7d0259b5ac5d71baef58fe5a13c699ce0bbf0?d=mp&s=160"},"body":"Hi, Lukas Sandström wrote:\n\n> After doing some maths; actually it is very exponential. 2**n - 1 to be precise.\n\nIn the general case, yes. However, you can just sort the packs by date\nand sequentially drop all that can be dropped. That's not optimal in the\ngeneral case, but for us it should be close enough.\n\n-- \nMatthias Urlichs   |   {M:U} IT Design @ m-u-it.de   |  smurf@smurf.noris.de\nDisclaimer: The quote was selected randomly. Really. | http://smurf.noris.de\n - -\nWhen was the last time you were drunk?\n"},{"id":"12229","messageId":"437E01A5.7040501@etek.chalmers.se","threadId":"2527","inReplyTo":"437C819C.4040507@etek.chalmers.se","subject":"[PATCH] Fix bug introduced by the latest changes to git-pack-redundant","fromName":"Lukas Sandström","fromEmail":"lukass@etek.chalmers.se","sentAt":"2005-11-18T16:30:29Z","receivedAt":"2005-11-18T16:30:29Z","isPatch":true,"sender":{"key":"luksan@gmail.com","avatar":"https://avatars.githubusercontent.com/u/152281?v=4"},"body":"I forgot to initialize part of the pll struct when copying it.\nFound by valgrind.\n\nSigned-off-by: Lukas Sandström <lukass@etek.chalmers.se>\n---\n\n pack-redundant.c |    2 +-\n 1 files changed, 1 insertions(+), 1 deletions(-)\n\napplies-to: 500482a7b3ebb2ebac182136696cb124332feba8\nb51be59ab5b323ef148f833976a9c324d6a27404\ndiff --git a/pack-redundant.c b/pack-redundant.c\nindex 2d7183e..3123f45 100644\n--- a/pack-redundant.c\n+++ b/pack-redundant.c\n@@ -442,7 +442,7 @@ void minimize(struct pack_list **min)\n \t\t\tbreak; /* ignore all larger permutations */\n \t\tif (is_superset(perm->pl, missing)) {\n \t\t\tnew_perm = xmalloc(sizeof(struct pll));\n-\t\t\tnew_perm->pl = perm->pl;\n+\t\t\tmemcpy(new_perm, perm, sizeof(struct pll));\n \t\t\tnew_perm->next = perm_ok;\n \t\t\tperm_ok = new_perm;\n \t\t}\n---\n0.99.9.GIT\n"},{"id":"12258","messageId":"437E4D54.60901@etek.chalmers.se","threadId":"2527","inReplyTo":"437C819C.4040507@etek.chalmers.se","subject":"[PATCH] Fix a bug in get_all_permutations.","fromName":"Lukas Sandström","fromEmail":"lukass@etek.chalmers.se","sentAt":"2005-11-18T21:53:24Z","receivedAt":"2005-11-18T21:53:24Z","isPatch":true,"sender":{"key":"luksan@gmail.com","avatar":"https://avatars.githubusercontent.com/u/152281?v=4"},"body":"This line was missing in the previous patch for some reason.\n\nSigned-off-by: Lukas Sandström <lukass@etek.chalmers.se>\n\n---\n\n pack-redundant.c |    1 +\n 1 files changed, 1 insertions(+), 0 deletions(-)\n\napplies-to: 5b820842ce0afb836ddbeded3a3f9e8d0ba223f9\ne65d77b8ece9f6e463de0ceeaf6812a2df6d7d96\ndiff --git a/pack-redundant.c b/pack-redundant.c\nindex 3655609..3e3f33a 100644\n--- a/pack-redundant.c\n+++ b/pack-redundant.c\n@@ -291,6 +291,7 @@ struct pll * get_all_permutations(struct\n \t\thint[0] = new_pll;\n \t\tnew_pll->next = NULL;\n \t\tnew_pll->pl = list;\n+\t\tnew_pll->pl_size = 1;\n \t\treturn new_pll;\n \t}\n \n---\n0.99.9.GIT\n"}]}