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

From

Junio C Hamano <gitster@pobox.com>

Date

Aug 11, 2011, 17:53 UTC

Message-ID

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

In-Reply-To

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

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