Re: Random thoughts about LRU Cache

[Selcuk AYA <ay...@gmail.com>]

On Sat, Apr 28, 2012 at 4:58 AM, Emmanuel Lécharny <el...@gmail.com> 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.

Agreed. CPU cost is probably coming from the touch and the list
operations done under the lru mutex. I am aware of algorithms similar
to what you and Howard suggested and I think implementing them would
reduce the CPU cost significantly.
>
> 2) Do we need to keep all the versions ?
> When we fetch an element from the cache, in a LDAP context, we won't fetch
> it a second time. Never. That means we will use a different version than the
> previous one. So the question to keep versions in the cache is raised : what
> if we simply replace the element when some modification occurs ?
>
> (just in case these versionned elements are needed in the context of an
> optimistic locking system, I wonder if those versionned cache are critical
> too, as the number of changes will in any case limited to a very few numbers
> of elements. But I may be wrong here...)

We need to keep all the versions as long as reader might need them(and
there might be multiple readers using the same version of data).
>
> I any case, I do think that we should keep the current LRUCache as is and
> start thinkig about a better version - if any -for after 2.0. This is
> typically something a student might want to play with...
>
> Thoughts ?
>
> --
> Regards,
> Cordialement,
> Emmanuel Lécharny
> www.iktek.com
>

thanks
Selcuk