lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Erick Erickson (Commented) (JIRA)" <>
Subject [jira] [Commented] (SOLR-2906) Implement LFU Cache
Date Mon, 19 Dec 2011 20:07:31 GMT


Erick Erickson commented on SOLR-2906:

We need to keep lastAccessed, removing it introduces a bug. The CacheEntry.compareTo method
looks like this:

    public int compareTo(CacheEntry<K, V> that) {
      if (this.hitsCopy == that.hitsCopy) {
        if (this.lastAccessedCopy == that.lastAccessedCopy) {
          return 0;
        return this.lastAccessedCopy < that.lastAccessedCopy ? 1 : -1;
      return this.hitsCopy < that.hitsCopy ? 1 : -1;

which is guaranteed to return non-zero unless the the exact same object is being compared
since lastAccessed(Copy) is monotonically increasing.

If we remove the lastAccessed, then any two elements having the same number of hits compare
as equal. Which also means that tree insertions overwrite each other in methods like getMost/LeastUsedItems.
I don't know of any cheaper amounts of overhead to carry along to prevent this.

I've made a few, mostly cosmetic changes while trying to understand the code, I'll check it
in shortly.
> Implement LFU Cache
> -------------------
>                 Key: SOLR-2906
>                 URL:
>             Project: Solr
>          Issue Type: Sub-task
>          Components: search
>    Affects Versions: 3.4
>            Reporter: Shawn Heisey
>            Assignee: Erick Erickson
>            Priority: Minor
>         Attachments:,, SOLR-2906.patch, SOLR-2906.patch,
> 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:!default.jspa
For more information on JIRA, see:


To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message