golang-lru
golang-lru copied to clipboard
Add expirable LRU implementation, with generics
My attempt at expirable cache implementation is similar to what was done in #41. I've tried to make the new cache as close as possible to the existing one regarding code style and behaviour.
The only difference I left in place is that size=0 on this type of cache means unlimited, which makes sense with the expirable cache.
Original work was done in lcw, but it turned out that I don't need it there, and I thought it would be nice to add my changes to upstream (this repo).
This PR is a recreation of #68, which was not merged. cc @jefferai @Dentrax for review.
How close is this to existing simplelru? I wonder if instead of having a totally separate type that shares a lot of code we could instead use an options pattern. This would keep the API compatible and allow passing in both values at the cache level and per-item overrides.
I'll check it this weekend. Adding the per-item expiration is not possible within the current interfaces, but overall, it should be possible to merge these two in the way it's written now.
I can integrate an expirable cache with simplelru.LRU as I did in this MR, but it becomes thread-safe which is a breaking change: it's impossible to make an expirable cache not thread-safe as then it will blow up in the runtime.
It's preferable to keep it as a separate thread-safe implementation as I did initially. Also, there would be no need for separate top-level package implementation like the current lru.New and lru.NewWithEvict, as it wouldn't be possible to prepare it differently to get a better performance like lru.Cache does now.
Benchmarks before and after simplelru.LRU becomes thread-safe on my MacBook Air M1 2020:
# before
Benchmark2Q_Freq-8 5232787 241.0 ns/op
Benchmark2Q_Rand-8 4382832 274.7 ns/op
BenchmarkARC_Freq-8 4548481 257.3 ns/op
BenchmarkARC_Rand-8 3548252 377.3 ns/op
BenchmarkLRU_Freq-8 8786037 130.8 ns/op
BenchmarkLRU_Rand-8 8940794 135.1 ns/op
# after, without removing double-locking from top-level packages, just to have some slow baseline
Benchmark2Q_Freq-8 3779685 316.4 ns/op (31% slower)
Benchmark2Q_Rand-8 3293716 364.5 ns/op (33% slower)
BenchmarkARC_Freq-8 3090226 420.7 ns/op (63% slower)
BenchmarkARC_Rand-8 2581510 464.6 ns/op (23% slower)
BenchmarkLRU_Freq-8 6536905 185.8 ns/op (42% slower)
BenchmarkLRU_Rand-8 6294895 191.0 ns/op (41% slower)
# after, with removing locks from top-level packages
Benchmark2Q_Freq-8 3938941 303.1 ns/op (26% slower)
Benchmark2Q_Rand-8 3275214 351.0 ns/op (28% slower)
BenchmarkARC_Freq-8 3049344 364.9 ns/op (42% slower)
BenchmarkARC_Rand-8 2709026 461.3 ns/op (22% slower)
BenchmarkLRU_Freq-8 7172146 166.3 ns/op (27% slower)
BenchmarkLRU_Rand-8 7000442 170.8 ns/op (26% slower)
I can wrap thread safety into expirable-cache-only code paths, but that would make simplelru.LRU a Frankenstein monster. My vote goes for having simplelru.Expirable a separate package and adding it without altering any top-level packages or simplelru.LRU.
@jefferai, what do you think?