LRU-Caches for Go

These are simple implementations of LRU cache, suitable for practical use, but mainly created for study and comparison:

• ListCache - classic implementation based on map and double-linked list
• GensCache - simpler and more compact, based on two maps (generations)
• StampsCache - also without list, using stamps and access counter

The two latter allow to keep more records in the same amount of memory and work slightly faster.

Usage

Get the dependency, e.g.:

go get github.com/rodiongork/lrucache

Now use it in your program, like this:

package main

import "github.com/rodiongork/lrucache"

func main() {
    cache := lrucache.NewListCache[string, int](4)
    cache.Put("yksi", 1)
    cache.Put("kaksi", 2)
    cache.Put("kolme", 3)
    cache.Put("nelja", 4)
    cache.Put("viisi", 5)
    println(cache.Get("yksi"), cache.Get("viisi"))
}

(it should print 0 5 as the first element was evicted already)

Performance Study

Folder study holds small performance test which may be run with go run test.go It shows the difference between two implementations:

ListCache[50k]
    hit: 4585k, miss: 15414k, time: 4.9
GensCache[50k]
    hit: 5477k, miss: 14522k, time: 3.5
StampsCache[50k]
    hit: 4450k, miss: 15549k, time: 4.9
ListCache[100k]
    hit: 6481k, miss: 13518k, time: 5.7
GensCache[100k]
    hit: 7658k, miss: 12341k, time: 3.8
StampsCache[100k]
    hit: 6328k, miss: 13671k, time: 5.4
ListCache[250k]
    hit: 10203k, miss: 9796k, time: 7.3
GensCache[250k]
    hit: 11743k, miss: 8256k, time: 5.0
StampsCache[250k]
    hit: 9984k, miss: 10015k, time: 6.2
ListCache[500k]
    hit: 14254k, miss: 5745k, time: 8.3
GensCache[500k]
    hit: 15711k, miss: 4288k, time: 5.6
StampsCache[500k]
    hit: 13804k, miss: 6195k, time: 6.3

The data consist of strings converted from six-digit decimal numbers which are generated by randomizer (with the fixed seed) in non-uniform (rather cubic) fashion.

It should be understood that real performance difference is observed when misses lead to more slow data calculation / extraction (it doesn't happen in this test for clarity of comparison).

Also to note is that StampsCache has a tunable parameter (flush part size) which affects performance and size variation.