Netflix/RxJava — pull request #1200 by akarnokd (2014-05-14 15:20:05+00:00)
Title: Scheduler dispatch algorithm and tests

Implemented an event loop scheduler based on thread pinning and work stealing for #1149. In addition, I've merged #1197, added tests and fixed a few minor issues.

Here are the comparative benchmark results using the ```MultipleObserversOnOneBusyObservable```JMH from #1197
```
Benchmark (NUM_INTEGERS) (schedulerIndex) Mode Samples Mean Mean error Units
runAll 50 0 thrpt 10 3012,015 176,800 ops/s
runAll 50 1 thrpt 10 32,035 0,014 ops/s
runAll 50 2 thrpt 10 2537,292 201,377 ops/s
runAll 50 3 thrpt 10 2452,117 60,938 ops/s
runAll 500 0 thrpt 10 296,673 4,419 ops/s
runAll 500 1 thrpt 10 32,037 0,011 ops/s
runAll 500 2 thrpt 10 211,382 21,754 ops/s
runAll 500 3 thrpt 10 246,312 3,714 ops/s
runAll 5000 0 thrpt 10 27,458 0,083 ops/s
runAll 5000 1 thrpt 10 32,070 0,238 ops/s
runAll 5000 2 thrpt 10 27,718 0,343 ops/s
runAll 5000 3 thrpt 10 21,415 0,289 ops/s
```

where 0 is the current computation scheduler, 1 is the balanced scheduler, 2 is the rerouting scheduler and 3 is the pinning scheduler. The reason for the 32 ops/s throughput of the balanced scheduler seems to be due to the drain loop, which made some self-scheduling tests run extremely slow. Adding the ```MAX_TIGHT_LOOPS``` improved on the test speed and the benchmark speed to 255 ops/s. I'm not sure why it is that slow.

I haven't run the other perf test, but run my own simple benchmark code: one that observes a single item 1M times and the other observes 16M items once. Results:
```
Algorithm Single Many
Current 1970 ns/item 117 ns/item
Balancing 30403 ns/item 110 ns/item
Rerouting 1979 ns/item 115 ns/item
Pinning 2122 ns/item 140 ns/item
```

The reason for the extra slowness of my implementation is the use of ```LinkedBlockingDeque``` as I need the ```offerFirst```, but ```ConcurrentLinkedDeque``` is in Java 7. In addition, the cost of waiting and parking is doubled.