Netflix/RxJava — pull request #1235 by akarnokd (2014-05-21 12:00:10+00:00)
Title: Lock-free, MPSC-queue based, fast-path serializing Observer.

I've rewritten the ```SerializedObserver``` to improve performance. It is now lock-free, uses a multiple-producer-single-consumer queue based on Netty's implementation and employs a fast-path logic for single-threaded write-through.

Benchmarked by measuring how fast 500k integers can get through it, if running 1-8 producers at the same time. For a single threaded case, master gives about 18 MOps/s, this implementation gives ~36 MOps/s (would be ~16 MOps/s on the slow path). For producers > 2, master gives ~5.5 MOps/s and this gives ~11.5 MOps/s. For 2 producers, aka 1 producer - 1 consumer, master gives ~4.5 MOps and this gives ~8.5 MOps/s.

The two new class, ```PaddedAtomicInteger``` and ```MpscPaddedQueue``` will come in handy with other lock-free structures such as Schedulers, etc. We may consider adding back the ```rx.util``` or some other sub-package to store these helper classes: they don't need to be part of the public API but can be left ```public``` to enable cross-package access internally.

Things I learned during the implementation:
- It is worth padding the wip counter to fit a cache line so the constant cache thrashing won't affect the parent class' other fields, most likely.
- Using FieldUpdaters saves space but ```sun.misc.Unsafe``` can add 8-10% more throughput. To avoid platform issues, I stayed with the FieldUpdaters.
- Using ```getAndIncrement``` and ```decrementAndGet``` are intrinsified in Java 8 and are compiled to a single x86 instruction, which generally outperforms any CAS loop. Same is true for the ```getAndSet```.
- Padding out the ```tail``` in the ```MpscPaddedQueue``` again helps separate producers trashing on the tail and a consumer reading the head. Without it, the throughput would decrease by about ~1.5 MOps/s
- By adding the fast-path logic, the single-threaded throughput increases by a factor of 2 since it avoids an unnecessary enqueue and dequeue and all associated volatile writes. However, if taking the fast-path fails, it incurs extra cost on the slow path for everyone else because of the +1 failed CAS at the start. To fix this case, I've introduced a flag that enables and disables fast-path. To disable the fast path, the active fast path checks if it was able to change wip to zero. If not, it means there was concurrent access and continues on the emission loop path, but disables the fast-path then on. It is basically a detector for concurrent use. Since such concurrent use may be transient, the loop counts how many elements it had to emit, an if it was only 1 or 2, it reenables the fast-path. This limit is the result of trying several values with the benchmark above.
- The fast-path logic has its weak spot in 2 producer case compared to a plain MPSC queue running in SPSC mode; the latter gives about ~11 MOps/s which is better than this implementation's ~8.5 MOps/s. In contrast, the single-treaded use for the plain MPSC is only ~16 MOps/s. Both implementations perform the same if producers > 2. Therefore, I decided it is more worth having an implementation that is weak for 2 producers but otherwise is as good or outperforms the alternatives. Note that if one knows the number of producers up front, one can create a more specialized implementation, but this is not the case with RxJava operators. This may affect ```merge``` and co which serialize multiple sources. Note however, that if the source speed isn't that high as in the benchmark, this implementation still provide less latency than the alternatives because the fast-path would be most likely open if the source emission is interleaved.