On Fri, Dec 16, 2011 at 4:27 PM, Eric Wong <normalperson / yhbt.net> wrote:
> Part of the problem is the Queue in MRI 1.9.x uses an Array internally.
> Calling Array#shift is expensive on larger Arrays as it needs to move
> all the unshifted elements. Using a linked list as the insternal
> structure should improve things.
>
> The array was growing larger due to thread scheduling being different
> and less likely to switch threads.
>
> I think there was an implementation of Queue for 1.9 in
> bugs.ruby-lang.org in C which may improve things, but I think there
> are some improvements to the Ruby-only version Queue that can be
> fixed.

FWIW, JRuby's Queue is implemented in Java, primarily because we it's
faster to use Java's synchronization primitives directly. And indeed,
it uses a LinkedList.

- Charlie