On Thu, May 02, 2013 at 08:46:08AM -0700, Junio C Hamano wrote:
> Johannes Sixt <j.sixt@xxxxxxxxxxxxx> 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
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html