Re: [PATCH] lookup_object: split up displacement penalty for hash collisions
- From
Jeff King <peff@peff.net>
- Date
- Aug 16, 2013, 13:49 UTC
- Message-ID
- <20130816134952.GG20138@sigill.intra.peff.net>
- In-Reply-To
- <20130816095722.GA11201@sigill.intra.peff.net>
On Fri, Aug 16, 2013 at 05:57:22AM -0400, Jeff King wrote:
Show 5 quoted lines
> 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, etc).
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;
-- 1.8.4.rc2.28.g6bb5f3f