From: Lukas Sandström <lukass@etek.chalmers.se>
Date: Tue, 22 Nov 2005 23:55:07 GMT
Subject: Re: [PATCH] speedup allocation in pack-redundant.c
Message-ID: <4383AFDB.90907@etek.chalmers.se>
In-Reply-To: <20051122233845.GC2916@steel.home>

Alex Riesen wrote:
> Lukas Sandström, Wed, Nov 23, 2005 00:14:53 +0100:
> 
>>>>I think making allocation/deallocation to the central place is a
>>>>good cleanup, but I am not sure about the free-nodes reusing.
>>>>Does this make difference in real life?
>>>
>>>It definitely does, though nor very much. I have no real numbers at
>>>hand (being home now), but I remember it was 1 min with against 3 min
>>>without the patch on cygwin+fat32, which is already bad enough all by
>>>itself. Very big repository with no redundant packs in it.
>>
>>Would you mind sharing the .idx files?
> 
> 
> this time I probably would (they're not here)... But for a perfomance
> testing any big repository will do, linux kernel, for example.
> 
The problem is that the large repository I have contains lots of
redundant packs, which makes quite fast to find a complete set
and end the search. If you don't have any redundant packs, the
complete set search really is 2**n (n = the number of packs).

I did some quick experiments with slab allocation and got a 4.4%
improvement on the redundant repo, so that might be worth persuing. 
(Concept patch below)

diff --git a/pack-redundant.c b/pack-redundant.c
index b38baa9..05294f8 100644
--- a/pack-redundant.c
+++ b/pack-redundant.c
@@ -8,6 +8,8 @@
 
 #include "cache.h"
 
+#define BLKSIZE 1024
+
 static const char pack_redundant_usage[] =
 "git-pack-redundant [ --verbose ] [ --alt-odb ] < --all | <.pack filename> ...>";
 
@@ -38,24 +40,28 @@ struct pll {
 
 static struct llist_item *free_nodes = NULL;
 
+static inline void llist_item_put(struct llist_item *item)
+{
+	item->next = free_nodes;
+	free_nodes = item;
+}
+
 static inline struct llist_item *llist_item_get()
 {
 	struct llist_item *new;
 	if ( free_nodes ) {
 		new = free_nodes;
 		free_nodes = free_nodes->next;
-	} else
-		new = xmalloc(sizeof(struct llist_item));
-
+	} else {
+		int i = 1;
+		new = xmalloc(sizeof(struct llist_item) * BLKSIZE);
+		for(;i < BLKSIZE; i++) {
+			llist_item_put(&new[i]);
+		}
+	}
 	return new;
 }
 
-static inline void llist_item_put(struct llist_item *item)
-{
-	item->next = free_nodes;
-	free_nodes = item;
-}
-
 static void llist_free(struct llist *list)
 {
 	while((list->back = list->front)) {