Evaluate performance of O(N) insertion

[ioquatix]

https://github.com/celluloid/timers/blob/8854e191d3b36df0602245d6f9523c3ef004c0fc/lib/timers/events.rb#L61

I found this was generally acceptable because insert is fast for small arrays. For HUGE numbers of timers, this might be a bottleneck. Perhaps a segmented array or deque might be more appropriate. However, anything implemented in pure ruby is likely to be slower.

[ioquatix]

@digitalextremist @takiy33 if you want to tackle some performance issues here is a good one to review.

Step one is to profile the code in question using the performance benchmarks and perhaps make other benchmarks to see if and when it becomes a problem. Step two is to see if there is any decent way to improve performance. Technically, some kind of tree (i.e. a min-heap) might be appropriate, but pure ruby for this data structure is slow compared to insert from my tests about a year ago..

[ioquatix]

Timers::Group
Serviced 192065 events in 8.354132437 seconds, 22990.44130157285 e/s.
Thread ID: 9851640
Fiber ID: 32710700
Total: 8.350259
Sort by: self_time

 %self      total      self      wait     child     calls  name
 35.57      5.914     2.970     0.000     2.944   202100   Timers::Events#bisect_left 
 21.44      2.944     1.790     0.000     1.154  2595479   Timers::Events::Handle#> 
 13.81      1.153     1.153     0.000     0.000  2595010   Timers::Events::Handle#to_f 
  5.01      6.918     0.418     0.000     6.500   202065   Timers::Events#schedule 
  4.09      7.400     0.342     0.000     7.058   202065   Timers::Timer#reset 
  3.86      7.559     0.322     0.000     7.237   192065   Timers::Timer#fire 
  3.00      0.250     0.250     0.000     0.000   202065   Array#insert 
  2.24      7.746     0.187     0.000     7.559   192065   Timers::Events::Handle#fire 
  1.75      0.146     0.146     0.000     0.000   202065   Timers::Events::Handle#initialize 
  1.67      0.678     0.140     0.000     0.538   212077  *Class#new 
  1.55      0.129     0.129     0.000     0.000   192065   Proc#call 
  1.31      7.856     0.110     0.000     7.746       35   Array#reverse_each 
  1.05      0.087     0.087     0.000     0.000   192065   Timers::Events::Handle#cancel! 

So here is the interesting data. If you look at Array#insert, it's actually relatively minor. The elephant in the room is bisect_left, which while significantly faster than the previous implementation, is now simply the slowest part and thus warrants the most attention. Personally, I don't know if it's possible to write a better implementation in pure Ruby. It's something I did spend some time considering, but the next step might be writing it in C.

[ioquatix]

I believe performance is good enough in practice.