From: Ben Tilly <ben_tilly@...>
Date: 2000-12-07T14:06:53+09:00
Subject: [ruby-talk:6874] Some performance issues

I decided to try out a few cases that I knew tend to present
possible performance issues in other languages.

  def tst_push (n)
    my_array = []
    for i in 1..n do
      my_array.push("hello")
    end
  end

  def tst_unshift (n)
    my_array = []
    for i in 1..n do
      my_array.unshift("hello")
    end
  end

  def tst_str_concat (n)
    my_str = ""
    for i in 1..n do
      my_str += "hello"
    end
  end

  for arg in ARGV do
    n = arg.to_i
    print "Pushing #{n} elements\n"
    tst_push(n)
    print "Unshifting #{n} elements\n"
    tst_unshift(n)
    print "Appending to a string #{n} times\n"
    tst_str_concat(n)
  end

With this highly unscientific test trying this 100, 1000,
10000, and 100000 times I see that push appears to be
fairly good, unshift appears to scale quadratically but
is not that slow, and appending to a string is definitely
quadratic and painful.  I couldn't figure out a simple
test that matched Perl's ability to produce a map which
returned more elements than it is fed:

  @bigger_list = map {($_, $_)} @list;

(OK, I can, but its performance is the same as push.)

By contrast Perl has for a long time had a fast push, a
fast string append, and a quadratic unshift.  The current
5.7 development has improved that to have a linear unshift
as well, albeit a little slower one than the push.  (The
1->2 map shown above was also quadratic, but will be linear
when 5.6.1 comes out.)

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.

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.

After all, you might as well use efficient algorithms by
default? :-)

Cheers,
Ben
_____________________________________________________________________________________
Get more from the Web.  FREE MSN Explorer download : http://explorer.msn.com