NovaX

Yeah, I wasn’t being particular about this exact issue and was generalizing about synchronization pinning the carrier. A deadlock is trivial once the implications of that are thought through.

https://mail.openjdk.org/pipermail/loom-dev/2023-July/005993...

It is a known caveat that virtual threads do not work well with long running synchronization by pinning the thread. That unfortunately means that for many applications it may be premature to adopt them, but it is mature enough for broader evaluation by the libraries and frameworks. The Java team provided a status of their efforts recently [1].

https://www.youtube.com/watch?v=WoQJnnMIlFY&t=421s

Or the author’s simulator if you prefer C. See their hyperbolic for an example.

https://github.com/1a1a11a/libCacheSim/blob/develop/libCache...

That could work efficiently in a sampled caching policy. For example, Hyperbolic [1] maintains the frequency and insertion time on each entry and evicts the entry in the sample with the least utility value of frequency / (currentTime - insertionTime). For yours, you could easily add it to the SampledPolicy in this simulator [2] and run it against a few traces to see how it compares.

[1] https://www.usenix.org/system/files/conference/atc17/atc17-b...

[2] https://github.com/ben-manes/caffeine/wiki/Simulator

The problem with that approach is not only the time and effort to capture and analyze the trace, but that the workload changes over the application's lifetime. When the workload is expensive and important then cache analysis is worth doing, and there are cache simulators that are pretty easy to work with.

For the general case the ideal is an eviction policy that adapts to fit the given workload. Unfortunately adaptivity is not a very well explored area so most policies have heuristic settings that default to work well in a target range of workloads, but this has to be tuned for others. In this and the author's other paper, S3-FIFO, their lower hit rates with TinyLFU turned out to be due to the implementation. When running it with Caffeine, a productionized version that adds hill climbing and jitter, it had equivalent hit rates [1]. That cache is pretty robust across a wide range of workloads, but also much more complicated to implement. I'd really like to see more research on adaptivity because I think all policies are converging on similar structures and goals, but self-tuning is still an error prone art.

[1] https://github.com/Yiling-J/theine/issues/21#issuecomment-18...

Oh, thank you! I didn't realize that LRU Maintainer Thread was more than an expiration reaper. When it was first being introduced that was its first responsibility as lazy expiration removal by size eviction meant dead entries wasted capacity. It was all work in progress when I had read about it [1] and talked to dormando, so it got fuzzy. The compat code [2, 3] might have also thrown me off if I only looked at the setting and not the usage. Its a neat variant to all of these ideas.

[1] https://github.com/memcached/memcached/pull/97

[2] https://github.com/memcached/memcached/blob/9723c0ea8ec1237b...

[3] https://github.com/memcached/memcached/blob/9723c0ea8ec1237b...

Locking does not mean blocking. If you don't block the readers on the LRU reordering then it scales very well. That's a trick that's been in my production systems for 14 years now, and pretty much everywhere in Java land, that scales to over 900M reads/s on my laptop. Instead of probabilistic eviction you can use probabilistic reordering, e.g. via lossy sampling of the hits. The main benefit over sampled eviction or clock policies is that it is easier to use more robust and constant time algorithms.

Those guarantees are also what makes the algorithm exploitable and inflexible to handle unknown or adversary workloads. Your LRU example suffers in scan / loop / zigzag patterns, which the author's policies do poorly at as well. They target CDNs workloads where that can be ignored there due to its scale, but that is not a generalizable assumption for other workloads where it more common like databases, search, and analytics.

If the algorithm is known and accepts user facing requests then it becomes a target. A client can use the network speed of a dialup modem to bring down a modern server simply by crafting a request pattern to exploit hash flooding. This is why you generally want some injected noise, adaptivity, and use an algorithm that offers robustly good hit rates. A specialized policy that is superior in a narrow set of workload is still very useful when targeted at an expensive problem, but that's a design assumption that few can reasonably make.

Unfortunately most researchers do not consider attack vectors and often consider inputs that do not meet their preferred examples to be invalid. If a hostile user is able to pollute the cache so that it significantly degrades then that exploit becomes an easy denial of service attack. It is somewhat out of scope, but means that more general robust algorithms are needed because most users won't fine tune a system for a bespoke algorithm and instead take an off-the-shelf solution. I am therefore not a big fan of these minor tweaks to historical algorithms by making a one or two line change and therefore only slightly modifying what it is good or bad at. I try for more holistic solutions, even if a small percent worse in some cases, and infuse randomness to avoid deterministic exploits. To me that's more worthwhile and a big factor in whether it is a research toy or production-grade engineering.

Yes, basically you sample requests to improve concurrency and rely on the hottest entries to be more frequently observed in the sample.

Memcached uses 60s intervals between promotions and a try-lock guard. A small variation is to do this probabilistically using a thread-local random.

Caffeine (BP-Wrapper) decouples the event from the policy by recording into an array of ring buffers hashed to by the thread id. This serves to spread out contention and drains them under a try-lock to update the eviction policy. When the buffers fill up to quickly then it will drop events instead of blocking. This allows the cache to shed load by reducing the sample quality if a burst of activity.

Sieve is a very slight modification to the classic Clock algorithm (1969, Multics) which is a well known and commonly used pseudo LRU. The clock hand is a cursor to scan from and to insert behind, where instead they separated it to maintain FIFO insertion order. Clock and its variations are probably the most commonly used caches, e.g. Linux's page cache and Postgres' buffer pool. Sieve decoupling the hand from the insertion point so that new arrivals are evicted sooner, so the benefit is very workload dependent.

Sampled policies are another common policy type, e.g. where the timestamp is updated on access. Then on eviction a random subset is chosen and a utility function discards the least valuable. Since there are no promotions it is nice for simple concurrent caches and mimics a classic lru or lfu policy.

In short, a concurrent cache will not promote synchronously on every access event. That is only done as a strawman comparison for a simple baseline, though its actually good enough for many simple use-cases. It would be very misleading if researchers pretended that is how concurrent LRU-style caches are implemented.

/u/someplaceguy,

Those LIRS traces, along with many others, are available at this page [1]. I did a cursory review using their traces with Caffeine's and the author's simulators to avoid bias or a mistaken implementation. In their target workloads Caffeine was on par or better [2]. I have not seen anything novel in this or their previous works and find their claims to be easily disproven, so I have not implement this policy in Caffeine’s simulator yet.

[1]: https://github.com/ben-manes/caffeine/wiki/Simulator

[2]: https://github.com/1a1a11a/libCacheSim/discussions/20

I think you may be right. The library author said he made many changes because implementing the eviction policy following the paper's design was pretty awful.

> 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.

> In summary, I completely disagree about the scalability advantage of S3-FIFO over the other policies

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

https://github.com/Yiling-J/theine-go/issues/29#issuecomment...

I found sorting by recency to be helpful to see what mistakes users would make. There is not much feedback in open-source until after an api is released, at which point it is usually too late to fix problems. Seeing what users did, what frustrated them, and providing feedback helped make a better library. That's typically what internal teams get to do on a large corpus, like google3, and github is equally excellent for these insights.

An alert on recently indexed content that matches keyword subscriptions, ala google alerts, would be an excellent alternative for that use-case.

Oh interesting. Typically the gradle release notes, like 8.4-rc-1, will have comments that imply that Groovy build scripts compile but Kotlin ones lag.

"Gradle now supports using Java 21 for compiling, testing, and starting other Java programs. This can be accomplished using toolchains. Currently, you cannot run Gradle on Java 21 because Kotlin lacks support for JDK 21. However, support for running Gradle with Java 21 is expected in future versions."

https://docs.gradle.org/8.4-rc-1/release-notes.html#support-...

Kotlin, not Groovy, has been the culprit for slower Gradle support. I believe there was some split module pain in Groovy wrt Java 9, but it has been very smooth since then. The Kotlin compiler on the other hand is not very forgiving.

This is a moot point because your the build execution and the project compile/run can be on different JDKs. It is a tiny amount of configuration to decouple them, e.g. to use an EA build.

qlio [1] was a really elegant implementation of this pattern before it was named and popularized. That provided a nice decoupling of the FE/BE teams by allowing very quick iterations, with an early means to compose apis to simplify the marshalling.

[1]: https://tech.ebayinc.com/engineering/announcing-ql-io

not to distract from your valid points but, when used properly, Caffeine + Reactor can work together really nicely [1].

[1]: https://github.com/ben-manes/caffeine/blob/master/examples/c...

It is sad that Googling didn't find the answer by ChatGPT did.

---

Here's an excerpt from the book "Java Threads" by Scott Oaks and Henry Wong, published by O'Reilly Media, which discusses green threads:

"Green threads provide a thread abstraction to the application, allowing the programmer to write multithreaded programs without worrying about the underlying OS support. However, because they're implemented at the user level, they are not subject to preemptive multitasking by the underlying OS. Instead, they must voluntarily yield control to other threads. If a green thread fails to do this, it can effectively freeze all other green threads in the system."

This excerpt supports the fact that green threads were not preemptive and relied on voluntary cooperation to switch control between threads.

I don't think VTs should be used in practice until Java 22, when it is likely that synchronization (monitors) will be supported [1]. A lot of code may synchronize and be non-trivial to convert to a ReentrantLock, such as ConcurrentHashMap's computeIfAbsent. This can lead to surprising failures outside of the application author's control, such as [2].

Go was originally non-preemptive ("the loops problem"). This was changed in 2019 to preempt at safepoints [3]. The Java team will probably have to do this too [4], but similarly it is low on their priority list and requires feedback.

java.util.concurrent is still the basis of good Java concurrency. Some external libraries for reactive or actors might become less popular, but they were always the minority. There will be some improvements with structured concurrency to make that a little bit easier, but the fundamental approach will remain the same. I think old advice will be relevant, except when it comes to thread pool sizing (which was always a black art). At best some over eager use of async will go away and we'll return to simpler blocking code.

[1] https://github.com/openjdk/loom/commit/24e80bdee3eaf347f2eab...

[2] https://mail.openjdk.org/pipermail/loom-dev/2023-July/005990...

[3] https://go.dev/src/runtime/preempt.go

[4] https://github.com/openjdk/loom/tree/preempt-support

[5] https://openjdk.org/jeps/453

To clarify, the 1% window was a heuristic that we recommended in the first paper a a good default for most workloads. However we showed that sometimes a larger window was needed, and concluded that as future work.

The follow up paper, which you also cite, explored adaptive techniques to resolve this deficiency. From there we introduced the idea of using hill climbing by monitoring the hit rate change over a sample period and adjusting the step direction. Caffeine incorporates this with a step size decay to allow for convergence. The implementation that you have does not include this improvement, but it is very simple to add and works surprisingly well.

Yes, I think that is my main concern in that often research papers do not disclose the weaknesses of their approaches and the opposing tradeoffs. There is no silver bullet.

The stress workload that I use is to chain corda-large [1], 5x loop [2], corda-large at a cache size of 512 entries (6M requests). This shifts from a strongly LRU-biased pattern to an MRU one, and then back again. My solution to this was to use hill climbing by sampling the hit rate to adaptively size of the admission window (aka your FIFO) to reconfigure the cache region sizes. You already have similar code in your CACHEUS implementation which built on that idea to apply it to a multi-agent policy.

Caffeine adjusts the frequency comparison for admission slightly to allow ~1% of losing warm candidates to enter the main region. This is to protect against hash flooding attack (HashDoS) [3]. That isn't intended to improve or correct the policy's decision making so should be unrelated to your observations, but an important change for real-world usage.

I believe LIRS2 [4] adaptively sizes their LIR region, but I do not recall the details as a complex algorithm. It did very well across different workloads when I tried it out and the authors were able to make a few performance fixes based on my feedback. Unfortunately I find LIRS algorithms to be too difficult to maintain for an industry setting because while excellent, the implementation logic is not intuitive which makes it frustrating to debug.

[1] https://github.com/ben-manes/caffeine/blob/master/simulator/...

[2] https://github.com/ben-manes/caffeine/blob/master/simulator/...

[3] https://github.com/ben-manes/caffeine/blob/59df43e522686b707...

[4] https://github.com/zhongch4g/LIRS2

In a shifting workload their algorithm achieves a 0.01% hit rate whereas LRU, ARC, and LIRS have a 20% hit rate and adaptive W-TinyLFU has an almost 40% hit rate.

You have a large corpus of similar workload patterns. Simply using a 750GB trace or many samples from a cluster of machines doing the same work does not make it a meaningful variety. It would be reasonable to have also tested with the traces that your comparison algorithms used, which shows your implementations are valid and how they differ on those authors terms. Skipping that may come across as cherry-picking because I find that QDLP under performs by -20% in zigzag, -15% in DS1, -33% in blockchain mining. Your algorithm is good in specific cases, like many others are, but there are many real workloads where it is not usable.

The LIRS papers do a good job of taking different workload patterns, such as loop and zig-zag and mixing multiple patterns together, to validate that their algorithm is robustly good as a general purpose cache. This seems to take traces with similar workload patterns that are distinguished by their excessive size to assert the algorithm's quality. When papers do this it looks good from an academic sense, but it is frustrating from an industry perspective because the workload may not be known upfront or the one must cherry-pick an algorithm for a bespone, consistent pattern. I find it more interesting when algorithm designers try to stress their work and discuss how/why it fails or succeeds. That gives more confidence to those of us who want to implement and use the work in a practical setting.

> Nondeterministically? Or maybe it was deterministic that "test" won over "main" because it was lexicographically larger?)

Java uses classpath ordering for resolution, so a duplicated fully-qualified class name will take the first on the path. This was useful when patching or pre-dependency management, when some library authors would bundle into a fat jar with incompatible versions. It became disallowed by Java 9's modules without command-line flags. It was always considered a bad practices and a natural fallout of the dynamic nature of the JVM. In your case test classes were resolved before main sources and libraries.

Unfortunately there is a broad view that Java == Spring. In over 15 years of full time Java development, I only used Spring Framework 1.x and 2.0 (migrating from pre-DI). Since then my employers and network all used Guice, though I never selected a role where I realized that choice upfront. That framework is far less magical and explicit, making it very easy to debug. I suppose tool popularity is regional, it's just that this type of Spring magic is abnormal and disliked throughout my work experience.

You can use native memory tracking to better inspect offheap usages. I had a similar problem where the default MaxMetaspaceSize was excessive and adjusted it to a reasonable setting.

-XX:NativeMemoryTracking=summary

jcmd <pid> VM.native_memory summary

You might enjoy the alternative approach taken by .NET's threadpool which uses hill climbing to dynamically adjust the number of threads. See this articles [1] and its references to Microsoft's papers on their design. Semi-relatedly, I used hill climbing to adjust the eviction policy in Caffeine (Java cache) to favor recency/frequency. While it seemed simple and naive, it worked surprisingly well and robustly.

[1] https://mattwarren.org/2017/04/13/The-CLR-Thread-Pool-Thread...

Support for Markdown-based JavaDoc has been available since at least 2009 via multiple implementations [1, 2]. There have been many extensions thanks to the doclets api. The difference here is that Markdown will be included in the standard doclet and supported by the Java team instead of a 3rd party. Kotlin has few innovations and is rarely a source of inspiration for Java changes, e.g. Jetbrain's often called Scala a research language that they borrowed heavily from to design an industry language.

[1] https://code.google.com/archive/p/markdown-doclet

[2] https://github.com/Abnaxos/markdown-doclet

Another to add to your collection, https://github.com/yahoo/Oak

Caffeine doesn't offer off-heap maps or primitive collections (many other great libraries do). It does use a data sketch for compact frequency storage and optimizes against the cpu cache line to avoid unnecessary memory accesses. There are many dimensions to being hardware efficient.