NovaX

> Caffeine had the same latency as Moka across all percentiles at twice the throughput.

Caffeine's next release has roughly 25% higher read throughput, with unchanged write throughput, thanks to fixing a false sharing mistake. That won't be visible in real workloads, but is fun nonetheless (500M reads/s on 8 cores).

Go tried that [1], a failed experiment that was a complex NIH version of the generational hypothesis. They currently use a CMS-stye collector.

[1] https://docs.google.com/document/d/1gCsFxXamW8RRvOe5hECz98Ft...

Thanks for the corrected evaluation. Just for your awareness, the HotSpot team is working on offering a spectrum of AOT/JIT options under the Leyden project [1]. Currently one has to choose between either a fully open world (JIT) or closed world (AOT) evaluation. The mixed world allows for a tunable knob, e.g. pre-warmup by AOT while retaining dynamic class loading and fast compile times for the application. This will soften the hard edges so developers can choose their constraints that best fit their application's deployment/usage model.

[1] https://openjdk.org/projects/leyden

That is just a normal JVM with optional Graal components if enabled, but not being used. The default memory allocation is based on a percentage of available memory and uncommitted (meaning its available for other programs). When people mention Graal they mean an AOT compiled executable that can be run without a JVM installed. Sometimes they may refer to Graal JIT as a replacement for C1/C2 available also in VM mode. You are using a plain HotSpot VM in server mode, as the optimized client mode was removed when desktop use-cases were deprioritized (e.g. JWS discontinued).

In both the asMap() view unwraps the opinionated Cache facade to the underlying bounded map.

There are a lot of little gotchas so it is best to not believe your own results until proven otherwise. A Rust influencer wrote EVMap, eagerly giving a talk about its performance equaling concurrent maps while being much simpler. However since he generated the random numbers as part of the test loop, he did not realize that it uses a lock to compute the next seed. This throttled the benchmark to make the faster maps slower as they created more contention, fully invalidating and inverting the results. Sadly since this was presented as part of a PhD such truths are of little importance and the false claims continue to be shown. That's just to share how innocent mistakes are the norm, but incentives to not correct them are doubly so, and that you should never trust your own results until you've exhausted all attempts to disprove them as invalid.

Sounds like you have the right perspective and a great attitude. Feel welcome to ping me if you run into any troubles or questions as I collab'd on Guava's cache and wrote Caffeine.

This was a good attempt but flawed.

1. You should use JMH to handle warmup, jit, timings, averaging of runs, etc. You might enjoy the following talks on the subject, though I am sure there are other gems out there.

- Performance Anxiety: https://wiki.jvmlangsummit.com/images/1/1d/PerformanceAnxiet...

- Benchmarking for Good: https://www.youtube.com/watch?v=SKPdqgD1I2U

- (The Art of) (Java) Benchmarking: https://shipilev.net/talks/j1-Oct2011-21682-benchmarking.pdf

- A Crash Course in Modern Hardware: https://www.youtube.com/watch?v=OFgxAFdxYAQ

- How NOT to Write a Microbenchmark https://www.slideshare.net/slideshow/2002-microbenchmarks/28...

- Anatomy of a flawed microbenchmark https://web.archive.org/web/20110513090823/http://www.ibm.co...

2. An uncontended lock is basically free, as you noticed.

3. Guava does implement the Map interface via asMap(). It also have a concurrencyLevel to adjust its performance. It is based on Java 5's CHM.

4. Caffeine is a Guava Cache rewrite based on Java 8's CHM rewrite, plus many learnings. You might look at its benchmarks for ideas: https://github.com/ben-manes/caffeine/wiki/Benchmarks

5. Data structures are surprisingly tricky. For example see this analysis showing an accidental misunderstanding degrading an LRU to O(n) eviction. https://gist.github.com/ben-manes/6312727adfa2235cb7c5e25cae...

6. It is important to remember that the goal of a benchmark is never which is faster or by how much. It is to ask (a) is it fast enough? (b) might I reach a point where it will not be? and (c) does it degrade unexpectedly? == This is to say the winner is of little interest, once all the choices are good enough then it is about usability, features, documentation, friendliness, and so on.

How about the senior engineer level error of forking Doug Lea's concurrent data structures only to make them operate in worst-case time complexity? Found this doozy recently.

[1] https://gist.github.com/ben-manes/6312727adfa2235cb7c5e25cae...

I think the idea is that the cache is so large that hot data won't be forced out by one-hit wonders. In this 2017 talk [1], the speaker says that Twitter's SLA depends on having a 99.9% hit rate. It is very common to have extremely over provisioned remote caching tier for popular sites. That makes eviction not as important and reducing their operational costs comes by purging expired data more proactively. Hence, memcached switched from away from relying on its LRU to discard expired entries to using a sweeper. Caffeine's approach, a timing wheel, was considered but dormando felt it was too much of an internal change for memcached and the sweeper could serve multiple purposes.

[1] https://www.youtube.com/watch?v=kxMKnx__uso

You might be interested in this thread [1] where I described an idea for how to incorporate the latency penalty into the eviction decision. A developer even hacked a prototype that showed promise. The problem is that there is not enough variety in the available trace data to be confident that a design isn't overly fit to a particular workload and doesn't generalize. As more data sets become available it will become possible to experiment with ideas and fix unexpected issues until a correct, simple, elegant design emerges.

[1] https://github.com/ben-manes/caffeine/discussions/1744

As the article mentions, Caffeine's approach is to monitor the workload and adapt to these phase changes. This stress test [1] demonstrates shifting back and forth between LRU and MRU request patterns, and the cache reconfiguring itself to maximize the hit rate. Unfortunately most policies are not adaptive or do it poorly.

Thankfully most workloads are a relatively consistent pattern, so it is an atypical worry. The algorithm designers usually have a target scenario, like cdn or database, so they generally skip reporting the low performing workloads. That may work for a research paper, but when providing a library we cannot know what our users workloads are nor should we expect engineers to invest in selecting the optimal algorithm. Caffeine's adaptivity removes this burden and broaden its applicability, and other language ecosystems have been slowly adopting similar ideas in their caching libraries.

[1] https://github.com/ben-manes/caffeine/wiki/Efficiency#adapti...

Yep, no bots. A real bug not only means that I wasted someone else’s time, but reporting is a gift for an improvement. If a misunderstanding then it’s motivation that my project is used and deserves a generous reply. This perspective and treating as strictly a hobby, rather than as a criticism or demand for work, makes OSS feel more sustainable.

Thanks Jonathan!

I tried to reimplement Linux’s algorithm in [1], but I cannot be sure about correctness. They adjust the fixed sizes at construction based on device’s total memory, so it varies if a phone or server. This fast trace simulation in the CI [2] may be informative (see DClock). Segmentation is very common, where algorithms differ by how they promote and how/if they adapt the sizes.

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

[2] https://github.com/ben-manes/caffeine/actions/runs/130865965...

Doesn’t reddit use Cassandra, Solr, and Kafka which uses Caffeine?

I've resorted to using Cmd-Shift-J (scrollback buffer) and grepping that, but its flaky about whether it will honor the command and emit a history file.

That’s in the works, where it adapts from 16mb to terabyte heaps. The current GCs have a max, with lazy allocation and ability to release back to the system periodically, but are not as system aware.

1. https://openjdk.org/jeps/8329758

2. https://m.youtube.com/watch?v=wcENUyuzMNM&embeds_referring_e...

It will likely become available for application developers to use. At work, we use it to assist warehouse checkins by allowing the guard to take photos of the truck, paperwork, seal, etc and fill out the forms going in and out. If built-in then it can be run on-device, so over time a lot more workflows can be seamless.

Endian indicates the byte order (MSB->LSB, LSB->MSB), but does not change the representation of a bit. The conditional logic says that an even result is 32 and an odd is 0 after a modulus two. In binary that (x & 1) is 0 for even and 1 for odd. When you shift by 5 that is 0 for even and 32 for odd, which is the opposite of the conditional logic. This is why I suggested using a binary NOT to flip the bits so that you get the same result as the original.

I believe it is (!i & 32) because the bitwise version is an incorrect rewrite.

[1] https://news.ycombinator.com/item?id=41830016

I'm confused because isn't the bitwise version the inverted logic? If the LSB is 1 then it is an odd value, which should be zero, yet that is shifted to become 32. The original modulus is for an even value becoming 32. Shouldn't the original code or compiler invert it first? I'd expect

    let shift = ((~(i >> 5) & 1) << 5);

EDIT: The compiler uses "vpandn" with the conditional version and "vpand" with the bitwise version. The difference is it includes a bitwise logical NOT operation on the first source operand. It looks like the compiler and I are correct, the author's bitwise version is inverted, and the incorrect code was merged in the author's commit. Also, I think this could be reduced to just (~i & 32).

Oh thank you, I’m glad it’s been helpful.

One optimization for background refresh is coalescing the individual reloads into a batch operation based on a time/space window. Here is how we do it in the Java world. [1]

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

In a typical LRU cache every read is a write in order to maintain access order. If this is a concurrent cache then those mutations would cause contention, as the skewed access distribution leads to serializing threads on atomic operations trying to maintain this ordering. The way concurrent caches work is by avoiding this work because popular items will be reordered more often, e.g. sample the requests into lossy ring buffers to replay those reorderings under a try-lock. This is what Java's Caffeine cache does for 940M reads/s using 16 thread (vs 2.3B/s for an unbounded map). At that point other system overhead, like network I/O, will dominate the profile so trying to rearrange the hash table to dynamically optimize the data layout for hot items seems unnecessary. As you suggest, one would probably be better served by using a SwissTable style approach to optimize the hash table data layout and instruction mix rather than muck with recency-aware structural adjustments.

The fastest retrieval will be a cache hit, so really once the data structures are not the bottleneck then the focus should switch to the hit rates. That's where the Count-Min sketch, hill climbing, etc. come into play in the Java case. There's also memoization to avoid cache stampedes, efficient expiration (e.g. timing wheels), async reloads, and so on that can become important. Or if a dedicated cache server like memcached, one has to worry about fragmentation, minimizing wasted space (to maximizing usable capacity), efficient I/O, etc. because every cache server can saturating the network these days so the goals shifts towards reducing the operational cost with stable tail latencies. What "good performance" means is actually on a spectrum because one should optimize for overall system performance rather than any individual, narrow metric.

Nope, I used the default in your github repository (10_000_000). From a quick profile it looked like previous benchmark allocations where crossing into later runs, who were then penalized unfairly, so I made those small adjustments.

Adding Guava testlib's GcFinalization.awaitFullGc() before a benchmark run and -XX:+UseParallelGC, I saw the runtimes decrease by 30s in Bench_Fury_Ordinal and 20s in Bench_ObjectOutputStream. Ideally you would run using JMH to avoid jit warmup issues, previous runs, etc from polluting your results.

The two articles on your epoll command queuing and prefetching have a lot of similar observations to the BP-Wrapper approach [1], so you might find that to be an interesting paper to read. That is used by Caffeine cache [2, 3] which uses a concurrent hash maps with lossy striped ring buffers for reads and lossless write buffer to record & replay policy updates. On my M3 Max 14-core, a 16 thread in-process zipf benchmark achieved 900M reads/s, 585M r/w per s, 40M writes/s (100% hit rate, so updates only). Of course the majority of your cost is your I/O threads but there are a few fun ideas nonetheless.

[1] https://dgraph.io/blog/refs/bp_wrapper.pdf

[2] https://highscalability.com/design-of-a-modern-cache/

[3] https://highscalability.com/design-of-a-modern-cachepart-deu...

In the example the DatabaseSetup is an existing task type that is registered under a new name. Since that has an action body, the doFirst and doLast append logic to run around that. Thus, after setting up the database it then runs a migration and code generator phase. The more straightforward way is to define a new task and use a dependsOn relationship.

    val databaseSetup = tasks.register<DatabaseSetup>("databaseSetup")
    tasks.register<GenerateJooq>("generateJooq") {
      dependsOn(databaseSetup)
    }

    class GenerateJooq : DefaultTask() {
      @TaskAction fun run() {
        println("Now migrating")
        migrate()
        jooqGenerate()
      }
    }

It is more code to define the custom task, but then allows for adding command-line input options. The doFirst / doLast are script shortcuts for quick proof-of-concept projects, whereas custom tasks are preferred for maintainability of long-lived ones.

RedisLabs actually was a somewhat hostile takeover of the project by a complete outsider. It commercialized Redis prior, kept trying to trademark the project name, change the company name to RedisDB to confuse users. A few of those attempts were halted by antirez and the community, but after they had thousands of customers he relented. At the time he complained about his own financial challenges and reluctance, but it gave him a just reward at the cost of legitimizing RedisLabs. The history of that company was always as exploitive to Redis OSS and feigning being good citizens. While you may be right in general, this is actually a case of those exploiting OSS winning.

Perhaps it’s better to say that they are not yet general purpose. There are many caveats which need to be resolved and are being actively worked on. I would not use them broadly yet, but that could change rapidly.

A monitor will pin the VT to the carrier thread. That can have surprising incompatibility in the current jdk. Soon these footguns will be fixed and you can use them worry free.

https://www.reddit.com/r/java/comments/1512xuo/virtual_threa...

By long running I just meant anything that was not fast compute. I was more focused on finding the reference link so I agree my wording wasn’t clear.

Go started without preemption and added it later. The Java team has indicated a similar path, so we might see that tackled in the future. I think they could do that using safe points or JEP 312‘s handshakes, so it’s not infeasible.

For file io they wanted to explore io_ring and they might need to add a loom friendly resolver for JEP 418. There is just so much left, like scalable timers, that I think it’s going to be a long time until VTs will be a good default choice.