Re: [PATCH] speedup allocation in pack-redundant.c

Alex Riesen [off-list ref] writes:

Subject: [PATCH] speedup allocation in pack-redundant.c

Reuse discarded nodes of llists

Signed-off-by: Alex Riesen <redacted>

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?  If so, it might be
worth doing the slab-like allocation, since free-nodes are very
small structure and malloc overhead is not ignorable there.

Junio C Hamano wrote:

Alex Riesen [off-list ref] writes:

quoted

Subject: [PATCH] speedup allocation in pack-redundant.c

Reuse discarded nodes of llists

Signed-off-by: Alex Riesen <redacted>

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?  If so, it might be
worth doing the slab-like allocation, since free-nodes are very
small structure and malloc overhead is not ignorable there.

I have done some tests, and unfortunatley I saw approx. zero
improvement with Alex's patch. (less than 10ms difference when
total runtime is 1.850s, tested on http://home.arcor.de/fork0/download/idx.tar.gz)

Did someone else notice an improvement?

It's a nice idea though. I'll look into doing slab-allocation
for the fun of it, but I'm not really sure that malloc is the
bottleneck.

/Lukas

Junio C Hamano, Tue, Nov 22, 2005 21:41:56 +0100:

quoted

Reuse discarded nodes of llists

Signed-off-by: Alex Riesen <redacted>

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.

If so, it might be worth doing the slab-like allocation, since
free-nodes are very small structure and malloc overhead is not
ignorable there.

Like this?

    if ( free_nodes ) { ... }
    else {
	struct llist_node *slab = malloc(sizeof(*slab) * BLKCNT);
	for ( i =0; i < BLKCNT; ++i ) {
	    slab->next = free_nodes;
	    free_nodes = slab++;
	}
    }

Alex Riesen wrote:

Junio C Hamano, Tue, Nov 22, 2005 21:41:56 +0100:

quoted

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?

Lukas Sandström, Wed, Nov 23, 2005 00:14:53 +0100:

quoted

quoted

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.

Lukas Sandström, Tue, Nov 22, 2005 23:48:51 +0100:

quoted

quoted

Subject: [PATCH] speedup allocation in pack-redundant.c
Reuse discarded nodes of llists
Signed-off-by: Alex Riesen <redacted>

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?  If so, it might be
worth doing the slab-like allocation, since free-nodes are very
small structure and malloc overhead is not ignorable there.

I have done some tests, and unfortunatley I saw approx. zero
improvement with Alex's patch. (less than 10ms difference when
total runtime is 1.850s, tested on http://home.arcor.de/fork0/download/idx.tar.gz)

Can I suggest you try it in a really really weird environment? Like
Cygwin. And switch some virus scanner on.

Did someone else notice an improvement?

My test case had over 100k files in it (just don't ask why. Weird
environments, weird projects, ...)

It's a nice idea though. I'll look into doing slab-allocation
for the fun of it, but I'm not really sure that malloc is the
bottleneck.

Yes, it usually is not a bottleneck. I think, it just another
exception.

Alex Riesen wrote:

Lukas Sandström, Wed, Nov 23, 2005 00:14:53 +0100:

quoted

quoted

quoted

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)) {

On 11/23/05, Lukas Sandström [off-list ref] wrote:

quoted

quoted

quoted

quoted

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)

I don't have the old packs anymore, but I benchmarked all three
allocation types anyway:

malloc/free:

$ time git-pack-redundant --all --alt-odb
real    0m0.092s
user    0m0.108s
sys     0m0.015s

simple node reuse (the patch in official tree):

$ time git-pack-redundant --all --alt-odb
real    0m0.074s
user    0m0.093s
sys     0m0.015s

slab node allocation (your concept patch):

$ time git-pack-redundant --all --alt-odb
real    0m0.031s
user    0m0.046s
sys     0m0.015s

This repository has one pack and 17758 files.