golang-lru icon indicating copy to clipboard operation
golang-lru copied to clipboard

Add expirable LRU implementation, with generics

Open paskal opened this issue 3 years ago • 3 comments

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.

paskal avatar Nov 14 '22 22:11 paskal

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.

jefferai avatar Nov 15 '22 12:11 jefferai

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.

paskal avatar Nov 17 '22 23:11 paskal

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?

paskal avatar Nov 18 '22 22:11 paskal