{"thread":{"id":"2886","subject":"[PATCH] git-pack-redundant: speed and memory usage improvements","startedAt":"2005-12-20T20:05:54Z","lastAt":"2005-12-20T21:26:19Z","messageCount":3,"participants":["Lukas Sandström","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"13842","messageId":"43A86422.3090909@etek.chalmers.se","threadId":"2886","inReplyTo":null,"subject":"[PATCH] git-pack-redundant: speed and memory usage improvements","fromName":"Lukas Sandström","fromEmail":"lukass@etek.chalmers.se","sentAt":"2005-12-20T20:05:54Z","receivedAt":"2005-12-20T20:05:54Z","isPatch":true,"sender":{"key":"luksan@gmail.com","avatar":"https://avatars.githubusercontent.com/u/152281?v=4"},"body":"Slab allocation of llist entries gives some speed improvements.\n\nNot computing the pack_list permutaions all at once reduces memory\nusage greatly on repositories with many packs.\n\nSigned-off-by: Lukas Sandström <lukass@etek.chalmers.se>\n\n---\nThis might be post-1.0 material, but I have tested it on a couple of\ndifferent repositories and it appears to work as before, only faster\nand using less memory.\n\n pack-redundant.c |  147 +++++++++++++++++++++++++-----------------------------\n 1 files changed, 68 insertions(+), 79 deletions(-)\n\ne21c29b79531a98d52dcaf647968cde8e9a462d9\ndiff --git a/pack-redundant.c b/pack-redundant.c\nindex 0a43278..1869b38 100644\n--- a/pack-redundant.c\n+++ b/pack-redundant.c\n@@ -8,6 +8,8 @@\n \n #include \"cache.h\"\n \n+#define BLKSIZE 512\n+\n static const char pack_redundant_usage[] =\n \"git-pack-redundant [ --verbose ] [ --alt-odb ] < --all | <.pack filename> ...>\";\n \n@@ -33,29 +35,32 @@ static struct pack_list {\n struct pll {\n \tstruct pll *next;\n \tstruct pack_list *pl;\n-\tsize_t pl_size;\n };\n \n static struct llist_item *free_nodes = NULL;\n \n+static inline void llist_item_put(struct llist_item *item)\n+{\n+\titem->next = free_nodes;\n+\tfree_nodes = item;\n+}\n+\n static inline struct llist_item *llist_item_get()\n {\n \tstruct llist_item *new;\n \tif ( free_nodes ) {\n \t\tnew = free_nodes;\n \t\tfree_nodes = free_nodes->next;\n-\t} else\n-\t\tnew = xmalloc(sizeof(struct llist_item));\n-\n+\t} else {\n+\t\tint i = 1;\n+\t\tnew = xmalloc(sizeof(struct llist_item) * BLKSIZE);\n+\t\tfor(;i < BLKSIZE; i++) {\n+\t\t\tllist_item_put(&new[i]);\n+\t\t}\n+\t}\n \treturn new;\n }\n \n-static inline void llist_item_put(struct llist_item *item)\n-{\n-\titem->next = free_nodes;\n-\tfree_nodes = item;\n-}\n-\n static void llist_free(struct llist *list)\n {\n \twhile((list->back = list->front)) {\n@@ -270,77 +275,58 @@ static void cmp_two_packs(struct pack_li\n \t}\n }\n \n-static void pll_insert(struct pll **pll, struct pll **hint_table)\n+void pll_free(struct pll *l)\n {\n-\tstruct pll *prev;\n-\tint i = (*pll)->pl_size - 1;\n+\tstruct pll *old;\n+\tstruct pack_list *opl;\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+\twhile (l) {\n+\t\told = l;\n+\t\twhile (l->pl) {\n+\t\t\topl = l->pl;\n+\t\t\tl->pl = opl->next;\n+\t\t\tfree(opl);\n \t\t}\n-\t\tif (hint_table[i] == NULL) /* no elements in list */\n-\t\t\tdie(\"Why did this happen?\");\n+\t\tl = l->next;\n+\t\tfree(old);\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-static struct pll * get_all_permutations(struct pack_list *list)\n+static struct pll * get_permutations(struct pack_list *list, int n)\n {\n-\tstruct pll *subset, *pll, *new_pll = NULL; /*silence warning*/\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+\tstruct pll *subset, *ret = NULL, *new_pll = NULL, *pll;\n+\n+\tif (list == NULL || pack_list_size(list) < n || n == 0)\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\tnew_pll->pl_size = 1;\n-\t\treturn new_pll;\n+\tif (n == 1) {\n+\t\twhile (list) {\n+\t\t\tnew_pll = xmalloc(sizeof(pll));\n+\t\t\tnew_pll->pl = NULL;\n+\t\t\tpack_list_insert(&new_pll->pl, list);\n+\t\t\tnew_pll->next = ret;\n+\t\t\tret = new_pll;\n+\t\t\tlist = list->next;\n+\t\t}\n+\t\treturn ret;\n \t}\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+\twhile (list->next) {\n+\t\tsubset = get_permutations(list->next, n - 1);\n+\t\twhile (subset) {\n+\t\t\tnew_pll = xmalloc(sizeof(pll));\n+\t\t\tnew_pll->pl = subset->pl;\n+\t\t\tpack_list_insert(&new_pll->pl, list);\n+\t\t\tnew_pll->next = ret;\n+\t\t\tret = new_pll;\n+\t\t\tsubset = subset->next;\n \t\t}\n-\t\tnew_pll = xmalloc(sizeof(struct 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-\treturn hint[0];\n+\t\tlist = list->next;\n+\t}\n+\treturn ret;\n }\n \n static int is_superset(struct pack_list *pl, struct llist *list)\n@@ -428,6 +414,7 @@ static void minimize(struct pack_list **\n \tstruct pll *perm, *perm_all, *perm_ok = NULL, *new_perm;\n \tstruct llist *missing;\n \tsize_t min_perm_size = (size_t)-1, perm_size;\n+\tint n;\n \n \tpl = local_packs;\n \twhile (pl) {\n@@ -441,8 +428,7 @@ static void minimize(struct pack_list **\n \tmissing = llist_copy(all_objects);\n \tpl = unique;\n \twhile (pl) {\n-\t\tllist_sorted_difference_inplace(missing,\n-\t\t\t\t\t\tpl->all_objects);\n+\t\tllist_sorted_difference_inplace(missing, pl->all_objects);\n \t\tpl = pl->next;\n \t}\n \n@@ -453,19 +439,21 @@ static void minimize(struct pack_list **\n \t}\n \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\tmemcpy(new_perm, perm, sizeof(struct pll));\n-\t\t\tnew_perm->next = perm_ok;\n-\t\t\tperm_ok = new_perm;\n+\tfor (n = 1; n <= pack_list_size(non_unique) && !perm_ok; n++) {\n+\t\tperm_all = perm = get_permutations(non_unique, n);\n+\t\twhile (perm) {\n+\t\t\tif (is_superset(perm->pl, missing)) {\n+\t\t\t\tnew_perm = xmalloc(sizeof(struct pll));\n+\t\t\t\tmemcpy(new_perm, perm, sizeof(struct pll));\n+\t\t\t\tnew_perm->next = perm_ok;\n+\t\t\t\tperm_ok = new_perm;\n+\t\t\t}\n+\t\t\tperm = perm->next;\n \t\t}\n-\t\tperm = perm->next;\n+\t\tif (perm_ok)\n+\t\t\tbreak;\n+\t\tpll_free(perm_all);\n \t}\n-\t\n \tif (perm_ok == NULL)\n \t\tdie(\"Internal error: No complete sets found!\\n\");\n \n@@ -537,6 +525,7 @@ static void scan_alt_odb_packs(void)\n \t\t\t\t\t\t\talt->all_objects);\n \t\t\tlocal = local->next;\n \t\t}\n+\t\tllist_sorted_difference_inplace(all_objects, alt->all_objects);\n \t\talt = alt->next;\n \t}\n }\n-- \n0.99.9.GIT\n"},{"id":"13843","messageId":"7virtjh479.fsf@assigned-by-dhcp.cox.net","threadId":"2886","inReplyTo":"43A86422.3090909@etek.chalmers.se","subject":"Re: [PATCH] git-pack-redundant: speed and memory usage improvements","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-12-20T21:02:50Z","receivedAt":"2005-12-20T21:02:50Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Lukas Sandström <lukass@etek.chalmers.se> writes:\n\n> This might be post-1.0 material, but I have tested it on a couple of\n> different repositories and it appears to work as before, only faster\n> and using less memory.\n\nThanks.\n\nI had an impression that somehow we already had this slabbish\nallocation but apparently we didn't.\n\nAny particular area you have worries/uncertainty about, that\nmakes you mark this post-1.0?\n"},{"id":"13844","messageId":"43A876FB.8020901@etek.chalmers.se","threadId":"2886","inReplyTo":"7virtjh479.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] git-pack-redundant: speed and memory usage improvements","fromName":"Lukas Sandström","fromEmail":"lukass@etek.chalmers.se","sentAt":"2005-12-20T21:26:19Z","receivedAt":"2005-12-20T21:26:19Z","isPatch":true,"sender":{"key":"luksan@gmail.com","avatar":"https://avatars.githubusercontent.com/u/152281?v=4"},"body":"Junio C Hamano wrote:\n> Lukas Sandström <lukass@etek.chalmers.se> writes:\n> \n> \n>>This might be post-1.0 material, but I have tested it on a couple of\n>>different repositories and it appears to work as before, only faster\n>>and using less memory.\n> \n> \n> Thanks.\n> \n> I had an impression that somehow we already had this slabbish\n> allocation but apparently we didn't.\n> \n> Any particular area you have worries/uncertainty about, that\n> makes you mark this post-1.0?\n> \n\nNo, as far as I can see, there should be no problems with the patch.\nIt is non-trivial though so, according to history, there might be \nbugs that only show on certain repositories.\n\n/Lukas\n"}]}