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 <p...@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);
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Reply via email to