From: Eric Wong <normalperson@...>
Date: 2011-12-17T07:27:25+09:00
Subject: Re: ruby 1.9 threading performance goes non-linear

Joel VanderWerf <joelvanderwerf@gmail.com> wrote:
> Two threads connected by a queue, passing one fixnum at a time,
> doing trivial calculations. Run time should be linear in number of
> inputs, right? Well, yeah, for 1.8.7 and jruby, but not for 1.9.3p0.

> N.times do
>   100.times do |x|
>     q.push x

Adding "Thread.pass" after q.push seems to improve things as it
keeps the queue smaller.

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.