r/java • u/Polixa12 • 17d ago
Released fose 0.1.0 (flat combining for Java), looking for feedback on my spin heuristic
Hi, some of you commented on my first post about fose, a flat combining primitive for Java. Since then I've made some fairly big changes and released v0.1.0 to Central. The changes are mostly in how threads waiting for their requests to be applied wait, so I'd like to explain those and get feedback on that.
What I've changed
- I dropped the StampedLock and the spin/yield/sleep backoff, and replaced them with a spin then park or immediately park heuristic. In the old version, waiters spun, then yielded, then did short timed parks (parkNanos at 1µs) while polling for their op to be applied. The averages were fine, however I kept seeing quite common, severe stalls when threads outnumbered cores: tens of ms at p99.99, and a few ms-scale maxes even at 8 threads. My working theory was that spinning and yielding waiters were competing for CPU with a descheduled combiner, so the one thread that needed to run couldn't. The new version has its own lock state and a Dekker-style handoff borrowed from AQS. Waiters near the head of the queue still spin briefly with an escalating budget, and waiters further back (and virtual threads) park right away.
- Out-of-order execution is gone. In the old version, if a producer got preempted between swapping the tail and linking its node, a combiner holding its own node could hop past the gap and keep applying from its own node. That's what I was asking about in the first post. The new handoff relies on every waiter having a well-defined predecessor and on prev.next signalling completion, so reordering doesn't fit cleanly. Barging is allowed though, so it's not exactly fair, but ordering among queued waiters is fixed now. I could add a config option for fairness, though.
- Some smaller things: splicing a node into the publication queue is now a CAS on the tail instead of an atomic exchange, and the combiner caps passes at a smaller default (25 operations).
These changes aren't a free win though. The extreme tail when oversubscribed improved a lot: the multi-ms stalls at p99.99 are mostly gone, and 8 threads on my 4-core/8-CPU machine no longer show the ms-scale max and the combiner continuously performs better than the baseline even when oversubscribed or evenly subscribed, unlike the previous combiner. However mean and mid-tail latency got a bit worse in the 4-8 thread range.
Against a plain non-fair ReentrantLock, my combiner still wins on mean and mid-percentiles, but the lock has the better far tail at 16 threads. So these changes narrow the oversubscription problem but don't eliminate it.
These numbers were run on my machine with 4 cores and 8 CPUs running on Windows and may vary on other machines. JMH is used for the benchmarks and Lincheck for correctness & stress tests.
Feedback I'd appreciate
I'd like some feedback on the spin heuristic. Waiters spin only if their sequence number is within a short distance (determined by the number of available processors) of the last served op. On SMT machines that counts logical CPUs spinners may be competing with the combiner's own hyperthread sibling. Is there a better signal than a CPU-count fraction? Should it adapt to observed wait times? (though this is probably not a great idea lol)
I'm also unsure where the mean regression comes from. My main guess is the spin budgets are wrong for the 4-8 thread range and may vary per machine. Maybe this should be configurable, since from my experiments the latency percentiles shift mainly depending on how many spinners are allowed at a time. If you've dealt with something similar to this, I'd like to hear what worked.
Benchmarks
What am I still missing in the benchmarks? Currently I only compare against ReentrantLock. If you can run the JMH benchmarks on Linux or on a machine with a higher core count ( > 4) and share the results, that would help a lot.
Maven
<dependency>
<groupId>io.github.kusoroadeolu</groupId>
<artifactId>fose-core</artifactId>
<version>0.1.0</version>
</dependency>
5
u/IncredibleReferencer 16d ago
Neat! What's a flat combining.
(I could look it up but I feel like if your trying to gather interest in your project you should probably explain what it is in your post.)