phuslu / lru Goto Github PK
View Code? Open in Web Editor NEWHigh performance LRU cache
License: MIT License
High performance LRU cache
License: MIT License
can u do a version which i think can be faster if you disregard the time expiry? meaning no time expiry
this is for maximum lru speed. i dont need the expiry field.
do u know what's wrong?
2024/03/28 16:10:44 started redhub server at 127.0.0.1:6380
panic: runtime error: invalid memory address or nil pointer dereference
[signal SIGSEGV: segmentation violation code=0x1 addr=0x0 pc=0x6e7ca2]
goroutine 10 [running]:
github.com/phuslu/lru.(*LRUCache[...]).Get(0x814a80, {0xc00034a012, 0x10})
/root/go/pkg/mod/github.com/phuslu/[email protected]/lru_cache.go:71 +0x22
code attached:
https://pastebin.com/DYD0sku7
redis-cli -p 6380
127.0.0.1:6380> set a b
Error: Server closed the connection
I'm plan to release v1.0.0, before this we need
Welcome feedback, thanks!
Thanks for share the nice repo, I have just added the Loader
to my code, the new version makes it outdated ;-), the last feature I'm missing is sliding caching, now the cache is absolute TTL, shall we add it?
https://github.com/daniel-hutao/spinlock
it seemed 5-10x faster so was wondering if it will faster
because it's on hotpath and most used feature currently, was checking cpu utilization and found...
it's great and it's fast but i'm not sure what's wrong with this, with my 12 core laptop, i can only push to use max 660% of cpu cores
meaning roughly 55% cpu usage using phuslu lru.
can you try out and see what i mean? i hope to push for 90% cpu utilization, u can comment out the cache.Set below and see the empty for loop with use around 99% cpu.
// +build linux
package main
/*
#define _GNU_SOURCE
#include <sched.h>
#include <pthread.h>
#include <string.h> // Include string.h for strerror
// Wrap CPU_ZERO and CPU_SET in functions to avoid macro expansion issues.
void my_CPU_ZERO(cpu_set_t *cs) { CPU_ZERO(cs); }
void my_CPU_SET(int cpu, cpu_set_t *cs) { CPU_SET(cpu, cs); }
*/
import "C"
import (
"syscall"
"fmt"
"log"
//"unsafe"
"time"
"runtime"
//"sync"
cxcputhread "github.com/cloudxaas/gocpu/thread"
phuslu "github.com/phuslu/lru"
)
var shardcount = func() int {
n := runtime.GOMAXPROCS(0) * 2
k := 1
for k < n {
k = k * 2
}
return k
}()
var (
cache = phuslu.NewLRUCache[string, string](32000000)
//cache = phuslu.NewLRUCache[string, string](32000000, phuslu.WithShards[string, string](uint32(shardcount)))
//cache = phuslu.NewLRUCache[string, string](32000,phuslu.WithShards(256))
)
/*
// setCPUAffinity sets the current thread's affinity to the specified CPU core.
func setCPUAffinity(cpu int) error {
var cpuset C.cpu_set_t
C.my_CPU_ZERO(&cpuset)
C.my_CPU_SET(C.int(cpu), &cpuset)
// pthread_setaffinity_np returns 0 on success, or an error number on failure.
// The previous implementation incorrectly interpreted the return value.
result := C.pthread_setaffinity_np(C.pthread_self(), C.size_t(unsafe.Sizeof(cpuset)), &cpuset)
if result != 0 {
// Convert the result (errno) to an error message using strerror.
return fmt.Errorf("error setting thread affinity: %s", C.GoString(C.strerror(result)))
}
return nil
}
*/
func main() {
numCores := runtime.NumCPU()
// runtime.GOMAXPROCS(numCores)
//var wg sync.WaitGroup
for i := 0; i < numCores; i++ {
// wg.Add(1)
go func(coreID int) {
// defer wg.Done()
runtime.LockOSThread() // Lock the goroutine to the current thread.
//err := setCPUAffinity(coreID)
err := cxcputhread.SetCPUAffinity(uint16(coreID)+1)
if err != nil {
fmt.Printf("Failed to set CPU affinity for core %d: %v\n", coreID, err)
return
}
// Your code here. This goroutine is now running with affinity set to a specific CPU core.
for {
//tid := C.pthread_self()
//for z:=0;z<10000000000;z++{
//}
for {
cache.Set("1231", "32141")
//cache.Get("1231")
}
tid := syscall.Gettid()
log.Printf("Thread pointer: %v == Core ID: %d", tid, coreID)
time.Sleep(time.Second)
}
// Simulate some work...
}(i)
}
// wg.Wait()
select {}
}
@phuslu pls pls pls implement a mmap option that can be shared across golang inter process.
can buy u a few coffees for this. possible to get it done?
maybe with an option to flush to mmap file at regular intervals or something. most importantly so can be used across different separate programs
Hi @phuslu, very interesting work, but some things in your repository raise questions for me.
Throughput benchmarks
b.SetParallelism(32)
is also unnecessary, since you run more goroutines than the number of available cores and the scheduler ends up spending a lot of CPU time switching between them.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.
})
Otter is also configured incorrectly, but it's not critical for now. But it will be soon!🙂
And now if you run the original benchmarks without runtime limit on 8 free perfomance cores with the command go test -run='^$' -cpu=8 -bench . -timeout=0 -benchmem
goos: darwin
goarch: arm64
pkg: github.com/maypok86/otter/bench
BenchmarkCloudflareGetSet-8 19329662 59.74 ns/op 16 B/op 1 allocs/op
BenchmarkEcacheGetSet-8 30167113 42.04 ns/op 2 B/op 0 allocs/op
BenchmarkLxzanGetSet-8 19655550 64.18 ns/op 0 B/op 0 allocs/op
BenchmarkFreelruGetSet-8 16393722 76.60 ns/op 0 B/op 0 allocs/op
BenchmarkRistrettoGetSet-8 13675732 91.52 ns/op 29 B/op 1 allocs/op
BenchmarkTheineGetSet-8 7859980 154.2 ns/op 0 B/op 0 allocs/op
BenchmarkOtterGetSet-8 19729608 70.02 ns/op 8 B/op 0 allocs/op
BenchmarkPhusluGetSet-8 23397532 52.11 ns/op 0 B/op 0 allocs/op
PASS
ok github.com/maypok86/otter/bench 17.342s
After other fixes we get the following
goos: darwin
goarch: arm64
pkg: github.com/maypok86/otter/bench
BenchmarkCloudflareGetSet-8 18841335 61.23 ns/op 16 B/op 1 allocs/op
BenchmarkEcacheGetSet-8 28833619 39.66 ns/op 2 B/op 0 allocs/op
BenchmarkLxzanGetSet-8 24512806 50.89 ns/op 0 B/op 0 allocs/op
BenchmarkFreelruGetSet-8 14905558 79.83 ns/op 0 B/op 0 allocs/op
BenchmarkRistrettoGetSet-8 22861460 52.04 ns/op 28 B/op 1 allocs/op
BenchmarkTheineGetSet-8 7006892 171.7 ns/op 0 B/op 0 allocs/op
BenchmarkOtterGetSet-8 30895054 47.92 ns/op 7 B/op 0 allocs/op
BenchmarkPhusluGetSet-8 26106796 47.16 ns/op 0 B/op 0 allocs/op
PASS
ok github.com/maypok86/otter/bench 17.371s
Here you should make sure that all implementations use the same number of shards, but I'm too lazy to do it anymore.
i := int(fastrandn(cachesize)); i <= threshold
. Do you really want to always write the same items and read the same items? Because that is exactly what you are doing.goos: darwin
goarch: arm64
pkg: github.com/maypok86/otter/perf
BenchmarkCache/Zipf_Theine_reads=100%,writes=0%-8 11608960 107.7 ns/op 9283558 ops/s 0 B/op 0 allocs/op
BenchmarkCache/Zipf_Ristretto_reads=100%,writes=0%-8 48676160 25.32 ns/op 39493565 ops/s 16 B/op 1 allocs/op
BenchmarkCache/Zipf_Phuslu_reads=100%,writes=0%-8 32948250 34.86 ns/op 28687550 ops/s 0 B/op 0 allocs/op
BenchmarkCache/Zipf_Otter_reads=100%,writes=0%-8 287808117 4.196 ns/op 238324807 ops/s 0 B/op 0 allocs/op
BenchmarkCache/Zipf_Theine_reads=75%,writes=25%-8 10141712 106.3 ns/op 9405869 ops/s 0 B/op 0 allocs/op
BenchmarkCache/Zipf_Ristretto_reads=75%,writes=25%-8 27029410 46.52 ns/op 21498335 ops/s 27 B/op 1 allocs/op
BenchmarkCache/Zipf_Phuslu_reads=75%,writes=25%-8 33284792 33.89 ns/op 29508730 ops/s 0 B/op 0 allocs/op
BenchmarkCache/Zipf_Otter_reads=75%,writes=25%-8 190370718 6.527 ns/op 153221398 ops/s 2 B/op 0 allocs/op
BenchmarkCache/Zipf_Theine_reads=50%,writes=50%-8 13183764 88.23 ns/op 11334143 ops/s 0 B/op 0 allocs/op
BenchmarkCache/Zipf_Ristretto_reads=50%,writes=50%-8 22789605 52.02 ns/op 19224501 ops/s 34 B/op 1 allocs/op
BenchmarkCache/Zipf_Phuslu_reads=50%,writes=50%-8 32335388 34.77 ns/op 28761246 ops/s 0 B/op 0 allocs/op
BenchmarkCache/Zipf_Otter_reads=50%,writes=50%-8 106489442 12.22 ns/op 81857267 ops/s 6 B/op 0 allocs/op
BenchmarkCache/Zipf_Theine_reads=25%,writes=75%-8 13120154 92.32 ns/op 10832209 ops/s 0 B/op 0 allocs/op
BenchmarkCache/Zipf_Ristretto_reads=25%,writes=75%-8 14231132 70.28 ns/op 14228276 ops/s 60 B/op 1 allocs/op
BenchmarkCache/Zipf_Phuslu_reads=25%,writes=75%-8 32800737 33.55 ns/op 29807980 ops/s 0 B/op 0 allocs/op
BenchmarkCache/Zipf_Otter_reads=25%,writes=75%-8 51792225 23.23 ns/op 43054563 ops/s 12 B/op 0 allocs/op
BenchmarkCache/Zipf_Theine_reads=0%,writes=100%-8 31050308 41.97 ns/op 23827702 ops/s 0 B/op 0 allocs/op
BenchmarkCache/Zipf_Ristretto_reads=0%,writes=100%-8 13311984 128.6 ns/op 7775102 ops/s 122 B/op 3 allocs/op
BenchmarkCache/Zipf_Phuslu_reads=0%,writes=100%-8 33116732 34.05 ns/op 29370837 ops/s 0 B/op 0 allocs/op
BenchmarkCache/Zipf_Otter_reads=0%,writes=100%-8 10602829 120.2 ns/op 8316114 ops/s 64 B/op 1 allocs/op
PASS
ok github.com/maypok86/otter/perf 30.320s
Memory usage benchmarks
So your implementation does show good memory utilization, but after fixing the implementation and benchmarks the gap will not be so big.
General questions
wanted to go extreme, how to make 192 cores faster? same pastebin info on server, doesnt really scale that well. can suggest how to make it multicore shard better?
某些场景下,需要做一个类似回调
as titled
func TestCollision_RuntimeHasher(t *testing.T) {
n := 20_000_000
sHasher := getRuntimeHasher[string]()
iHasher := getRuntimeHasher[int]()
seed := uintptr(fastrand64())
ms := make(map[uint32]string)
mi := make(map[uint32]int)
for i := 0; i < n; i++ {
s := strconv.Itoa(i)
hs := uint32(sHasher(noescape(unsafe.Pointer(&s)), seed))
hi := uint32(iHasher(noescape(unsafe.Pointer(&i)), seed))
if v, ok := ms[hs]; ok {
t.Fatalf("Collision(seed: %d): %s(%d) == %s(%d)", seed, v, hs, s, hs)
}
if v, ok := mi[hi]; ok {
t.Fatalf("Collision(seed: %d): %d(%d) == %d(%d)", seed, v, hi, i, hi)
}
ms[hs] = s
mi[hi] = i
}
i := 7
hi := uint32(iHasher(noescape(unsafe.Pointer(&i)), seed))
if _, ok := mi[hi]; !ok {
t.Fatalf("Number 7 should exist")
}
if len(ms) != len(mi) || len(ms) != n {
t.Fatalf("Hash count: %d, %d, %d", len(ms), len(mi), n)
}
}
func TestCollision_RuntimeHasher_Uint64(t *testing.T) {
n := 20_000_000
sHasher := getRuntimeHasher[string]()
iHasher := getRuntimeHasher[int]()
seed := uintptr(fastrand64())
ms := make(map[uint64]string)
mi := make(map[uint64]int)
for i := 0; i < n; i++ {
s := strconv.Itoa(i)
hs := uint64(sHasher(noescape(unsafe.Pointer(&s)), seed))
hi := uint64(iHasher(noescape(unsafe.Pointer(&i)), seed))
if v, ok := ms[hs]; ok {
t.Fatalf("Collision(seed: %d): %s(%d) == %s(%d)", seed, v, hs, s, hs)
}
if v, ok := mi[hi]; ok {
t.Fatalf("Collision(seed: %d): %d(%d) == %d(%d)", seed, v, hi, i, hi)
}
ms[hs] = s
mi[hi] = i
}
i := 7
hi := uint64(iHasher(noescape(unsafe.Pointer(&i)), seed))
if _, ok := mi[hi]; !ok {
t.Fatalf("Number 7 should exist")
}
if len(ms) != len(mi) || len(ms) != n {
t.Fatalf("Hash count: %d, %d, %d", len(ms), len(mi), n)
}
}
# go version
go version go1.22.1 linux/amd64
# go test -count=1 -run=TestCollision_RuntimeHasher_Uint64
PASS
ok github.com/phuslu/lru 9.913s
# go test -count=1 -run=TestCollision_RuntimeHasher
--- FAIL: TestCollision_RuntimeHasher (0.02s)
runtime_test.go:21: Collision(seed: 852041415638190986): 55718(684107357) == 75813(684107357)
FAIL
exit status 1
FAIL github.com/phuslu/lru 9.920s
After reading scalalang2/go-cache-benchmark#4 , especially @maypok86’s comment. I think below points should be clarify for fairness
i'll be honored to have your feedback on this lru i created for your comparison, remarks and comments.
hope to have your comments / input
https://github.com/cloudxaas/gocache/tree/main/lru/bytes
you can try on the hit / misses etc which i have no idea how you would do the benchmark comparison. thx in advance.
i created it coz most lru need to predefined a capacity but i would prefer to be limited by memory size set.
i've been following your lru for some time and your analysis is the most comprehensive.
possible to have an onevict call back feature for both the ttl and non ttl version?
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.