directory-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Howard Chu <>
Subject Re: Random thoughts about LRU Cache
Date Sat, 28 Apr 2012 13:36:23 GMT
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. 
   Director, Highland Sun
   Chief Architect, OpenLDAP

View raw message