* Junio C Hamano <gitster@xxxxxxxxx> wrote:
> Ingo Molnar <mingo@xxxxxxx> 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 */
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html