LFU: Optimize frequency list

[erwanor]

Consider an LFU cache with capacity=10 i.e

gc, err := gcache.New(10).LFU().Build()

The internal cache.freqList is a linked list. Each of its entries represent a given frequency along with a map (bucket) with all the items with such frequency.

The issue is that we never clean-up empty entries, over time the list grows larger and larger. It's not great.

Example:

We fill-up our cache:

for key := 0; key < 10; key++ {
    value := fmt.Sprintf("val%d", key)
    gc.Set(key, value)
}

Folllowing this, our cache.freqList has one entry (freq=0) containing all the items with such frequency. In that case that's everything.

Let's simulate some read workload:

numReads := 1000
for read := 0; read < numReads; read++ {
     gc.Get(5)
}

Our cache.freqList should only have two entries because there are only two frequencies i.e freq=0 and freq=1000. The current behavior makes it keep tracks of all the frequency historically used. In other words, the cache.freqList will have 1001 entries, even though only two are needed to represent the whole state!