Re: [PATCH] lookup_object(): Speed up 'git gc' by 12%, by reducing hash chain length

[Ingo Molnar <mingo@elte.hu>]

* Junio C Hamano <gitster@pobox.com> wrote:

> Ingo Molnar <mingo@elte.hu> writes:
> 
> > diff --git a/object.c b/object.c
> > index 7e1f2bb..b3fe485 100644
> > --- a/object.c
> > +++ b/object.c
> > @@ -91,7 +91,7 @@ struct object *lookup_object(const unsigned char *sha1)
> >  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 : 16 * obj_hash_size;
> >  	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 (obj_hash_size - 1 <= nr_objs * 16)
> >  		grow_object_hash();
> >  
> >  	insert_obj_hash(obj, obj_hash, obj_hash_size);
> 
> Shawn was telling me about this exact topic a few months ago, and I do
> agree that object hash grows too slowly when you need to slurp in many
> objects.

I think the main effect might not be the rate of growth and reduced overhead of 
reallocating and reconstructing the hash 4-6 times, but the *spread* of objects 
within the hash table - i.e. the maximum (i.e. optimal) size of the hash.

In a git gc run the hash grows to the max very quickly, then 99% of execution 
time is spent with that optimally sized hash - so growth rate per se does not 
matter much. (it might matter in other usecases)

Find below a debug patch i use to run with a configurable spread.

Note, i just ran the patch on a different system and there the effect was much 
less pronounced. So i'd prefer independent confirmation as well that it speeds 
up things for others as well.

I'll run more numbers - maybe we are just very sensitive to the exact layout of 
the object hash and a 16x spread created a different, more optimal layout.

Thanks,

	Ingo

---

 git.c    |    6 ++++++
 object.c |    5 +++--
 object.h |    1 +
 3 files changed, 10 insertions(+), 2 deletions(-)

diff --git a/git.c b/git.c
index 4b7dbfa..4c59316 100644
--- a/git.c
+++ b/git.c
@@ -4,6 +4,7 @@
 #include "help.h"
 #include "quote.h"
 #include "run-command.h"
+#include "object.h"
 
 const char git_usage_string[] =
 	"git [--version] [--exec-path[=<path>]] [--html-path]\n"
@@ -97,6 +98,11 @@ static int handle_options(const char ***argv, int *argc, int *envchanged)
 			exit(0);
 		} else if (!strcmp(cmd, "-p") || !strcmp(cmd, "--paginate")) {
 			use_pager = 1;
+		} else if (!strcmp(cmd, "--object-hash-spread")) {
+			object_hash_spread = atol((*argv)[1]);
+			printf("object hash spread: %d\n", object_hash_spread);
+			(*argv)++;
+			(*argc)--;
 		} else if (!strcmp(cmd, "--no-pager")) {
 			use_pager = 0;
 			if (envchanged)
diff --git a/object.c b/object.c
index 7e1f2bb..3d16a8a 100644
--- a/object.c
+++ b/object.c
@@ -7,6 +7,7 @@
 
 static struct object **obj_hash;
 static int nr_objs, obj_hash_size;
+int object_hash_spread = 2;
 
 unsigned int get_max_object_index(void)
 {
@@ -91,7 +92,7 @@ struct object *lookup_object(const unsigned char *sha1)
 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 : object_hash_spread * obj_hash_size;
 	struct object **new_hash;
 
 	new_hash = xcalloc(new_hash_size, sizeof(struct object *));
@@ -116,7 +117,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 (obj_hash_size - 1 <= nr_objs * object_hash_spread)
 		grow_object_hash();
 
 	insert_obj_hash(obj, obj_hash, obj_hash_size);
diff --git a/object.h b/object.h
index b6618d9..180a6c1 100644
--- a/object.h
+++ b/object.h
@@ -75,5 +75,6 @@ int object_list_contains(struct object_list *list, struct object *obj);
 void add_object_array(struct object *obj, const char *name, struct object_array *array);
 void add_object_array_with_mode(struct object *obj, const char *name, struct object_array *array, unsigned mode);
 void object_array_remove_duplicates(struct object_array *);
+extern int object_hash_spread;
 
 #endif /* OBJECT_H */