Stefan BellerA little background on hash tables first: Consider you want to have the object X, which you'd expect at position i, but because that place was already taken by B, it is not found at position i, you start looking right of position i to find X until you find it.
index | i-1 | i | i+1 | i+2 | i+3 | i+4 |
--------------------------------------------
entry ... | A | B | C | D | E | X | ...
--------------------------------------------Once you have found X at i+4, the commit 9a414486d9f0 (2013-05-01, lookup_object: prioritize recently found objects) did an optimization and swapped the object B with X, so the placement looks like
index | i-1 | i | i+1 | i+2 | i+3 | i+4 |
--------------------------------------------
entry ... | A | X | C | D | E | B | ...
--------------------------------------------This would improve the lookup times, because you'd likely be looking up X again soon. However we are putting a heavy penalty on B for the collision. Also suppose we'd look up B now, which is expected to be at i or even left from there (i-n). So it is a long way to go until B is found. So if B were expected at the same place as X, we'd end up as before the swap, now penalizing the lookup of X again.
Jeff stated in the referenced commit, that another solution, an LRU scheduling would be to shift all of the objects. So when looking for X in the first diagram, once we found X, we'd shift all the objects and put X to position i:
index | i-1 | i | i+1 | i+2 | i+3 | i+4 |
--------------------------------------------
entry ... | A | X | B | C | D | E | ...
--------------------------------------------But that strategy would need to go through all the positions, hence taking even longer.
This patch proposes another strategy: We split the penalty into parts and add the penalty to different objects. To keep the overhead small, we're splitting up the penalty to only 2 portions and assign it to the object B and an arbitrary object in the range between B and X.
The reason why moving that arbitrary object in between is analogous to the explanation of moving the first object. See 9a414486d9f0 (2013-05-01, lookup_object: prioritize recently found objects) for a detailed explanation.
But which of the objects to choose from in between? At first I naively choose the exact mid between those 2 objects, so here is the diagram from the beginning again:
index | i-1 | i | i+1 | i+2 | i+3 | i+4 |
--------------------------------------------
entry ... | A | B | C | D | E | X | ...
--------------------------------------------If we now want to find X and X is expected at i, we put X to the position i and B to the middle position between B and X at D and D will go to the old position of X:
index | i-1 | i | i+1 | i+2 | i+3 | i+4 |
--------------------------------------------
entry ... | A | X | C | B | E | D | ...
--------------------------------------------So let's test how it works out: # running the current git.git master (c1ebd90c832e), repeat 25 times: perf stat -r 25 -- ./git-rev-list --all --objects >/dev/null ... 5.294512141 seconds time elapsed ( +- 7.88% ) # Now running with this patch applied: 5.111576725 seconds time elapsed ( +- 8.17% )
This is an average 5 percent performance gain, though the measure times are varying itself by that amount (7.88 and 8.17 percent)
This approach is faster than before, because it still doesn't touch too many object for resorting, but also doesn't put the penalty to one outlier. The lookup penalty is split up between two objects, which probably have nothing to do with each other.
But is the mid object really the right thing to do? We could split the lookup penalty not into 2 halfs, but in a huge and a small amount. So instead of the mid object, we are free to choose any other arbitrary object in between B and X. Let's try to use the nearest object (C) and farest object(E), because there we may have better cache effects (near the objects we're accessing anyway) and the calculation is easier:
If using C as the mid object, we'd end up with
index | i-1 | i | i+1 | i+2 | i+3 | i+4 |
--------------------------------------------
entry ... | A | X | B | D | E | C | ...
--------------------------------------------or if taking the E object we'd end up with
index | i-1 | i | i+1 | i+2 | i+3 | i+4 |
--------------------------------------------
entry ... | A | X | C | D | B | E | ...
--------------------------------------------# Test with C as mid object (25 repetitions as well): # 5.35 seconds time elapsed ( +- 7.09% ) # Test with E as mid object (25 repetitions as well): # 5.42 seconds time elapsed ( +- 6.50% )
So that was not successful, hence the initial idea to take the mid object is in this patch. A second run of the original state and this patch yieled a 5 percent performance gain again, so I am quite confident now this patch is good.
However please do check if this patch brings the promised performance on your own, as you're likely using different hardware and another software setup. Feel free to share your performance differences.
Signed-off-by: Stefan Beller <stefanbeller@googlemail.com> --- object.c | 22 ++++++++++++++++++++-- 1 file changed, 20 insertions(+), 2 deletions(-)
Show changes to object.c +20 −2
diff --git a/object.c b/object.c index d8a4b1f..014290d 100644 --- a/object.c +++ b/object.c @@ -71,7 +71,7 @@ static unsigned int hashtable_index(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,27 @@ 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 the object being + * moved from the first position, so divide the penalty to + * two different objects. */ + + /* + * First make sure i > first, so the middle is really + * in between the i and first object + */ + if (i < first) + i += obj_hash_size; + + middle = (i + first) / 2; + if (i >= obj_hash_size) + i -= obj_hash_size; + if (middle >= obj_hash_size) + middle -= obj_hash_size; + struct object *tmp = obj_hash[i]; - obj_hash[i] = obj_hash[first]; + obj_hash[i] = obj_hash[middle]; + obj_hash[middle] = obj_hash[first]; obj_hash[first] = tmp; } return obj;
-- 1.8.4.rc3.498.g5af1768
