[PATCH 00/11] Micro-optimizing lookup_object()

[PATCH 00/11] Micro-optimizing lookup_object()

[Junio C Hamano]

I noticed that a typical "git repack -a -d -f" spends about 50% of the
time during the "Counting objects" phase inside lookup_object(). The
look-up is implemented as a hashtable with linear probing that limits the
maximum load-factor to 50%, and during repacking the Linux kernel
repository, we count 2,139,209 objects, and the worst case we probe 50
hash entries to find a single object in the hash table due to slot
collisions. The lookup_object() function is called 88,603,392 times.

After cleaning up the existing code a bit, this series adds "--count-only"
option to "pack-objects" to tell it to stop after the "Counting objects"
phase for benchmarking purposes. To emulate the "Counting objects" phase
of a full repack, we can run this (perhaps under "/usr/bin/time"):

  git pack-objects --count-only --keep-true-parents --honor-pack-keep \
      --non-empty --all --reflog --no-reuse-delta \
      --delta-base-offset --stdout </dev/null >/dev/null

On my development box, the slightly cleaned-up existing linear probing
code gives (best of three runs with hot cache):

  31.89user 2.16system 0:34.16elapsed 99%CPU (0avgtext+0avgdata 2965264maxresident)k
  0inputs+0outputs (0major+225336minor)pagefaults 0swaps

Then the series replaces lookup_object(), insert_obj_hash() and
grow_object_hash() with a naive implementation of cuckoo hashing that uses
two hash functions. The performance is not very impressive, and this wastes
too much memory, due to its rather poor strategy to re-grow the table size:

  32.04user 3.43system 0:35.58elapsed 99%CPU (0avgtext+0avgdata 8178672maxresident)k
  0inputs+0outputs (0major+1206546minor)pagefaults 0swaps

As we have 20-byte object names as the hash key material, we could easily
extend this to use 5 hash functions instead of 2. This reduces the memory
usage by improving the load factor, but we spend extra cycles in lookup:

  31.66user 2.14system 0:33.91elapsed 99%CPU (0avgtext+0avgdata 2874176maxresident)k
  0inputs+0outputs (0major+225342minor)pagefaults 0swaps

At this step with 5-way cuckoo, we are slightly better than the original
linear probing. By using smaller number of hash functions, we can reduce
the cycles we need in lookup, while we lose on the load factor.

Here is what we get from the code with 4 hashes:

  30.88user 2.32system 0:33.31elapsed 99%CPU (0avgtext+0avgdata 3135984maxresident)k
  0inputs+0outputs (0major+290857minor)pagefaults 0swaps

And here is with 3 hashes:

  30.68user 2.26system 0:33.05elapsed 99%CPU (0avgtext+0avgdata 3660832maxresident)k
  0inputs+0outputs (0major+421963minor)pagefaults 0swaps

The best balance is somewhere between 3-hash and 4-hash, it seems. We are
getting ~4% runtime performance improvements (31.89 vs 30.68).

Just as a sanity check, the final patch in the series reduces the number
of hashes back to 2, which yields a similar performance characteristics
from the original "naive" cuckoo implementation:

  31.06user 3.22system 0:34.39elapsed 99%CPU (0avgtext+0avgdata 8176512maxresident)k
  0inputs+0outputs (0major+1206542minor)pagefaults 0swaps

The real optimization opportunity _may_ be to reduce the calls we make to
the function---we are calling lookup() 40+ times on one object. But that
is outside the scope of this series.

This series is not for application but primarily is to serve as the
supplimental data for the above numbers. A re-rolled series that consists
of the earlier clean-ups and then a patch to replace the linear probing
with 4-way cuckoo will be queued instead in 'pu'.

Junio C Hamano (11):
  object.c: code movement for readability
  object.c: remove duplicated code for object hashing
  pack-objects --count-only
  object: next_size() helper for readability
  object hash: we know the table size is a power of two
  object: growing the hash-table more aggressively does not help much
  object: try naive cuckoo hashing
  object: try 5-way cuckoo -- use all 20-bytes of SHA-1
  object: try 4-way cuckoo
  object: try 3-way cuckoo
  object: try 2-way cuckoo again

 builtin/pack-objects.c |    7 +++
 object.c               |  138 +++++++++++++++++++++++++++++-------------------
 2 files changed, 91 insertions(+), 54 deletions(-)

-- 
1.7.6.433.g1421f

[PATCH 01/11] object.c: code movement for readability

[Junio C Hamano]

This only moves the lines around a bit to gather the definitions of code
and data that manage the hash function and the object hash table into one
place (examine "blame -M" output to see nothing new is introduced).

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 object.c |   40 ++++++++++++++++++++--------------------
 1 files changed, 20 insertions(+), 20 deletions(-)

diff --git a/object.c b/object.c
index 31976b5..35ff130 100644
--- a/object.c
+++ b/object.c
@@ -5,19 +5,6 @@
 #include "commit.h"
 #include "tag.h"
 
-static struct object **obj_hash;
-static int nr_objs, obj_hash_size;
-
-unsigned int get_max_object_index(void)
-{
-	return obj_hash_size;
-}
-
-struct object *get_indexed_object(unsigned int idx)
-{
-	return obj_hash[idx];
-}
-
 static const char *object_type_strings[] = {
 	NULL,		/* OBJ_NONE = 0 */
 	"commit",	/* OBJ_COMMIT = 1 */
@@ -43,6 +30,19 @@ int type_from_string(const char *str)
 	die("invalid object type \"%s\"", str);
 }
 
+static struct object **obj_hash;
+static int nr_objs, obj_hash_size;
+
+unsigned int get_max_object_index(void)
+{
+	return obj_hash_size;
+}
+
+struct object *get_indexed_object(unsigned int idx)
+{
+	return obj_hash[idx];
+}
+
 static unsigned int hash_obj(struct object *obj, unsigned int n)
 {
 	unsigned int hash;
@@ -50,6 +50,13 @@ static unsigned int hash_obj(struct object *obj, unsigned int n)
 	return hash % n;
 }
 
+static unsigned int hashtable_index(const unsigned char *sha1)
+{
+	unsigned int i;
+	memcpy(&i, sha1, sizeof(unsigned int));
+	return i % obj_hash_size;
+}
+
 static void insert_obj_hash(struct object *obj, struct object **hash, unsigned int size)
 {
 	unsigned int j = hash_obj(obj, size);
@@ -62,13 +69,6 @@ static void insert_obj_hash(struct object *obj, struct object **hash, unsigned i
 	hash[j] = obj;
 }
 
-static unsigned int hashtable_index(const unsigned char *sha1)
-{
-	unsigned int i;
-	memcpy(&i, sha1, sizeof(unsigned int));
-	return i % obj_hash_size;
-}
-
 struct object *lookup_object(const unsigned char *sha1)
 {
 	unsigned int i;
-- 
1.7.6.433.g1421f

[PATCH 02/11] object.c: remove duplicated code for object hashing

[Junio C Hamano]

The index into object hash was computed in two different places,
risking them to diverge. Implement a single helper function and
use it in these two locations.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 object.c |   17 +++++------------
 1 files changed, 5 insertions(+), 12 deletions(-)

diff --git a/object.c b/object.c
index 35ff130..4ff2d7d 100644
--- a/object.c
+++ b/object.c
@@ -43,23 +43,16 @@ struct object *get_indexed_object(unsigned int idx)
 	return obj_hash[idx];
 }
 
-static unsigned int hash_obj(struct object *obj, unsigned int n)
+static unsigned int hash_val(const unsigned char *sha1)
 {
 	unsigned int hash;
-	memcpy(&hash, obj->sha1, sizeof(unsigned int));
-	return hash % n;
-}
-
-static unsigned int hashtable_index(const unsigned char *sha1)
-{
-	unsigned int i;
-	memcpy(&i, sha1, sizeof(unsigned int));
-	return i % obj_hash_size;
+	memcpy(&hash, sha1, sizeof(unsigned int));
+	return hash;
 }
 
 static void insert_obj_hash(struct object *obj, struct object **hash, unsigned int size)
 {
-	unsigned int j = hash_obj(obj, size);
+	unsigned int j = hash_val(obj->sha1) % size;
 
 	while (hash[j]) {
 		j++;
@@ -77,7 +70,7 @@ struct object *lookup_object(const unsigned char *sha1)
 	if (!obj_hash)
 		return NULL;
 
-	i = hashtable_index(sha1);
+	i = hash_val(sha1) % obj_hash_size;
 	while ((obj = obj_hash[i]) != NULL) {
 		if (!hashcmp(sha1, obj->sha1))
 			break;
-- 
1.7.6.433.g1421f

[PATCH 03/11] pack-objects --count-only

[Junio C Hamano]

This is merely to help debugging the bottleneck of "Counting objects"
phase of the pack-objects process.  Use it like this:

git pack-objects --count-only --keep-true-parents --honor-pack-keep \
	--non-empty --all --reflog --no-reuse-delta \
	--delta-base-offset --stdout </dev/null >/dev/null

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 builtin/pack-objects.c |    7 +++++++
 1 files changed, 7 insertions(+), 0 deletions(-)

diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index f402a84..6a208a9 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -2121,6 +2121,7 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)
 	int use_internal_rev_list = 0;
 	int thin = 0;
 	int all_progress_implied = 0;
+	int count_only = 0;
 	uint32_t i;
 	const char **rp_av;
 	int rp_ac_alloc = 64;
@@ -2291,6 +2292,10 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)
 			grafts_replace_parents = 0;
 			continue;
 		}
+		if (!strcmp("--count-only", arg)) {
+			count_only = 1;
+			continue;
+		}
 		usage(pack_usage);
 	}
 
@@ -2348,6 +2353,8 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)
 
 	if (non_empty && !nr_result)
 		return 0;
+	if (count_only)
+		return 0;
 	if (nr_result)
 		prepare_pack(window, depth);
 	write_pack_file();
-- 
1.7.6.433.g1421f

[PATCH 04/11] object: next_size() helper for readability

[Junio C Hamano]

Move the heuristics to grow the table size into a separate
helper function to make the caller more readable.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 object.c |    7 ++++++-
 1 files changed, 6 insertions(+), 1 deletions(-)

diff --git a/object.c b/object.c
index 4ff2d7d..259a67e 100644
--- a/object.c
+++ b/object.c
@@ -81,10 +81,15 @@ struct object *lookup_object(const unsigned char *sha1)
 	return obj;
 }
 
+static int next_size(int sz)
+{
+	return sz < 32 ? 32 : 2 * sz;
+}
+
 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 = next_size(obj_hash_size);
 	struct object **new_hash;
 
 	new_hash = xcalloc(new_hash_size, sizeof(struct object *));
-- 
1.7.6.433.g1421f

[PATCH 05/11] object hash: we know the table size is a power of two

[Junio C Hamano]

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 object.c |    4 ++--
 1 files changed, 2 insertions(+), 2 deletions(-)

diff --git a/object.c b/object.c
index 259a67e..d95d7a6 100644
--- a/object.c
+++ b/object.c
@@ -52,7 +52,7 @@ static unsigned int hash_val(const unsigned char *sha1)
 
 static void insert_obj_hash(struct object *obj, struct object **hash, unsigned int size)
 {
-	unsigned int j = hash_val(obj->sha1) % size;
+	unsigned int j = hash_val(obj->sha1) & (size-1);
 
 	while (hash[j]) {
 		j++;
@@ -70,7 +70,7 @@ struct object *lookup_object(const unsigned char *sha1)
 	if (!obj_hash)
 		return NULL;
 
-	i = hash_val(sha1) % obj_hash_size;
+	i = hash_val(sha1) & (obj_hash_size-1);
 	while ((obj = obj_hash[i]) != NULL) {
 		if (!hashcmp(sha1, obj->sha1))
 			break;
-- 
1.7.6.433.g1421f

[PATCH 06/11] object: growing the hash-table more aggressively does not help much

[Junio C Hamano]

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
../+v/2555c0d98970098861c97b7746f2b8846c823e6f/git-pack-objects
Counting objects: 2139209, done.
32.07user 1.96system 0:34.15elapsed 99%CPU (0avgtext+0avgdata 2966176maxresident)k
0inputs+0outputs (0major+225410minor)pagefaults 0swaps
Counting objects: 2139209, done.
31.89user 2.16system 0:34.16elapsed 99%CPU (0avgtext+0avgdata 2965264maxresident)k
0inputs+0outputs (0major+225336minor)pagefaults 0swaps
Counting objects: 2139209, done.
32.01user 2.12system 0:34.23elapsed 99%CPU (0avgtext+0avgdata 2964832maxresident)k
0inputs+0outputs (0major+225332minor)pagefaults 0swaps
---
 object.c |    3 ++-
 1 files changed, 2 insertions(+), 1 deletions(-)

diff --git a/object.c b/object.c
index d95d7a6..c2c0a7d 100644
--- a/object.c
+++ b/object.c
@@ -83,7 +83,8 @@ struct object *lookup_object(const unsigned char *sha1)
 
 static int next_size(int sz)
 {
-	return sz < 32 ? 32 : 2 * sz;
+	return (sz < 32 ? 32 :
+		(sz < 1024 * 1024 ? 8 : 2) * sz);
 }
 
 static void grow_object_hash(void)
-- 
1.7.6.433.g1421f

[PATCH 07/11] object: try naive cuckoo hashing

[Junio C Hamano]

Signed-off-by: Junio C Hamano <gitster@pobox.com>

---
../+v/65c71a61547aecd8a6830391fda31ed5d18e0529/git-pack-objects
Counting objects: 2139209, done.
32.04user 3.43system 0:35.58elapsed 99%CPU (0avgtext+0avgdata 8178672maxresident)k
0inputs+0outputs (0major+1206546minor)pagefaults 0swaps
Counting objects: 2139209, done.
33.41user 3.15system 0:36.67elapsed 99%CPU (0avgtext+0avgdata 8178688maxresident)k
0inputs+0outputs (0major+1206547minor)pagefaults 0swaps
Counting objects: 2139209, done.
32.24user 3.17system 0:35.51elapsed 99%CPU (0avgtext+0avgdata 8179968maxresident)k
0inputs+0outputs (0major+1206598minor)pagefaults 0swaps
---
 object.c |   99 ++++++++++++++++++++++++++++++++++++++++++--------------------
 1 files changed, 67 insertions(+), 32 deletions(-)

diff --git a/object.c b/object.c
index c2c0a7d..7624c48 100644
--- a/object.c
+++ b/object.c
@@ -50,33 +50,52 @@ static unsigned int hash_val(const unsigned char *sha1)
 	return hash;
 }
 
-static void insert_obj_hash(struct object *obj, struct object **hash, unsigned int size)
-{
-	unsigned int j = hash_val(obj->sha1) & (size-1);
 
-	while (hash[j]) {
-		j++;
-		if (j >= size)
-			j = 0;
-	}
-	hash[j] = obj;
-}
+#define H1(sha1) (hash_val(sha1) % obj_hash_size)
+#define H2(sha1) (hash_val((sha1) + sizeof(unsigned int)) % obj_hash_size)
 
 struct object *lookup_object(const unsigned char *sha1)
 {
-	unsigned int i;
 	struct object *obj;
 
 	if (!obj_hash)
 		return NULL;
 
-	i = hash_val(sha1) & (obj_hash_size-1);
-	while ((obj = obj_hash[i]) != NULL) {
-		if (!hashcmp(sha1, obj->sha1))
-			break;
-		i++;
-		if (i == obj_hash_size)
-			i = 0;
+	if ((obj = obj_hash[H1(sha1)]) && !hashcmp(sha1, obj->sha1))
+		return obj;
+	if ((obj = obj_hash[H2(sha1)]) && !hashcmp(sha1, obj->sha1))
+		return obj;
+	return NULL;
+}
+
+static void grow_object_hash(void); /* forward */
+
+/*
+ * A naive single-table cuckoo hashing implementation.
+ * Return NULL when "obj" is successfully inserted. Otherwise
+ * return a pointer to the object to be inserted (which may
+ * be different from the original obj). The caller is expected
+ * to grow the hash table and re-insert the returned object.
+ */
+static struct object *insert_obj_hash(struct object *obj)
+{
+	int loop;
+
+	for (loop = obj_hash_size / 2; 0 <= loop; loop--) {
+		struct object *tmp_obj;
+		unsigned int ix;
+
+		ix = H1(obj->sha1);
+		if (!obj_hash[ix]) {
+			obj_hash[ix] = obj;
+			return NULL;
+		}
+		ix = H2(obj->sha1);
+		tmp_obj = obj_hash[ix];
+		obj_hash[ix] = obj;
+		if (!tmp_obj)
+			return NULL;
+		obj = tmp_obj;
 	}
 	return obj;
 }
@@ -89,25 +108,36 @@ static int next_size(int sz)
 
 static void grow_object_hash(void)
 {
-	int i;
-	int new_hash_size = next_size(obj_hash_size);
-	struct object **new_hash;
-
-	new_hash = xcalloc(new_hash_size, sizeof(struct object *));
-	for (i = 0; i < obj_hash_size; i++) {
-		struct object *obj = obj_hash[i];
-		if (!obj)
+	struct object **current_hash;
+	int current_size;
+
+	current_hash = obj_hash;
+	current_size = obj_hash_size;
+	while (1) {
+		int i;
+		obj_hash_size = next_size(obj_hash_size);
+		obj_hash = xcalloc(obj_hash_size, sizeof(struct object *));
+
+		for (i = 0; i < current_size; i++) {
+			if (!current_hash[i])
+				continue;
+			if (insert_obj_hash(current_hash[i]))
+				break;
+		}
+		if (i < current_size) {
+			/* too small - grow and retry */
+			free(obj_hash);
 			continue;
-		insert_obj_hash(obj, new_hash, new_hash_size);
+		}
+		free(current_hash);
+		return;
 	}
-	free(obj_hash);
-	obj_hash = new_hash;
-	obj_hash_size = new_hash_size;
 }
 
 void *create_object(const unsigned char *sha1, int type, void *o)
 {
 	struct object *obj = o;
+	struct object *to_insert;
 
 	obj->parsed = 0;
 	obj->used = 0;
@@ -117,8 +147,13 @@ void *create_object(const unsigned char *sha1, int type, void *o)
 
 	if (obj_hash_size - 1 <= nr_objs * 2)
 		grow_object_hash();
-
-	insert_obj_hash(obj, obj_hash, obj_hash_size);
+	to_insert = obj;
+	while (1) {
+		to_insert = insert_obj_hash(to_insert);
+		if (!to_insert)
+			break;
+		grow_object_hash();
+	}
 	nr_objs++;
 	return obj;
 }
-- 
1.7.6.433.g1421f

[PATCH 08/11] object: try 5-way cuckoo -- use all 20-bytes of SHA-1

[Junio C Hamano]

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
../+v/ced878c983ddc9a256b22535aa8af006529ec3d0/git-pack-objects
Counting objects: 2139209, done.
31.66user 2.14system 0:33.91elapsed 99%CPU (0avgtext+0avgdata 2874176maxresident)k
0inputs+0outputs (0major+225342minor)pagefaults 0swaps
Counting objects: 2139209, done.
31.79user 2.03system 0:33.93elapsed 99%CPU (0avgtext+0avgdata 2875808maxresident)k
0inputs+0outputs (0major+225444minor)pagefaults 0swaps
Counting objects: 2139209, done.
31.80user 1.94system 0:33.84elapsed 99%CPU (0avgtext+0avgdata 2875792maxresident)k
0inputs+0outputs (0major+225443minor)pagefaults 0swaps
---
 object.c |   43 ++++++++++++++++++++++++++++++-------------
 1 files changed, 30 insertions(+), 13 deletions(-)

diff --git a/object.c b/object.c
index 7624c48..c777520 100644
--- a/object.c
+++ b/object.c
@@ -43,27 +43,27 @@ struct object *get_indexed_object(unsigned int idx)
 	return obj_hash[idx];
 }
 
-static unsigned int hash_val(const unsigned char *sha1)
-{
-	unsigned int hash;
-	memcpy(&hash, sha1, sizeof(unsigned int));
-	return hash;
-}
-
 
-#define H1(sha1) (hash_val(sha1) % obj_hash_size)
-#define H2(sha1) (hash_val((sha1) + sizeof(unsigned int)) % obj_hash_size)
+#define H(hv,ix) ((hv[ix]) & (obj_hash_size-1))
 
 struct object *lookup_object(const unsigned char *sha1)
 {
 	struct object *obj;
+	unsigned int hashval[5];
 
 	if (!obj_hash)
 		return NULL;
 
-	if ((obj = obj_hash[H1(sha1)]) && !hashcmp(sha1, obj->sha1))
+	memcpy(hashval, sha1, 20);
+	if ((obj = obj_hash[H(hashval, 0)]) && !hashcmp(sha1, obj->sha1))
+		return obj;
+	if ((obj = obj_hash[H(hashval, 1)]) && !hashcmp(sha1, obj->sha1))
+		return obj;
+	if ((obj = obj_hash[H(hashval, 2)]) && !hashcmp(sha1, obj->sha1))
 		return obj;
-	if ((obj = obj_hash[H2(sha1)]) && !hashcmp(sha1, obj->sha1))
+	if ((obj = obj_hash[H(hashval, 3)]) && !hashcmp(sha1, obj->sha1))
+		return obj;
+	if ((obj = obj_hash[H(hashval, 4)]) && !hashcmp(sha1, obj->sha1))
 		return obj;
 	return NULL;
 }
@@ -84,13 +84,30 @@ static struct object *insert_obj_hash(struct object *obj)
 	for (loop = obj_hash_size / 2; 0 <= loop; loop--) {
 		struct object *tmp_obj;
 		unsigned int ix;
+		unsigned int hashval[5];
 
-		ix = H1(obj->sha1);
+		memcpy(hashval, obj->sha1, 20);
+		ix = H(hashval, 0);
+		if (!obj_hash[ix]) {
+			obj_hash[ix] = obj;
+			return NULL;
+		}
+		ix = H(hashval, 1);
+		if (!obj_hash[ix]) {
+			obj_hash[ix] = obj;
+			return NULL;
+		}
+		ix = H(hashval, 2);
+		if (!obj_hash[ix]) {
+			obj_hash[ix] = obj;
+			return NULL;
+		}
+		ix = H(hashval, 3);
 		if (!obj_hash[ix]) {
 			obj_hash[ix] = obj;
 			return NULL;
 		}
-		ix = H2(obj->sha1);
+		ix = H(hashval, 4);
 		tmp_obj = obj_hash[ix];
 		obj_hash[ix] = obj;
 		if (!tmp_obj)
-- 
1.7.6.433.g1421f

[PATCH 09/11] object: try 4-way cuckoo

[Junio C Hamano]

The more we probe alternative slots, the more expensive average
look-up gets, while it helps reduce the load factor of the hash
table.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
../+v/6bb99816f5676ed5ddb6922363b7470a7e8c61f7/git-pack-objects
Counting objects: 2139209, done.
31.09user 2.05system 0:33.25elapsed 99%CPU (0avgtext+0avgdata 3135840maxresident)k
0inputs+0outputs (0major+290849minor)pagefaults 0swaps
Counting objects: 2139209, done.
31.12user 2.14system 0:33.37elapsed 99%CPU (0avgtext+0avgdata 3136128maxresident)k
0inputs+0outputs (0major+290866minor)pagefaults 0swaps
Counting objects: 2139209, done.
31.17user 2.01system 0:33.29elapsed 99%CPU (0avgtext+0avgdata 3136512maxresident)k
0inputs+0outputs (0major+290890minor)pagefaults 0swaps
---
 object.c |   15 ++++-----------
 1 files changed, 4 insertions(+), 11 deletions(-)

diff --git a/object.c b/object.c
index c777520..caced56 100644
--- a/object.c
+++ b/object.c
@@ -49,12 +49,12 @@ struct object *get_indexed_object(unsigned int idx)
 struct object *lookup_object(const unsigned char *sha1)
 {
 	struct object *obj;
-	unsigned int hashval[5];
+	unsigned int hashval[4];
 
 	if (!obj_hash)
 		return NULL;
 
-	memcpy(hashval, sha1, 20);
+	memcpy(hashval, sha1, 16);
 	if ((obj = obj_hash[H(hashval, 0)]) && !hashcmp(sha1, obj->sha1))
 		return obj;
 	if ((obj = obj_hash[H(hashval, 1)]) && !hashcmp(sha1, obj->sha1))
@@ -63,8 +63,6 @@ struct object *lookup_object(const unsigned char *sha1)
 		return obj;
 	if ((obj = obj_hash[H(hashval, 3)]) && !hashcmp(sha1, obj->sha1))
 		return obj;
-	if ((obj = obj_hash[H(hashval, 4)]) && !hashcmp(sha1, obj->sha1))
-		return obj;
 	return NULL;
 }
 
@@ -84,9 +82,9 @@ static struct object *insert_obj_hash(struct object *obj)
 	for (loop = obj_hash_size / 2; 0 <= loop; loop--) {
 		struct object *tmp_obj;
 		unsigned int ix;
-		unsigned int hashval[5];
+		unsigned int hashval[4];
 
-		memcpy(hashval, obj->sha1, 20);
+		memcpy(hashval, obj->sha1, 16);
 		ix = H(hashval, 0);
 		if (!obj_hash[ix]) {
 			obj_hash[ix] = obj;
@@ -103,11 +101,6 @@ static struct object *insert_obj_hash(struct object *obj)
 			return NULL;
 		}
 		ix = H(hashval, 3);
-		if (!obj_hash[ix]) {
-			obj_hash[ix] = obj;
-			return NULL;
-		}
-		ix = H(hashval, 4);
 		tmp_obj = obj_hash[ix];
 		obj_hash[ix] = obj;
 		if (!tmp_obj)
-- 
1.7.6.433.g1421f

[PATCH 10/11] object: try 3-way cuckoo

[Junio C Hamano]

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
../+v/48b49262cd2d0d64696b489fe5bdfa8efb9180f5/git-pack-objects
Counting objects: 2139209, done.
30.68user 2.26system 0:33.05elapsed 99%CPU (0avgtext+0avgdata 3660832maxresident)k
0inputs+0outputs (0major+421963minor)pagefaults 0swaps
Counting objects: 2139209, done.
30.76user 2.26system 0:33.12elapsed 99%CPU (0avgtext+0avgdata 3660480maxresident)k
0inputs+0outputs (0major+421941minor)pagefaults 0swaps
Counting objects: 2139209, done.
30.74user 2.33system 0:33.18elapsed 99%CPU (0avgtext+0avgdata 3661696maxresident)k
0inputs+0outputs (0major+422017minor)pagefaults 0swaps
---
 object.c |   15 ++++-----------
 1 files changed, 4 insertions(+), 11 deletions(-)

diff --git a/object.c b/object.c
index caced56..18e6bcf 100644
--- a/object.c
+++ b/object.c
@@ -49,20 +49,18 @@ struct object *get_indexed_object(unsigned int idx)
 struct object *lookup_object(const unsigned char *sha1)
 {
 	struct object *obj;
-	unsigned int hashval[4];
+	unsigned int hashval[3];
 
 	if (!obj_hash)
 		return NULL;
 
-	memcpy(hashval, sha1, 16);
+	memcpy(hashval, sha1, 12);
 	if ((obj = obj_hash[H(hashval, 0)]) && !hashcmp(sha1, obj->sha1))
 		return obj;
 	if ((obj = obj_hash[H(hashval, 1)]) && !hashcmp(sha1, obj->sha1))
 		return obj;
 	if ((obj = obj_hash[H(hashval, 2)]) && !hashcmp(sha1, obj->sha1))
 		return obj;
-	if ((obj = obj_hash[H(hashval, 3)]) && !hashcmp(sha1, obj->sha1))
-		return obj;
 	return NULL;
 }
 
@@ -82,9 +80,9 @@ static struct object *insert_obj_hash(struct object *obj)
 	for (loop = obj_hash_size / 2; 0 <= loop; loop--) {
 		struct object *tmp_obj;
 		unsigned int ix;
-		unsigned int hashval[4];
+		unsigned int hashval[3];
 
-		memcpy(hashval, obj->sha1, 16);
+		memcpy(hashval, obj->sha1, 12);
 		ix = H(hashval, 0);
 		if (!obj_hash[ix]) {
 			obj_hash[ix] = obj;
@@ -96,11 +94,6 @@ static struct object *insert_obj_hash(struct object *obj)
 			return NULL;
 		}
 		ix = H(hashval, 2);
-		if (!obj_hash[ix]) {
-			obj_hash[ix] = obj;
-			return NULL;
-		}
-		ix = H(hashval, 3);
 		tmp_obj = obj_hash[ix];
 		obj_hash[ix] = obj;
 		if (!tmp_obj)
-- 
1.7.6.433.g1421f

[PATCH 11/11] object: try 2-way cuckoo again

[Junio C Hamano]

This should match the first "naive" cuckoo hashing implementation.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
../+v/ddb2c7c09c7af16bf00aa5aef6cdf54ae4611aec/git-pack-objects
Counting objects: 2139209, done.
31.28user 3.15system 0:34.53elapsed 99%CPU (0avgtext+0avgdata 8177056maxresident)k
0inputs+0outputs (0major+1206514minor)pagefaults 0swaps
Counting objects: 2139209, done.
31.06user 3.26system 0:34.43elapsed 99%CPU (0avgtext+0avgdata 8177056maxresident)k
0inputs+0outputs (0major+1206514minor)pagefaults 0swaps
Counting objects: 2139209, done.
31.06user 3.22system 0:34.39elapsed 99%CPU (0avgtext+0avgdata 8176512maxresident)k
0inputs+0outputs (0major+1206542minor)pagefaults 0swaps
---
 object.c |   15 ++++-----------
 1 files changed, 4 insertions(+), 11 deletions(-)

diff --git a/object.c b/object.c
index 18e6bcf..fc08e5b 100644
--- a/object.c
+++ b/object.c
@@ -49,18 +49,16 @@ struct object *get_indexed_object(unsigned int idx)
 struct object *lookup_object(const unsigned char *sha1)
 {
 	struct object *obj;
-	unsigned int hashval[3];
+	unsigned int hashval[2];
 
 	if (!obj_hash)
 		return NULL;
 
-	memcpy(hashval, sha1, 12);
+	memcpy(hashval, sha1, 8);
 	if ((obj = obj_hash[H(hashval, 0)]) && !hashcmp(sha1, obj->sha1))
 		return obj;
 	if ((obj = obj_hash[H(hashval, 1)]) && !hashcmp(sha1, obj->sha1))
 		return obj;
-	if ((obj = obj_hash[H(hashval, 2)]) && !hashcmp(sha1, obj->sha1))
-		return obj;
 	return NULL;
 }
 
@@ -80,20 +78,15 @@ static struct object *insert_obj_hash(struct object *obj)
 	for (loop = obj_hash_size / 2; 0 <= loop; loop--) {
 		struct object *tmp_obj;
 		unsigned int ix;
-		unsigned int hashval[3];
+		unsigned int hashval[2];
 
-		memcpy(hashval, obj->sha1, 12);
+		memcpy(hashval, obj->sha1, 8);
 		ix = H(hashval, 0);
 		if (!obj_hash[ix]) {
 			obj_hash[ix] = obj;
 			return NULL;
 		}
 		ix = H(hashval, 1);
-		if (!obj_hash[ix]) {
-			obj_hash[ix] = obj;
-			return NULL;
-		}
-		ix = H(hashval, 2);
 		tmp_obj = obj_hash[ix];
 		obj_hash[ix] = obj;
 		if (!tmp_obj)
-- 
1.7.6.433.g1421f

[FFT/PATCH 12/11] object.c: make object hash implementation more opaque

[Junio C Hamano]

There are only a handful of callers that want to enumerate all the objects
known to the process. Unfortunately they at least know that the object
hash can be iterated over with an integer index.

Introduce an opaque "struct object_cursor" type to hide the implementation
detail, so that later we may be able to switch to an implementation that
is not a based on a flat and sparse array that is used as a hash table.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---

 * This is not necessary for the purpose of the earlier "cuckoo" update,
   as that still is an implementation based on a single flat sparse array,
   but I am throwing it out as a food-for-thought.

   - The function "object_cursor_max()" returns obj_hash_size, but it only
     is used by fsck to give an overestimate of the number of objects to
     check. We could change it to return nr_obj to give a more precise
     number, but I kept the behaviour bug-for-bug compatible for now.

   - Later if we need to libify the in-core object store, we would wrap
     obj_hash, nr_obj and obj_hash_size into a single "struct obj_ctx"
     (the context of a series of git operations that access the object
     store), and have a pointer to it in the "struct object_cursor".
     get_object_cursor() API function may get a new variant that takes a
     pointer to "struct obj_ctx" to switch between contexts, etc.

   This patch is designed to apply before all the others, outside the main
   series. If this "more opaque" approach is going in a desirable
   direction, the "cuckoo" series should be rebased on top of this.

 builtin/fsck.c       |   17 ++++++++---------
 builtin/index-pack.c |   10 ++++++----
 builtin/name-rev.c   |   12 +++++-------
 object.c             |   34 ++++++++++++++++++++++++++++++----
 object.h             |    7 +++++--
 5 files changed, 54 insertions(+), 26 deletions(-)

diff --git a/builtin/fsck.c b/builtin/fsck.c
index 5ae0366..a71b36d 100644
--- a/builtin/fsck.c
+++ b/builtin/fsck.c
@@ -266,22 +266,21 @@ static void check_object(struct object *obj)
 
 static void check_connectivity(void)
 {
-	int i, max;
+	struct object_cursor *objects;
+	struct object *obj;
 
 	/* Traverse the pending reachable objects */
 	traverse_reachable();
 
 	/* Look up all the requirements, warn about missing objects.. */
-	max = get_max_object_index();
+	objects = get_object_cursor();
 	if (verbose)
-		fprintf(stderr, "Checking connectivity (%d objects)\n", max);
-
-	for (i = 0; i < max; i++) {
-		struct object *obj = get_indexed_object(i);
+		fprintf(stderr, "Checking connectivity (%d objects)\n",
+			object_cursor_max(objects));
 
-		if (obj)
-			check_object(obj);
-	}
+	while ((obj = get_next_object(objects)) != NULL)
+		check_object(obj);
+	free_object_cursor(objects);
 }
 
 static int fsck_sha1(const unsigned char *sha1)
diff --git a/builtin/index-pack.c b/builtin/index-pack.c
index e40451f..ca172d5 100644
--- a/builtin/index-pack.c
+++ b/builtin/index-pack.c
@@ -104,11 +104,13 @@ static void check_object(struct object *obj)
 
 static void check_objects(void)
 {
-	unsigned i, max;
+	struct object_cursor *objects;
+	struct object *obj;
 
-	max = get_max_object_index();
-	for (i = 0; i < max; i++)
-		check_object(get_indexed_object(i));
+	objects = get_object_cursor();
+	while ((obj = get_next_object(objects)) != NULL)
+		check_object(obj);
+	free_object_cursor(objects);
 }
 
 
diff --git a/builtin/name-rev.c b/builtin/name-rev.c
index 31f5c1c..ec6b952 100644
--- a/builtin/name-rev.c
+++ b/builtin/name-rev.c
@@ -284,16 +284,14 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)
 			name_rev_line(p, &data);
 		}
 	} else if (all) {
-		int i, max;
+		struct object_cursor *objects;
+		struct object *obj;
 
-		max = get_max_object_index();
-		for (i = 0; i < max; i++) {
-			struct object *obj = get_indexed_object(i);
-			if (!obj)
-				continue;
+		objects = get_object_cursor();
+		while ((obj = get_next_object(objects)) != NULL)
 			show_name(obj, NULL,
 				  always, allow_undefined, data.name_only);
-		}
+		free_object_cursor(objects);
 	} else {
 		int i;
 		for (i = 0; i < revs.nr; i++)
diff --git a/object.c b/object.c
index 31976b5..986d243 100644
--- a/object.c
+++ b/object.c
@@ -8,14 +8,40 @@
 static struct object **obj_hash;
 static int nr_objs, obj_hash_size;
 
-unsigned int get_max_object_index(void)
+struct object_cursor {
+	int cursor_at;
+};
+
+struct object_cursor *get_object_cursor(void)
 {
-	return obj_hash_size;
+	struct object_cursor *objects;
+	objects = xmalloc(sizeof(*objects));
+	objects->cursor_at = 0;
+	return objects;
+}
+
+int object_cursor_max(struct object_cursor *objects)
+{
+	return obj_hash_size; /* nr_objs is more precise, though */
+}
+
+struct object *get_next_object(struct object_cursor *objects)
+{
+	int i = objects->cursor_at;
+	while (i < obj_hash_size) {
+		struct object *obj = obj_hash[i++];
+		if (!obj)
+			continue;
+		objects->cursor_at = i;
+		return obj;
+	}
+	objects->cursor_at = i;
+	return NULL;
 }
 
-struct object *get_indexed_object(unsigned int idx)
+void free_object_cursor(struct object_cursor *objects)
 {
-	return obj_hash[idx];
+	free(objects);
 }
 
 static const char *object_type_strings[] = {
diff --git a/object.h b/object.h
index b6618d9..fdd14a1 100644
--- a/object.h
+++ b/object.h
@@ -35,8 +35,11 @@ struct object {
 extern const char *typename(unsigned int type);
 extern int type_from_string(const char *str);
 
-extern unsigned int get_max_object_index(void);
-extern struct object *get_indexed_object(unsigned int);
+struct object_cursor; /* opaque */
+extern struct object_cursor *get_object_cursor(void);
+extern int object_cursor_max(struct object_cursor *);
+extern struct object *get_next_object(struct object_cursor *);
+extern void free_object_cursor(struct object_cursor *);
 
 /*
  * This can be used to see if we have heard of the object before, but

git_checkattr() is inefficient when repeated [Re: [PATCH 00/11] Micro-optimizing lookup_object()]

[Thomas Rast]

Junio C Hamano wrote:
> 4-way cuckoo

Cool stuff!

While looking at the performance of it, I noticed something odd about
packing: stracing the command you gave for your timings

  strace -o pack.trace \
    ./git-pack-objects --count-only --keep-true-parents --honor-pack-keep \
    --non-empty --all --reflog --no-reuse-delta --delta-base-offset \
    --stdout  </dev/null >/dev/null

yields the fairly crazy

  $ grep -c 'open.*attrib' pack.trace 
  4398

including runs such as (with a line of context for clarity)

  munmap(0x7f9cd39f7000, 4096)            = 0
  open("compat/.gitattributes", O_RDONLY) = -1 ENOENT (No such file or directory)
  open("compat/.gitattributes", O_RDONLY) = -1 ENOENT (No such file or directory)
  open("compat/.gitattributes", O_RDONLY) = -1 ENOENT (No such file or directory)
  open("compat/.gitattributes", O_RDONLY) = -1 ENOENT (No such file or directory)
  open("compat/.gitattributes", O_RDONLY) = -1 ENOENT (No such file or directory)
  open("compat/.gitattributes", O_RDONLY) = -1 ENOENT (No such file or directory)
  open("compat/.gitattributes", O_RDONLY) = -1 ENOENT (No such file or directory)
  open("compat/.gitattributes", O_RDONLY) = -1 ENOENT (No such file or directory)
  open("t/.gitattributes", O_RDONLY)      = 3
  fstat(3, {st_mode=S_IFREG|0644, st_size=36, ...}) = 0

So calling git_checkattr in a loop is quite inefficient.  Indeed
there's a good optimization opportunity: compiled for 4-way hashing I
have (best of 3)

  6.76user 0.23system 0:07.02elapsed 99%CPU (0avgtext+0avgdata 479792maxresident)

but making no_try_delta() in pack-objects.c a dummy 'return 0' gives

  6.45user 0.13system 0:06.61elapsed 99%CPU (0avgtext+0avgdata 478256maxresident)

Which would be a 4.5% speedup.  Obviously that won't quite be
attainable since we want the attributes mechanism to work, but we
still shouldn't have to open 4398 .gitattributes files when there are
only 8 .gitattributes plus one .git/info/attributes.

-- 
Thomas Rast
trast@{inf,student}.ethz.ch

Re: git_checkattr() is inefficient when repeated [Re: [PATCH 00/11] Micro-optimizing lookup_object()]

[Junio C Hamano]

Thomas Rast <trast@student.ethz.ch> writes:

> Which would be a 4.5% speedup.  Obviously that won't quite be
> attainable since we want the attributes mechanism to work, but we
> still shouldn't have to open 4398 .gitattributes files when there are
> only 8 .gitattributes plus one .git/info/attributes.

True. At runtime, the attribute mechanism wants a stack of per-directory
attributes it can walk up to find the applicable ones maintained for the
directory it currently is looking at, and the elements near the leaf are
popped from the stack to be discarded when the caller goes on to inspect
paths in a different directory (IOW the machinery is optimized for callers
that walk the paths in order, without randomly jumping around).

But at least within a process like pack-objects that are known to be long
lived, we should be able to instead _keep_ the elements that are popped
when we leave directories at deeper levels, and bring them back to the
stack when the caller asks for a path in that directory later, without
going back to the filesystem.