lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Yonik Seeley (Commented) (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (SOLR-2906) Implement LFU Cache
Date Sat, 19 Nov 2011 00:18:52 GMT

    [ 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-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org


Mime
View raw message