From: Peter Zotov <whitequark@...>
Date: 2011-12-17T08:14:41+09:00
Subject: Re: ruby 1.9 threading performance goes non-linear

Eric Wong писал 17.12.2011 03:05:
> 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().

Yes, RARRAY_PTR will break. This is unacceptable.

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

I'm not sure that a pure Ruby implementation will be even nearly as 
efficient
as Array on MRI. How would you implement it?

-- 
   WBR, Peter Zotov.