Eric Wong ڧѧ 17.12.2011 02:27:
> 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.

I wonder if we can make a more efficient Array by making it a circular 
buffer,
so that #shift and #pop would always be O(1), and #unshift and #push be
O(n) only if the array grows bigger. Are there any implications I don't 
see?

>
> 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.

-- 
   WBR, Peter Zotov.