[ruby-talk:6928] Re: Some performance issues

Ben Tilly <[e-mail]> wrote:

>Glancing at array.c and string.c the reason for this is
>obvious.  Strings in Ruby take up exactly the room
>allocated for them.  Arrays are in a buffer where they
>have to be aligned on the left with the buffer but there
>is room on the right.  Therefore any playing with the
>boundaries of a string forces you to recopy the whole
>thing.  And likewise any playing with the left side of an
>array forces you to recopy it.  (So shift should also be
>slow.)  But when you need to play games on the right
>(eg with push and pop) you have a buffer so you generally
>can leave the array alone.

There is a flip side, of course, to using extra
memory.  That is, less bang to the buck for pages
allocated from the free store, so more cache misses
in the hardware, etc.  That downside might occur
on other miscellaneous processing having nothing
to do with strings.

>If Ruby wants good performance on this set of operations
>(trust me, people coming from Perl are going to be very
>likely to call shift a lot without realizing that it is
>slow) it needs to use a buffering system closer to that
>which Perl uses.  

>In ruby.h this would mean adding a
>"capa" field to RString and an "offset" field to RArray,
>and adding logic in the C files to use these in an
>intelligent way.  To get the same performance profile as
>Perl on the array handling, if an array needs to be
>reallocated always left-align it, then inside your unshift
>function have logic that will ask for the array to be
>grown significantly more than you want, slide it, and then
>do the accounting to turn the initial part into a buffer.

Intuitively, it seems like a good heuristic would be
to allocate only the needed space at first, but then
extend by some extra factor after the first append.

Another possibility is to recognize that many malloc
implementations are actually allocating extra memory
internally in a set of fix sized bins to reduce
fragmentation.  Malloc is not all that big a piece
of code, so it would be possible to borrow it,
from e.g. glibc, and open up the interface to string
and array routines to something like the following
for those routines:

void* malloc(size_t needed, size_t* howMuchDidIGet)

...and then make use of the extra, where available.


-= Josh