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

[Jeff King <peff@peff.net>]

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

> On Fri, Mar 29, 2013 at 10:12 PM, Jeff King <peff@peff.net> wrote:
> > 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:
> 
> It also uses a lot more memory. 5.8m entries for ".. * 2" and 8.8m for
> "... * 3". Probably no big deal for modern machines..

Yeah, it will use more, but it's not going to waste more than half again
more than we already were.

> > 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.
> 
> Agreed. Although I think it's getting out of my domain. I'm not even
> sure how many factors are involved.

There's the load factor that causes us to grow, and the growth factor of
how aggressively we expand when we do need to grow. I fooled around with
a few numbers and the patch below seemed to give good results. Probably
varying both numbers over a range and graphing the result would make
sense, but I don't have time to do it at the moment (each run takes a
while, if I do best-of-five).

[before]
real    0m46.255s
user    0m45.812s
sys     0m0.276s

[after]
real    0m43.729s
user    0m43.204s
sys     0m0.356s

diff --git a/object.c b/object.c
index 20703f5..c3be886 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 : obj_hash_size * 5/2;
 	struct object **new_hash;
 
 	new_hash = xcalloc(new_hash_size, sizeof(struct object *));
@@ -116,7 +116,7 @@ void *create_object(const unsigned char *sha1, int type, void *o)
 	obj->flags = 0;
 	hashcpy(obj->sha1, sha1);
 
-	if (obj_hash_size - 1 <= nr_objs * 2)
+	if (nr_objs + 1 > obj_hash_size * 1/3)
 		grow_object_hash();
 
 	insert_obj_hash(obj, obj_hash, obj_hash_size);