On Fri, Aug 16, 2013 at 05:57:22AM -0400, Jeff King wrote:

> In that case, it seems like we would want to move B to the second
> position. This lets the 2-hot case just keep swapping the hot items back
> and forth as quickly as possible. To the detriment of C, D, etc, which
> never get promoted. But the likelihood of having _3_ hot items in a
> collision chain is even less than 2.

That was one of the cases Stefan considered in the original patch, but
didn't show code. Here's my make-shift code to try it; one could also
parameterize it to shift down at most N items, and then just bump the
N+1th item to the end (so the existing behavior is N=0, my patch is N+1,

However, I measured no speedup at all. Oh well. It was worth a shot.

 object.c | 17 +++++++++++++++--
 1 file changed, 15 insertions(+), 2 deletions(-)

diff --git a/object.c b/object.c
index d8a4b1f..f7ca969 100644
--- a/object.c
+++ b/object.c
@@ -71,7 +71,7 @@ struct object *lookup_object(const unsigned char *sha1)
 struct object *lookup_object(const unsigned char *sha1)
-       unsigned int i, first;
+       unsigned int i, first, middle;
        struct object *obj;
        if (!obj_hash)
@@ -90,9 +90,22 @@ struct object *lookup_object(const unsigned char *sha1)
                 * Move object to where we started to look for it so
                 * that we do not need to walk the hash table the next
                 * time we look for it.
+                *
+                * However, we don't want to penalize the object being
+                * moved from the first position, so shift it down only one
+                * slot, and bump the next object to the end. This is faster
+                * than shifting the whole chain down, and covers the common
+                * case of a few "hot" items near the front of the chain.
+               int second = (first + 1) % obj_hash_size;
                struct object *tmp = obj_hash[i];
-               obj_hash[i] = obj_hash[first];
+               if (i != second) {
+                       obj_hash[i] = obj_hash[second];
+                       obj_hash[second] = obj_hash[first];
+               } else
+                       obj_hash[i] = obj_hash[first];
                obj_hash[first] = tmp;
        return obj;

To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Reply via email to