Re: [PATCH] rev-list: preallocate object hash table in --all --objects

From: Jeff King <peff@peff.net>
Date: Mar 29, 2013, 15:12 UTC
Message-ID: <20130329151208.GA22744@sigill.intra.peff.net>
In-Reply-To: <1364563210-28813-1-git-send-email-pclouds@gmail.com>

On Fri, Mar 29, 2013 at 08:20:10PM +0700, Nguyen Thai Ngoc Duy wrote:

Show 16 quoted lines

> Every time the object hash table grows, all entries must be
> rearranged. The few last times could be really expensive when the
> table contains a lot of entries.
> 
> When we do "--all --objects" we know in advance we may need to hash
> all objects. Just prepare the hash table big enough, so there won't be
> any resizing later on. The hash table is resized a couple times before
> prehash_objects() is called. But that's ok because there aren't many
> objects by that time (unless you have tons of refs, likely tags..)
> 
> On linux-2.6.git:
> 
>         before       after
> real    0m34.402s    0m33.288s
> user    0m34.111s    0m32.863s
> sys     0m0.205s     0m0.352s

This feels weirdly specific, and like we should just be tuning our hash table growth better. You show a 3.2% speedup here. I was able to get a 2.8% speedup just by doing this:

diff --git a/object.c b/object.c
index 20703f5..8e5e12c 100644
--- a/object.c
+++ b/object.c
@@ -91,7 +91,7 @@ static void grow_object_hash(void)
 static void grow_object_hash(void)
 {
 	int i;
-	int new_hash_size = obj_hash_size < 32 ? 32 : 2 * obj_hash_size;
+	int new_hash_size = obj_hash_size < 32 ? 32 : 3 * obj_hash_size;
 	struct object **new_hash;
 
 	new_hash = xcalloc(new_hash_size, sizeof(struct object *));

It might be worth trying to figure out what the optimium growth rate is
first, which would help this use case and others. With less fragile
code.

-Peff