Netflix/RxJava — pull request #1145 by akarnokd (2014-05-05 11:10:03+00:00)
Title: Large CompositeSubscription performance improvements

This is a proposition to improve the addition/removal speed of the ```CompositeSubscription``` in case of thousands of items in it.

In some operators, especially when using Schedulers and/or observeOn, thousands of items may be present in the composite and since adding/removing a new item is O(n), it takes more and more time to add and remove items once the composite gets large.

My proposal is to change the composite state implementation to switch to a HashSet representation above a certain threshold (and switch back below some). The following diagram shows some benchmarking results. (Configuration: i7 920 @ 2.4GHz, 32K L1 Data, 256K L2, 8M L3, 6GB DDR3 1333MHz RAM, Windows 7 x64, Java 8u05 x64.)

![image](https://cloud.githubusercontent.com/assets/1269832/2877095/4779ac40-d443-11e3-9c0a-908ea49c6219.png)

This benchmark how the CompositeSubscription behaves when there are some items already in it and a new unique item is added and removed immediately (all single threaded). The blue line indicates the current master implementation; the red, green and purple show the new implementation with thresholds set to 8, 16 and 24 respectively. Once the internal array size reaches the cache-line size, it is generally better to use HashSet instead.

The second benchmark compares how fast can the CompositeSubscription be filled with subscribers to a various capacity, and how the target size affects the fill speed.

![image](https://cloud.githubusercontent.com/assets/1269832/2877162/afcb76a6-d444-11e3-8c4c-c3ba85e6c1d3.png)

When the composite is filled in, the one-by-one array resize performs better until a larger capacity is reached, but then again, using a HashSet to append further items is faster. Unfortunately, what seems to be an optimal threshold for the first case performs worse in this case.

There are some drawbacks of this hybrid approach:
- The optimal threshold value depends on the use case and the target system. How can we enable to tune this parameter. Parameter tuning could be handy in other places in RxJava; how can we enable it?
- I'm not 100% certain if I've correctly implemented the switchover from atomic states to mutable state and back.