code-hex / go-generics-cache Goto Github PK
View Code? Open in Web Editor NEWA key:value store/cache library written in Go generics. LRU, LFU, FIFO, MRU, Clock support.
License: MIT License
A key:value store/cache library written in Go generics. LRU, LFU, FIFO, MRU, Clock support.
License: MIT License
Example test:
cache := clock.NewCache[int, int](clock.WithCapacity(10))
for i := 0; i < 10; i++ {
cache.Set(i, i)
}
cache.Set(10, 10)
if len(cache.Keys()) != 10 {
t.Errorf("want number of keys 10, but got %d, %v", len(cache.Keys()), cache.Keys())
}
When the cache is full, and new page is set, the hand will iterate through all the element in the cache and set referenceCount = 0
.
In that case, line 122 of clock.go failed to get the keys that is still in the page (but with ref count == 0).
$ go env
GO111MODULE="on"
GOARCH="arm64"
GOBIN=""
GOEXE=""
GOEXPERIMENT=""
GOFLAGS=""
GOHOSTARCH="arm64"
GOHOSTOS="darwin"
GOINSECURE=""
GOOS="darwin"
GOPROXY="https://goproxy.cn,direct"
GOROOT="/opt/homebrew/opt/go/libexec"
GOSUMDB="sum.golang.org"
GOTMPDIR=""
GOTOOLDIR="/opt/homebrew/opt/go/libexec/pkg/tool/darwin_arm64"
GOVCS=""
GOVERSION="go1.20.4"
GCCGO="gccgo"
AR="ar"
CC="cc"
CXX="c++"
CGO_ENABLED="1"
GOWORK=""
CGO_CFLAGS="-O2 -g"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-O2 -g"
CGO_FFLAGS="-O2 -g"
CGO_LDFLAGS="-O2 -g"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -arch arm64 -pthread -fno-caret-diagnostics -Qunused-arguments -fmessage-length=0 -fdebug-prefix-map=/var/folders/91/6ypxbjvs1_3007pts7zflvwh0000gn/T/go-build1223268749=/tmp/go-build -gno-record-gcc-switches -fno-common"
package main
import (
"time"
cache "github.com/Code-Hex/go-generics-cache"
"github.com/Code-Hex/go-generics-cache/policy/lfu"
)
func main() {
c := cache.New(
cache.AsLFU[string, string](lfu.WithCapacity(3)),
cache.WithJanitorInterval[string, string](time.Second),
)
c.Set("key1", "value1", cache.WithExpiration(time.Second))
c.Set("key2", "value3", cache.WithExpiration(time.Second))
time.Sleep(time.Minute)
}
$ go run main.go
panic: runtime error: index out of range [-1]
goroutine 17 [running]:
github.com/Code-Hex/go-generics-cache/policy/lfu.priorityQueue[...].Swap(...)
/Users/cyc/go/pkg/mod/github.com/!code-!hex/[email protected]/policy/lfu/priotiry_queue.go:53
container/heap.Remove({0x104545080, 0x140000a6018}, 0xffffffffffffffff)
/opt/homebrew/opt/go/libexec/src/container/heap/heap.go:71 +0x54
github.com/Code-Hex/go-generics-cache/policy/lfu.(*Cache[...]).Delete(0x1045457e0, {0x1045154ce, 0x4})
/Users/cyc/go/pkg/mod/github.com/!code-!hex/[email protected]/policy/lfu/lfu.go:95 +0x5c
github.com/Code-Hex/go-generics-cache.(*Cache[...]).DeleteExpired(0x104545660)
/Users/cyc/go/pkg/mod/github.com/!code-!hex/[email protected]/cache.go:228 +0xf8
github.com/Code-Hex/go-generics-cache.(*janitor).run.func1()
/Users/cyc/go/pkg/mod/github.com/!code-!hex/[email protected]/janitor.go:39 +0xe8
created by github.com/Code-Hex/go-generics-cache.(*janitor).run
/Users/cyc/go/pkg/mod/github.com/!code-!hex/[email protected]/janitor.go:33 +0x78
exit status 2
Use sync.RWMutex instead of sync.Mutex ?
Hi! Thanks for a good cache library that provides generics โ it's really handy.
I've used this a bit for certain things, and found out that adding an expiry to items adds a new goroutine:
Lines 170 to 180 in a0612be
A lot of goroutines is pretty expensive, both in terms of switching and in terms of memory usage (each is 2kb in size).
Would you be open to a PR for a more performant implementation? github.com/patrickmn/go-cache uses a janitor, and I suppose this library could implement something like that -- falling back to the current behaviour if a cleanup interval isn't provided.
https://github.com/bahlo/generic-list-go - for example this looks very similar to containers/list but without empty interfaces.
I noticed what the library uses containers/list because my program sometimes crashes
panic: interface conversion: interface {} is nil, not *lru.entry[string,*github.com/Code-Hex/go-generics-cache.Item[string,int64]]
goroutine 241845 [running]:
github.com/Code-Hex/go-generics-cache/policy/lru.(*Cache[...]).delete(...)
/go/pkg/mod/github.com/!code-!hex/[email protected]/policy/lru/lru.go:118
github.com/Code-Hex/go-generics-cache/policy/lru.(*Cache[...]).deleteOldest(0xc000234330?)
/go/pkg/mod/github.com/!code-!hex/[email protected]/policy/lru/lru.go:113 +0xed
github.com/Code-Hex/go-generics-cache/policy/lru.(*Cache[...]).Set(0xc00023a048, {0xc0061324b0, 0x42}, 0xc007a885a0)
/go/pkg/mod/github.com/!code-!hex/[email protected]/policy/lru/lru.go:85 +0x339
github.com/Code-Hex/go-generics-cache.(*Cache[...]).Set(0xc0002340f0, {0xc0061324b0, 0x42}, 0x48, {0x0?, 0x0, 0x0})
/go/pkg/mod/github.com/!code-!hex/[email protected]/cache.go:158 +0x1f3
It also can be problem in logic (maybe some races)
Hii !!
It would be greate to have data persistance. I would like to contribute to add save and load feature.
I am thinking of using gob to save / retreive data to / from file.
func TestLFUPop(t *testing.T) {
const maxKeySize = 10000000
c := New[int, int](AsLFU[int, int](lfu.WithCapacity(maxKeySize)))
take := time.Now()
for i := 0; i < maxKeySize; i++ {
c.Set(i, i)
}
t.Log(time.Since(take))
take = time.Now()
for i := 0; i < 300; i++ {
c.Delete(i * 2)
}
t.Log(time.Since(take))
}
=== RUN TestLFUPop
cache_internal_test.go:366: 7.5215588s
cache_internal_test.go:372: 11.4654817s // delete 300 count key...used 11sec
After updating dependencies in a project and moving from go-generic-cache 1.1.0 to 1.3.1, I had the pipeline failing with the following nil panic:
panic: runtime error: invalid memory address or nil pointer dereference
[signal SIGSEGV: segmentation violation code=0x1 addr=0x0 pc=0x102dffd]
goroutine 375 [running]:
github.com/Code-Hex/go-generics-cache/policy/simple.(*Cache[...]).Keys.func1(0x3)
/home/vsts/agents/3.236.1/go/pkg/mod/github.com/!code-!hex/[email protected]/policy/simple/simple.go:53 +0x15d
sort.order2_func(...)
/opt/hostedtoolcache/go/1.22.1/x64/src/sort/zsortfunc.go:299
sort.median_func({0xc00007bd08?, 0xc00038b290?}, 0x3, 0x6, 0x9, 0xc00007bb50)
/opt/hostedtoolcache/go/1.22.1/x64/src/sort/zsortfunc.go:308 +0x53
sort.choosePivot_func({0xc00007bd08?, 0xc00038b290?}, 0x0, 0xf)
/opt/hostedtoolcache/go/1.22.1/x64/src/sort/zsortfunc.go:284 +0x190
sort.pdqsort_func({0xc00007bd08?, 0xc00038b290?}, 0x0, 0xf, 0x4)
/opt/hostedtoolcache/go/1.22.1/x64/src/sort/zsortfunc.go:89 +0x148
sort.Slice({0x15a36e0, 0xc0024d9878}, 0xc00007bd08)
/opt/hostedtoolcache/go/1.22.1/x64/src/sort/slice.go:29 +0xab
github.com/Code-Hex/go-generics-cache/policy/simple.(*Cache[...]).Keys(0x19a8e60)
/home/vsts/agents/3.236.1/go/pkg/mod/github.com/!code-!hex/[email protected]/policy/simple/simple.go:50 +0x3a5
github.com/Code-Hex/go-generics-cache.(*Cache[...]).DeleteExpired(0x19a99e0)
/home/vsts/agents/3.236.1/go/pkg/mod/github.com/!code-!hex/[email protected]/cache.go:220 +0x6c
github.com/Code-Hex/go-generics-cache.(*janitor).run.func1()
/home/vsts/agents/3.236.1/go/pkg/mod/github.com/!code-!hex/[email protected]/janitor.go:39 +0x202
created by github.com/Code-Hex/go-generics-cache.(*janitor).run in goroutine 1
/home/vsts/agents/3.236.1/go/pkg/mod/github.com/!code-!hex/[email protected]/janitor.go:33 +0xd1
This is the code that uses the cache:
lastHeard, found := c.lastHeardCache.Get(key)
if found {
return lastHeard, nil
}
lastHeard, err := c.getLastHeard(ctx, key)
if err != nil {
return 0, err
}
c.lastHeardCache.Set(key, lastHeard, cache.WithExpiration(c.cacheTTL))
With the cache being initialized without any option: cache.New[lastHeardKey, int64]()
I was also able to reproduce the error with 1.2.0.
The issue does not appear when running my tests locally, only in a pipeline. They use concurrency quite a lot and are significantly slower in the pipeline, possibly explaining why the error does not occur locally. From what I could find in the code, it seems a key has been deleted in the middle of a call to sort, which makes the sort func panic. I can't figure out though why this happens as everything seems protected by a mutex in cache.go.
c.Set("1", 10, WithExpiration(10*time.Minute)) // queue index 0
c.Set("2", 20, WithExpiration(20*time.Minute)) // queue index 1
c.Set("1", 11, WithExpiration(100*time.Minute)) // must queue index 0 move to 1, check point
nowFunc = func() time.Time {
return now.Add(30 * time.Minute).Add(time.Minute)
}
maxItems = c.Len()
c.DeleteExpired()
got3 := c.Len()
want3 := maxItems - 1
if want3 != got3 {
t.Errorf("want3 %d items but got3 %d", want3, got3)
}
func (m *expirationManager[K]) update(key K, expiration time.Time) {
if e, ok := m.mapping[key]; ok {
e.expiration = expiration
heap.Fix(&m.queue, e.index)
} else {
Don't use full keys scan........
I am a bit confused, in the README, it says it is thread safe, but I check the NewCache()
methods, it says non-thread safe
.
https://github.com/search?q=repo%3ACode-Hex%2Fgo-generics-cache%20NewCache&type=code
Problem: fatal error: concurrent map read and map write
Reproduce Code:
func BenchmarkConcurrentSet(b *testing.B) {
cache := clock.NewCache[string, string]()
group := sync.WaitGroup{}
for i := 0; i < b.N; i++ {
group.Add(1)
var count int = 1000
go func() {
for count > 0 {
cache.Set("key", "value")
count--
if count <= 0 {
group.Done()
return
}
}
}()
}
group.Wait()
}
Expected: RWLocker for Set/Read.
Related codes
cacheStore := cache.New(cache.AsLFU[string, SomeStruct](lfu.WithCapacity(5)))
cacheStore.Set(someKey, someValue, cache.WithExpiration(10 * time.Second))
Logs
panic: runtime error: index out of range [-1]
goroutine 71 [running]:
github.com/Code-Hex/go-generics-cache/policy/lfu.priorityQueue[...].Swap(...)
github.com/Code-Hex/[email protected]/policy/lfu/priotiry_queue.go:51
container/heap.Remove({0x1e0c8c0, 0xc0006982b8}, 0xffffffffffffffff)
container/heap/heap.go:72 +0x53
github.com/Code-Hex/go-generics-cache/policy/lfu.(*Cache[...]).Delete(0xc0006982d0, {0xc000322181, 0xbf})
github.com/Code-Hex/[email protected]/policy/lfu/lfu.go:92 +0x65
github.com/Code-Hex/go-generics-cache.(*Cache[...]).DeleteExpired(0xc0002c2a20)
github.com/Code-Hex/[email protected]/cache.go:209 +0x158
github.com/Code-Hex/go-generics-cache.NewContext[...].func1()
github.com/Code-Hex/[email protected]/cache.go:175 +0x25
github.com/Code-Hex/go-generics-cache.(*janitor).run.func1()
github.com/Code-Hex/[email protected]/janitor.go:39 +0x122
created by github.com/Code-Hex/go-generics-cache.(*janitor).run
github.com/Code-Hex/[email protected]/janitor.go:33 +0x72
I have a dictionary in which I want to keep the 20 most frequent words / queries for example. So I make a LFU cache:
frequency = lfu.NewCache[string, int](lfu.WithCapacity(20))
and then
count, _ := frequency.Get(query)
frequency.Set(query, count+1)
on every query.
So when it exceeds 20, the least frequent query is deleted.
And I can save this to a JSON file as well.
So far so good.
But when I run the program next time and load this JSON file, and set the values, the internal frequency (heap order) is not updated (they are all one) unless I run Get()
or Set()
the same number of times (or at least N
times for the top item, if we have N
items), which is very slow.
So if I could run frequency.SetWithCount(key, value, count)
for example, that is just like
for i:=0; i<count; i++ {
frequency.Set(key, value)
}
But much faster.
That would solve the problem.
It would be useful to have Len() method available in common interface. I would need it for getting metrics for cache usage.
It is available if the cache is created with exact policy lru.NewCache()
but if you want to use context cache.NewContext()
then common interface is returned. len(c.Keys())
could be used but it's still not the same.
Example:
ctx := context.Background()
var myCache *cache.Cache[string, int]
myCache = cache.NewContext(ctx, cache.AsLRU[string, int](lru.WithCapacity(10)))
// myCache is LRU cache but myCache.Len() is not available
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.