lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Adrien Grand (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (SOLR-3393) Implement an optimized LFUCache
Date Thu, 06 Sep 2012 13:43:09 GMT

    [ https://issues.apache.org/jira/browse/SOLR-3393?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13449665#comment-13449665
] 

Adrien Grand commented on SOLR-3393:
------------------------------------

Hi hoss, thanks for bringing this up!

 - {{put}} should return the previous value instead of returning the value that has been put
into the cache.
 - I don't like the {{evictDecay}} option, I assume it is here to prevent the most frequently
used entry from being evicted in case all entries have a frequency >= maxFreq but on the
other hand it makes every put operation run in O( n ) so maybe we should just remove it and
add a message in the class javadocs to warn users that entries that have a frequency >=
maxFreq are evicted according to a LRU policy.
 - Maybe we should remove warmDecay as well, I understand it is here to try to prevent cache
pollution but it makes the cache behave differently in case there are commits: if an entry
is retrieved 5 times before a commit and 5 times after, it will be considered less frequently
used than an entry that has been retrieved 8 times after the commit, this is counterintuitive.
 - I think Entry.value and Entry.frequency don't need to be volatile?
 - maxCacheSize - 1 is probably a too high default value for maxFreq. It can make doEviction
(and consequently put) run in O( n ). Maybe we should make it configurable with something
like log( n ) or 10 as a default value? Moreover, lower values of maxFreq are less prone to
cache pollution.

Regarding your (2), I personally don't mind if it is a little slower on average. I would expect
the get method to be slower with this impl but on the other hand ConcurrentLFUCache seems
to provide no warranty that it will be able to evict entries as fast as they get inserted
into the cache  so I think this new impl is better.
                
> Implement an optimized LFUCache
> -------------------------------
>
>                 Key: SOLR-3393
>                 URL: https://issues.apache.org/jira/browse/SOLR-3393
>             Project: Solr
>          Issue Type: Improvement
>          Components: search
>    Affects Versions: 3.6, 4.0-ALPHA
>            Reporter: Shawn Heisey
>            Priority: Minor
>             Fix For: 4.0
>
>         Attachments: SOLR-3393.patch, SOLR-3393.patch, SOLR-3393.patch, SOLR-3393.patch,
SOLR-3393.patch
>
>
> SOLR-2906 gave us an inefficient LFU cache modeled on FastLRUCache/ConcurrentLRUCache.
 It could use some serious improvement.  The following project includes an Apache 2.0 licensed
O(1) implementation.  The second link is the paper (PDF warning) it was based on:
> https://github.com/chirino/hawtdb
> http://dhruvbird.com/lfu.pdf
> Using this project and paper, I will attempt to make a new O(1) cache called FastLFUCache
that is modeled on LRUCache.java.  This will (for now) leave the existing LFUCache/ConcurrentLFUCache
implementation in place.

--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
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