Mailing-List: contact dev-help@lucene.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@lucene.apache.org
Date: Sat, 19 Nov 2011 00:18:52 +0000 (UTC)
From: "Yonik Seeley (Commented) (JIRA)" <jira@apache.org>
To: dev@lucene.apache.org
Message-ID: 
 <1304608390.45675.1321661932740.JavaMail.tomcat@hel.zones.apache.org>
In-Reply-To: 
 <1151033237.43801.1321629773447.JavaMail.tomcat@hel.zones.apache.org>
Subject: [jira] [Commented] (SOLR-2906) Implement LFU Cache
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit


    [ 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