benjchristensen/RxJava — pull request #10 by akarnokd (2014-12-04 15:29:23+00:00)
Title: RxRingBuffer enhanced performance and some measurements.

I apologize if I flood you or the project with PRs, I'll respect a backpressure if necessary.

I've repost this PR because the original didn't actually work, but now I'm more confident this works.

I've implemented 3 resizing atomic array queues:
- ```AtomicArrayQueue``` with plain java atomic classes (aaqn)
- ```AtomicArrayQueueUnsafe``` with Unsafe atomics (aaqu)
- ```AtomicArrayQueuePadded``` with element padding, but no field padding. (aaqp)

and benchmarked them against SpscArrayQueue (spaq) and SpscLinkedQueue (spsc):
```
Benchmark Mode Samples Score Score error Units
r.i.RP.aaquCreateUseAndDestroy1 thrpt 5 27520602,070 504571,165 ops/s
r.i.RP.aaquCreateUseAndDestroy1000 thrpt 5 662582,205 64579,721 ops/s
r.i.RP.aaquRingBufferAddRemove1 thrpt 5 84642026,650 2470577,363 ops/s
r.i.RP.aaquRingBufferAddRemove1000 thrpt 5 475414,152 9822,705 ops/s

r.i.RP.aaqpCreateUseAndDestroy1 thrpt 5 17584287,989 597101,740 ops/s
r.i.RP.aaqpCreateUseAndDestroy1000 thrpt 5 267384,086 6985,954 ops/s
r.i.RP.aaqpRingBufferAddRemove1 thrpt 5 52889272,696 590511,776 ops/s
r.i.RP.aaqpRingBufferAddRemove1000 thrpt 5 360241,617 6047,325 ops/s

r.i.RP.aaqnCreateUseAndDestroy1 thrpt 5 23171385,086 448760,659 ops/s
r.i.RP.aaqnCreateUseAndDestroy1000 thrpt 5 318566,102 6294,829 ops/s
r.i.RP.aaqnRingBufferAddRemove1 thrpt 5 54069982,058 758327,742 ops/s
r.i.RP.aaqnRingBufferAddRemove1000 thrpt 5 375933,487 6271,312 ops/s

r.i.RP.spscCreateUseAndDestroy1 thrpt 5 10959175,709 113356,136 ops/s
r.i.RP.spscCreateUseAndDestroy1000 thrpt 5 314820,879 4632,766 ops/s
r.i.RP.spscRingBufferAddRemove1 thrpt 5 41398169,060 747113,735 ops/s
r.i.RP.spscRingBufferAddRemove1000 thrpt 5 327144,015 15522,612 ops/s

r.i.RP.spaqCreateUseAndDestroy1 thrpt 5 2990478,364 90732,967 ops/s
r.i.RP.spaqCreateUseAndDestroy1000 thrpt 5 732780,351 13201,861 ops/s
r.i.RP.spaqRingBufferAddRemove1 thrpt 5 108916574,580 1102474,342 ops/s
r.i.RP.spaqRingBufferAddRemove1000 thrpt 5 832670,999 9548,087 ops/s
```

The ```AtomicArrayQueueUnsafe``` was the quickest in the single-use scenario and performed quite well in the other cases. Removing the counters for the bounded queues gives great performance for improvement over the unbounded ```SpscLinkedQueue```. The worst singe-use was the ```SpscArrayQueue``` because one single allocation takes up large amounts of memory due to padding. In addition, in order to compensate for its look-ahead capability (which makes the effective queue capacity less), the capacity had to be doubled so ```MissingBackpressureException``` is not thrown. Otherwise, it shines in prolonged use with great performance. The normal-atomics ```AtomicArrayQueue``` gives good single-use and moderate prolonged use performance; it mostly outruns ```SpscLinkedQueue```. The ```AtomicArrayQueuePadded``` with its long class hierarchy seems to increase the instantiation cost. The spacing between the elements increase the cache/memory pressure in single threaded use.

So in conclusion, I'd go for ```AtomicArrayQueueUnsafe``` and ```AtomicArrayQueue``` as these give reasonable overall edge to the others. I'd say the lack of padding might not be of a big issue because in our scenarios, it is likely the one who offers the element will poll it as well.