Experiment with S3-FIFO eviction policy

Just saw this pass by on Hacker News: https://blog.jasony.me/system/cache/2023/08/01/s3fifo. Seems interesting. I wonder if it outperforms (not just in hit ratio, but also CPU time to calculate whether to evict) TinyLFU.

Let me give my opinion as well, since I've already gathered a lot of attempts at adopting it.

First, I tried to implement cache on hash table and lock free queues, as the authors wrote. I was annoyed, s3-fifo was indeed many times faster than lru cache implemented on hash table with global mutex, but still lost to ristretto and theine, which use bp-wrapper techniques. The profiler also showed that it was the eviction policy that was spending the bulk of the time. And I was only able to beat ristretto and theine after rewriting the implementation using bp-wrapper.

Actually, the big hit ratio jumps are caused by differences in the implementation of ghost queue. In the paper the authors suggested to keep storing items in the ghost queue (this is what redpanda does now and I decided to try to do it this way too). It seems that large big hit ratio jumps are caused by the fact that the size of the ghost queue is limited by the size of the main queue according to the algorithm. And with a larger cache capacity the capacity of the small queue increases => we store items longer => more items get into the main queue => the ghost queue also stores more items. In the end I came to the conclusion that storing small queue capacity + main queue capacity + ghost queue capacity = 0.1 capacity + 0.9 capacity + 0.9 capacity = 1.9 capacity of items is too cheater. So I decided to try storing hashes of items in ghost queue and evicting them in fifo order. And got frustrated 😔. Limiting the ghost queue to the size of the main queue works very badly on small cache sizes. The best I got tonight was limiting the ghost queue to the size of the entire cache with these results: r.txt. S3-FIFO (with minor modifications) actually outperformed or was about equal to W-TinyLFU on all traces except S3 and DS1 without much fluctuation.

In summary, I completely disagree about the scalability advantage of S3-FIFO over the other policies. In terms of hit ratio S3-FIFO can indeed often outperform W-TinyLFU, but feels bad on lfu-friendly traces. I think S3-FIFO has a right to live, especially if someone can make something more adaptive out of it, but the thought of dropping everything and rewriting everything on W-TinyLFU is getting more and more tempting 🙂.

Though to be honest, what was causing the hit ratio to go down in DS1 I still don't understand

Thanks @maypok86! It's always very interesting to hear an experience report.
I can't speak for any implementation other than my own, so it would be helpful if you could also compare hit rates against Caffeine in its simulator. Can you please report give that a try? I expect that static W-TinyLFU will lose on recency-biased traces as this was a known deficiency (shared with the S3-FIFO author in 2016 (https://github.com/1a1a11a/PyMimircache/issues/2)). The adaptive scheme has worked very well in all of the workloads that I have to test with where the policy is competitive with the leading algorithm. I don't expect it to always win, but for a general purpose cache I wanted it to robustly be near the top in any user workload. There are likely areas deserving improvement, but without data I have to wait until there is something to analyze and discuss around.
If comparing just on hit rates, the best alternative policy that I have seen is LIRS2 (code, paper, video). However LIRS (v1) is very complicated to implement correctly and debug, which is why I invested in improving TinyLFU as it seemed to be a more promising approach that I could reasonably maintain. In their v2 it is competitive except for my adaptive stress test. Of course in practice one has to consider all of the other characteristics, like metadata overhead and concurrency needs. There are a lot of design tradeoffs to consider when deciding on a policy as the best choice depends on the end goals.
I would have expected S3FIFO to support lock-free reads and blocking writes based on the description. Since the worst case eviction time is O(n), that time under the lock could become a concern. I'd probably just evict the next item after a threshold scan limit because I would be concerned of an unknown user workload hitting the worst case behavior (akin to GC thrashing causing long pauses). The BP-Wrapper approach amortizes those costs as it samples the read requests and the read throughput exceeds practical needs, so the time it steals helps keep the critical stays bounded and more predictable. It is more complex then using a Clock-based policy, but as an engineer this predictability in tail latencies is worth the effort when providing a library. My very limited (and likely outdated) understanding is that Go does not a very good suite of concurrent data structures and primitives, at least compared to Java's, so it can be much more difficult to implement efficient multi-threaded code. I don't recall the author implementing a thread-safe version so there might be oversights and I suppose those claims should be taken skeptically.

@maypok86 one thing i'm interested: did you compare the performance of xsync map and sharded map(throughput and gc)? from xsync author there is some overhead(https://github.com/puzpuzpuz/xsync/issues/102)? If xsync map always outperforms, I think i can also switch to that. Current Theine implementation is based on sharded map and I do some optimizations on it. Also as @ben-manes suggested, you can test hit rates using Caffeine's simulator, Theine's window queue and adaptive algorithm is a little different from Caffeine's

@Yiling-J I wanted to come with a separate issue about this (and most likely about theine benchmarks in general), but that would be a very long discussion, and it's much more important for me to finish work on otter right now. So I'll come with that, but much later 🙂 or else I was able to get my ideas to the author of memorycache, but it just took a huge amount of time.
@ben-manes LIRS2 looks very smart, I'll try to look in its direction, but I'm not sure it would be easy to maintain such a thing. I also tried running the caffeine simulator and the verdict is about the same: S3-FIFO was +- 2% on all traces used in otter except S3 and DS1 and otter showed about the same hit ratio. On DS1 (6000000 capacity) for example the loss was quite serious
╔══════════════════╤══════════╤════════════╤════════════╤════════════╤════════════╤════════════╤═══════════╗
║ Policy           │ Hit Rate │ Hits       │ Misses     │ Requests   │ Evictions  │ Steps      │ Time      ║
╠══════════════════╪══════════╪════════════╪════════════╪════════════╪════════════╪════════════╪═══════════╣
║ opt.Clairvoyant  │ 61.82 %  │ 27,019,597 │ 16,685,382 │ 43,704,979 │ 10,685,382 │            │ 1.080 min ║
╟──────────────────┼──────────┼────────────┼────────────┼────────────┼────────────┼────────────┼───────────╢
║ product.Caffeine │ 58.51 %  │ 25,570,957 │ 18,134,022 │ 43,704,979 │ 12,134,022 │            │ 39.94 s   ║
╟──────────────────┼──────────┼────────────┼────────────┼────────────┼────────────┼────────────┼───────────╢
║ two-queue.Qdlp   │ 46.65 %  │ 20,390,489 │ 23,314,490 │ 43,704,979 │ 17,314,490 │ 43,704,979 │ 35.36 s   ║
╚══════════════════╧══════════╧════════════╧════════════╧════════════╧════════════╧════════════╧═══════════╝

By the way, I was quite surprised by the difference in hit ratio between theine and caffeine on P3 (25000 capacity) 8% vs 14%.
Yes, perhaps the main problems with S3-FIFO are the inability to adapt and the possibility of an element being pushed out for O(n) and any attempts to fix this can lead to a worse hit ratio. And in the short term, I don't know what to do about it.
Go really still doesn't have efficient concurrent data structures, there are only implementations scattered across different libraries based on research papers or ports from other languages, but unfortunately most of them are barely supported. This is largely what motivated me to build an efficient cache library under such limited circumstances.

It looks like the ARC traces are no longer public due to an overzealous Dropbox security restriction, and unfortunately I did not use P3 regularly or recently enough to have it locally. I emailed the author to ask if they can be made available again, but if you have all of the downloads I might need you to publish them.

Hi all, I missed the fun party! This is the author of the S3-FIFO algorithm.
@maypok86 I just created an issue (https://github.com/maypok86/otter/issues/17), I believe there is a potential bug causing more objects to be evicted. I think this should fix the fluctuation problem.
However, It is true that S3-FIFO is still not as good as WTinyLFU on the DS1 and S3 traces.
I believe this partially comes from not being adaptive, and this is one direction we are working on. In general, **S3-FIFO is more suitable for web workloads (e.g., key-value cache, object cache), which follow skewed popularity with popularity decay. **
On block workloads, especially the old ones (like the ARC ones, which are more than twenty years old), S3-FIFO may not outperform W-TinyLFU. Similar results can also be found in our paper https://dl.acm.org/doi/10.1145/3600006.3613147
With that being said, I believe if

you need a very general cache replacement that can handle both block and web workloads
and don't mind the complexity
don't mind scalability
ok with extra metadata overhead
W-TinyLFU is still better than S3-FIFO, but if your workloads are mostly from web applications, then S3-FIFO should be
a better choice.

@1a1a11a I'm certainly not Ben, but it seems that bp-wrapper and a set of wait-free lossy buffers can give even greater scalability than lock-free queues. Articles on caffeine architecture: first and second

Cachelib mimics memcached's scheme of an exclusive lock (optionally try-lock) and a per-item time interval between policy updates (60s). That was good enough for there internal needs.
Caffeine uses dynamic striped, lock-free, lossy mpsc ring buffers to sample the request events. This differs from BP-Wrapper where as an isolated system with a dedicated cache (Postgres) they could use thread-local buffers as the memory usage and thread counts were known up front. That didn't make sense for a general purpose library embedded into an application which might have hundreds of instances, and each with different scalability needs.
The dynamic striping (number of read buffers) increases as contention is detected, mirroring how a scalable counter is implemented. The ring buffers capture the events cheaply, but if full then it is dropped. Since a cache is probabilistic and trying to detect a usage pattern for hot-cold entries, this lossy behavior does not meaningfully impact the hit rates. Whether one uses a lossy buffer, a time threshold, a fifo clock, etc. the insight is the same that a perfect history of the access order is not required to make good predictions.
The writes are also buffered using a bounded mpsc queue, which grows up to a threshold. This allows the cache to absorb most writes without threads contending on each other and batch the work to be replayed under the lock.  While in applications the write rate won't exceed the eviction rate, it can happen in a synthetic stress test. In those cases, back-pressure is applied to the buffering assists in batching the work to avoid context switches or lock contention. Generally writes are limited by the hash table's write throughput, as shown in those benchmarks.
The buffering of events allows us to schedule the draining as appropriate, either after a write or when a read buffer is full. That uses a simple state machine and a try-lock to coordinate, so the eviction policy does not suffer from lock contention. As BP-Wrapper describes itself, it "(almost) eliminates lock contention for any replacement algorithm without requiring any changes to the algorithm". This allows for more exploration of algorithms and data structures because the policies do not need to be thread-safe.
The benchmark that I use has a pre-populated cache with a zipf distribution for the access requests. That creates hot spots as some entries are much used much more often than others, just like a real cache would experience. A common mistake is a uniform policy which evenly spreads the contention, which would imply random replacement is the ideal policy. A skewed distribution means that locks suffer higher contention so it exacerbates that as a problems, while also benefiting contention-free implementations who can better utilize the cpu cache. In the real world, 50-70M reads/s is a good bar to reach to satisfy most users and the focus turns towards other areas like hit rate and features.

you need a very general cache replacement that can handle both block and web workloads

Yes

and don't mind the complexity

Yes. There are more pieces, each simple, which offer greater predictability. It is a tradeoff of a little more upfront work for fewer runtime surprises.

don't mind scalability

No. If we assume zero overhead (an unbounded map) then the measured per operation overhead is,
1.06 nanoseconds − 0.435 nanoseconds ≈ 0.625 nanoseconds
A Clock-based policy would fall in the middle, e.g. 0.7 ns. At these numbers the cache would not be the scalability bottleneck and it would be bounded by something else in the system.

ok with extra metadata overhead

This seems debatable and would require being more explicit about the calculations.
If we assume a traditional ghost history based on a doubly-linked list, closed hashing, and 64-bit machine then
List node (2 x 8 bytes) + Hash Entry (2 x 8 bytes) + key hash (4 bytes) = 36 bytes
This does not account for wasted space due to the load factor, object headers, etc that might be required.
If optimized for space, we can say the lower limit must be at least the 32-bit key hash (4 bytes). As in, we increase the time complexity for find / add / delete through an array of hashes. This seems to be an unlikely implementation choice and it will be higher in practice.
Caffeine uses a CountMinSketch sized at 8 bytes x ceilingPowerOfTwo(maximumSize) to hold 4-bit counters. This means that each entry adds 8-16 bytes. The paper discusses the doorkeeper optimization (adding a bloom filter) to reduce the size of the CountMinSketch. In my experiments this allowed the total memory overhead to be reduced by 50% without meaningfully impacting the hit rate. Thus, we are looking at a range between 4-16 bytes per entry for maintaining the history metadata.
The extra metadata overhead of maintaining the history seems to be, at best, equivalent. In practice it appears more likely that the frequency sketch will be a lower cost than a ghost list.
The resident per entry metadata overhead is less clear. W-TinyLFU describes only an algorithmic structure and the paper discusses the implementation choices made by Caffeine for the purpose of an evaluation. Ristretto decided to use sampled LFU with TinyLFU (doorkeeper + count-min) to reduce the metadata overhead, based on their analysis that their use-case was frequency-biased. It looks to be equivalent in the common implementations.

Ugh, I urgently need a reaction with popcorn on github. I'm probably not competent enough to argue about S3-FIFO and W-TinyLFU. Let me just say that if you only need find and add operations in a ghost queue, you can manage with about 18 additional bytes if the hash takes 8 bytes (if it takes 4 bytes, you need half as many bytes), but if you need to remove random items from it when changing the algorithm, things get bad

It's not so much an argument for or against, its that there are a lot of design choices where those details matter. I find it frustrating when sweeping generalizations are made that conveniently leave out important caveats or alternatives that a reader should be aware of because it may weaken the author's thesis. As an engineer, I appreciate having a richer picture because I need to balance tradeoffs, support the usage long-term, and cope with future requirements. This in conflict with an academic audience where goals are more short-term, e.g. peer review and that typically the work is discarded after publication. When the discussions are oriented towards an engineering audience then going into more breadth and depth over the facts matters so that the tradeoffs are understood. Usually that should ends up with a mixture of ideas, like how you applied insights from both BP-Wrapper and S3-FIFO, to discover the right design fit for the target environment.

Hi @ben-manes, Thanks for the super detailed explanations! A few comments and questions.
Comments
I like the TinyLFU design, and it shows the second best results in our evaluation (with a window size of 10%). I have no doubt calling it the state-of-the-art.

The figure above shows the evaluation of 6594 traces from 14 datasets (CDN, kv, and block).
Whether S3-FIFO is truly better than TinyLFU is hard to say; we have traces where S3-FIFO is better (especially for web workloads), and we also have traces where S3-FIFO is worse than TinyLFU (especially on block workloads).
These empirical results depend on workloads, and since we do not have a good model of workloads, I will not argue that S3-FIFO is strictly better than TinyLFU on the miss ratio.
metadata size
Regarding the metadata size, as a FIFO-based algorithm, if objects in the workload have a uniform size, we can implement the FIFO queues using ring buffers, and AFAIK, several production cache implementations (e.g., TigerBeetle, VMware) do use ring buffers.
For the ghost entries, we implemented them as part of a bucket-based hash table to take advantage of the over-provisioned space. They are cleared out during hash collisions. This means we used no more than 8 bytes (4-byte timestamp, and 4-byte fingerprint) per ghost entry. Since there are a similar number of ghost entries as the entries in the cache, we can estimate that the ghost entries add no more than 8 bytes per cached object. Our sensitivity analysis shows that we can reduce the number of ghost entries to 40% of the cached entries with almost no impact.
In summary, the ghost entry adds fewer than 4 bytes per object.
Scalability
I appreciate the efforts put into making Caffeine very scalable. However, the FIFO queues in S3-FIFO do not need any fancy technique to be scalable. All we need is atomics. I implemented it in C/C++, and everything is straightforward. However, I recently realized that it is non-trivial to have scalable and efficient implementations in other languages, e.g., Java and Rust. But the scalability in S3-FIFO is fundamental in the design.
Questions

1.06 nanoseconds − 0.435 nanoseconds ≈ 0.625 nanoseconds
Can you explain what the numbers are?

I still doubt how Caffeine can achieve 1000 MQPS on 16 threads. The numbers indicate that a hash look-up and recording the request on a ring buffer takes 16 ns. But CPU L1 access is ~1 ns, and DRAM access takes 100 ns. I simply don't understand how this is possible. This indicates that most data accesses (including the hash table) happen in the L1 cache.
A friend of mine implemented (not optimized) FIFO in C and benchmarked its scalability on a server with 72 cores (using a pre-populated Zipf request stream). However, she was only able to get ~100 MQPS.

Great comments @1a1a11a. I am very happy to see more caches moving beyond LRU, so a variety of simple and easy or more comprehensive solutions is a wonderful. There is a lot of low hanging fruit beyond the classics.
One of the differences to keep in mind is that TinyLFU papers are closer to design patterns than algorithms. They provide a structure and techniques, but only suggest implementation approaches. That means that implementations can differ, e.g. cachelib uses 32-bit counters in their CountMinSketch, whereas Caffeine's is 4-bit. The variety of choices can impact the metadata overhead, hit rate, throughput, and concurrency support.
Metadata
I don't believe that the ghost entry's cost of the hash table and FIFO queue can be dismissed to say it only takes 8-bytes (timestamp + fingerprint). A hash table typically has a load factor around 75%, and may be higher for a cache since the maximum capacity is known. That leaves less space for the over provisioned table size, but also adds at least a pointer for the chained entry and maybe more (e.g. hash is cached, uses a doubly linked list, etc). The cost of the FIFO is should also be accounted for as part of the ghost's overhead. A reasonable estimate is that the FIFO holds a 4-byte fingerprint, the hash table adds only 8 bytes for the chain pointer, the table over provisioning is dismissed for simplicity, the entry costs 8 bytes for the key and timestamp, and ghost region ranges from 0.4x to 0.9x of total capacity. That is then an incremental cost of 8 to 18 bytes of metadata overhead for each additional cache entry. That's great and not much higher than the 4-16 bytes per entry for TinyLFU.
Scalability

This indicates that most data accesses (including the hash table) happen in the L1 cache.

Yes, that is the ideal because this micro-benchmark tries to isolate the costs to only measuring the cache in a concurrent workload.  It would expose costs such as by hardware cache coherence, data dependencies, poor branch prediction, saturates the logic units (there are multiple ALUs for every FP unit), SIMD, wait on the store buffer, blocking and context switches, system calls, etc.

The numbers indicate that a hash look-up and recording the request on a ring buffer takes 16 ns. But CPU L1 access is ~1 ns, and DRAM access takes 100 ns.

A modern cpu core is superscalar (e.g. 6 instructions) and fuses multiple operations into a bundle (e.g. 8 micro-ops). If we avoid data dependencies and use simple integer instructions then we'll see higher cpu utilization as it much more work than a single instruction per cycle. For example that could mean at best a cpu core can perform is 48 instructions per cycle, which at 4GHz means 192 instructions per nanosecond; or 2688 instructions per nanoseconds across all 14 cores.
The benchmark's own overhead is thread-local work for an index increment, array lookup, loop, and operation counter. A read performs a hash table lookup, a few liveliness validation checks, hashing, and maybe an addition to a ring buffer. The hashes are very inexpensive bitwise (1 cycle) and multiplication (6 cycle) operations. Since the ring buffers for recording a read are lossy and drained by a single thread, they fill up very quickly and are usually skipped. There is no blocking on a lock, no CAS, no volatile writes, etc. when maximizing the load so it stays close to hash table's performance. If we introduce a cost like data dependencies (such as by using a random number generator to select the next key) we'd see this fall sharply as we no longer allow the cpu/compiler to maximize its potential.
I refer to BP-Wrapper as request sampling because we the sample rate as load increases and it sheds load (the policy maintenance penalty) by not recording the read in the ring buffer. The zipf popular items will reenter the buffer at a higher frequency, so when the policy drains them it still gets to observe the heavy hitters and the policy can make a reasonable predication without severely penalizing the application requests.

A friend of mine implemented (not optimized) FIFO in C and benchmarked its scalability on a server with 72 cores (using a pre-populated Zipf request stream). However, she was only able to get ~100 MQPS.

There are many easy mistakes that could severely diminish throughput.

Confirm that the key distribution is pre-generated. If not, you are paying not only the cost of randomizing but also creating data dependencies, which severely limits the instruction parallelism. The random seed is often modified under a lock. The benchmark's own cost should be scrutinized.
Is all of the mutable state (effectively) thread local? If you are reading and updating shared state, like incrementing statistic counters, then that introduces coherence costs and data dependencies.
Is shared mutable state padded to avoid false sharing? Any write barrier (CAS, volatile update) should be inspected to avoid contention on the cache line. The field may be isolated to the thread, but updating a shared cache line can have a severe penalty.
Does the workload fit within the cpu cache? A large distribution would include misses to main memory, thereby creating cpu stalls, and may increase the number of collisions observed during the hash table's lookup.
Is the workload only reads with a 100% hit rate?
Is the hash function and other math performed efficiently? An integer modulus or division (20-80 cycles) is much more expensive than a add/sub/bitwise (1 cycle) or multiplication (~6 cycles), and FP is even more (30-150). Often power-of-two sizing is used to replace a modulus with a mask, e.g. hash % table.length becomes hash & (table.length - 1). A 32-bit hash may be cheaper than 64-bit by packing more work per hardware logic unit. An expensive algorithm like SipHash might be replaced by a very simplistic hash by using red-black tree bins to mitigate collisions.
What is the cost compared to an unbounded hash table? An immutable map vs a concurrent one? Do reads lock-free (e.g. do they require a read-lock)? Also compare against a modern hash table, like Google's Abseil and Facebook's Folly. Even on decade old hardware, over 10M reads/s per core was observed for concurrent hash tables (6 core benchmark, 2 core and up but note low perf cores used at high cpu counts). A modern 2022 benchmark observed 100M/s on 2 cores.
Are there any hard to predict branches, system calls (e.g. clock read), locks, memory fences, problematic data dependencies (e.g. disallow loop unrollng), etc. on the critical path? Has the code been profiled?
Does performance scale linearly or super-linear as threads/cores are added? It should until saturation.

I tried to update the otter benchmarks today and tried to replicate the caffeine benchmarks and there seems to be a reason for these numbers in the caffeine benchmark results.
Caffeine uses 2 << 14 = 32768 capacity (cache pre-filled) and scrambled zipfian from yahoo.
And on such a benchmark I got fantastic speed from otter.
goos: darwin
goarch: arm64
pkg: github.com/maypok86/benchmarks/perf
BenchmarkCache/Zipf_Theine_reads=75%,writes=25%-8               11247033               102.2 ns/op         9780838 ops/s               0 B/op          0 allocs/op
BenchmarkCache/Zipf_Ristretto_reads=75%,writes=25%-8            24089149                44.99 ns/op       22225554 ops/s              27 B/op          1 allocs/op
BenchmarkCache/Zipf_Bigcache_reads=75%,writes=25%-8             18038624                61.85 ns/op       16167099 ops/s             108 B/op          1 allocs/op
BenchmarkCache/Zipf_Fastcache_reads=75%,writes=25%-8            21097772                53.16 ns/op       18811359 ops/s              43 B/op          0 allocs/op
BenchmarkCache/Zipf_Otter_reads=75%,writes=25%-8                240418147                5.085 ns/op     196646932 ops/s               0 B/op          0 allocs/op
PASS
ok      github.com/maypok86/benchmarks/perf     6.965s

But if I increase cache capacity to 2 << 20 = 2097152 (used in ristretto benchmarks), the results are already decently worse and I suspect it will be the same with caffeine.
goos: darwin
goarch: arm64
pkg: github.com/maypok86/benchmarks/perf
BenchmarkCache/Zipf_Theine_reads=75%,writes=25%-8                8520392               127.9 ns/op         7819737 ops/s               0 B/op          0 allocs/op
BenchmarkCache/Zipf_Ristretto_reads=75%,writes=25%-8            19632382                56.17 ns/op       17804392 ops/s              27 B/op          1 allocs/op
BenchmarkCache/Zipf_Bigcache_reads=75%,writes=25%-8             13077836                99.85 ns/op       10015271 ops/s              86 B/op          1 allocs/op
BenchmarkCache/Zipf_Fastcache_reads=75%,writes=25%-8            15576997                75.88 ns/op       13178764 ops/s              41 B/op          0 allocs/op
BenchmarkCache/Zipf_Otter_reads=75%,writes=25%-8                67229958                16.86 ns/op       59302586 ops/s               0 B/op          0 allocs/op
PASS
ok      github.com/maypok86/benchmarks/perf     21.023s

I also don't understand why benchmarks are configured so that elements are not evicted at all. It doesn't seem to be very representative of real world loads.

Of course, I can attach such pictures in the readme, but I have big questions about the honesty of such benchmarks.

I also don't understand why benchmarks are configured so that elements are not evicted at all. It doesn't seem to be very representative of real world loads.

This is because it is easy to write an incorrect benchmark or to misunderstand its results. Therefore that benchmark is very narrow to answer a very specific question. In this case that is if the cache is a fundamental scalability bottleneck that may harm the application's performance. A thorough analysis should ask multiple, narrow, verifiable questions that each have their own micro-benchmark for understanding the system. In no way is that single benchmark enough, but it does answer a common question and directly counters the assertion against LRU. That question (if the cache read is a bottleneck) and its answer does not mean that being infinitely faster is important; there is a point of diminishing returns and answer is "yes or no" not "by how much".
Caffeine does include an eviction benchmark to measure that worst case throughput. Otherwise the questions became much murkier and easy to misinterpret, so they were written as needed and not included in the repository. The concern is that if included that might imply that they are valid and trustworthy comparisons rather than exploratory throwaways during development. You should write more benchmarks for analyzing your cache, but you should also be conservative publicly to avoid others misrepresenting the results.
An example of trying to follow your logic and making an easy mistake was in RedHat's benchmark. It is much faster to perform a cache miss than a cache hit because there is no additional work for maintaining the eviction policy. That penalized caches with higher hit rates as an increased throughput was observed when there are more misses. They didn't realize this and misunderstood their measurements, so during a rewrite their newer implementation suffered very high contention on a cache hit and the lower hit rate made it appear to be an improvement. Your question is good and worth exploring, but be very careful due to how trivially easy it is to make an invalid comparison or an honest misunderstanding of the results.
A few related talks that I found useful,

Performance Anxiety
Benchmarking for Good (or skip to a real mistake)
(The Art of) (Java) Benchmarking
A Crash Course in Modern Hardware

Interesting idea about the benchmark separation.
Let me share my yesterday's adventures (and conclusion). I think it might be useful to someone.
I ran the benchmarks in the same configuration as caffeine on two versions of otter:

Used spinlock to synchronize the key-value pair (to get the value atomically too) and the results came out as follows:

goos: darwin
goarch: arm64
pkg: github.com/maypok86/otter/perf
BenchmarkCache/Zipf_Theine_reads=75%,writes=25%-8               11870023               100.4 ns/op         9960592 ops/s               0 B/op          0 allocs/op
BenchmarkCache/Zipf_Ristretto_reads=75%,writes=25%-8            28630963                43.99 ns/op       22732079 ops/s              26 B/op          1 allocs/op
BenchmarkCache/Zipf_Bigcache_reads=75%,writes=25%-8             17515051                60.59 ns/op       16503227 ops/s             106 B/op          1 allocs/op
BenchmarkCache/Zipf_Fastcache_reads=75%,writes=25%-8            21355162                53.30 ns/op       18761140 ops/s              43 B/op          0 allocs/op
BenchmarkCache/Zipf_Otter_reads=75%,writes=25%-8                86992596                14.91 ns/op       67050184 ops/s               0 B/op          0 allocs/op
PASS
ok      github.com/maypok86/otter/perf  7.752s

used atomic.Pointer on the value, in fact that's what caffeine does.

type Node[K comparable, V any] struct {
	key        K
	value      atomic.Pointer[V]
	...
}

And the results were much better (you've already seen them):
goos: darwin
goarch: arm64
pkg: github.com/maypok86/otter/perf
BenchmarkCache/Zipf_Theine_reads=75%,writes=25%-8                9978348               115.1 ns/op         8690168 ops/s               0 B/op          0 allocs/op
BenchmarkCache/Zipf_Ristretto_reads=75%,writes=25%-8            25813344                48.54 ns/op       20603083 ops/s              27 B/op          1 allocs/op
BenchmarkCache/Zipf_Bigcache_reads=75%,writes=25%-8             18204561                64.09 ns/op       15602573 ops/s             113 B/op          1 allocs/op
BenchmarkCache/Zipf_Fastcache_reads=75%,writes=25%-8            19909934                55.59 ns/op       17987431 ops/s              43 B/op          0 allocs/op
BenchmarkCache/Zipf_Otter_reads=75%,writes=25%-8                210819736                5.589 ns/op     178916881 ops/s               1 B/op          0 allocs/op
PASS
ok      github.com/maypok86/otter/perf  7.292s

So it looks like no one in go can come close to the throughput of caffeine without additional memory overhead and pressure on gc. Otter of course already uses a set of tricks to reduce gc pressure and use extra memory, but such changes actually crosses them all out.

We are running on different machines, so you would have to see what Caffeine's numbers were on yours. My latest numbers came from a brand new M3 Max macbook, where I bumped the benchmark from 8 to 16 threads. The three workload types would also be nice to see, and a comparison to the unbounded hash map as a control group. Java's ConcurrentHashMap is very fast so that might be what gives caffeine an advantage if it wins on your hardware.

I’m unsure why you’d spin lock on read, but if important then you might find a stamped lock useful. Basically use a version counter so reads verify their stamp to ensure a consistent read, instead of blocking each other by acquiring exclusive access.

Oh, and your spinlock is TAS whereas using TTAS is usually preferred.

The problem isn't even so much the numbers compared to caffeine, but the fact that spinlock eats up a lot of time on such benchmarks (CLHT is the hash table that otter uses).
goos: darwin
goarch: arm64
pkg: github.com/maypok86/otter/perf
BenchmarkCache/Zipf_Theine_reads=75%,writes=25%-8               10268367               102.8 ns/op         9725720 ops/s               0 B/op          0 allocs/op
BenchmarkCache/Zipf_Ristretto_reads=75%,writes=25%-8            23940507                45.51 ns/op       21972560 ops/s              27 B/op          1 allocs/op
BenchmarkCache/Zipf_Bigcache_reads=75%,writes=25%-8             19561802                61.60 ns/op       16234376 ops/s             111 B/op          1 allocs/op
BenchmarkCache/Zipf_Fastcache_reads=75%,writes=25%-8            20381444                53.41 ns/op       18721946 ops/s              43 B/op          0 allocs/op
BenchmarkCache/Zipf_CLHT_reads=75%,writes=25%-8                 280790150                4.242 ns/op     235737370 ops/s               1 B/op          0 allocs/op
BenchmarkCache/Zipf_Otter_reads=75%,writes=25%-8                194110579                5.995 ns/op     166793393 ops/s               1 B/op          0 allocs/op
PASS
ok      github.com/maypok86/otter/perf  9.498s

With the spinlock, the otter is about three times slower

spinlock eats up a lot of time on such benchmarks

I think if you use a stamped spinlock then the optimistic read will usually succeed and the spinlock overhead will mostly disappear.

@ben-manes Why am I using spinlock?
To update asynchronously the received Entry from the hash table when calling Set, since there is no synchronized or anything like that in golang. And I was even able to save 4 bytes for this. Also, since it makes it necessary to atomically do getValue when calling Get on the cache instance I use the same spinlock.
There is a problem with StambledLock - it takes much more memory, judging by the java implementation.

And TTAS spinlock doesn't seem to save the situation much either
func (sl *SpinLock) Lock() {
	acquired := false
	for !acquired {
		if atomic.LoadUint32((*uint32)(sl)) == 0 {
			acquired = atomic.CompareAndSwapUint32((*uint32)(sl), 0, 1)
		}
	}
}

goos: darwin
goarch: arm64
pkg: github.com/maypok86/otter/perf
BenchmarkCache/Zipf_Theine_reads=75%,writes=25%-8               10992760               104.5 ns/op         9566058 ops/s               0 B/op          0 allocs/op
BenchmarkCache/Zipf_Ristretto_reads=75%,writes=25%-8            26589556                46.96 ns/op       21294953 ops/s              28 B/op          1 allocs/op
BenchmarkCache/Zipf_Bigcache_reads=75%,writes=25%-8             17358097                62.27 ns/op       16059811 ops/s             107 B/op          1 allocs/op
BenchmarkCache/Zipf_Fastcache_reads=75%,writes=25%-8            20358709                54.12 ns/op       18478836 ops/s              43 B/op          0 allocs/op
BenchmarkCache/Zipf_CLHT_reads=75%,writes=25%-8                 267684039                4.182 ns/op     239110129 ops/s               1 B/op          0 allocs/op
BenchmarkCache/Zipf_Otter_reads=75%,writes=25%-8                76844876                14.15 ns/op       70652962 ops/s               0 B/op          0 allocs/op
PASS
ok      github.com/maypok86/otter/perf  7.847s

There is a problem with StambledLock - it takes much more memory, judging by the java implementation.

yeah, they tend to write more bullet proof libs due to many Java devs not understanding concurrency well. I thought you might be able to borrow some of the core ideas instead of the exact implementation. Since you don't use this to support blocking you can use a simpler sequence lock. That's basically a counter where even is read mode and odd is write mode, a reader waits until it obtains a read mode stamp, reads the data, and validates that the stamp was unchanged. That lets you perform an optimistic read without blocking other readers, and works well when there is a low write rate (else better to preemption instead of busy wait). This wouldn't require any more space than your current one, so a cheap but effective trick.

The TTAS is meant to avoid the CAS in the busy loop so that you only perform the CAS if observed to be unlocked. That way you loop on the cache line without memory bus traffic, wait for the cache coherency invalidation, and then race to acquire. Otherwise you are always penalized by the CAS trying to make a state change. Here's a version generated by chatgpt.
func (sl *SpinLock) Lock() {
	for {
		// Test (check if the lock is currently held)
		for atomic.LoadUint32((*uint32)(sl)) == 1 {
			// Spin while the lock is held
			// This is the "Test" part of TTAS
		}

		// Now attempt to acquire the lock
		if atomic.CompareAndSwapUint32((*uint32)(sl), 0, 1) {
			// Successfully acquired the lock
			return
		}

		// The lock was not acquired, retry the whole process
		// This is the "Test" part of TTAS (retry if the lock is taken while attempting to acquire)
	}
}

Here is a version using a sequence lock and TTAS. It took some fighting with chatgpt so it may be wrong, but gets the idea across I hope.
seqlock.go
package main

import (
	"fmt"
	"sync"
	"sync/atomic"
	"time"
)

type SequenceSpinLock struct {
	counter int32
}

// OptimisticRead spins until the counter is even and then returns the counter value.
func (ssl *SequenceSpinLock) OptimisticRead() int32 {
	for {
		counter := atomic.LoadInt32(&ssl.counter)
		if counter&1 == 0 {
			return counter
		}
		// Spin while the lock is held by a writer
		// This is the "Test" part of optimistic read
		// You can use a more efficient strategy like backoff
	}
}

// ValidateRead returns true if the counter matches the given stamp.
func (ssl *SequenceSpinLock) ValidateRead(stamp int32) bool {
	return atomic.LoadInt32(&ssl.counter) == stamp
}

// Lock spins until the counter is in read mode (even).
// Then it tries to CAS to the next odd value to acquire the lock.
func (ssl *SequenceSpinLock) Lock() {
	for {
		// Wait until the lock is not held by a writer (counter is even)
		counter := atomic.LoadInt32(&ssl.counter)
		for counter&1 != 0 {
			// Spin while the lock is held by a writer
			// This is the "Test" part of Lock
			// You can use a more efficient strategy like backoff
			counter = atomic.LoadInt32(&ssl.counter)
		}

		// Now attempt to acquire the lock
		newCounter := counter + 1
		if atomic.CompareAndSwapInt32(&ssl.counter, counter, newCounter) {
			// Successfully acquired the lock
			return
		}

		// The lock was not acquired, retry the whole process
		// This is the "Test" part of Lock (retry if the lock is taken while attempting to acquire)
	}
}

// Unlock increments the counter to make it even, therefore available in read mode.
func (ssl *SequenceSpinLock) Unlock() {
	// Release the lock by incrementing the counter
	atomic.AddInt32(&ssl.counter, 1)
}

func main() {
	var wg sync.WaitGroup
	var ssl SequenceSpinLock

	// Writer
	wg.Add(1)
	go func() {
		defer wg.Done()

		ssl.Lock()
		fmt.Println("Writer: Acquired lock")
		time.Sleep(time.Millisecond * 100)
		ssl.Unlock()
		fmt.Println("Writer: Released lock")
	}()

	// Readers
	for i := 0; i < 5; i++ {
		wg.Add(1)
		go func(id int) {
			defer wg.Done()

			stamp := ssl.OptimisticRead()
			fmt.Printf("Reader %d: Successfully performed optimistic read with stamp %d\n", id, stamp)

			// Simulate read operation

			// Validate the read
			if ssl.ValidateRead(stamp) {
				fmt.Printf("Reader %d: Validation successful\n", id)
			} else {
				fmt.Printf("Reader %d: Validation failed (lock held by writer)\n", id)
			}
		}(i)
	}

	wg.Wait()
}

Seqlock could help, but maybe I don't understand something, but seqlock allows both readers and writer to enter a critical section, which sounds like data race. I can already see the faces of users who get warning from a third-party library when running tests with -race flag or trying to debug. I guess I could limit the implementation with seqlock with a build flag and a caption, "With this flag you get x3 throughput and data race as a gift".

The intent is that while you get a race while copying the data being read, you will then validate that it was a consistent or throw away that work and try again. That is why you pair the OptimisticRead with the ValidateRead(stamp) methods, wrapped by a retry loop until successful. Once validated then you know that the data was safely copied, so if the data is small like pointer reads then this is very inexpensive. It does not ensure exclusivity like a read-write lock (aka shared-exclusive lock), so you cannot perform mutations that would cause the readers to fail in their inconsistent read. That makes this optimistic concurrency more niche, but offers a very fast solution when a good fit.

I still don’t understand why you would lock on reads instead of only on writes. The value can be read by an atomic load while writing is made exclusive. You could then use lock striping instead of per entry locks by hashing to an array of mutexes. I thought Go copied the Java Memory Model so you have the guarantees needed to do this safely.

The intent is that while you get a race while copying the data being read, you will then validate that it was a consistent or throw away that work and try again.

This is clear, but the problem is that go data race detector (as far as I remember) triggers on any simultaneous read/write of one variable. And this may lead to the fact that users of such a library with seqlock will constantly get warnings when debugging or running tests with this detector.

The value can be read by an atomic load while writing is made exclusive.

Oh, if only it were that easy. The problem is that in Java all values are references and, of course, you can easily use atomics on them.
But that's not the case in go. Values are copies of the original passed value (if an object contains pointers, such as strings, then this structure is copied, not the bytes in the string). And actually in go there are three ways to use atomic operations on such types.

atomic.Value: actually makes the object a reference, since it is stored as an interface. This adds an additional 16 bytes to the memory used, since the interface in go is a pair of two pointers: to the type and to the value.
atomic.Pointer: very similar to the previous point, as it stores a pointer to a value and therefore requires 8 additional bytes and also puts an additional pressure on gc.
Some other kind of synchronization: mutexes, channels, etc.

Oh, thanks for that insight! That makes a lot of sense and certainly confused me in the past as to the over use of read/write locks in Go. Java has minimal tearing as value types are still in development.
I guess then maybe try the TTAS spinlock that I provided in case it helps, while keeping it exclusive.

In general, TTAS doesn't help much either, but it has more stable results than TAS, so I'll switch to it and accept defeat, because the array of smart mutexes didn't help either. And it looks like nothing except atomics will help, because the amount of work under locks is too small.
goos: darwin
goarch: arm64
pkg: github.com/maypok86/otter/perf
BenchmarkCache/Zipf_Theine_reads=75%,writes=25%-8                8573086               131.4 ns/op         7610200 ops/s               0 B/op          0 allocs/op
BenchmarkCache/Zipf_Ristretto_reads=75%,writes=25%-8            21819586                48.17 ns/op       20759453 ops/s              28 B/op          1 allocs/op
BenchmarkCache/Zipf_Bigcache_reads=75%,writes=25%-8             15848017                70.14 ns/op       14258177 ops/s             102 B/op          1 allocs/op
BenchmarkCache/Zipf_Fastcache_reads=75%,writes=25%-8            19319406                55.37 ns/op       18061154 ops/s              43 B/op          0 allocs/op
BenchmarkCache/Zipf_CLHT_reads=75%,writes=25%-8                 286224150                4.246 ns/op     235541757 ops/s               1 B/op          0 allocs/op
BenchmarkCache/Zipf_Otter_reads=75%,writes=25%-8                86898153                12.95 ns/op       77209914 ops/s               0 B/op          0 allocs/op
PASS
ok      github.com/maypok86/otter/perf  9.003s

not sure if this helps, but you could try to suppress those warnings in a hacky way.

As of my last knowledge update in January 2022, there isn't a built-in annotation or directive in the Go programming language specifically designed to instruct the race detector to ignore a particular section of code. The race detector operates at runtime and analyzes the concurrent execution of goroutines, so it doesn't have a mechanism to selectively ignore parts of the code.
However, you can achieve a similar effect by using the // +build directive along with build tags. For example, you could conditionally exclude certain files or sections of code from the build when you want to run the race detector.
Here's an example:
// +build !race

package main

func main() {
    // Your code here
}

In this example, the code will be excluded from the build when the race build tag is present. So when you want to run the race detector, you can build your program with the -race flag:
go build -race

This way, you can isolate the parts of your code where race conditions are not relevant and exclude them from the race detector checks. Keep in mind that this approach may not be perfect, and you should carefully test and verify the absence of race conditions in critical sections of your code. Always strive to design your concurrent code to be race-free whenever possible.

Wow, that's quite a boost from seqlock...
goos: darwin
goarch: arm64
pkg: github.com/maypok86/otter/perf
BenchmarkCache/Zipf_Theine_reads=75%,writes=25%-8               10644934               110.2 ns/op         9075592 ops/s               0 B/op          0 allocs/op
BenchmarkCache/Zipf_Ristretto_reads=75%,writes=25%-8            23894643                46.67 ns/op       21426799 ops/s              27 B/op          1 allocs/op
BenchmarkCache/Zipf_Bigcache_reads=75%,writes=25%-8             17937655                60.45 ns/op       16543840 ops/s             111 B/op          1 allocs/op
BenchmarkCache/Zipf_Fastcache_reads=75%,writes=25%-8            20935054                53.07 ns/op       18842569 ops/s              43 B/op          0 allocs/op
BenchmarkCache/Zipf_CLHT_reads=75%,writes=25%-8                 278835458                4.245 ns/op     235593697 ops/s               1 B/op          0 allocs/op
BenchmarkCache/Zipf_Otter_reads=75%,writes=25%-8                202141250                5.572 ns/op     179468488 ops/s               0 B/op          0 allocs/op
PASS
ok      github.com/maypok86/otter/perf  8.537s

However, you can achieve a similar effect by using the // +build directive along with build tags. For example, you could conditionally exclude certain files or sections of code from the build when you want to run the race detector.

I thought about it, but I'll probably close it with an additional build flag, as I think most applications should be fine with 50-60 million qps throughput, and if it's really not enough and it's a cache issue, then the user can unlock a new level of performance.

@maypok86
Correct me if I am wrong, the problem you are trying to solve is to avoid updating the value being read.
Can you just create a new node for the new value, update the hash table, and put the old value onto the deletion buffer? In this way, you do not need to lock the reads.
But you would need a reference count to make sure the old node is not freed before it finishes reading.

@1a1a11a yes, but when you create an additional node, you will also have to update the eviction policy, and that costs a lot more CPU time. Also I have a suspicion that allocation + interaction with one of the limited number of deletion buffers may rather slow down write operations.

@maypok86 You will need to insert the new node, but you don't need to update the eviction policy because the old node will be reclaimed soon. Do I miss something here? Or is your concern about the temporary memory usage increase? If so, you could reduce the cache size by the maximum number of concurrent writes (e.g., 16 or 64). But in my very limited understanding, the temporary memory usage increase should not be an issue due to the GC.
Regarding slowdown, it well depends on your use case; if the workload is read-heavy (>80% read), removing the lock at read would improve the performance. But if your workload is update-heavy, you are right; we may experience a slowdown. There are write-heavy workloads in the wild, but I haven't seen any update-heavy workloads.

@1a1a11a but the eviction policy must also store a reference to the node and without a direct delete command from the eviction policy GC will not delete it.

Hi @maypok86, Thank you for the reply! Can you elaborate on your point?

Hi @1a1a11a, I suspect that in proposing such a solution, you are assuming that the small and main queues simply store keys in ring buffers (otherwise I don't see how this could work at all). But there is a set of problems here at once:

otter supports cost-based eviction, because of which the size of the ring buffers cannot be known initially. Okay, this can be solved by recreating a buffer with a larger size and moving the keys.
Here the second problem immediately appears. It may be necessary to delete random items from the ring buffer (because of the expiration policy or because of a direct delete call). Okay, we can maintain the indexes to the ring buffer somewhere (I understand that in some hash table, because due to the solution with the creation of a new node we can't store the index to the buffer in the node). And here's the question: how much memory will be consumed in the end? It seems like quite a lot and the eviction policy will slow down because of hash tables. Also if we do lock-free policy like in the original article, it sounds like a huge hemorrhoid.

Hi @maypok86, I am not assuming a ring-buffer implementation. I have read your repo, and the linked-list implementation is reasonable. I might miss some critical background because I still do not understand why an update would affect eviction. Can you help me better understand the missing piece? Here is my mental model.
Upon an update request,

create a new node (instead of updating the old value) and push the new node to the end of the queue, like writing a new object. All these can be done without locking because the old value is not updated.
update the hash table pointing to the new value so that new read requests will find the new value.
put the old node onto a deletion buffer to be reclaimed.

This is effectively an RCU operation and has been widely used in many systems.
Let me know if I misunderstood some parts that may make this not possible. If you are interested, I am happy to have a call.

@1a1a11a In my world, it breaks the eviction policy here's why:

Each node stores pointers to the previous and next nodes in the eviction policy.
When you create a new node you copy the node completely, there is nothing wrong with that. The new node will reference the correct nodes. But what about the previous and next node? They keep referencing the old node and don't know anything about the new one, since it's a doubly linked list. And how to fix this effectively is not very clear.

I see the problem now.
In my mental model, update = insert + delete, and the updated note is placed at the head of the queue, but you prefer keeping the node in the old position in the queue when updating the value.
What would be the problem if the new node (with an updated value) is placed at the head of the queue (with prev pointing to null, and next pointing to the old head)?

@1a1a11a Yes, you can do that (moreover, otter did it in a similar way for some time), but such actions would require locking of eviction policy + time to select removal buffer and cas operation to insert there + allocation and time for gc (also insert into hash table also requires locking). And this is very similar to the time of a regular insert, although you could do away with a lock per node. This is where I have to seriously think about what really matters and how it's best. I would have chosen seqlock without a doubt if it weren't for the race :(.

And as far as I remember, the insertion speed did drop quite a lot to be noticeable already on a load of 75% reads and 25% writes.

@maypok86 True, you would have to pay for the cost of inserting into removal buffer + hash table + gc if you do this, but if not, you need to lock on each get request as your current implementation does. It all boils down to what traffic you would expect --- ready-heavy or update-heavy.
Opportunistic concurrency control (occ), e.g., seqlock, is very effective under low contention. If you expect an update-heavy workload, especially multiple updates on a few hot keys, occ is much slower because of repeated retries. So I don't think it is a good solution if you expect many updates.
Locking the eviction policy is not really needed if you use S3-FIFO or other FIFO-based algorithms (e.g., FIFO-Reinsertion or TinyLFU + FIFO-Reinsertion). In general, FIFO-based algorithms can be implemented with locking. I wrote a blog recently https://blog.jasony.me/system/cache/2023/12/28/fifo
I fully understand this may not be the route you want to pursue.
Not everyone likes atomics and it is non-trivial to write bug-free concurrent code. Moreover, performance optimization around atomics is non-trivial due to many micro-architecture level details.
But I do not see any evidence suggesting lock-free implementation is not possible. And we have a hacky and not well-engineered lock-free implementation in cachelib.

a bit of weekend rambling...
In that lock-free eviction example the threads CAS on shared atomic variables (head and tail). Their independent work is to maybe unset the accessed flag and reinsert into a different queue, and likely also need to adjust the size counters. Since that parallel part is so small it would serialize against the queue outermost operation, in that case the removal. In a simple producer-consumer queue benchmark (Java), I observed a TTAS spinlock queue slightly beating a ConcurrentLinkedQueue (equivalent to your linked queue) on a push+pop operation at 5.9M vs 4.5M qps. That makes sense since TTAS reduces contention and spins using a PAUSE instruction, which hints to the cpu that it can prefer work from other threads.
Since the write / eviction is mostly serialized anyway, the benefit of FIFO / Clock / SecondChance based caches has tended to be advocated as a simple approach for lock-free reads with locking writes. For example see ClockPro (LIRS-based) and Linux's Double Clock, where reads are fast but writes are mentally challenging . If not encountering their O(n) problems then those have had acceptable eviction throughput rates. A sampled or associativity-based caches could offer throughput, but its not a strong differentiator as the needs were met.
In my experience a write-heavy cache tends to primarily bottleneck on the hash table, so an associativity-based one would be the winner if a necessity. However, other than a cache warm up typically writes are rare compared to reads. An eviction rate of a few million qps has been enough to settle my concerns if Caffeine's was good enough. If it was not then striping over multiple instances is the first and easy solution that I'd advise users to try. So far that hasn't been needed since the buffering of independent writes into batches means the writers usually won't serialize against a shared lock.
For the singular purpose of a size-bounded S3-FIFO cache, I don't think BP-Wrapper should be necessary. It is very nice for features and flexibility, but many of those are write-time which could happily live under an eviction lock. For example time-to-live is far more common than time-to-idle expiration, so that could either not be offered or use a more brute force approach (memcached/redis defer expiration to size eviction and uses a reaper to scan proactively).
If choosing a non-concurrent eviction policy then BP-Wrapper is excellent. The main concern might be that by sampling requests then when it sheds load the hit rate could degrade because fewer events are forwarded to the policy. That's easy to simulate by only updating the policy on X% of the hits when found in the hash table. Last time I looked into it was when the Ristretto authors asked, and my notes was that it was stable across modestly sized traces at a 100% to 0.5% sample rate (less than 1% hit rate loss), then fell more sharply 0.01% - 0.001% sample rate but only by up to a 3-6% hit rate loss. Since the cache is looking for heavy hitters in a stream of events, popular keys will be observed and it more aggressively discards others as one-hit wonders. Thus, 1:10,000 was the same hit rate as 1:100 in the majority of my data sets as either cache pollutants or, if recency biased, the hill climber adapted to delay filtering (slower as fewer observed events but fast enough). It was only on small pattern traces of 500K or fewer events did that loss sometimes become higher due to less training data, primarily being Lirs' loop at 0.005% (979 out of 505,500 requests; 512 max size). In that outlier it still beat most policies which have a 0% hit rate (LRU, 2Q, ARC, DoubleClock, GDSF, S3-FIFO) or lower hit rate (random), where only ClockPro and sampled MRU won that are concurrency-friendly. Thus, only at a sustained high load where most requests cannot be recorded by the policy was there a hit rate degradation and it still matched or outperformed most concurrent-friendly policies. That made it a good combination as the cache can policy work is very inexpensive, making this a rarely observed phenomenon.

Hi @ben-manes , greetings!
I always like your insightful comments! And I always learn from you. But I have a few questions. Can you help me better understand them?

Since that parallel part is so small it would serialize against the queue outermost operation, in that case the removal.

Why would CAS serialize against the removal (of a random object in the queue)?

I observed a TTAS spinlock queue slightly beating a ConcurrentLinkedQueue

Yup, TTAS is better than TAS, but few places mention it. Do you think ConcurrentLinkedQueue can be implemented with TTAS as well?

the write / eviction is mostly serialized

It feels to me that only one pointer update is serialized, other operations (e.g., copy value, resetting frequency, setting up other pointers, and a few other feature-dependent operations) are concurrent. So I do not agree the eviction is mostly serialized. I do agree with you that guarding by an eviction lock may have a similar performance as using atomics.
As you have mentioned, CLOCK-based algorithms do have O(n) worst-case complexity at eviction, but your suggestion on forcing an eviction upon examining x objects is a good solution. I was recently told that on Zipf workloads, on average, each eviction examines around two objects. If this number is reliable, it is not that bad.

the cache is looking for heavy hitters in a stream of events

I think It depends. It is ok to lose most of the promotions (updates) for very small cache size. For a large cache size, I think they do have penalties. but I don't have numbers and am not sure of the actual impact. This is similar to the try-lock approach that HHVM used, but BP-wrapper also amortizes the locking overhead and prefetch the object metadata. One of my students is evaluating the impact of probabilistic promotion, I may have numbers in the next few weeks.

time-to-live is far more common than time-to-idle expiration, so that could either not be offered or use a more brute force approach

FIFO queues actually make supporting "Time-to-live" easier as long as we put objects of similar TTLs on the same queue. If you are interested, Segcache is an example design.
A story on how I arrived at S3-FIFO and SIEVE: I noticed that the FIFO-based algorithm (SIEVE is a general formulation of this algorithm) in Segcache was more effective than I expected, so I dug deeper to understand why. Then I noticed that contrary to the conventional wisdom, FIFO-Reinsertion has lower miss ratios than LRU on most traces. Moreover, a key difference between Belady and other algorithms is that Belady evicts most objects very quickly after insertion. That's how I arrived here. The key points of my recent works are to show that "always promotion (on reads) is not needed" and "quickly removing new and unpopular objects is important". S3-FIFO and SIEVE are just examples to demonstrate these.
In case my early comments indicated the other side, I have never thought or stated that TinyLFU or Caffeine are not good.
I like the idea behind TinyLFU, and I believe there are opportunities to combine the idea with my recent findings to make it better.
The caffeine project is awesome. As the maintainer, you are very active in adopting and evaluating new ideas. And you demonstrated great efforts in educating us and helping newbies grow. I have not seen anyone better than you on this.
It is true that I'm not too fond of the caffeine benchmarks because I think they are confusing and misleading. But you have good points for them.
For everyone in this thread, Happy Holidays!

Happy (almost) new year @1a1a11a!

Why would CAS serialize against the removal (of a random object in the queue)?

I meant for eviction which removes from one end of the queue and not the random removal problem being discussed for expiration or user deletion. For eviction the sample would serialize as only one thread can win the CAS for updating those hot spots, so while fast it forces a lock-step sequence as that dequeuing cannot be parallelized. The ring buffer approach described in the paper would be nicer since it could replace the CAS loop with a fetch-and-add to claim a slot with reduced contention at these hotspots.

Yup, TTAS is better than TAS, but few places mention it. Do you think ConcurrentLinkedQueue can be implemented with TTAS as well?

For eviction the TTAS lock would replace a concurrent linked queue with a regular one, since I don't think you'll gain much benefit parallel evictions. It's not really combinable except if you wanted exclusive deletions like in your reader-writer lock or background thread sections. In that case, you could avoid the dedicated thread by using a try-lock to amortize that work on the calling threads so that the clean up is nonblocking and relatively prompt.
I think that I learned about TTAS from The Art of Multiprocessor Programming; that was a wonderful book.

It feels to me that only one pointer update is serialized, other operations (e.g., copy value, resetting frequency, setting up other pointers, and a few other feature-dependent operations) are concurrent. So I do not agree the eviction is mostly serialized. I do agree with you that guarding by an eviction lock may have a similar performance as using atomics.

I think we agree. It depends on how expensive those other operations are versus the overhead of a hot atomic. Usually those operations are very fast, like resetting the frequency, so reducing contention is a bigger win. If you have have expensive work  then you're right that lock-free should be better.

As you have mentioned, CLOCK-based algorithms do have O(n) worst-case complexity at eviction, but your suggestion on forcing an eviction upon examining x objects is a good solution. I was recently told that on Zipf workloads, on average, each eviction examines around two objects. If this number is reliable, it is not that bad.

Yep, I have no qualms against CLOCK-based approaches and started with them in my original experiments. ClockPro can have longer walks, is very complicated, and how it would behave with early eviction is unclear. I didn't trust myself to be able to maintain and improve that algorithm without more data and tooling, whereas bp-wrapper was a timely alternative. I often recommend the simpler Clock-based approach whenever someone needs a dependency-free, embedded cache. That's where I'll advocate for Clock/Sieve/S3Fifo as easy to understand, fast, and should be easy sells.

One of my students is evaluating the impact of probabilistic promotion, I may have numbers in the next few weeks.

I think that would be an interesting topic and make for a good paper if explored in depth. A little non-determinism is useful for avoiding worst-case behavior, like that early eviction to avoid O(n). Caffeine adds jitter to TinyLFU's admission for protection against denial-of-service attacks via hash flooding. Adding a little noise to a process can make it more robust, and I think that's too often forgotten and overlooked.

If you are interested, Segcache is an example design.

Yes, I quite like that design and it is a good fit for a dedicated cache server. It is very similar to a hashed timing wheel or calendar queue. I actually discussed something along those lines with the memcached maintainer (Alan, aka dormando) in 2016 over lunch, as he had made similar findings to your later twitter traces. It was too invasive of a rewrite so he pursued a reaper with a new queue structure, but your approach is what he would have liked to explore in a redo.

Then I noticed that contrary to the conventional wisdom, FIFO-Reinsertion has lower miss ratios than LRU on most traces.

I hadn't heard that misconception, only that FIFO has a lower hit rate and suffers from Bélády's anomaly. Instead, pseudo-LRU policies were often praised by being more robust against short-term fluctuations, leading to the insight that determinism can cause the policy to be too sensitive in worst-case situations.

In case my early comments indicated the other side...

I am very happy too see new work or rediscovery of old ideas, which might be mostly forgotten or revalidated with fresh data sets. I'm really not tied to TinyLFU, though I like Gil's insights and simplicity. Adopting it was a surprise as it originally underperformed at recency, but I was getting frustrated while debugging LIRS against their reference code and would try to fix TinyLFU during breaks as a mental reset. If something comes out better or improves to offer more good choices then I am all for that.
Sorry if my words came across as harsh or acidic at times. I have read and debugged many papers that took broad liberties in their claims, which is frustrating but okay when staying within an academic community as a known flaw towards progress. It is when those half truths are evangelized towards engineers that I become very protective because they take it all at face value and assume a very higher bar is required for publication. That can not only waste a lot of time but can cause production fires that impact end users.
If advocated on the merits while disclosing alternatives or flaws then sharing new insights is truly wonderful. Unfortunately it is instead unintentionally used to bludgeon maintainers to rewrite or fear being irrelevant, or diminish their efforts as dumb and outdated, which causes a lot of fiery drama for open-source maintainers who are contributing their weekends. Instead a competitive replacement is actually much more preferred, but most work does not receive the investment to be at that bar. The MemC3 paper had that impact towards memcached (originally a perl hack fix a prod fire!) and became such a sore topic that the maintainer finally wrote a public analysis to stop the regular harassment (innocently brought up by random users as suggestions). Or more recently LHD (sampling policy) was also innocently advocated for by engineers, but it required a slight-of-hand analysis by warming / replaying the traces so that its statistics became clairvoyant and did poorly without that future insight. So I apologize if I was overly defensive as I felt some of the claims, like lru scalability, were too broadly stated and left out details that were misleading non-academic readers.

It is true that I'm not too fond of the caffeine benchmarks because I think they are confusing and misleading. But you have good points for them.

agreed, but then all benchmarks are misleading. The wiki pages are meant for quick yes-no answers to common questions (does it have good concurrent performance? does it have good hit rates in diverse workloads?). A more thorough analysis is left for discussions to understand a wider set of data and I definitely ran far more workloads then those presented. I think we'll all disagree on some benchmark designs and how much weight to give their results, and certainly mine are not perfect and easily to misunderstand (myself included).
happy 2024!

Happy (almost) new year @1a1a11a!

Why would CAS serialize against the removal (of a random object in the queue)?

I meant for eviction which removes from one end of the queue and not the random removal problem being discussed for expiration or user deletion. For eviction the sample would serialize as only one thread can win the CAS for updating those hot spots, so while fast it forces a lock-step sequence as that dequeuing cannot be parallelized. The ring buffer approach described in the paper would be nicer since it could replace the CAS loop with a fetch-and-add to claim a slot with reduced contention at these hotspots.

Yup, TTAS is better than TAS, but few places mention it. Do you think ConcurrentLinkedQueue can be implemented with TTAS as well?

For eviction the TTAS lock would replace a concurrent linked queue with a regular one, since I don't think you'll gain much benefit parallel evictions. It's not really combinable except if you wanted exclusive deletions like in your reader-writer lock or background thread sections. In that case, you could avoid the dedicated thread by using a try-lock to amortize that work on the calling threads so that the clean up is nonblocking and relatively prompt.
I think that I learned about TTAS from The Art of Multiprocessor Programming; that was a wonderful book.

It feels to me that only one pointer update is serialized, other operations (e.g., copy value, resetting frequency, setting up other pointers, and a few other feature-dependent operations) are concurrent. So I do not agree the eviction is mostly serialized. I do agree with you that guarding by an eviction lock may have a similar performance as using atomics.

I think we agree. It depends on how expensive those other operations are versus the overhead of a hot atomic. Usually those operations are very fast, like resetting the frequency, so reducing contention is a bigger win. If you have have expensive work  then you're right that lock-free should be better.

As you have mentioned, CLOCK-based algorithms do have O(n) worst-case complexity at eviction, but your suggestion on forcing an eviction upon examining x objects is a good solution. I was recently told that on Zipf workloads, on average, each eviction examines around two objects. If this number is reliable, it is not that bad.

Yep, I have no qualms against CLOCK-based approaches and started with them in my original experiments. ClockPro can have longer walks, is very complicated, and how it would behave with early eviction is unclear. I didn't trust myself to be able to maintain and improve that algorithm without more data and tooling, whereas bp-wrapper was a timely alternative. I often recommend the simpler Clock-based approach whenever someone needs a dependency-free, embedded cache. That's where I'll advocate for Clock/Sieve/S3Fifo as easy to understand, fast, and should be easy sells.

One of my students is evaluating the impact of probabilistic promotion, I may have numbers in the next few weeks.

I think that would be an interesting topic and make for a good paper if explored in depth. A little non-determinism is useful for avoiding worst-case behavior, like that early eviction to avoid O(n). Caffeine adds jitter to TinyLFU's admission for protection against denial-of-service attacks via hash flooding. Adding a little noise to a process can make it more robust, and I think that's too often forgotten and overlooked.

If you are interested, Segcache is an example design.

Yes, I quite like that design and it is a good fit for a dedicated cache server. It is very similar to a hashed timing wheel or calendar queue. I actually discussed something along those lines with the memcached maintainer (Alan, aka dormando) in 2016 over lunch, as he had made similar findings to your later twitter traces. It was too invasive of a rewrite so he pursued a reaper with a new queue structure, but your approach is what he would have liked to explore in a redo.

Then I noticed that contrary to the conventional wisdom, FIFO-Reinsertion has lower miss ratios than LRU on most traces.

I hadn't heard that misconception, only that FIFO has a lower hit rate and suffers from Bélády's anomaly. Instead, pseudo-LRU policies were often praised by being more robust against short-term fluctuations, leading to the insight that determinism can cause the policy to be too sensitive in worst-case situations.

In case my early comments indicated the other side...

I am very happy too see new work or rediscovery of old ideas, which might be mostly forgotten or revalidated with fresh data sets. I'm really not tied to TinyLFU, though I like Gil's insights and simplicity. Adopting it was a surprise as it originally underperformed at recency, but I was getting frustrated while debugging LIRS against their reference code and would try to fix TinyLFU during breaks as a mental reset. If something comes out better or improves to offer more good choices then I am all for that.
Sorry if my words came across as harsh or acidic at times. I have read and debugged many papers that took broad liberties in their claims, which is frustrating but okay when staying within an academic community as a known flaw towards progress. It is when those half truths are evangelized towards engineers that I become very protective because they take it all at face value and assume a very higher bar is required for publication. That can not only waste a lot of time but can cause production fires that impact end users.
If advocated on the merits while disclosing alternatives or flaws then sharing new insights is truly wonderful. Unfortunately it is instead unintentionally used to bludgeon maintainers to rewrite or fear being irrelevant, or diminish their efforts as dumb and outdated, which causes a lot of fiery drama for open-source maintainers who are contributing their weekends. Instead a competitive replacement is actually much more preferred, but most work does not receive the investment to be at that bar. The MemC3 paper had that impact towards memcached (originally a perl hack fix a prod fire!) and became such a sore topic that the maintainer finally wrote a public analysis to stop the regular harassment (innocently brought up by random users as suggestions). Or more recently LHD (sampling policy) was also innocently advocated for by engineers, but it required a slight-of-hand analysis by warming / replaying the traces so that its statistics became clairvoyant and did poorly without that future insight. So I apologize if I was overly defensive as I felt some of the claims, like lru scalability, were too broadly stated and left out details that were misleading non-academic readers.

It is true that I'm not too fond of the caffeine benchmarks because I think they are confusing and misleading. But you have good points for them.

agreed, but then all benchmarks are misleading. The wiki pages are meant for quick yes-no answers to common questions (does it have good concurrent performance? does it have good hit rates in diverse workloads?). A more thorough analysis is left for discussions to understand a wider set of data and I definitely ran far more workloads then those presented. I think we'll all disagree on some benchmark designs and how much weight to give their results, and certainly mine are not perfect and easily to misunderstand (myself included).
happy 2024!

Hi @ben-manes,
I am glad that we are on the same page about most things.
I agree that it would be great if there is a forum for engineers to provide feedback to papers or ask paper to have a section to talk about the trade offs or downsides. On this end, I am totally with you. This is not only helpful for engineers who may implement the ideas, but also for researchers to seek to innovate on more ideas. And it is often the case that many engineers know critical details that researchers/students do not. Besides the ones you pointed out, there are more where such feedback can be helpful, such as this one here.

For eviction the TTAS lock would replace a concurrent linked queue with a regular one, since I don't think you'll gain much benefit parallel evictions

I was thinking about whether Java ConcurrentLinkedQueue would also benefit from using TTAS (assuming it uses CAS in current implementation).

I hadn't heard that misconception ...

It is pretty common that people call CLOCK or FIFO-Reinsertion as weak LRU or LRU approximation and indicate CLOCK is worse than LRU.

Regarding whether LRU is scalable

Most production systems do not need the scalability to scale to 10s millions of requests per second. The use of BP-Wrapper does reduce the lock contention and provides an elegant solution to graceful "degradation".
But I think claiming LRU is not scalable is correct.
I was not aware of BP-wrapper back then. If I can modify my statement, I am ok with the claim that BP-wrapper enables LRU to achieve scalability sufficient for most production systems.
If we want strict LRU behavior (meaning the read buffer cannot be lost), FIFO-based approaches will be better.

Happy holidays, everyone!
I have no words, only emotions.
I tried testing the seqlock implementation and died, it returns dirty data. If these tests are to be believed (spinlock and rwmutex pass them).
Since debug and gaze method didn't help, I decided to check the instructions that go compiler gives after different compilation stages. And it looks like it just rearranges the value copying 😬.
At the opt stage it was:
b11: ← b6-
  v32 (+23) = NilCheck <void> v6 v16
  v33 (23) = OffPtr <*any> [8] v6
  v34 (23) = Load <any> v33 v16 (value[any])
  v35 (+25) = NilCheck <void> v6 v16
  v36 (25) = OffPtr <*"sync/atomic".Uint32> [0] v6 ("sync/atomic".x[*"sync/atomic".Uint32])
  v37 (25) = InlMark <void> [3] v16
  v38 (+116) = NilCheck <void> v36 v16
  v39 (116) = OffPtr <*uint32> [0] v6
  v40 (116) = AtomicLoad32 <uint32,mem> v39 v16
  v41 (116) = Select1 <mem> v40
  v42 (116) = Select0 <uint32> v40 (~R0[uint32], newSeq[uint32])
  v45 (+26) = Eq32 <bool> v17 v42
If v45 → b13 b12 (26)

But already at the lower stage it became:
b11: ← b6-
  v37 (+25) = InlMark <void> [3] v16
  v40 (+116) = MOVLatomicload <uint32,mem> v6 v16
  v42 (116) = Select0 <uint32> v40 (~R0[uint32], newSeq[uint32])
  v41 (116) = Select1 <mem> v40
  v35 (+23) = MOVQload <uintptr> [8] v6 v16 (value.type[uintptr])
  v32 (+23) = MOVQload <*uint8> [16] v6 v16 (value.data[*uint8])
  v48 (+26) = CMPL <flags> v42 v17
EQ v48 → b13 b12 (26)

You’re go.mod is using go 1.18 but the memory model was introduced in go 1.19 so you didn’t have compiler support. Can you try updating?

 It is to ensure that seq is considered live and used to preventing the compiler from optimizing it away, or in this case placing after the value assignment. However that seems to be a poorly explained trick and I am unsure if it works, but maybe try that next.
func compilerBarrier() {
	var dummy int
	_ = dummy
}

func (n *Node[K, V]) Value() V {
for {
seq := n.lock.Load()
compilerBarrier()
if seq&1 != 0 {
  runtime.Gosched()
  continue
}

value := n.value // Safe read after memory barrier

newSeq := n.lock.Load()
if seq == newSeq {
  return value
}

}
}

I've tried something similar, but it doesn't work. The compiler is too smart in this case. I'll have to take the issue to the developers, because I don't really understand why it decides to put a copy value after newSeq.
b15: ← b7-
  v46 (+38) = InlMark <void> [6] v17
  v60 (+35) = MOVQload <int> [8] v6 v17
  v56 (35) = MOVQload <int> [16] v6 v17
  v54 (35) = MOVQload <int> [24] v6 v17
  v49 (+116) = MOVLatomicload <uint32,mem> v6 v17
  v51 (116) = Select0 <uint32> v49 (~R0[uint32], newSeq[uint32])
  v50 (116) = Select1 <mem> v49
  v14 (+40) = CMPL <flags> v51 v18
EQ v14 → b17 b16 (unlikely) (40)

gossa

What if you make a method scoped mutex variable and lock around the read? It would be uncontended as dead code, but might not be eliminated or at least force the barriers. If Go follows the roach motel model it would also be safe, I think?

Ahahahaha, that kind of thing really works.
func (n *Node[K, V]) Value() V {
	var mutex sync.Mutex
	for {
		seq := n.lock.Load()
		if seq&1 != 0 {
			runtime.Gosched()
			continue
		}

		mutex.Lock()
		value := n.value
		mutex.Unlock()

		newSeq := n.lock.Load()
		if seq == newSeq {
			return value
		}
	}
}

wonderful! you may be able to use an atomic.Uint32 in a similar, lighter fashion to create a store barrier. It sounds like they'll reorder load barriers but not stores, where the lock/unlock are writing to the state field. We assumed they would honor an acquiring load, e.g. [LoadLoad][LoadStore] barrier on the atomic.LoadInt32, and not allow the compiler to reordering around that. Instead it seems that you have to rely on the releasing store, [StoreStore][LoadStore], for the compiler act how one should expect. It would be nice if they wrote those semantics down or provided the ability to emit the proper fences. I believe this method scoped variable would be stack allocated, so it would incur no GC penalty, and therefore should be extremely chap and could be optimized away as just the emit the fences.

@ben-manes Yes, it's very similar to that and everything will indeed happen on the stack. I played around a bit and found out that even this ridiculous variant works.
func (n *Node[K, V]) Value() V {
	var lol atomic.Uint32
	for {
		seq := n.lock.Load()
		if seq&1 != 0 {
			runtime.Gosched()
			continue
		}

		value := n.value
		lol.Store(1)

		newSeq := n.lock.Load()
		if seq == newSeq {
			return value
		}
	}
}

Yep, that's what I was suggesting and it makes sense. They are enforcing compiler barriers for release semantics but oddly not for acquire semantics. That's really convoluted, but 🤷♂

Very interesting, on laptops with linux, windows and intel and amd (x64) processors (all combinations) everything works fine without additional atomics but it doesn't work on macs on arm. I wish I could get a mac on intel somewhere....

I believe ARM uses weak memory consistency model https://preshing.com/20120930/weak-vs-strong-memory-models/

In general, it doesn't look like it, since gossa shows a rearrangement of instructions. And when adding Store, judging by the instructions, the barrier is triggered. Perhaps on some processors/architectures race condition does not work in time. But it is not certain.

True, if the instruction has already been rearranged before running, then it is probably not relevant. I am not an expert on this, so I will just watch and learn.

My very limited (and likely outdated) understanding is that Go does not have a very good suite of concurrent data structures and primitives, at least compared to Java's...

@ben-manes That is true, thread-safe data structures are rife with locks in Go. But in my experience, this is less of an issue than in Java because of goroutines (lightweight threads) and channels, which encourage message passing over memory sharing.

Oh man, in Value method lol and mutex are allocated on the heap.

@jbduncan it's not true, for a large number of applications in Go, Java and other languages the usual map with mutex will suffice, but if you need something more, you suddenly start to have problems. Because a map with mutex will not save you from blocking hundreds of goroutines, and sync.Map is actually useless. Also the channels cannot be called efficient in any way. In conditional Java you can take ConcurrentHashMap at once and live peacefully, but in go people start to get out of it (most often just using map sharding). The canonical go way unfortunately doesn't always work either, the simplest examples are fasthttp and VictoriaMetrics, which break the rules but achieve excellent efficiency and are very popular. For example, my company switched to VictoriaMetrics simply because it was able to handle loads that competitors couldn't and nobody cares that it has a huge amount of non-canonical code and specific optimizations. Also, when you have a well-performing, more efficient solution, everyone I know immediately asks, "Why would I use something else?"

@maypok86 Oh, good point about sync.Map and mutexes blocking goroutines. I've only ever had to consider problems like net/http servers where things are abstracted away or small ETL jobs where goroutines and channels could be viable, so thanks for bringing me back down to earth.
Though I'm not sure what you mean by "channels cannot be called efficient in any way", so at the risk of derailing things, I was wondering if you had an example?

@jbduncan In fact it is very hard to feel the problems with channels, unlike map with mutex and they really do their job in 99% of cases, but they use mutex internally because of what on large machines and heavy loads on data transfer through goroutines can become a bottleneck of the program.
Here is an example of comparison with a more tricky queue architecture (сoncurrent producers and consumers (1:1), queue/channel size 1,000, some work done by both producers and consumers):
QueueProdConsWork100                             252ns ± 0%
QueueProdConsWork100-2                           206ns ± 5%
QueueProdConsWork100-4                           136ns ±12%
QueueProdConsWork100-8                           110ns ± 6%
QueueProdConsWork100-16                          108ns ± 2%
QueueProdConsWork100-32                          102ns ± 2%
QueueProdConsWork100-64                          101ns ± 0%
ChanProdConsWork100                              283ns ± 0%
ChanProdConsWork100-2                            406ns ±21%
ChanProdConsWork100-4                            549ns ± 7%
ChanProdConsWork100-8                            754ns ± 7%
ChanProdConsWork100-16                           828ns ± 7%
ChanProdConsWork100-32                           810ns ± 8%
ChanProdConsWork100-64                           832ns ± 4%

Oh man, in Value method lol and mutex are allocated on the heap.

In sync.pool it uses runtime_LoadAcquintptr for acquiring semantics which the compiler probably honors. Would a pool.Get() on an empty, never populated, shared pool give you a compiler barrier without causing unnecessary heap or coherence overhead? if that works, how much overhead is this no-op hack?

In sync.pool it uses runtime_LoadAcquintptr for acquiring semantics which the compiler probably honors. Would a pool.Get() on an empty, never populated, shared pool give you a compiler barrier without causing unnecessary heap or coherence overhead? if that works, how much overhead is this no-op hack?

It is huge because the empty sync.Pool uses the getSlow method (finds nothing and tries to find something in other pools). What's interesting, the approach from counters to determine the OS thread id is faster, but actually equals spinlocks.
Benchmark results (reads slower than updates)
goos: darwin
goarch: arm64
pkg: github.com/maypok86/otter/perf
BenchmarkCache/Zipf_Theine_reads=100%,writes=0%-8               10877155               111.5 ns/op         8969638 ops/s               0 B/op          0 allocs/op
BenchmarkCache/Zipf_Ristretto_reads=100%,writes=0%-8            40693945                30.85 ns/op       32418153 ops/s              16 B/op          1 allocs/op
BenchmarkCache/Zipf_Bigcache_reads=100%,writes=0%-8             27307274                45.90 ns/op       21788883 ops/s              96 B/op          2 allocs/op
BenchmarkCache/Zipf_Fastcache_reads=100%,writes=0%-8            36409423                33.47 ns/op       29873592 ops/s              47 B/op          0 allocs/op
BenchmarkCache/Zipf_Otter_reads=100%,writes=0%-8                43991157                23.78 ns/op       42049901 ops/s               0 B/op          0 allocs/op
BenchmarkCache/Zipf_Theine_reads=75%,writes=25%-8                8651826               124.7 ns/op         8017364 ops/s               0 B/op          0 allocs/op
BenchmarkCache/Zipf_Ristretto_reads=75%,writes=25%-8            24971624                51.71 ns/op       19336805 ops/s              28 B/op          1 allocs/op
BenchmarkCache/Zipf_Bigcache_reads=75%,writes=25%-8             17303230                71.20 ns/op       14044841 ops/s             108 B/op          1 allocs/op
BenchmarkCache/Zipf_Fastcache_reads=75%,writes=25%-8            19197260                58.07 ns/op       17219988 ops/s              43 B/op          0 allocs/op
BenchmarkCache/Zipf_Otter_reads=75%,writes=25%-8                58528850                18.31 ns/op       54613259 ops/s               0 B/op          0 allocs/op
BenchmarkCache/Zipf_Theine_reads=0%,writes=100%-8               20914059                54.85 ns/op       18231676 ops/s               0 B/op          0 allocs/op
BenchmarkCache/Zipf_Ristretto_reads=0%,writes=100%-8             8795355               136.0 ns/op         7354091 ops/s             120 B/op          3 allocs/op
BenchmarkCache/Zipf_Bigcache_reads=0%,writes=100%-8             12765872                81.69 ns/op       12241376 ops/s             165 B/op          0 allocs/op
BenchmarkCache/Zipf_Fastcache_reads=0%,writes=100%-8            21821074                53.93 ns/op       18540956 ops/s               0 B/op          0 allocs/op
BenchmarkCache/Zipf_Otter_reads=0%,writes=100%-8                71402260                16.70 ns/op       59866267 ops/s               0 B/op          0 allocs/op
PASS
ok      github.com/maypok86/otter/perf  20.408s

I guess then what is the impact of having a global atomic field that is blindly written to, e.g. always set a boolean false? Since it’s not loaded or in lockstep, will it cause a lot of coherence traffic as cpus trade mesi ownership of the cache line? Or will it just create a store barrier and some light traffic?
I suspect a little heap allocation will be the best of the bad choices. The gc will keep getting better as that until you get a proper compiler fence to replace it.

Unfortunately, global atomics is making things much worse.
goos: darwin
goarch: arm64
pkg: github.com/maypok86/otter/perf
BenchmarkCache/Zipf_Theine_reads=100%,writes=0%-8               11039739                99.10 ns/op       10091010 ops/s               0 B/op          0 allocs/op
BenchmarkCache/Zipf_Ristretto_reads=100%,writes=0%-8            43249087                24.22 ns/op       41296106 ops/s              16 B/op          1 allocs/op
BenchmarkCache/Zipf_Bigcache_reads=100%,writes=0%-8             29019181                38.42 ns/op       26025690 ops/s              96 B/op          2 allocs/op
BenchmarkCache/Zipf_Fastcache_reads=100%,writes=0%-8            34859906                29.98 ns/op       33353715 ops/s              47 B/op          0 allocs/op
BenchmarkCache/Zipf_Otter_reads=100%,writes=0%-8                45606712                24.18 ns/op       41349324 ops/s               0 B/op          0 allocs/op
BenchmarkCache/Zipf_Theine_reads=75%,writes=25%-8               10703342               102.7 ns/op         9736724 ops/s               0 B/op          0 allocs/op
BenchmarkCache/Zipf_Ristretto_reads=75%,writes=25%-8            25954760                43.42 ns/op       23030717 ops/s              27 B/op          1 allocs/op
BenchmarkCache/Zipf_Bigcache_reads=75%,writes=25%-8             18474672                61.49 ns/op       16263119 ops/s             112 B/op          1 allocs/op
BenchmarkCache/Zipf_Fastcache_reads=75%,writes=25%-8            22329164                52.62 ns/op       19004293 ops/s              43 B/op          0 allocs/op
BenchmarkCache/Zipf_Otter_reads=75%,writes=25%-8                60689072                19.50 ns/op       51290554 ops/s               0 B/op          0 allocs/op
BenchmarkCache/Zipf_Theine_reads=0%,writes=100%-8               28396710                44.02 ns/op       22715338 ops/s               0 B/op          0 allocs/op
BenchmarkCache/Zipf_Ristretto_reads=0%,writes=100%-8            10060098               123.9 ns/op         8068016 ops/s             121 B/op          3 allocs/op
BenchmarkCache/Zipf_Bigcache_reads=0%,writes=100%-8             14165078                75.17 ns/op       13303308 ops/s             173 B/op          0 allocs/op
BenchmarkCache/Zipf_Fastcache_reads=0%,writes=100%-8            25403186                49.72 ns/op       20114664 ops/s               0 B/op          0 allocs/op
BenchmarkCache/Zipf_Otter_reads=0%,writes=100%-8                75778336                17.89 ns/op       55907056 ops/s               0 B/op          0 allocs/op
PASS
ok      github.com/maypok86/otter/perf  20.938s

Allocation for each Get request confuses me because with high probability GC will spend much more time (and in fact a lot of memory will be spent on it too) to clean up these allocations than we will gain.
And there are several ways of solution here

use atomic.Value and put up with memory loss and load on GC, especially since unlike theine and many other cache libraries otter does not store keys twice (the ristretto approach with replacing keys with hash is too dirty in my opinion). Because of this, for example, when using strings as keys, our implementations can actually compare in terms of GC load and memory consumption (although clearing values from the heap is certainly a more unpleasant operation).

goos: darwin
goarch: arm64
pkg: github.com/maypok86/otter/perf
BenchmarkCache/Zipf_Theine_reads=100%,writes=0%-8               10890712               105.2 ns/op         9506177 ops/s               0 B/op          0 allocs/op
BenchmarkCache/Zipf_Ristretto_reads=100%,writes=0%-8            42186675                25.67 ns/op       38957096 ops/s              16 B/op          1 allocs/op
BenchmarkCache/Zipf_Bigcache_reads=100%,writes=0%-8             32435317                40.15 ns/op       24909024 ops/s              96 B/op          2 allocs/op
BenchmarkCache/Zipf_Fastcache_reads=100%,writes=0%-8            38724302                30.79 ns/op       32474269 ops/s              47 B/op          0 allocs/op
BenchmarkCache/Zipf_Otter_reads=100%,writes=0%-8                266765196                4.576 ns/op     218544656 ops/s               0 B/op          0 allocs/op
BenchmarkCache/Zipf_Theine_reads=75%,writes=25%-8               10897141               110.2 ns/op         9071319 ops/s               0 B/op          0 allocs/op
BenchmarkCache/Zipf_Ristretto_reads=75%,writes=25%-8            27160022                45.09 ns/op       22177331 ops/s              28 B/op          1 allocs/op
BenchmarkCache/Zipf_Bigcache_reads=75%,writes=25%-8             17890664                63.31 ns/op       15794165 ops/s             106 B/op          1 allocs/op
BenchmarkCache/Zipf_Fastcache_reads=75%,writes=25%-8            23185473                51.38 ns/op       19464213 ops/s              43 B/op          0 allocs/op
BenchmarkCache/Zipf_Otter_reads=75%,writes=25%-8                185191293                6.631 ns/op     150817471 ops/s               1 B/op          0 allocs/op
BenchmarkCache/Zipf_Theine_reads=0%,writes=100%-8               28361977                42.62 ns/op       23461253 ops/s               0 B/op          0 allocs/op
BenchmarkCache/Zipf_Ristretto_reads=0%,writes=100%-8            12942342                95.99 ns/op       10417285 ops/s             120 B/op          3 allocs/op
BenchmarkCache/Zipf_Bigcache_reads=0%,writes=100%-8             13148985                76.05 ns/op       13148494 ops/s             171 B/op          0 allocs/op
BenchmarkCache/Zipf_Fastcache_reads=0%,writes=100%-8            24734936                48.88 ns/op       20459221 ops/s               0 B/op          0 allocs/op
BenchmarkCache/Zipf_Otter_reads=0%,writes=100%-8                60494036                24.93 ns/op       40112645 ops/s              16 B/op          1 allocs/op
PASS
ok      github.com/maypok86/otter/perf  21.076s

use RCU approach and put up with its disadvantages. Here we will have to edit quite a lot in the current implementation, but we can agree with it, although the strongest slowdown of updates is alarming.

Leave everything as it is and live with slower reads.

By the way, performance with seqlock and atomic barrier on every Get request.
goos: darwin
goarch: arm64
pkg: github.com/maypok86/otter/perf
BenchmarkCache/Zipf_Theine_reads=100%,writes=0%-8               11564922               100.3 ns/op         9973789 ops/s               0 B/op          0 allocs/op
BenchmarkCache/Zipf_Ristretto_reads=100%,writes=0%-8            40285806                26.70 ns/op       37454930 ops/s              16 B/op          1 allocs/op
BenchmarkCache/Zipf_Bigcache_reads=100%,writes=0%-8             30965144                40.81 ns/op       24502239 ops/s              96 B/op          2 allocs/op
BenchmarkCache/Zipf_Fastcache_reads=100%,writes=0%-8            40173415                31.08 ns/op       32171586 ops/s              47 B/op          0 allocs/op
BenchmarkCache/Zipf_Otter_reads=100%,writes=0%-8                192483022                6.916 ns/op     144595413 ops/s               4 B/op          1 allocs/op
BenchmarkCache/Zipf_Theine_reads=75%,writes=25%-8               10873077               106.4 ns/op         9395601 ops/s               0 B/op          0 allocs/op
BenchmarkCache/Zipf_Ristretto_reads=75%,writes=25%-8            29815732                43.06 ns/op       23222686 ops/s              27 B/op          1 allocs/op
BenchmarkCache/Zipf_Bigcache_reads=75%,writes=25%-8             17980041                62.49 ns/op       16002663 ops/s             103 B/op          1 allocs/op
BenchmarkCache/Zipf_Fastcache_reads=75%,writes=25%-8            22022995                53.27 ns/op       18773787 ops/s              43 B/op          0 allocs/op
BenchmarkCache/Zipf_Otter_reads=75%,writes=25%-8                136333018                9.592 ns/op     104255772 ops/s               3 B/op          0 allocs/op
BenchmarkCache/Zipf_Theine_reads=0%,writes=100%-8               31642126                39.82 ns/op       25115454 ops/s               0 B/op          0 allocs/op
BenchmarkCache/Zipf_Ristretto_reads=0%,writes=100%-8             9879114               120.2 ns/op         8317107 ops/s             121 B/op          3 allocs/op
BenchmarkCache/Zipf_Bigcache_reads=0%,writes=100%-8             13663359                86.14 ns/op       11609071 ops/s             238 B/op          0 allocs/op
BenchmarkCache/Zipf_Fastcache_reads=0%,writes=100%-8            24398157                49.66 ns/op       20135512 ops/s               0 B/op          0 allocs/op
BenchmarkCache/Zipf_Otter_reads=0%,writes=100%-8                58525999                21.32 ns/op       46915199 ops/s               0 B/op          0 allocs/op
PASS
ok      github.com/maypok86/otter/perf  22.698s

And with spinlock they are like this.
goos: darwin
goarch: arm64
pkg: github.com/maypok86/otter/perf
BenchmarkCache/Zipf_Theine_reads=100%,writes=0%-8               11513593               102.8 ns/op         9725518 ops/s               0 B/op          0 allocs/op
BenchmarkCache/Zipf_Ristretto_reads=100%,writes=0%-8            44476977                28.48 ns/op       35114128 ops/s              16 B/op          1 allocs/op
BenchmarkCache/Zipf_Bigcache_reads=100%,writes=0%-8             29389074                41.46 ns/op       24118353 ops/s              96 B/op          2 allocs/op
BenchmarkCache/Zipf_Fastcache_reads=100%,writes=0%-8            40236950                30.71 ns/op       32565429 ops/s              47 B/op          0 allocs/op
BenchmarkCache/Zipf_Otter_reads=100%,writes=0%-8                87322472                12.33 ns/op       81082476 ops/s               0 B/op          0 allocs/op
BenchmarkCache/Zipf_Theine_reads=75%,writes=25%-8               10701369               109.8 ns/op         9109595 ops/s               0 B/op          0 allocs/op
BenchmarkCache/Zipf_Ristretto_reads=75%,writes=25%-8            23923245                45.17 ns/op       22139916 ops/s              27 B/op          1 allocs/op
BenchmarkCache/Zipf_Bigcache_reads=75%,writes=25%-8             18169131                60.89 ns/op       16421834 ops/s             103 B/op          1 allocs/op
BenchmarkCache/Zipf_Fastcache_reads=75%,writes=25%-8            22694677                53.62 ns/op       18649904 ops/s              43 B/op          0 allocs/op
BenchmarkCache/Zipf_Otter_reads=75%,writes=25%-8                87237304                13.64 ns/op       73295198 ops/s               0 B/op          0 allocs/op
BenchmarkCache/Zipf_Theine_reads=0%,writes=100%-8               35994420                47.10 ns/op       21231164 ops/s               0 B/op          0 allocs/op
BenchmarkCache/Zipf_Ristretto_reads=0%,writes=100%-8             9810844               129.5 ns/op         7724999 ops/s             121 B/op          3 allocs/op
BenchmarkCache/Zipf_Bigcache_reads=0%,writes=100%-8             13800042                78.14 ns/op       12797693 ops/s             185 B/op          0 allocs/op
BenchmarkCache/Zipf_Fastcache_reads=0%,writes=100%-8            24117067                48.82 ns/op       20484021 ops/s               0 B/op          0 allocs/op
BenchmarkCache/Zipf_Otter_reads=0%,writes=100%-8                67451888                18.75 ns/op       53345341 ops/s               0 B/op          0 allocs/op
PASS
ok      github.com/maypok86/otter/perf  20.128s

In fact, I doubt they will add anything to go that can fix seqlocks.
So I tried rewriting the code to rcu, and by preliminary measurements I'm quite happy with the performance. (On 100% writes it looks like it's all bottlenecked by the queue).
reads=100%,writes=0%
BenchmarkCache/Zipf_Theine_reads=100%,writes=0%-8               10947901               100.4 ns/op         9958631 ops/s               0 B/op          0 allocs/op
BenchmarkCache/Zipf_Ristretto_reads=100%,writes=0%-8            45642127                25.84 ns/op       38702390 ops/s              16 B/op          1 allocs/op
BenchmarkCache/Zipf_Bigcache_reads=100%,writes=0%-8             32109850                40.04 ns/op       24973950 ops/s              96 B/op          2 allocs/op
BenchmarkCache/Zipf_Fastcache_reads=100%,writes=0%-8            39218516                30.52 ns/op       32761562 ops/s              47 B/op          0 allocs/op
BenchmarkCache/Zipf_Otter_reads=100%,writes=0%-8                253637361                4.377 ns/op     228480222 ops/s               0 B/op          0 allocs/op

reads=75%,writes=25%
BenchmarkCache/Zipf_Theine_reads=75%,writes=25%-8               10209930               104.4 ns/op         9582855 ops/s               0 B/op          0 allocs/op
BenchmarkCache/Zipf_Ristretto_reads=75%,writes=25%-8            27865933                43.44 ns/op       23020143 ops/s              27 B/op          1 allocs/op
BenchmarkCache/Zipf_Bigcache_reads=75%,writes=25%-8             19538709                62.58 ns/op       15979712 ops/s             110 B/op          1 allocs/op
BenchmarkCache/Zipf_Fastcache_reads=75%,writes=25%-8            19207093                54.99 ns/op       18184478 ops/s              43 B/op          0 allocs/op
BenchmarkCache/Zipf_Otter_reads=75%,writes=25%-8                176039958                6.490 ns/op     154081867 ops/s               2 B/op          0 allocs/op

reads=50%,writes=50%
BenchmarkCache/Zipf_Theine_reads=50%,writes=50%-8               11559314                97.44 ns/op       10262300 ops/s               0 B/op          0 allocs/op
BenchmarkCache/Zipf_Ristretto_reads=50%,writes=50%-8            22018971                48.94 ns/op       20435061 ops/s              34 B/op          1 allocs/op
BenchmarkCache/Zipf_Bigcache_reads=50%,writes=50%-8             16228872                62.82 ns/op       15919191 ops/s             132 B/op          1 allocs/op
BenchmarkCache/Zipf_Fastcache_reads=50%,writes=50%-8            21352249                54.48 ns/op       18355882 ops/s              39 B/op          0 allocs/op
BenchmarkCache/Zipf_Otter_reads=50%,writes=50%-8                107763754               10.72 ns/op       93268480 ops/s               5 B/op          0 allocs/op

reads=25%,writes=75%
BenchmarkCache/Zipf_Theine_reads=25%,writes=75%-8               12707719                92.89 ns/op       10765447 ops/s               0 B/op          0 allocs/op
BenchmarkCache/Zipf_Ristretto_reads=25%,writes=75%-8            20564748                57.58 ns/op       17367336 ops/s              55 B/op          1 allocs/op
BenchmarkCache/Zipf_Bigcache_reads=25%,writes=75%-8             16359062                65.76 ns/op       15206757 ops/s             165 B/op          0 allocs/op
BenchmarkCache/Zipf_Fastcache_reads=25%,writes=75%-8            23839993                45.78 ns/op       21843813 ops/s              23 B/op          0 allocs/op
BenchmarkCache/Zipf_Otter_reads=25%,writes=75%-8                52671734                22.94 ns/op       43586449 ops/s              11 B/op          0 allocs/op

reads=0%,writes=100%
BenchmarkCache/Zipf_Theine_reads=0%,writes=100%-8               26785988                42.13 ns/op       23735382 ops/s               0 B/op          0 allocs/op
BenchmarkCache/Zipf_Ristretto_reads=0%,writes=100%-8             9223939               126.2 ns/op         7920840 ops/s             122 B/op          3 allocs/op
BenchmarkCache/Zipf_Bigcache_reads=0%,writes=100%-8             13591893                81.53 ns/op       12264735 ops/s             252 B/op          0 allocs/op
BenchmarkCache/Zipf_Fastcache_reads=0%,writes=100%-8            24455442                49.59 ns/op       20163620 ops/s               0 B/op          0 allocs/op
BenchmarkCache/Zipf_Otter_reads=0%,writes=100%-8                 9646405               116.5 ns/op         8587281 ops/s              64 B/op          1 allocs/op

It seems that even for write-heavy workloads, a quick-written rcu holds up quite well.

Anyway, if anyone is interested, seqlocks in go can be fixed with dark magic.
Namely by importing this function from the go runtime.
//go:linkname runtimeatomicwb runtime.atomicwb
//go:noescape
func runtimeatomicwb(ptr *unsafe.Pointer, new unsafe.Pointer)

But this is too forbidden technique🙂.

@maypok86
I'm considering improving Theine a bit, and the first thing I plan to do is change the read buffer. I take a look Otter and the striped ring buffer seems very high performance. However, I also have another interesting idea.
The original Ristretto version uses a sync pool with a buffer, making each buffer local to P so no lock is needed. However, sync pools are easily GCed, causing lose of buffers. What if I disable sync pool GC, preallocate all buffers, and make sync pool's New function to only return nil?
An example of overriding sync pool: https://github.com/bytedance/gopkg/blob/main/lang/syncx/pool.go
I actually write some simple demo code when reading Otter code:
type SyncPoolBuffer[K comparable, V any] struct {
	pool Pool
	pm   []*PolicyBuffers[K, V]
}

func NewSP[K comparable, V any](nodeManager *node.Manager[K, V], size int) *SyncPoolBuffer[K, V] {

	b := &SyncPoolBuffer[K, V]{
		pool: Pool{
			New: func() any {
				return nil
			},
		},
	}
	for i := 0; i < size/4; i++ {
		buffer := &PolicyBuffers[K, V]{make([]node.Node[K, V], 0, capacity)}
		b.pm = append(b.pm, buffer)
		go b.pool.Put(buffer)
	}

	return b
}

func (b *SyncPoolBuffer[K, V]) Add(n node.Node[K, V]) *PolicyBuffers[K, V] {
	raw := b.pool.Get()
	if raw == nil {
		return nil
	}
	pb := raw.(*PolicyBuffers[K, V])
	if lb := len(pb.Returned); lb >= capacity {
		return pb
	} else {
		pb.Returned = append(pb.Returned, n)
		b.pool.Put(pb)
		return nil
	}
}

// Free returns the processed buffer back and also clears it.
func (b *SyncPoolBuffer[K, V]) Free(pb *PolicyBuffers[K, V]) {
	pb.Returned = pb.Returned[:0]
	b.pool.Put(pb)
}

But the problem with this approach is also obvious: there is no contention anymore. Here I add a simple counter in afterGet:
	if SyncPoolBufferMode {
		pb = c.syncPoolBuffer.Add(got)
	} else {
		pb = c.stripedBuffer[idx].Add(got)
	}
	if pb != nil {
		c.evictionMutex.Lock()
		c.policy.Read(pb.Returned)
		logged += 1
		c.evictionMutex.Unlock()

		if SyncPoolBufferMode {
			c.syncPoolBuffer.Free(pb)
		} else {
			c.stripedBuffer[idx].Free()
		}
	}

and here is the throughput benchmark result:
Striped RingBuffer:
cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
BenchmarkCache/zipf_otter_reads=100%,writes=0%-8         	100000000	        12.25 ns/op	  81640149 ops/s
==== logged 20817

SyncPool Buffer:
cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
BenchmarkCache/zipf_otter_reads=100%,writes=0%-8         	100000000	        36.38 ns/op	  27486156 ops/s
==== logged 5882350

What do you think about this idea?

I plan to do is change the read buffer.

Yeah, this is probably theine's main problem when working with a high load.
for i := 0; i < size/4; i++ {
	buffer := &PolicyBuffers[K, V]{make([]node.Node[K, V], 0, capacity)}
	b.pm = append(b.pm, buffer)
	go b.pool.Put(buffer)
}

It looks interesting and funny. It should even work, although it relies very heavily on the behavior of the scheduler. I would be careful here that the scheduler may ignore one of the P's and then the cache will always work poorly.
It seems that you implemented read buffers from ristretto, but removing the gc option. I wouldn't say that gc is a problem of ristretto read buffers. Moreover, I suspect that this has almost no effect on throughput benchmarks. It may affect the hit ratio, but it needs to be checked. I haven't been able to replicate most of the ristretto charts, although the charts of my hit ratio simulator are almost exactly the same as yours. But at least I found the reason for a very small hit ratio in ristretto.
In fact, I thought about the options for implementing read buffers for an incredibly long time and decided to do it in this form based on the following thoughts:

Under high load, sync.Pool won't help much, since all cores will be waiting for the read buffer to be processed by the eviction policy.
With contention-based losses, the cores will not wait and will show excellent results on throughput benchmarks. This may affect the hit ratio, but I don't think it's very important for two reasons. Firstly, it has almost no effect on the vast majority of users, since they are not able to generate such a load. Secondly, if the application is able to handle such a load, then the cache is still only trying to identify hot entries, and if you remove a small number of accesses, it will hardly change the distribution of hot-cold entries. Especially with millions of requests per second. That's how much it takes to generate meaningful contention. I even tried to compare the hit ratio losses of theine and otter and the difference there is about 2% at 100% cpu usage (quite expected), which is extremely unlikely in reality. I was more surprised by the presence of hit ratio losses due to the use of bp-wrapper.

Maybe I'm wrong somewhere, but I reasoned something like this :)
It's funny that I recently tried to make the read buffers dynamic and even something worked out, but I won't risk pushing and merging it :).

@maypok86 I revisited your Ristretto issue, and finally, part of the mystery has been solved. Totally agree losses is intended on read buffer. I think I'll just borrow your striped buffer because it naturally fits the current Theine, which handles read policy updates synchronously. The modified sync pool is extremely 'unsafe' and seems too magical, and also need to figure out how to make it lossy.

@maypok86 Here is the improved result after switching to Otter striped buffer and several other optimizations:
BenchmarkCache/zipf_otter_reads=100%,writes=0%-8         	101792066	        11.97 ns/op	  83515868 ops/s
BenchmarkCache/zipf_theine_reads=100%,writes=0%-8        	40965662	        30.05 ns/op	  33275970 ops/s
BenchmarkCache/zipf_ristretto_reads=100%,writes=0%-8     	29334450	        39.74 ns/op	  25166567 ops/s

BenchmarkCache/zipf_otter_reads=75%,writes=25%-8         	54122091	        18.56 ns/op	  53871082 ops/s
BenchmarkCache/zipf_theine_reads=75%,writes=25%-8        	29716508	        41.82 ns/op	  23910140 ops/s
BenchmarkCache/zipf_ristretto_reads=75%,writes=25%-8     	16239280	        86.11 ns/op	  11613020 ops/s

And this is the PR (https://github.com/Yiling-J/theine-go/pull/42), maybe you can also help review it because I borrowed your code directly and only made a small modification.