otter is one of the fastest implementation but memory usage is too high, possible to reduce?

[kolinfluence]

otther completes at 26ns while phuslu completes at 29ns

./cachemain otter 10000000
otter	10000000	1216 MB	1600 MB	1431 MB
./cachemain nottl 10000000
nottl	10000000	355 MB	433 MB	438 MB

// memusage.go
package main

import (
        "fmt"
        "os"
        "runtime"
        "time"
        "strconv"

        theine "github.com/Yiling-J/theine-go"
        "github.com/cespare/xxhash/v2"
        cloudflare "github.com/cloudflare/golibs/lrucache"
        ristretto "github.com/dgraph-io/ristretto"
        freelru "github.com/elastic/go-freelru"
        hashicorp "github.com/hashicorp/golang-lru/v2/expirable"
        ccache "github.com/karlseguin/ccache/v3"
        lxzan "github.com/lxzan/memorycache"
        otter "github.com/maypok86/otter"
        ecache "github.com/orca-zhang/ecache"
        phuslu "github.com/phuslu/lru"
)

const keysize = 16

var keys []string

func main() {
        name := os.Args[1]
        cachesize, _ := strconv.Atoi(os.Args[2])

        keys = make([]string, cachesize)
        for i := 0; i < cachesize; i++ {
                keys[i] = fmt.Sprintf(fmt.Sprintf("%%0%dd", keysize), i)
        }

        var o runtime.MemStats
        runtime.ReadMemStats(&o)

        map[string]func(int){
                "nottl":      SetupNottl,
                //"phuslu":     SetupPhuslu,
                "freelru":    SetupFreelru,
                "ristretto":  SetupRistretto,
                "otter":      SetupOtter,
                "lxzan":      SetupLxzan,
                "ecache":     SetupEcache,
                "cloudflare": SetupCloudflare,
                "ccache":     SetupCcache,
                "hashicorp":  SetupHashicorp,
                "theine":     SetupTheine,
        }[name](cachesize)

        var m runtime.MemStats
        runtime.ReadMemStats(&m)

        fmt.Printf("%s\t%d\t%v MB\t%v MB\t%v MB\n",
                name,
                cachesize,
                (m.Alloc-o.Alloc)/1048576,
                (m.TotalAlloc-o.TotalAlloc)/1048576,
                (m.Sys-o.Sys)/1048576,
        )
}

func SetupNottl(cachesize int) {
        cache := phuslu.New[string, int](cachesize)
        for i := 0; i < cachesize; i++ {
                cache.Set(keys[i], i)
        }
}

/*
func SetupPhuslu(cachesize int) {
        cache := phuslu.NewTTLCache[string, int](cachesize)
        for i := 0; i < cachesize; i++ {
                cache.Set(keys[i], i, time.Hour)
        }
}
*/

func SetupFreelru(cachesize int) {
        cache, _ := freelru.NewSharded[string, int](uint32(cachesize), func(s string) uint32 { return uint32(xxhash.Sum64String(s)) })
        for i := 0; i < cachesize; i++ {
                cache.AddWithLifetime(keys[i], i, time.Hour)
        }
}

func SetupOtter(cachesize int) {
        //cache, _ := otter.MustBuilder[string, int](cachesize).WithVariableTTL().Build()
        cache, _ := otter.MustBuilder[string, int](cachesize).Build()
        for i := 0; i < cachesize; i++ {
                cache.Set(keys[i], i)
        }
}

func SetupEcache(cachesize int) {
        cache := ecache.NewLRUCache(1024, uint16(cachesize/1024), time.Hour)
        for i := 0; i < cachesize; i++ {
                cache.Put(keys[i], i)
        }
}

func SetupRistretto(cachesize int) {
        cache, _ := ristretto.NewCache(&ristretto.Config{
                NumCounters: int64(10 * cachesize), // number of keys to track frequency of (10M).
                MaxCost:     int64(cachesize),      // maximum cost of cache (1M).
                BufferItems: 64,             // number of keys per Get buffer.
        })
        for i := 0; i < cachesize; i++ {
                cache.SetWithTTL(keys[i], i, 1, time.Hour)
        }
}

func SetupLxzan(cachesize int) {
        cache := lxzan.New[string, int](
                lxzan.WithBucketNum(128),
                lxzan.WithBucketSize(cachesize/128, cachesize/128),
                lxzan.WithInterval(time.Hour, time.Hour),
        )
        for i := 0; i < cachesize; i++ {
                cache.Set(keys[i], i, time.Hour)
        }
}

func SetupTheine(cachesize int) {
        cache, _ := theine.NewBuilder[string, int](int64(cachesize)).Build()
        for i := 0; i < cachesize; i++ {
                cache.SetWithTTL(keys[i], i, 1, time.Hour)
        }
}

func SetupCloudflare(cachesize int) {
        cache := cloudflare.NewMultiLRUCache(1024, uint(cachesize/1024))
        for i := 0; i < cachesize; i++ {
                cache.Set(keys[i], i, time.Now().Add(time.Hour))
        }
}

func SetupCcache(cachesize int) {
        cache := ccache.New(ccache.Configure[int]().MaxSize(int64(cachesize)).ItemsToPrune(100))
        for i := 0; i < cachesize; i++ {
                cache.Set(keys[i], i, time.Hour)
        }
}

func SetupHashicorp(cachesize int) {
        cache := hashicorp.NewLRU[string, int](cachesize, nil, time.Hour)
        for i := 0; i < cachesize; i++ {
                cache.Add(keys[i], i)
        }
}

[maypok86]

Oh, it's not very clear why compare the memory consumption of the onheap cache with implementations that are struggling to avoid more memory consumption, sacrificing a lot for this.

1. LRU, in principle, has a slightly smaller overhead for each entry, but has a much lower hit ratio.
2. In fact, phuslu/lru does not have any expiration policy, since it deletes expired entries only when they are accessed. This saves him most of the costs for each node, but in reality it will lead to greater memory consumption and lower hit ratio.
3. Since otter has such a feature as cost-based eviction, it cannot initially predict the size of its internal data structures. This is strongly reflected on such benchmarks, but in reality you will not notice it. In this case, running GC should free about 300 MB.
4. Such sizes are quite rare for onheap caches. On them, in fact, you are more likely to encounter increased pressure on the GC than memory consumption. Usually, the size of onheap caches does not exceed 1000000-5000000. If you really need to store a lot more, then it's better to use offheap caches (implementations such as phuslu/lru will not save you there) or what usually happens is redis or memcached and use the onheap cache as the L1 cache. Maybe I'll add the ability to specify a custom allocator sometime, but that will be much later.

Usually very loaded services use 20-50+ instances, and in this case you simply do not need to store such a large cache in each, and for non-loaded services a large cache is simply not needed.

And most database engines, search engines, kafka, etc. quietly use onheap caches and live perfectly, so it's better to choose a tool for your task.

You also need to think about consistency in such large caches, redis/memcached will do it for you, otherwise you need to write the worst analog yourself.

P.S. The throughput benchmarks there are quite funny, but that's a separate conversation.

[maypok86]

And if you start comparing with onheap implementations, then memory consumption will almost always be lower or about the same on small caches.

[maypok86]

I think this issue has been resolved. If you need something else, then write.