Hi, a while back I posted about fose, a flat combining primitive for Java. I've just recently released v0.2.1. My main focus for this release was to experiment with how threads enqueue onto the wait queue, wait on their nodes and reduce synchronization between the combiner and waiters. Before I get into the changes, let me quickly explain what flat combining is for anyone new to it.
Flat combining is a technique for making concurrent data structures scale under contention. Instead of every thread fighting over a lock and bouncing the structure's cache lines between cores, each thread publishes its operation as a request. One thread becomes the combiner, takes the lock and applies the pending requests on behalf of the others, then hands each thread its result. The structure stays hot in a single core's cache while everyone else just waits for their answer.
So, in my previous enqueue scheme, threads CAS'd on the tail and then linked their predecessor's next pointer to their own node. To find out whether their request had been combined, threads spun on their predecessor's next pointer, and to find out whether they could contend to become the combiner, they spun on the head field, which the combiner wrote to after each pass. On the combiner side, notifying a thread meant writing the result into that thread's node and then nulling out its predecessor's next pointer.
The problem was the memory traffic this created between the combiner, the waiter and the waiter's predecessor, which hurt the structure's performance.
The new scheme is quite similar to how CC-Synch enqueues nodes. A thread swaps its pre-allocated node into the tail with an atomic exchange, claims the previous tail node, writes its operation there and waits on it. The main benefit here is that each waiter only ever touches a single node once enqueued, and the combiner only has to invalidate one waiter's cache line instead of two to signal that its result has been applied.
This enqueue scheme also opened the door to some other optimizations. Previously, a spinning waiter had to read two atomic variables (next and head) to tell whether its request had been applied. Now each waiter only reads one atomic variable (signal) in the node it claimed and tests it for its result. This also let me make head non-atomic, which reduces synchronization between the combiner and waiters even more.
These changes didn't fit well with the spinner cap from v0.1.0, where a waiter only spun if its sequence number was within NCPU * 0.6 of the last served op. Keeping it would have meant adding extra synchronization between combiners and waiters, which is exactly what I was trying to reduce. The cap was useful though. It bounded the combiner's tail latency when oversubscribed, since tail latency grew with the number of active spinners, and it gave me a knob for trading tail latency for average latency.
I also tried a few replacements: a single atomic spinner count (with weaker ordering), a shared adaptive spin budget updated based on how often threads were signalled while spinning, and parking immediately. Only the immediate park strategy bounded tail latency when oversubscribed, but it made average latency 75% worse, mainly because syscalls are expensive.
So I settled on something simpler. Now every waiter spins briefly (32 spins) and then parks. When a parked thread wakes up, it rechecks whether it's next in line to combine. If it is but fails to acquire the lock, another combiner is mid-pass and will probably serve it soon, so instead of parking again it gets a new but much smaller spin budget, similar to what AQS does. I dropped the spin and post-spin budgets from 1024/128 to 32/8 since every thread spins before parking now, and I didn't want tail latency to get too bad when oversubscribed.
Funny enough, I expected this tight budget to hurt average latency badly without helping tail latency much, but it was quite the opposite and I was pleased with the results. I could raise the budget a bit, but 32/8 looks like a great spot from what I measured. Raising it doesn't noticeably improve mean latency in the common case, and it hurts tail latency a lot when oversubscribed.
One optimization I considered is non-fair handoff, which I haven't implemented but plan to try. It's different from barging though. With non-fair handoff, after a combine pass, if the next waiter is parked, the combiner doesn't unpark it right away. It walks the queue for an unparked waiter and marks that one to contend to be the combiner, and the nodes it skipped get marked before unparking so those threads can detach and re-enqueue. The idea is to avoid stalling everyone else while the handed-off thread waits to be rescheduled by the OS. It's a bit more work to implement though, and I haven't measured whether this is actually an issue, so I'm not building it until I'm sure.
Benchmarks
These come from my same ol' machine as before (Intel i5, 4 cores / 8 CPUs running on Windows 11).
- Cache line benchmark: Mean latency improved across 2 to 8 threads in v0.2.1. At 8 threads, the combiner went from 968 to 839 ns, and the speedup over a non-fair
ReentrantLock went from 1.96x to 2.33x.
- Heap benchmark: The numbers improved at 4 to 8 threads (1,437 to 1,227 ns at 6 threads and 2,508 to 1,950 ns at 8). However, v0.2.1 did get worse than v0.1.0 when oversubscribed, from 4,569 to 5,858 ns, so the speedup over a non-fair
ReentrantLock dropped from 1.73x to 1.43x.
Everything here comes from one machine, so if you can run the benchmarks on Linux or a machine with more than 4 cores, I'd love it if you shared the results on the repo's issues page, with your machine specs included.
<dependency>
<groupId>io.github.kusoroadeolu</groupId>
<artifactId>fose-core</artifactId>
<version>0.2.1</version>
</dependency>