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,
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
--
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
