izturn/lruPublic

forked fromphuslu/lru

NotificationsYou must be signed in to change notification settings
Fork0
Star0

High performance LRU cache

License

MIT license

0 stars 8 forks Branches Tags Activity

Star

Notifications

You must be signed in to change notification settings

Branches Tags

Folders and files

Name		Name	Last commit message	Last commit date
Latest commit History 241 Commits
.github/workflows		.github/workflows
LICENSE		LICENSE
README.md		README.md
bytes_cache.go		bytes_cache.go
bytes_cache_test.go		bytes_cache_test.go
bytes_file.go		bytes_file.go
bytes_shard.go		bytes_shard.go
bytes_shard_list.go		bytes_shard_list.go
bytes_shard_table.go		bytes_shard_table.go
bytes_shard_test.go		bytes_shard_test.go
example_test.go		example_test.go
go.mod		go.mod
lru_cache.go		lru_cache.go
lru_cache_test.go		lru_cache_test.go
lru_shard.go		lru_shard.go
lru_shard_list.go		lru_shard_list.go
lru_shard_table.go		lru_shard_table.go
lru_shard_test.go		lru_shard_test.go
options.go		options.go
runtime.go		runtime.go
singleflight.go		singleflight.go
stats.go		stats.go
ttl_cache.go		ttl_cache.go
ttl_cache_test.go		ttl_cache_test.go
ttl_clock.go		ttl_clock.go
ttl_shard.go		ttl_shard.go
ttl_shard_list.go		ttl_shard_list.go
ttl_shard_table.go		ttl_shard_table.go
ttl_shard_test.go		ttl_shard_test.go
wyhash.go		wyhash.go

Repository files navigation

a high-performance and gc-friendly LRU cache

Features

Simple
- No Dependencies.
- Straightforward API.
Fast
- Outperforms well-knownLRU caches.
- Zero memory allocations.
GC friendly
- Pointerless and continuous data structs.
- Minimized GC scan times.
Memory efficient
- Adds only 26 extra bytes per entry.
- Minimized memory usage.
Feature optional
- Using SlidingCache viaWithSliding(true) option.
- Create LoadingCache viaWithLoader(func(context.Context, K) (V, time.Duration, error)) option.

Limitations

The TTL is accurate to the nearest second.
Expired items are only removed when accessed again or the cache is full.

Getting Started

package mainimport ("time""github.com/phuslu/lru")funcmain() {cache:= lru.NewTTLCache[string,int](8192)cache.Set("a",1,2*time.Second)println(cache.Get("a"))println(cache.Get("b"))time.Sleep(1*time.Second)println(cache.Get("a"))time.Sleep(2*time.Second)println(cache.Get("a"))stats:=cache.Stats()println("SetCalls",stats.SetCalls,"GetCalls",stats.GetCalls,"Misses",stats.Misses)}

Throughput benchmarks

Disclaimer: This have been testing on the busy GitHub runners with 8 vCPUs and the results may be very different from your real environment. seephuslu#14

A Performance result as below. Check githubbenchmark action for more results and details.

go1.22 benchmark on keysize=16, itemsize=1000000, cachesize=50%, concurrency=8

// env writeratio=0.1 zipfian=false go test -v -cpu=8 -run=none -bench=. -benchtime=5s -benchmem bench_test.gopackage benchimport ("crypto/sha1""fmt""math/rand/v2""math/bits""os""runtime""strconv""testing""time"_"unsafe"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""github.com/aclements/go-perfevent/perfbench")const (keysize=16cachesize=1000000)varwriteratio,_=strconv.ParseFloat(os.Getenv("writeratio"),64)varzipfian,_=strconv.ParseBool(os.Getenv("zipfian"))typeCheapRandstruct {Seeduint64}func (rand*CheapRand)Uint32()uint32 {rand.Seed+=0xa0761d6478bd642fhi,lo:=bits.Mul64(rand.Seed,rand.Seed^0xe7037ed1a0b428db)returnuint32(hi^lo)}func (rand*CheapRand)Uint32n(nuint32)uint32 {returnuint32((uint64(rand.Uint32())*uint64(n))>>32)}func (rand*CheapRand)Uint64()uint64 {returnuint64(rand.Uint32())<<32^uint64(rand.Uint32())}varshardcount=func()int {n:=runtime.GOMAXPROCS(0)*16k:=1fork<n {k=k*2}returnk}()varkeys=func() (x []string) {x=make([]string,cachesize)fori:=rangecachesize {x[i]=fmt.Sprintf("%x",sha1.Sum([]byte(fmt.Sprint(i))))[:keysize]}return}()funcBenchmarkHashicorpSetGet(b*testing.B) {c:=perfbench.Open(b)cache:=hashicorp.NewLRU[string,int](cachesize,nil,time.Hour)fori:=rangecachesize/2 {cache.Add(keys[i],i)}b.ResetTimer()c.Reset()b.RunParallel(func(pb*testing.PB) {threshold:=uint32(float64(^uint32(0))*writeratio)cheaprand:=&CheapRand{uint64(time.Now().UnixNano())}zipf:=rand.NewZipf(rand.New(cheaprand),1.0001,10,cachesize-1)forpb.Next() {ifthreshold>0&&cheaprand.Uint32()<=threshold {i:=int(cheaprand.Uint32n(cachesize))cache.Add(keys[i],i)}elseifzipfian {cache.Get(keys[zipf.Uint64()])}else {cache.Get(keys[cheaprand.Uint32n(cachesize)])}}})}funcBenchmarkCloudflareSetGet(b*testing.B) {c:=perfbench.Open(b)cache:=cloudflare.NewMultiLRUCache(uint(shardcount),uint(cachesize/shardcount))fori:=rangecachesize/2 {cache.Set(keys[i],i,time.Now().Add(time.Hour))}expires:=time.Now().Add(time.Hour)b.ResetTimer()c.Reset()b.RunParallel(func(pb*testing.PB) {threshold:=uint32(float64(^uint32(0))*writeratio)cheaprand:=&CheapRand{uint64(time.Now().UnixNano())}zipf:=rand.NewZipf(rand.New(cheaprand),1.0001,10,cachesize-1)forpb.Next() {ifthreshold>0&&cheaprand.Uint32()<=threshold {i:=int(cheaprand.Uint32n(cachesize))cache.Set(keys[i],i,expires)}elseifzipfian {cache.Get(keys[zipf.Uint64()])}else {cache.Get(keys[cheaprand.Uint32n(cachesize)])}}})}funcBenchmarkEcacheSetGet(b*testing.B) {c:=perfbench.Open(b)cache:=ecache.NewLRUCache(uint16(shardcount),uint16(cachesize/shardcount),time.Hour)fori:=rangecachesize/2 {cache.Put(keys[i],i)}b.ResetTimer()c.Reset()b.RunParallel(func(pb*testing.PB) {threshold:=uint32(float64(^uint32(0))*writeratio)cheaprand:=&CheapRand{uint64(time.Now().UnixNano())}zipf:=rand.NewZipf(rand.New(cheaprand),1.0001,10,cachesize-1)forpb.Next() {ifthreshold>0&&cheaprand.Uint32()<=threshold {i:=int(cheaprand.Uint32n(cachesize))cache.Put(keys[i],i)}elseifzipfian {cache.Get(keys[zipf.Uint64()])}else {cache.Get(keys[cheaprand.Uint32n(cachesize)])}}})}funcBenchmarkLxzanSetGet(b*testing.B) {c:=perfbench.Open(b)cache:=lxzan.New[string,int](lxzan.WithBucketNum(shardcount),lxzan.WithBucketSize(cachesize/shardcount,cachesize/shardcount),lxzan.WithInterval(time.Hour,time.Hour),)fori:=rangecachesize/2 {cache.Set(keys[i],i,time.Hour)}b.ResetTimer()c.Reset()b.RunParallel(func(pb*testing.PB) {threshold:=uint32(float64(^uint32(0))*writeratio)cheaprand:=&CheapRand{uint64(time.Now().UnixNano())}zipf:=rand.NewZipf(rand.New(cheaprand),1.0001,10,cachesize-1)forpb.Next() {ifthreshold>0&&cheaprand.Uint32()<=threshold {i:=int(cheaprand.Uint32n(cachesize))cache.Set(keys[i],i,time.Hour)}elseifzipfian {cache.Get(keys[zipf.Uint64()])}else {cache.Get(keys[cheaprand.Uint32n(cachesize)])}}})}funchashStringXXHASH(sstring)uint32 {returnuint32(xxhash.Sum64String(s))}funcBenchmarkFreelruSetGet(b*testing.B) {c:=perfbench.Open(b)cache,_:=freelru.NewSharded[string,int](cachesize,hashStringXXHASH)fori:=rangecachesize/2 {cache.AddWithLifetime(keys[i],i,time.Hour)}b.ResetTimer()c.Reset()b.RunParallel(func(pb*testing.PB) {threshold:=uint32(float64(^uint32(0))*writeratio)cheaprand:=&CheapRand{uint64(time.Now().UnixNano())}zipf:=rand.NewZipf(rand.New(cheaprand),1.0001,10,cachesize-1)forpb.Next() {ifthreshold>0&&cheaprand.Uint32()<=threshold {i:=int(cheaprand.Uint32n(cachesize))cache.AddWithLifetime(keys[i],i,time.Hour)}elseifzipfian {cache.Get(keys[zipf.Uint64()])}else {cache.Get(keys[cheaprand.Uint32n(cachesize)])}}})}funcBenchmarkPhusluSetGet(b*testing.B) {c:=perfbench.Open(b)cache:=phuslu.NewTTLCache[string,int](cachesize, phuslu.WithShards[string,int](uint32(shardcount)))fori:=rangecachesize/2 {cache.Set(keys[i],i,time.Hour)}b.ResetTimer()c.Reset()b.RunParallel(func(pb*testing.PB) {threshold:=uint32(float64(^uint32(0))*writeratio)cheaprand:=&CheapRand{uint64(time.Now().UnixNano())}zipf:=rand.NewZipf(rand.New(cheaprand),1.0001,10,cachesize-1)forpb.Next() {ifthreshold>0&&cheaprand.Uint32()<=threshold {i:=int(cheaprand.Uint32n(cachesize))cache.Set(keys[i],i,time.Hour)}elseifzipfian {cache.Get(keys[zipf.Uint64()])}else {cache.Get(keys[cheaprand.Uint32n(cachesize)])}}})}funcBenchmarkNoTTLSetGet(b*testing.B) {c:=perfbench.Open(b)cache:=phuslu.NewLRUCache[string,int](cachesize, phuslu.WithShards[string,int](uint32(shardcount)))fori:=rangecachesize/2 {cache.Set(keys[i],i)}b.ResetTimer()c.Reset()b.RunParallel(func(pb*testing.PB) {threshold:=uint32(float64(^uint32(0))*writeratio)cheaprand:=&CheapRand{uint64(time.Now().UnixNano())}zipf:=rand.NewZipf(rand.New(cheaprand),1.0001,10,cachesize-1)forpb.Next() {ifthreshold>0&&cheaprand.Uint32()<=threshold {i:=int(cheaprand.Uint32n(cachesize))cache.Set(keys[i],i)}elseifzipfian {cache.Get(keys[zipf.Uint64()])}else {cache.Get(keys[cheaprand.Uint32n(cachesize)])}}})}funcBenchmarkCcacheSetGet(b*testing.B) {c:=perfbench.Open(b)cache:=ccache.New(ccache.Configure[int]().MaxSize(cachesize).ItemsToPrune(100))fori:=rangecachesize/2 {cache.Set(keys[i],i,time.Hour)}b.ResetTimer()c.Reset()b.RunParallel(func(pb*testing.PB) {threshold:=uint32(float64(^uint32(0))*writeratio)cheaprand:=&CheapRand{uint64(time.Now().UnixNano())}zipf:=rand.NewZipf(rand.New(cheaprand),1.0001,10,cachesize-1)forpb.Next() {ifthreshold>0&&cheaprand.Uint32()<=threshold {i:=int(cheaprand.Uint32n(cachesize))cache.Set(keys[i],i,time.Hour)}elseifzipfian {cache.Get(keys[zipf.Uint64()])}else {cache.Get(keys[cheaprand.Uint32n(cachesize)])}}})}funcBenchmarkRistrettoSetGet(b*testing.B) {c:=perfbench.Open(b)cache,_:=ristretto.NewCache(&ristretto.Config{NumCounters:10*cachesize,// number of keys to track frequency of (10M).MaxCost:cachesize,// maximum cost of cache (1M).BufferItems:64,// number of keys per Get buffer.})fori:=rangecachesize/2 {cache.SetWithTTL(keys[i],i,1,time.Hour)}b.ResetTimer()c.Reset()b.RunParallel(func(pb*testing.PB) {threshold:=uint32(float64(^uint32(0))*writeratio)cheaprand:=&CheapRand{uint64(time.Now().UnixNano())}zipf:=rand.NewZipf(rand.New(cheaprand),1.0001,10,cachesize-1)forpb.Next() {ifthreshold>0&&cheaprand.Uint32()<=threshold {i:=int(cheaprand.Uint32n(cachesize))cache.SetWithTTL(keys[i],i,1,time.Hour)}elseifzipfian {cache.Get(keys[zipf.Uint64()])}else {cache.Get(keys[cheaprand.Uint32n(cachesize)])}}})}funcBenchmarkTheineSetGet(b*testing.B) {c:=perfbench.Open(b)cache,_:= theine.NewBuilder[string,int](cachesize).Build()fori:=rangecachesize/2 {cache.SetWithTTL(keys[i],i,1,time.Hour)}b.ResetTimer()c.Reset()b.RunParallel(func(pb*testing.PB) {threshold:=uint32(float64(^uint32(0))*writeratio)cheaprand:=&CheapRand{uint64(time.Now().UnixNano())}zipf:=rand.NewZipf(rand.New(cheaprand),1.0001,10,cachesize-1)forpb.Next() {ifthreshold>0&&cheaprand.Uint32()<=threshold {i:=int(cheaprand.Uint32n(cachesize))cache.SetWithTTL(keys[i],i,1,time.Hour)}elseifzipfian {cache.Get(keys[zipf.Uint64()])}else {cache.Get(keys[cheaprand.Uint32n(cachesize)])}}})}funcBenchmarkOtterSetGet(b*testing.B) {c:=perfbench.Open(b)cache,_:= otter.MustBuilder[string,int](cachesize).WithVariableTTL().Build()fori:=rangecachesize/2 {cache.Set(keys[i],i,time.Hour)}b.ResetTimer()c.Reset()b.RunParallel(func(pb*testing.PB) {threshold:=uint32(float64(^uint32(0))*writeratio)cheaprand:=&CheapRand{uint64(time.Now().UnixNano())}zipf:=rand.NewZipf(rand.New(cheaprand),1.0001,10,cachesize-1)forpb.Next() {ifthreshold>0&&cheaprand.Uint32()<=threshold {i:=int(cheaprand.Uint32n(cachesize))cache.Set(keys[i],i,time.Hour)}elseifzipfian {cache.Get(keys[zipf.Uint64()])}else {cache.Get(keys[cheaprand.Uint32n(cachesize)])}}})}

with randomly read (90%) and randomly write(10%)

goos: linuxgoarch: amd64cpu: AMD EPYC 7763 64-Core Processor                BenchmarkHashicorpSetGetBenchmarkHashicorpSetGet-8    13146066       553.3 ns/op      11 B/op       0 allocs/opBenchmarkCloudflareSetGetBenchmarkCloudflareSetGet-8   36612316       208.6 ns/op      16 B/op       1 allocs/opBenchmarkEcacheSetGetBenchmarkEcacheSetGet-8       47435138       138.0 ns/op       2 B/op       0 allocs/opBenchmarkLxzanSetGetBenchmarkLxzanSetGet-8        48343774       153.5 ns/op       0 B/op       0 allocs/opBenchmarkFreelruSetGetBenchmarkFreelruSetGet-8      56105211       137.8 ns/op       0 B/op       0 allocs/opBenchmarkPhusluSetGetBenchmarkPhusluSetGet-8       66522236       114.7 ns/op       0 B/op       0 allocs/opBenchmarkCcacheSetGetBenchmarkCcacheSetGet-8       21252092       369.4 ns/op      34 B/op       2 allocs/opBenchmarkRistrettoSetGetBenchmarkRistrettoSetGet-8    35511078       152.7 ns/op      29 B/op       1 allocs/opBenchmarkTheineSetGetBenchmarkTheineSetGet-8       21374548       311.4 ns/op       5 B/op       0 allocs/opBenchmarkOtterSetGetBenchmarkOtterSetGet-8        51896601       159.1 ns/op       8 B/op       0 allocs/opPASSok  command-line-arguments113.829s

with zipfian read (99%) and randomly write(1%)

goos: linuxgoarch: amd64cpu: AMD EPYC 7763 64-Core Processor                BenchmarkHashicorpSetGetBenchmarkHashicorpSetGet-8    14631464       418.5 ns/op       0 B/op       0 allocs/opBenchmarkCloudflareSetGetBenchmarkCloudflareSetGet-8   48996306       129.3 ns/op      16 B/op       1 allocs/opBenchmarkEcacheSetGetBenchmarkEcacheSetGet-8       61667361       101.6 ns/op       0 B/op       0 allocs/opBenchmarkLxzanSetGetBenchmarkLxzanSetGet-8        59331700        99.66 ns/op       0 B/op       0 allocs/opBenchmarkFreelruSetGetBenchmarkFreelruSetGet-8      57392088       113.7 ns/op       0 B/op       0 allocs/opBenchmarkPhusluSetGetBenchmarkPhusluSetGet-8       78875428        81.73 ns/op       0 B/op       0 allocs/opBenchmarkCcacheSetGetBenchmarkCcacheSetGet-8       23366601       270.9 ns/op      21 B/op       2 allocs/opBenchmarkRistrettoSetGetBenchmarkRistrettoSetGet-8    44893608       114.3 ns/op      20 B/op       1 allocs/opBenchmarkTheineSetGetBenchmarkTheineSetGet-8       32717158       172.2 ns/op       0 B/op       0 allocs/opBenchmarkOtterSetGetBenchmarkOtterSetGet-8        70170547        85.62 ns/op       1 B/op       0 allocs/opPASSok  command-line-arguments96.989s

GC scan

The GC scan times as below. Check githubgcscan action for more results and details.

GC scan times on keysize=16(string), valuesize=8(int), cachesize in (100000,200000,400000,1000000)

// env GODEBUG=gctrace=1 go run gcscan.go phuslu 1000000package mainimport ("fmt""os""runtime""runtime/debug""strconv""time"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")constkeysize=16varrepeat,_=strconv.Atoi(os.Getenv("repeat"))varkeys []stringfuncmain() {name:=os.Args[1]cachesize,_:=strconv.Atoi(os.Args[2])keys=make([]string,cachesize)fori:=rangecachesize {keys[i]=fmt.Sprintf(fmt.Sprintf("%%0%dd",keysize),i)}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)}funcSetupNottl(cachesizeint) {deferdebug.SetGCPercent(debug.SetGCPercent(-1))cache:= phuslu.NewLRUCache[string,int](cachesize)runtime.GC()forrangerepeat {fori:=rangecachesize {cache.Set(keys[i],i)}runtime.GC()}}funcSetupPhuslu(cachesizeint) {deferdebug.SetGCPercent(debug.SetGCPercent(-1))cache:= phuslu.NewTTLCache[string,int](cachesize)runtime.GC()forrangerepeat {fori:=rangecachesize {cache.Set(keys[i],i,time.Hour)}runtime.GC()}}funcSetupFreelru(cachesizeint) {deferdebug.SetGCPercent(debug.SetGCPercent(-1))cache,_:=freelru.NewSharded[string,int](uint32(cachesize),func(sstring)uint32 {returnuint32(xxhash.Sum64String(s)) })runtime.GC()forrangerepeat {fori:=rangecachesize {cache.AddWithLifetime(keys[i],i,time.Hour)}runtime.GC()}}funcSetupOtter(cachesizeint) {deferdebug.SetGCPercent(debug.SetGCPercent(-1))cache,_:= otter.MustBuilder[string,int](cachesize).WithVariableTTL().Build()runtime.GC()forrangerepeat {fori:=rangecachesize {cache.Set(keys[i],i,time.Hour)}runtime.GC()}}funcSetupEcache(cachesizeint) {deferdebug.SetGCPercent(debug.SetGCPercent(-1))cache:=ecache.NewLRUCache(1024,uint16(cachesize/1024),time.Hour)runtime.GC()forrangerepeat {fori:=rangecachesize {cache.Put(keys[i],i)}runtime.GC()}}funcSetupRistretto(cachesizeint) {deferdebug.SetGCPercent(debug.SetGCPercent(-1))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.})runtime.GC()forrangerepeat {fori:=rangecachesize {cache.SetWithTTL(keys[i],i,1,time.Hour)}runtime.GC()}}funcSetupLxzan(cachesizeint) {deferdebug.SetGCPercent(debug.SetGCPercent(-1))cache:=lxzan.New[string,int](lxzan.WithBucketNum(128),lxzan.WithBucketSize(cachesize/128,cachesize/128),lxzan.WithInterval(time.Hour,time.Hour),)runtime.GC()forrangerepeat {fori:=rangecachesize {cache.Set(keys[i],i,time.Hour)}runtime.GC()}}funcSetupTheine(cachesizeint) {deferdebug.SetGCPercent(debug.SetGCPercent(-1))cache,_:= theine.NewBuilder[string,int](int64(cachesize)).Build()runtime.GC()forrangerepeat {fori:=rangecachesize {cache.SetWithTTL(keys[i],i,1,time.Hour)}runtime.GC()}}funcSetupCloudflare(cachesizeint) {deferdebug.SetGCPercent(debug.SetGCPercent(-1))cache:=cloudflare.NewMultiLRUCache(1024,uint(cachesize/1024))runtime.GC()forrangerepeat {fori:=rangecachesize {cache.Set(keys[i],i,time.Now().Add(time.Hour))}runtime.GC()}}funcSetupCcache(cachesizeint) {deferdebug.SetGCPercent(debug.SetGCPercent(-1))cache:=ccache.New(ccache.Configure[int]().MaxSize(int64(cachesize)).ItemsToPrune(100))runtime.GC()forrangerepeat {fori:=rangecachesize {cache.Set(keys[i],i,time.Hour)}runtime.GC()}}funcSetupHashicorp(cachesizeint) {deferdebug.SetGCPercent(debug.SetGCPercent(-1))cache:=hashicorp.NewLRU[string,int](cachesize,nil,time.Hour)runtime.GC()forrangerepeat {fori:=rangecachesize {cache.Add(keys[i],i)}runtime.GC()}}

GCScan	100000	200000	400000	1000000
phuslu	1 ms	3 ms	6 ms	15 ms
freelru	2 ms	3 ms	6 ms	16 ms
ristretto	4 ms	6 ms	9 ms	17 ms
lxzan	2 ms	4 ms	7 ms	18 ms
cloudflare	5 ms	10 ms	21 ms	56 ms
ecache	5 ms	10 ms	21 ms	57 ms
ccache	5 ms	10 ms	22 ms	58 ms
otter	6 ms	12 ms	28 ms	64 ms
hashicorp	7 ms	16 ms	30 ms	79 ms
theine	6 ms	13 ms	34 ms	83 ms

Memory usage

The Memory usage result as below. Check githubmemory action for more results and details.

memory usage on keysize=16(string), valuesize=8(int), cachesize in (100000,200000,400000,1000000,2000000,4000000)

// memusage.gopackage mainimport ("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")constkeysize=16varkeys []stringfuncmain() {name:=os.Args[1]cachesize,_:=strconv.Atoi(os.Args[2])keys=make([]string,cachesize)fori:=rangecachesize {keys[i]=fmt.Sprintf(fmt.Sprintf("%%0%dd",keysize),i)}varo runtime.MemStatsruntime.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)varm runtime.MemStatsruntime.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,)}funcSetupNottl(cachesizeint) {cache:= phuslu.NewLRUCache[string,int](cachesize)fori:=rangecachesize {cache.Set(keys[i],i)}}funcSetupPhuslu(cachesizeint) {cache:= phuslu.NewTTLCache[string,int](cachesize)fori:=rangecachesize {cache.Set(keys[i],i,time.Hour)}}funcSetupFreelru(cachesizeint) {cache,_:=freelru.NewSharded[string,int](uint32(cachesize),func(sstring)uint32 {returnuint32(xxhash.Sum64String(s)) })fori:=rangecachesize {cache.AddWithLifetime(keys[i],i,time.Hour)}}funcSetupOtter(cachesizeint) {cache,_:= otter.MustBuilder[string,int](cachesize).WithVariableTTL().Build()fori:=rangecachesize {cache.Set(keys[i],i,time.Hour)}}funcSetupEcache(cachesizeint) {cache:=ecache.NewLRUCache(1024,uint16(cachesize/1024),time.Hour)fori:=rangecachesize {cache.Put(keys[i],i)}}funcSetupRistretto(cachesizeint) {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.})fori:=rangecachesize {cache.SetWithTTL(keys[i],i,1,time.Hour)}}funcSetupLxzan(cachesizeint) {cache:=lxzan.New[string,int](lxzan.WithBucketNum(128),lxzan.WithBucketSize(cachesize/128,cachesize/128),lxzan.WithInterval(time.Hour,time.Hour),)fori:=rangecachesize {cache.Set(keys[i],i,time.Hour)}}funcSetupTheine(cachesizeint) {cache,_:= theine.NewBuilder[string,int](int64(cachesize)).Build()fori:=rangecachesize {cache.SetWithTTL(keys[i],i,1,time.Hour)}}funcSetupCloudflare(cachesizeint) {cache:=cloudflare.NewMultiLRUCache(1024,uint(cachesize/1024))fori:=rangecachesize {cache.Set(keys[i],i,time.Now().Add(time.Hour))}}funcSetupCcache(cachesizeint) {cache:=ccache.New(ccache.Configure[int]().MaxSize(int64(cachesize)).ItemsToPrune(100))fori:=rangecachesize {cache.Set(keys[i],i,time.Hour)}}funcSetupHashicorp(cachesizeint) {cache:=hashicorp.NewLRU[string,int](cachesize,nil,time.Hour)fori:=rangecachesize {cache.Add(keys[i],i)}}

	100000	200000	400000	1000000	2000000	4000000
nottl*	3 MB	7 MB	13 MB	39 MB	78 MB	155 MB
phuslu	4 MB	8 MB	16 MB	46 MB	93 MB	185 MB
lxzan	8 MB	17 MB	35 MB	95 MB	190 MB	379 MB
ristretto*	14 MB	15 MB	34 MB	89 MB	213 MB	412 MB
otter	13 MB	22 MB	54 MB	104 MB	209 MB	419 MB
freelru*	6 MB	14 MB	27 MB	112 MB	224 MB	448 MB
ecache	11 MB	22 MB	44 MB	123 MB	238 MB	468 MB
theine	15 MB	31 MB	62 MB	178 MB	357 MB	714 MB
cloudflare	15 MB	33 MB	64 MB	183 MB	358 MB	717 MB
ccache	16 MB	33 MB	65 MB	183 MB	365 MB	730 MB
hashicorp	18 MB	37 MB	57 MB	242 MB	484 MB	968 MB

nottl saves 20% memory usage compared to phuslu by removing its ttl functionality, resulting in a slight increase in throughput.
ristretto employs a questionable usage pattern due to its rejection of items via a bloom filter, resulting in a lower hit ratio.
freelru overcommits the cache size to the next power of 2, leading to higher memory usage particularly at larger cache sizes.

Hit ratio

It is a classic sharded LRU implementation, so the hit ratio is comparable to or slightly lower than a regular LRU.

License

LRU is licensed under the MIT License. See the LICENSE file for details.

Contact

For inquiries or support, contactphus.lu@gmail.com or raise github issues.

About

High performance LRU cache

Releases1

bump to match go 1.24 Latest

Aug 5, 2024

Packages

No packages published

Languages

Go100.0%

Movatterモバイル変換

Navigation Menu

Search code, repositories, users, issues, pull requests...

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

License

Uh oh!

Folders and files

Latest commit

History

Repository files navigation

a high-performance and gc-friendly LRU cache

Features

Limitations

Getting Started

Throughput benchmarks

GC scan

Memory usage

Hit ratio

License

Contact

About

Resources

License

Uh oh!

Stars

Watchers

Forks

Releases1

Packages

Uh oh!

Languages

Movatterモバイル変換

License

izturn/lru

Folders and files

Latest commit

History

Repository files navigation

a high-performance and gc-friendly LRU cache

Features

Limitations

Getting Started

Throughput benchmarks

GC scan

Memory usage

Hit ratio

License

Contact

About

Resources

License

Uh oh!

Stars

Watchers

Forks

Releases1

Packages0

Uh oh!

Languages

Packages