directory-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Howard Chu <...@symas.com>
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.           http://www.symas.com
   Director, Highland Sun     http://highlandsun.com/hyc/
   Chief Architect, OpenLDAP  http://www.openldap.org/project/



Mime
View raw message