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

[Junio C Hamano <gitster@pobox.com>]

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