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

From

Junio C Hamano <gitster@pobox.com>

Date

Aug 11, 2011, 17:53 UTC

Message-ID

<1313085196-13249-9-git-send-email-gitster@pobox.com>

In-Reply-To

<1313085196-13249-1-git-send-email-gitster@pobox.com>

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