fose: A flat combining primitive for Java (looking for review)

[u/Polixa12]

Hi, so I've been building fose, an open source flat combining primitive for Java. As of now, it is not released as a library, so you'd have to clone the repo to try it.

The idea comes from the 2010 SPAA paper. You wrap a sequential object and submit operations against it. If the lock is free, your thread runs its own op. If it's contended, the op is published to a queue and the current lock holder applies it on your behalf with the main benefits being reduced cache coherence traffic and sometimes opportunities for batching

Currently, I've only benchmarked it with JMH against a StampedLock write lock baseline on my 4-core i5 (Windows), a heap benchmark with some work between operations showed about 60-70% lower avg latency at 4+ threads. These are averages only and I haven't measured latency across different percentiles. I also haven't tested on Linux or on more cores. Currently, correctness tests use Lincheck

I'd especially like feedback on:

• If executing operations out of order in certain scenarios as a means to improve perf is acceptable
• The backoff heuristic which uses missed lock acquisitions as a guess at queue depth
• Also, whether the benchmarks are fair, and what baselines I'm missing. Also, if you can run the benchmarks on your machine and lmk the results, that'd be useful as well

I'd be interested to hear whether it fits anything you're working on, and what might be missing.

Repo: https://github.com/kusoroadeolu/fose

[u/lpt_7]

The application of this technique depends on whether the thread has spare time to process more elements. If other threads overwhelm a single thread, it may essentially block forever, unable to make progress.

[u/Polixa12 → u/lpt_7]

Yeah that's true, however, to prevent this, the combiner is capped at a fixed number of operations, after which it releases the lock and another thread can take over.

[u/its4thecatlol]

Seems very similar to the “helping” idea behind wait free algorithms. In your example, how do you prevent the lockholder from processing infinitely many queue elements? Does it eventually pass off the lock after N (finite) steps? Also, how do you synchronize the queue itself? Doesn’t the queue itself need a lock?

The core idea behind wait free algorithms is a linked list of operations with a quick CAS on the head to put/get combined with “helping” from other threads. The problem is it tends not to beat simpler lock free or even lock based algos, and uses a ton of memory.

[u/hakdogan75]

Nice work, the design is clean. Out-of-order execution seems fine to me: the stalled thread's call is still pending, so its op can linearize after the ones that skipped ahead. You only lose FIFO fairness.

I ran a quick stress test locally (8 cores, macOS), not your JMH suite. Each op was a single counter increment with no work between ops. Correctness held up to 64 threads. Against ReentrantLock, it was about 2.5–3x slower overall, and at 32 threads p99.9 was about 1.1ms vs 0.24ms, with max about 70ms vs 2ms. That's the worst case for flat combining, and I'd add it to your benchmarks so readers can see where it stops paying off.

The tail is probably from parked waiters never being unparked; they only wake on the parkNanos timeout. I'd also add percentiles (SampleTime) and ReentrantLock/synchronized baselines.

[u/BullfrogCharming1202]

If you can't be bothered to release it to Maven Central, I can't be bothered to try it out

[u/chabala → u/BullfrogCharming1202]

Y'all are burying this, but it's not wrong. Publishing to Maven Central is a core skill for an open source library. This is a reasonable request.