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

Peter Zotov <whitequark@whitequark.org> wrote:
> Eric Wong писал 17.12.2011 02:27:
> >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?

It would require a lot of changes to existing C code in both Ruby itself
and C extensions that depend on RARRAY_PTR().

Better to start with a new data structure (implemented entirely in Ruby)
for an uncommon case.