[
https://issues.apache.org/jira/browse/SOLR-2906?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13153258#comment-13153258
]
Yonik Seeley commented on SOLR-2906:
------------------------------------
bq. I've been trying to find my bug. Looking back at the original LRU
implementation, I have no idea how it's working.
Heh... it is pretty complex, and I did try to add a ton of comments because of
that.
The basic idea is that I wanted to avoid an O(n*log( n )) solution of sorting
everything and then discarding the lowest.
In my testing, it seems to work, and we often just need to take a singe O( n )
pass to evict all the entries we need.
The comment at the top is the most important to understanding how it works:
{code}
// if we want to keep at least 1000 entries, then timestamps of
// current through current-1000 are guaranteed not to be the oldest (but
that does
// not mean there are 1000 entries in that group... it's acutally anywhere
between
// 1 and 1000).
// Also, if we want to remove 500 entries, then
// oldestEntry through oldestEntry+500 are guaranteed to be
// removed (however many there are there).
{code}
But really, it seems like you should disregard all the algorithmic stuff in LRU
when implementing LFU.
If you think you see a bug in the existing LRU stuff, you're going to have to
spell it out for me a bit more.
> Implement LFU Cache
> -------------------
>
> Key: SOLR-2906
> URL: https://issues.apache.org/jira/browse/SOLR-2906
> Project: Solr
> Issue Type: Sub-task
> Components: search
> Affects Versions: 3.4
> Reporter: Shawn Heisey
> Priority: Minor
> Attachments: ConcurrentLFUCache.java, FastLFUCache.java
>
>
> Implement an LFU (Least Frequently Used) cache as the first step towards a
> full ARC cache
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators:
https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org
