{"thread":{"id":"2649","subject":"[PATCH] speedup allocation in pack-redundant.c","startedAt":"2005-11-22T14:56:35Z","lastAt":"2005-11-23T07:31:57Z","messageCount":10,"participants":["Alex Riesen","Junio C Hamano","Lukas Sandström"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"12540","messageId":"81b0412b0511220656l528436b1xea80ee18965e4dda@mail.gmail.com","threadId":"2649","inReplyTo":null,"subject":"[PATCH] speedup allocation in pack-redundant.c","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2005-11-22T14:56:35Z","receivedAt":"2005-11-22T14:56:35Z","isPatch":true,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"Reuse discarded nodes of llists\n\n\nSubject: [PATCH] speedup allocation in pack-redundant.c\n\nSigned-off-by: Alex Riesen \n\n\n---\n\n pack-redundant.c | 32 ++++++++++++++++++++++++++------\n 1 files changed, 26 insertions(+), 6 deletions(-)\n\napplies-to: 0a8441bc998f995dd35380472314802f53c6e1f3\n738ce6cef594ae09b89372859d28f37b1bef9aa1\ndiff --git a/pack-redundant.c b/pack-redundant.c\nindex 1519385..3681170 100644\n--- a/pack-redundant.c\n+++ b/pack-redundant.c\n@@ -36,11 +36,31 @@ struct pll {\n \tsize_t pl_size;\n };\n \n-static inline void llist_free(struct llist *list)\n+static struct llist_item *free_nodes = NULL;\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+\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 \t\tlist->front = list->front->next;\n-\t\tfree(list->back);\n+\t\tllist_item_put(list->back);\n \t}\n \tfree(list);\n }\n@@ -62,13 +82,13 @@ static struct llist * llist_copy(struct \n \tif ((ret->size = list->size) == 0)\n \t\treturn ret;\n \n-\tnew = ret->front = xmalloc(sizeof(struct llist_item));\n+\tnew = ret->front = llist_item_get();\n \tnew->sha1 = list->front->sha1;\n \n \told = list->front->next;\n \twhile (old) {\n \t\tprev = new;\n-\t\tnew = xmalloc(sizeof(struct llist_item));\n+\t\tnew = llist_item_get();\n \t\tprev->next = new;\n \t\tnew->sha1 = old->sha1;\n \t\told = old->next;\n@@ -82,7 +102,7 @@ static struct llist * llist_copy(struct \n static inline struct llist_item * llist_insert(struct llist *list,\n \t\t\t\t\tstruct llist_item *after, char *sha1)\n {\n-\tstruct llist_item *new = xmalloc(sizeof(struct llist_item));\n+\tstruct llist_item *new = llist_item_get();\n \tnew->sha1 = sha1;\n \tnew->next = NULL;\n \n@@ -153,7 +173,7 @@ redo_from_start:\n \t\t\t\tprev->next = l->next;\n \t\t\tif (l == list->back)\n \t\t\t\tlist->back = prev;\n-\t\t\tfree(l);\n+\t\t\tllist_item_put(l);\n \t\t\tlist->size--;\n \t\t\treturn prev;\n \t\t}\n---\n0.99.9.GIT\n"},{"id":"12566","messageId":"7vek58ct4b.fsf@assigned-by-dhcp.cox.net","threadId":"2649","inReplyTo":"81b0412b0511220656l528436b1xea80ee18965e4dda@mail.gmail.com","subject":"Re: [PATCH] speedup allocation in pack-redundant.c","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-11-22T20:41:56Z","receivedAt":"2005-11-22T20:41:56Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Alex Riesen writes:\n\n> Subject: [PATCH] speedup allocation in pack-redundant.c\n>\n> Reuse discarded nodes of llists\n>\n> Signed-off-by: Alex Riesen \n\nI think making allocation/deallocation to the central place is a\ngood cleanup, but I am not sure about the free-nodes reusing.\nDoes this make difference in real life? If so, it might be\nworth doing the slab-like allocation, since free-nodes are very\nsmall structure and malloc overhead is not ignorable there.\n"},{"id":"12569","messageId":"4383A053.8020100@etek.chalmers.se","threadId":"2649","inReplyTo":"7vek58ct4b.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] speedup allocation in pack-redundant.c","fromName":"Lukas Sandström","fromEmail":"lukass@etek.chalmers.se","sentAt":"2005-11-22T22:48:51Z","receivedAt":"2005-11-22T22:48:51Z","isPatch":true,"sender":{"key":"luksan@gmail.com","avatar":"https://avatars.githubusercontent.com/u/152281?v=4"},"body":"Junio C Hamano wrote:\n> Alex Riesen writes:\n> \n> \n>>Subject: [PATCH] speedup allocation in pack-redundant.c\n>>\n>>Reuse discarded nodes of llists\n>>\n>>Signed-off-by: Alex Riesen \n> \n> \n> I think making allocation/deallocation to the central place is a\n> good cleanup, but I am not sure about the free-nodes reusing.\n> Does this make difference in real life? If so, it might be\n> worth doing the slab-like allocation, since free-nodes are very\n> small structure and malloc overhead is not ignorable there.\n> \n> \nI have done some tests, and unfortunatley I saw approx. zero\nimprovement with Alex's patch. (less than 10ms difference when\ntotal runtime is 1.850s, tested on http://home.arcor.de/fork0/download/idx.tar.gz)\n\nDid someone else notice an improvement?\n\nIt's a nice idea though. I'll look into doing slab-allocation\nfor the fun of it, but I'm not really sure that malloc is the\nbottleneck.\n\n/Lukas\n"},{"id":"12570","messageId":"20051122230011.GA2916@steel.home","threadId":"2649","inReplyTo":"7vek58ct4b.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] speedup allocation in pack-redundant.c","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2005-11-22T23:00:11Z","receivedAt":"2005-11-22T23:00:11Z","isPatch":true,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"Junio C Hamano, Tue, Nov 22, 2005 21:41:56 +0100:\n> > Reuse discarded nodes of llists\n> >\n> > Signed-off-by: Alex Riesen \n> \n> I think making allocation/deallocation to the central place is a\n> good cleanup, but I am not sure about the free-nodes reusing.\n> Does this make difference in real life?\n\nIt definitely does, though nor very much. I have no real numbers at\nhand (being home now), but I remember it was 1 min with against 3 min\nwithout the patch on cygwin+fat32, which is already bad enough all by\nitself. Very big repository with no redundant packs in it.\n\n> If so, it might be worth doing the slab-like allocation, since\n> free-nodes are very small structure and malloc overhead is not\n> ignorable there.\n\nLike this?\n\n if ( free_nodes ) { ... }\n else {\n\tstruct llist_node *slab = malloc(sizeof(*slab) * BLKCNT);\n\tfor ( i =0; i < BLKCNT; ++i ) {\n\t slab->next = free_nodes;\n\t free_nodes = slab++;\n\t}\n }\n"},{"id":"12572","messageId":"7vr798b7qz.fsf@assigned-by-dhcp.cox.net","threadId":"2649","inReplyTo":"4383A053.8020100@etek.chalmers.se","subject":"Re: [PATCH] speedup allocation in pack-redundant.c","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-11-22T23:08:52Z","receivedAt":"2005-11-22T23:08:52Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Lukas Sandström writes:\n\n> Did someone else notice an improvement?\n\nNot me. I merged it only for its clean-up value, not immediate\nperformance reasons.\n"},{"id":"12574","messageId":"4383A66D.2030201@etek.chalmers.se","threadId":"2649","inReplyTo":"20051122230011.GA2916@steel.home","subject":"Re: [PATCH] speedup allocation in pack-redundant.c","fromName":"Lukas Sandström","fromEmail":"lukass@etek.chalmers.se","sentAt":"2005-11-22T23:14:53Z","receivedAt":"2005-11-22T23:14:53Z","isPatch":true,"sender":{"key":"luksan@gmail.com","avatar":"https://avatars.githubusercontent.com/u/152281?v=4"},"body":"Alex Riesen wrote:\n> Junio C Hamano, Tue, Nov 22, 2005 21:41:56 +0100:\n>>I think making allocation/deallocation to the central place is a\n>>good cleanup, but I am not sure about the free-nodes reusing.\n>>Does this make difference in real life?\n> \n> \n> It definitely does, though nor very much. I have no real numbers at\n> hand (being home now), but I remember it was 1 min with against 3 min\n> without the patch on cygwin+fat32, which is already bad enough all by\n> itself. Very big repository with no redundant packs in it.\n> \n\nWould you mind sharing the .idx files?\n"},{"id":"12576","messageId":"20051122233845.GC2916@steel.home","threadId":"2649","inReplyTo":"4383A66D.2030201@etek.chalmers.se","subject":"Re: [PATCH] speedup allocation in pack-redundant.c","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2005-11-22T23:38:45Z","receivedAt":"2005-11-22T23:38:45Z","isPatch":true,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"Lukas Sandström, Wed, Nov 23, 2005 00:14:53 +0100:\n> >>I think making allocation/deallocation to the central place is a\n> >>good cleanup, but I am not sure about the free-nodes reusing.\n> >>Does this make difference in real life?\n> > \n> > It definitely does, though nor very much. I have no real numbers at\n> > hand (being home now), but I remember it was 1 min with against 3 min\n> > without the patch on cygwin+fat32, which is already bad enough all by\n> > itself. Very big repository with no redundant packs in it.\n> \n> Would you mind sharing the .idx files?\n\nthis time I probably would (they're not here)... But for a perfomance\ntesting any big repository will do, linux kernel, for example.\n"},{"id":"12578","messageId":"20051122234622.GD2916@steel.home","threadId":"2649","inReplyTo":"4383A053.8020100@etek.chalmers.se","subject":"Re: [PATCH] speedup allocation in pack-redundant.c","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2005-11-22T23:46:22Z","receivedAt":"2005-11-22T23:46:22Z","isPatch":true,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"Lukas Sandström, Tue, Nov 22, 2005 23:48:51 +0100:\n> >>Subject: [PATCH] speedup allocation in pack-redundant.c\n> >>Reuse discarded nodes of llists\n> >>Signed-off-by: Alex Riesen \n> > \n> > I think making allocation/deallocation to the central place is a\n> > good cleanup, but I am not sure about the free-nodes reusing.\n> > Does this make difference in real life? If so, it might be\n> > worth doing the slab-like allocation, since free-nodes are very\n> > small structure and malloc overhead is not ignorable there.\n> > \n> I have done some tests, and unfortunatley I saw approx. zero\n> improvement with Alex's patch. (less than 10ms difference when\n> total runtime is 1.850s, tested on http://home.arcor.de/fork0/download/idx.tar.gz)\n\nCan I suggest you try it in a really really weird environment? Like\nCygwin. And switch some virus scanner on.\n\n> Did someone else notice an improvement?\n\nMy test case had over 100k files in it (just don't ask why. Weird\nenvironments, weird projects, ...)\n\n> It's a nice idea though. I'll look into doing slab-allocation\n> for the fun of it, but I'm not really sure that malloc is the\n> bottleneck.\n\nYes, it usually is not a bottleneck. I think, it just another\nexception.\n"},{"id":"12579","messageId":"4383AFDB.90907@etek.chalmers.se","threadId":"2649","inReplyTo":"20051122233845.GC2916@steel.home","subject":"Re: [PATCH] speedup allocation in pack-redundant.c","fromName":"Lukas Sandström","fromEmail":"lukass@etek.chalmers.se","sentAt":"2005-11-22T23:55:07Z","receivedAt":"2005-11-22T23:55:07Z","isPatch":true,"sender":{"key":"luksan@gmail.com","avatar":"https://avatars.githubusercontent.com/u/152281?v=4"},"body":"Alex Riesen wrote:\n> Lukas Sandström, Wed, Nov 23, 2005 00:14:53 +0100:\n> \n>>>>I think making allocation/deallocation to the central place is a\n>>>>good cleanup, but I am not sure about the free-nodes reusing.\n>>>>Does this make difference in real life?\n>>>\n>>>It definitely does, though nor very much. I have no real numbers at\n>>>hand (being home now), but I remember it was 1 min with against 3 min\n>>>without the patch on cygwin+fat32, which is already bad enough all by\n>>>itself. Very big repository with no redundant packs in it.\n>>\n>>Would you mind sharing the .idx files?\n> \n> \n> this time I probably would (they're not here)... But for a perfomance\n> testing any big repository will do, linux kernel, for example.\n> \nThe problem is that the large repository I have contains lots of\nredundant packs, which makes quite fast to find a complete set\nand end the search. If you don't have any redundant packs, the\ncomplete set search really is 2**n (n = the number of packs).\n\nI did some quick experiments with slab allocation and got a 4.4%\nimprovement on the redundant repo, so that might be worth persuing. \n(Concept patch below)\n\ndiff --git a/pack-redundant.c b/pack-redundant.c\nindex b38baa9..05294f8 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 1024\n+\n static const char pack_redundant_usage[] =\n \"git-pack-redundant [ --verbose ] [ --alt-odb ] < --all | <.pack filename> ...>\";\n \n@@ -38,24 +40,28 @@ struct pll {\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"},{"id":"12600","messageId":"81b0412b0511222331tc43057aqfd942afdebea052c@mail.gmail.com","threadId":"2649","inReplyTo":"4383AFDB.90907@etek.chalmers.se","subject":"Re: speedup allocation in pack-redundant.c","fromName":"Alex Riesen","fromEmail":"raa.lkml@gmail.com","sentAt":"2005-11-23T07:31:57Z","receivedAt":"2005-11-23T07:31:57Z","isPatch":false,"sender":{"key":"raa.lkml@gmail.com","avatar":"https://avatars.githubusercontent.com/u/324101?v=4"},"body":"On 11/23/05, Lukas Sandström wrote:\n> >>>>I think making allocation/deallocation to the central place is a\n> >>>>good cleanup, but I am not sure about the free-nodes reusing.\n> >>>>Does this make difference in real life?\n> >>>\n> >>>It definitely does, though nor very much. I have no real numbers at\n> >>>hand (being home now), but I remember it was 1 min with against 3 min\n> >>>without the patch on cygwin+fat32, which is already bad enough all by\n> >>>itself. Very big repository with no redundant packs in it.\n> >>\n> >>Would you mind sharing the .idx files?\n> >\n> > this time I probably would (they're not here)... But for a perfomance\n> > testing any big repository will do, linux kernel, for example.\n> >\n> The problem is that the large repository I have contains lots of\n> redundant packs, which makes quite fast to find a complete set\n> and end the search. If you don't have any redundant packs, the\n> complete set search really is 2**n (n = the number of packs).\n>\n> I did some quick experiments with slab allocation and got a 4.4%\n> improvement on the redundant repo, so that might be worth persuing.\n> (Concept patch below)\n>\n\nI don't have the old packs anymore, but I benchmarked all three\nallocation types anyway:\n\nmalloc/free:\n\n$ time git-pack-redundant --all --alt-odb\nreal 0m0.092s\nuser 0m0.108s\nsys 0m0.015s\n\nsimple node reuse (the patch in official tree):\n\n$ time git-pack-redundant --all --alt-odb\nreal 0m0.074s\nuser 0m0.093s\nsys 0m0.015s\n\nslab node allocation (your concept patch):\n\n$ time git-pack-redundant --all --alt-odb\nreal 0m0.031s\nuser 0m0.046s\nsys 0m0.015s\n\nThis repository has one pack and 17758 files.\n"}]}