Emmanuel Lécharny wrote:
Hi guys,
as I was conducting some perf tests yesterday and this morning, I found
that the LRUCache.get(...) took around 14% of all the CPU, which is
quite big.
There is nothing wrong with the current implementation though. It's
pretty normal that when the data are cached, that at some point, it
becomes ne of the major bottleneck. The alternative would be to fetch
the serialized value from disk, and that would cost way more time.
I also digged the code to see where we can improve it, but it's pretty
optimal.
Basically (correct me if I'm wrong), we are looking for an element in a
hash table, then we try to find the correct version, as the cache stores
versionned elements, and then we 'touch' the element so that it won't be
evicted fast.
Here are a few ideas I have had, some food for thoughts.
1) Do we need to touch the elements ?
the touch() method move the element from the middle of a circular linked
list to the beginning of the list. This is not exactly a free operation.
What if we simply update a flag with the latest version in this elemnt ?
The eviction strategy would then be to select the elements that have the
lower counter. Of course, that would imply we have to go through all the
elemnts from time to time, and remove a set of them when kicking the
eviction (This would be very similar to a garbage collection).
It's likely to be more efficient than a touch() done for every access.
You've just described the CLOCK cache replacement method. We switched to it
from LRU in OpenLDAP quite a long time ago.
--
-- Howard Chu
CTO, Symas Corp. http://www.symas.com
Director, Highland Sun http://highlandsun.com/hyc/
Chief Architect, OpenLDAP http://www.openldap.org/project/
