eventmachine/eventmachine — pull request #311 by grddev (2012-04-03 19:33:58+00:00)
Title: Reimplement Queue to avoid shift/push performance problem

The existing EM::Queue implementation uses push and shift to shuffle the queued items through an array. Unfortunately, a shift followed by a push has linear time complexity in the size of the array, making queue operations very expensive for long queues.

The patch replaces the @items array with two separate arrays @sink for pushing elements into it and @drain for shifting out elements. This ensures that both push and shift get amortized constant time complexity.

In addition, the patch introduces a test that demonstrates the performance issues. For me, the new test passes with both Queue implementations, but takes minutes with the old implementation and much less than a second with the new implementation.