The highest tagged major version is
README
¶
RingDict
A map-like structure over a ring
How?
go get -u git.sr.ht/~blallo/go-ringdict@interface
This version is the one pre-generics, that supports only string as key type
and uses interface{} to handle the values.
To use the one backed by generics (go>=1.18) use the generics branch.
What?
This go module offers two data structures that have a map-like API but behave like a ring.
*RDict is unsafe for concurrent use. *SafeRDict is safe, protected by a
sync.RWLock, but is slower. You can instantiate the former with New and the
latter with NewSafe. In both cases, you have to provide a capacity for the
underlying ring. Given a capacity N, when inserting the N+1th element, the
first inserted will be overwritten, just like a ring.
You can cast a *RDict to *SafeRDict with Safe, and do the contrary with
Unsafe.
Why?
This was inspired to me by a task I was assigned to some years ago: I had to tame a memory leak in a big python application I didn't write (it was a huge mess). The main logic was running in a big for loop. Somewhere there were dictionaries used as caches. I implemented something similar to this package (but in pure python) to get a hold on the memory usage, at the cost of a somehow degraded time performance.
I was inspired by the container/ring in go standard library, but could not
find a way to use it to replicate that structure, until today. I was surprised
to discover that the code is very much simpler than what I had anticipated.
Benchmarks
The BenchmarkMap* are used as a reference baseline.
$ make bench
go test -bench=. -benchmem -v .
=== RUN TestRingDict
--- PASS: TestRingDict (0.00s)
goos: linux
goarch: amd64
pkg: git.sr.ht/~blallo/go-ringdict
cpu: 11th Gen Intel(R) Core(TM) i7-1185G7 @ 3.00GHz
BenchmarkRingDict10
BenchmarkRingDict10-8 5937477 202.0 ns/op 43 B/op 4 allocs/op
BenchmarkSafeRingDict10
BenchmarkSafeRingDict10-8 5225078 227.5 ns/op 43 B/op 4 allocs/op
BenchmarkMap10
BenchmarkMap10-8 3043899 360.4 ns/op 99 B/op 2 allocs/op
BenchmarkRingDict10_000
BenchmarkRingDict10_000-8 4488156 266.7 ns/op 43 B/op 4 allocs/op
BenchmarkSafeRingDict10_000
BenchmarkSafeRingDict10_000-8 4248956 274.8 ns/op 43 B/op 4 allocs/op
BenchmarkMap10_000
BenchmarkMap10_000-8 3096568 354.0 ns/op 98 B/op 2 allocs/op
BenchmarkRingDict10_000_000
BenchmarkRingDict10_000_000-8 3029902 373.6 ns/op 345 B/op 7 allocs/op
BenchmarkSafeRingDict10_000_000
BenchmarkSafeRingDict10_000_000-8 2462072 427.5 ns/op 416 B/op 8 allocs/op
BenchmarkMap10_000_000
BenchmarkMap10_000_000-8 4635259 236.3 ns/op 115 B/op 1 allocs/op
PASS
ok git.sr.ht/~blallo/go-ringdict 23.534s
Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type RDict ¶
type RDict struct {
// contains filtered or unexported fields
}
RDict is a data structure that behaves both as a map and as a ring. It is defined by a capacity, just as a ring. As more key-value pairs are added to it, it fills up until the capacity is reached. At that point, the first key in insertion order gets overwritten.
It supports only string as key type. It is not goroutine-safe.
func (*RDict) Del ¶
Del removes the key-value pair from the RDict. Returns true if the provided key was present in the RDict, false otherwise. Beware: it is O(N) in the worst case, being N the capacity of the RDict.
func (*RDict) Do ¶
Do is the API to iterate over all the RDict elements. The provided input function receives, for each element stored in RDict, the key as first argument and the corresponding value as second.
type SafeRDict ¶
type SafeRDict struct {
// contains filtered or unexported fields
}
SafeRDict is the goroutine-safe version of RDict.
func NewSafe ¶
NewSafe is the constructor for the SafeRDict. One needs to provide the capacity as sole input.
func (*SafeRDict) Del ¶
Del removes the key-value pair from the RDict. Returns true if the provided key was present in the RDict, false otherwise. Beware: it is O(N) in the worst case, being N the capacity of the SafeRDict. Locks RW.
func (*SafeRDict) Do ¶
Do is the API to iterate over all the RDict elements. The provided input function receives, for each element stored in RDict, the key as first argument and the corresponding value as second. Locks R.
Source Files