From: Jeff King <peff@peff.net>
Date: Thu, 02 May 2013 15:50:37 GMT
Subject: Re: [PATCH] lookup_object: prioritize recently found objects
Message-ID: <20130502155037.GB18462@sigill.intra.peff.net>
In-Reply-To: <7vzjwd1j27.fsf@alter.siamese.dyndns.org>

On Thu, May 02, 2013 at 08:46:08AM -0700, Junio C Hamano wrote:

> Johannes Sixt <j.sixt@viscovery.net> writes:
> 
> > BTW, do you notice that the function is now modifying an object (the hash
> > table) even though this is rather unexpected from a "lookup" function?
> 
> At the philosophical level, "lookup" ought to be operating on a
> "const" table.  But at the implementation level, the table does not
> have to be "const" in the sense the implemenation language and data
> structure defines.
> 
> I think this patch is a good example of that.

Very much agreed.

> I am kind of surprised that Jeff's attempt to do a full LRU made
> things worse, though.  The only additional code compared to swap is
> a single memmove(): are we colliding too often (having to move a
> lot)?

I actually didn't use memmove, but a hand-rolled loop. I wonder if that
would have made the difference. It's a little tricky because you may
have to cross the mod(obj_hash_size) wrap-around. The patch I tested
was:

diff --git a/object.c b/object.c
index 1ba2083..8b2412c 100644
--- a/object.c
+++ b/object.c
@@ -85,10 +85,13 @@ struct object *lookup_object(const unsigned char *sha1)
 		if (i == obj_hash_size)
 			i = 0;
 	}
-	if (obj && i != first) {
-		struct object *tmp = obj_hash[i];
-		obj_hash[i] = obj_hash[first];
-		obj_hash[first] = tmp;
+	if (obj) {
+		while (i != first) {
+			int prev = i ? i - 1 : obj_hash_size - 1;
+			obj_hash[i] = obj_hash[prev];
+			i = prev;
+		}
+		obj_hash[i] = obj;
 	}
 	return obj;
 }

-Peff