[
https://issues.apache.org/jira/browse/SOLR-3393?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Adrien Grand updated SOLR-3393:
-------------------------------
Attachment: SOLR-3393.patch
bq. I can't see anything in there that maintains the frequency values from the
old cache to the new cache.
You're right, I forgot to add a nocommit about it! This should be fixed with
this new patch.
bq. With maxFreq of 10 and a cache size much larger (200, 1000, etc), there's
no difference from the cache's perspective between something that has been
requested 50 times versus something that has been requested 100 times.
Their frequency is considered equal but they are sorted according to their
access order, so only the least recently used has a chance to be evicted.
bq. How did the maxFreq being related to the cache size make it slower?
This was because of the call to findLowestFrequency in doEviction. If one
element has frequency=0 and all other ones have frequency=maxFreq,
findLowestFrequency must inspect every slot. But this should be avoidable:
since doEviction is only called inside put, there is no need to compute
lowestFreq inside doEviction, put will always set lowestFreq=0 in the end.
I also modified the patch to rename the previous LFUCache impl to
ConcurrentLFUCache (similarly to FastLRUCache, I just didn't want to prefix
with "Fast" since I think this is a bit misleading).
> 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-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: [email protected]
For additional commands, e-mail: [email protected]
