Ruby Compile-time optimization

ruby-talk
1

Hello,

I was wondering about what exactly makes Perl faster than Ruby, and I made
a small test to examine this a bit. I sort of assumed that it was because
Ruby has more powerful data structures, but it seems that compile-time
optimization might be a significant factor.

The first step of my test was to look at the loop speed of Perl and Ruby.
I ran a loop that did nothing at all about 500,000 times. These are the
average of 3 tries:

ruby 1.023s
perl 1.140s

So Ruby’s loop was faster than Perl’s. I then put ‘val = 2 + 2’ inside
each loop (average of 3 tries):

    Total    Minus-the-loop

ruby 2.660s 1.637s 100.0%
perl 1.770s 0.630s 38.5%

In the second column I subtract the loop time from the total to get the
time spent in the “val = 2 + 2” step. Here Perl is better than twice as
fast as Ruby.

Now, as many of you know, Perl is not exactly an interpreted language.
Perl first “compiles” the program into some internal bytecode, which is
optimized before being run. For instance, if you have this:

use constant $MYCONST => 3
$val = 2 + $MYCONST

Perl turns it into:

$val = 5

I ran the ruby code again, but this time I replaced ‘val = 2 + 2’ by ‘val
= 4’ to simulate the effect of optimization. Again, the average of 3
tries:

             Total     Minus-the-loop

ruby 2.660 1.637 100.0%
ruby -optimized 1.793 0.770 47.0%
perl 1.770 0.630 38.5%

Now ther Perl’s operation is only about 18% faster, which in this case
particular case is mitigated by Ruby’s loop being 11% faster. Overall,
the Perl code is only 1% faster (which is less than experimental error).

I realize that the fact that Ruby is a more dynamic language makes
optimization more difficult, but I really think that we should look into
it.

Just a thought.

···

–
Daniel Carrera
Graduate Teaching Assistant. Math Dept.
University of Maryland. (301) 405-5137

2

If you poke around in the mailing lists, you’ll find it has been brought
up before. In short, Fixnum#+ may be redefined at any time, so
constant folding won’t work.

···

Daniel Carrera (dcarrera@math.umd.edu) wrote:

Now, as many of you know, Perl is not exactly an interpreted language.
Perl first “compiles” the program into some internal bytecode, which is
optimized before being run. For instance, if you have this:

use constant $MYCONST => 3
$val = 2 + $MYCONST

Perl turns it into:

$val = 5

I ran the ruby code again, but this time I replaced ‘val = 2 + 2’ by ‘val
= 4’ to simulate the effect of optimization. Again, the average of 3
tries:

             Total     Minus-the-loop

ruby 2.660 1.637 100.0%
ruby -optimized 1.793 0.770 47.0%
perl 1.770 0.630 38.5%

Now ther Perl’s operation is only about 18% faster, which in this case
particular case is mitigated by Ruby’s loop being 11% faster. Overall,
the Perl code is only 1% faster (which is less than experimental error).

I realize that the fact that Ruby is a more dynamic language makes
optimization more difficult, but I really think that we should look into
it.

–
Eric Hodel - drbrain@segment7.net - http://segment7.net
All messages signed with fingerprint:
FEC2 57F1 D465 EB15 5D6E 7C11 332A 551C 796C 9F04

3

In article 20030227002438.GA3877@math.umd.edu,

···

Daniel Carrera dcarrera@math.umd.edu wrote:

Hello,

I was wondering about what exactly makes Perl faster than Ruby, and I made
a small test to examine this a bit. I sort of assumed that it was because
Ruby has more powerful data structures, but it seems that compile-time
optimization might be a significant factor.

Actually, at the last meeting of the Portland Rubyists we had a new person
show up who apparently does a lot of OO Perl and from what he said, for OO
programs Ruby is faster because Perl is a lot slower at method dispatch.
Anyone else got any data on this?

Phil

4

^Hi,

did you do this with a loop body that does really do something? I mean,
your example is a bit artificial and optimizing this scenario would have not
much impact for real code, because nobody would repeat a constant operation
in a loop exept for performance measurements.

You could simply sum up a sequence of random numbers or something similar.

Kind regards

robert

“Daniel Carrera” dcarrera@math.umd.edu schrieb im Newsbeitrag
news:20030227002438.GA3877@math.umd.edu…

···

Hello,

I was wondering about what exactly makes Perl faster than Ruby, and I made
a small test to examine this a bit. I sort of assumed that it was because
Ruby has more powerful data structures, but it seems that compile-time
optimization might be a significant factor.

The first step of my test was to look at the loop speed of Perl and Ruby.
I ran a loop that did nothing at all about 500,000 times. These are the
average of 3 tries:

ruby 1.023s
perl 1.140s

So Ruby’s loop was faster than Perl’s. I then put ‘val = 2 + 2’ inside
each loop (average of 3 tries):

    Total    Minus-the-loop

ruby 2.660s 1.637s 100.0%
perl 1.770s 0.630s 38.5%

In the second column I subtract the loop time from the total to get the
time spent in the “val = 2 + 2” step. Here Perl is better than twice as
fast as Ruby.

Now, as many of you know, Perl is not exactly an interpreted language.
Perl first “compiles” the program into some internal bytecode, which is
optimized before being run. For instance, if you have this:

use constant $MYCONST => 3
$val = 2 + $MYCONST

Perl turns it into:

$val = 5

I ran the ruby code again, but this time I replaced ‘val = 2 + 2’ by ‘val
= 4’ to simulate the effect of optimization. Again, the average of 3
tries:

             Total     Minus-the-loop

ruby 2.660 1.637 100.0%
ruby -optimized 1.793 0.770 47.0%
perl 1.770 0.630 38.5%

Now ther Perl’s operation is only about 18% faster, which in this case
particular case is mitigated by Ruby’s loop being 11% faster. Overall,
the Perl code is only 1% faster (which is less than experimental error).

I realize that the fact that Ruby is a more dynamic language makes
optimization more difficult, but I really think that we should look into
it.

Just a thought.

Daniel Carrera
Graduate Teaching Assistant. Math Dept.
University of Maryland. (301) 405-5137

5

Assuming constant folding can be done, what would be the impact on
typical programs? And what would come after?

I’m not sure it’s worth working hard on optimizing the current
implementation: it’s been out for years now and if it was not optimized
it’s because it’s not easy. It might be better to focus our limited
resources on Rite. That could be much faster, doing method inlining,
specialization, etc…

···

On Thu, Feb 27, 2003 at 09:24:42AM +0900, Daniel Carrera wrote:

I realize that the fact that Ruby is a more dynamic language makes
optimization more difficult, but I really think that we should look into
it.

–
_ _

__ __ | | ___ _ __ ___ __ _ _ __
'_ \ / | __/ __| '_ _ \ / ` | ’ \
) | (| | |__ \ | | | | | (| | | | |
.__/ _,|_|/| || ||_,|| |_|
Running Debian GNU/Linux Sid (unstable)
batsman dot geo at yahoo dot com

On the Internet, no one knows you’re using Windows NT
– Submitted by Ramiro Estrugo, restrugo@fateware.com

6

Now, as many of you know, Perl is not exactly an interpreted language.
Perl first “compiles” the program into some internal bytecode, which is
optimized before being run.

This isn’t actually true. Perl 5 uses the same sort of optree
structure that Ruby does, though it does do a very trivial peephole
optimization pass over it first.

For instance, if you have this:

use constant $MYCONST => 3
$val = 2 + $MYCONST

Perl turns it into:

$val = 5

This part, though, is true–perl does do constant folding as part of
its peepholing. (And that’s nearly all, it’s a very simple
optimizier) You can do it across an optree if you want and the
language allows.

Perl’s method dispatch is definitely very slow, though. One of the
places it’ll pick up a win over ruby is in regular expressions, as
the regex engine’s been viciously optimized over the years. Also
perl, being a bit less general in semantics in spots, can skip some
of the more general things Ruby has. Whether that’s good or bad
depends on whether you need the generality in the corner cases, of
course.

There’s almost always a tradeoff between generality and speed. Just
one of those things.

···

At 9:24 AM +0900 2/27/03, Daniel Carrera wrote:

                                     Dan

--------------------------------------“it’s like this”-------------------
Dan Sugalski even samurai
dan@sidhe.org have teddy bears and even
teddy bears get drunk

7

Alright, it seems that things like contant folding would not be so
significant after all. So when and why is Perl faster than Ruby?

From what I’ve gathered so far:

  • Ruby has faster OO.
  • Perl uses Bob Jenkins’ hashing algorithm which is supposedly faster.
  • Perl has optimized REs.

Are these last two things the main things that Perl is faster at?
We can implement the better hashing algorithm in Ruby. Would it be hard
to use Perl’s source to speed Ruby’s RE’s?

···

–
Daniel Carrera
Graduate Teaching Assistant. Math Dept.
University of Maryland. (301) 405-5137

8

I realize that the fact that Ruby is a more dynamic language makes
optimization more difficult, but I really think that we should look into
it.

If you poke around in the mailing lists, you’ll find it has been brought
up before. In short, Fixnum#+ may be redefined at any time, so
constant folding won’t work.

Yes, I realize that. That’s the kind of problem that I referred to when I
said that Ruby was dynamic. I think that we should try to find a way to
optimize Ruby code. For instance, here are two ideas for implementing
constant folding:

  1. Create a “Constant” class whose “+” operator cannot be overloaded and
    whose value cannot be changed.
  2. Give Ruby a ‘-O’ option that does constant folding and raises an error
    if you either change the value of a constant or overload Fixnum#+.

I’m not saying that these are good ideas. What I’m saying is that we
might be able to come up with something. Idea (2) is not too
unreasonable.

···

–
Daniel Carrera
Graduate Teaching Assistant. Math Dept.
University of Maryland. (301) 405-5137

9

Correct me if I’m wrong, I very well might be. I think that my example
suggests that Ruby’s loops and assignments are not more expensive than
Perl’s, but Ruby’s Fixnum#+ is. We might infer that this is true for
other arithmetic operations as well. Am I right?

This is only the most miniscule example of optimization, I know. But I
wonder if we can use traditional optimization techniques to (like constant
folding) to speed up Ruby without significantly altering Ruby’s
implementation.

It’s just a thought. I don’t really know much about the subject.

···

On Thu, Feb 27, 2003 at 04:18:24PM +0900, Robert wrote:

^Hi,

did you do this with a loop body that does really do something? I mean,
your example is a bit artificial and optimizing this scenario would have not
much impact for real code, because nobody would repeat a constant operation
in a loop exept for performance measurements.

You could simply sum up a sequence of random numbers or something similar.

Kind regards

robert

–
Daniel Carrera
Graduate Teaching Assistant. Math Dept.
University of Maryland. (301) 405-5137

10

What is Rite?
Where can I learn about it?

···

On Thu, Feb 27, 2003 at 05:21:00PM +0900, Mauricio Fernández wrote:

On Thu, Feb 27, 2003 at 09:24:42AM +0900, Daniel Carrera wrote:

I realize that the fact that Ruby is a more dynamic language makes
optimization more difficult, but I really think that we should look into
it.

Assuming constant folding can be done, what would be the impact on
typical programs? And what would come after?

I’m not sure it’s worth working hard on optimizing the current
implementation: it’s been out for years now and if it was not optimized
it’s because it’s not easy. It might be better to focus our limited
resources on Rite. That could be much faster, doing method inlining,
specialization, etc…

–
_ _

__ __ | | ___ _ __ ___ __ _ _ __
'_ \ / | __/ __| '_ _ \ / ` | ’ \
) | (| | |__ \ | | | | | (| | | | |
.__/ _,|_|/| || ||_,|| |_|
Running Debian GNU/Linux Sid (unstable)
batsman dot geo at yahoo dot com

On the Internet, no one knows you’re using Windows NT
– Submitted by Ramiro Estrugo, restrugo@fateware.com

–
Daniel Carrera
Graduate Teaching Assistant. Math Dept.
University of Maryland. (301) 405-5137

11

As an informal benchmark, the “Language Shootout” would seem to suggest that
Ruby’s method dispatch is indeed a good bit faster:

http://www.bagley.org/~doug/shootout/bench/methcall/

Specifically, there’s over a 2x difference in the execution time for the specific
test used for that data. In addition, the ‘Object Instantiation’ test showed an even
more dramatic difference, with Ruby almost 5x faster.

Of course, to be fair, in its more traditional strong areas, (regexp matching, hash
access, etc.) Perl shows an equal or better advantage.

So, not too surprisingly, the performance is likely to depend far more on the
style of code you’re writing, algorithms and data structures used, etc., than on
the implementation language, at least among the “usual suspects” (Ruby, Perl,
Python, etc.).

Lennon Day-Reynolds
lennon@day-reynolds.com

···

On Thu, 27 Feb 2003 12:57:54 +0900 ptkwt@shell1.aracnet.com (Phil Tomson) wrote:

In article 20030227002438.GA3877@math.umd.edu,
Daniel Carrera dcarrera@math.umd.edu wrote:

Hello,

I was wondering about what exactly makes Perl faster than Ruby, and I made
a small test to examine this a bit. I sort of assumed that it was because
Ruby has more powerful data structures, but it seems that compile-time
optimization might be a significant factor.

Actually, at the last meeting of the Portland Rubyists we had a new person
show up who apparently does a lot of OO Perl and from what he said, for OO
programs Ruby is faster because Perl is a lot slower at method dispatch.
Anyone else got any data on this?

Phil

12

Alright, it seems that things like contant folding would not be so
significant after all. So when and why is Perl faster than Ruby?

From what I’ve gathered so far:

  • Ruby has faster OO.
  • Perl uses Bob Jenkins’ hashing algorithm which is supposedly faster.
  • Perl has optimized REs.

Are these last two things the main things that Perl is faster at?

I believe the overall picture is best described by saying that in Perl
some things are resolved much earlier (even as early as statically…).

We can implement the better hashing algorithm in Ruby. Would it be hard
to use Perl’s source to speed Ruby’s RE’s?

matz didn’t use Perl’s RE engine because it is strongly tied to other
things and taking it would mean adopting a sizable amount of Perl’s
runtime system (I think matz stated that in the LL2 talk).

Plus it seems Perl’s REs have been hand-crafted in such a way that the
mere inspection of the source code would drive any developer to madness.
We certainly don’t want to lose matz or any of the core language-hackers
:slight_smile:

···

On Fri, Feb 28, 2003 at 04:17:26AM +0900, Daniel Carrera wrote:

–
_ _

__ __ | | ___ _ __ ___ __ _ _ __
'_ \ / | __/ __| '_ _ \ / ` | ’ \
) | (| | |__ \ | | | | | (| | | | |
.__/ _,|_|/| || ||_,|| |_|
Running Debian GNU/Linux Sid (unstable)
batsman dot geo at yahoo dot com

Microsoft is not the answer.
Microsoft is the question.
NO (or Linux) is the answer.
– Taken from a .signature from someone from the UK, source unknown

13

Or don’t raise an error… I don’t think optimization should be
guaranteed. Kind of like ‘register’ in C… it’s more a suggestion than
anything else.

···
  1. Give Ruby a ‘-O’ option that does constant folding and raises an error
    if you either change the value of a constant or overload Fixnum#+.
14

Hello Daniel,

Thursday, February 27, 2003, 6:31:09 AM, you wrote:

  1. Give Ruby a ‘-O’ option that does constant folding and raises an error
    if you either change the value of a constant

but how? :slight_smile:

or overload Fixnum#+.

i have another idea - program can include statements like

“freeze Fixnum, String, Regexp”

that guarantees to optimizer that appropriate classes will be not
changed after this statements and methods of this classes can be
dispatched as “finalized” (in terms of Java)

but i think that “freeze” will be not very helpful w/o explicit type declarations

···

–
Best regards,
Bulat mailto:bulatz@integ.ru

15

Ruby’s upcoming reimplementation for version 2.0.
It only exists in matz’s head right now, but I think I read somewhere he
had a working bytecode interpreter prototype.

The only sources of info about Rite are AFAIK

  • this list
  • some slides of matz’s talks at various conferences

matz’s last word on Rite is here:
http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/65212

Some “background” :slight_smile:
http://www.ruby-lang.org/en/rc2002-minor/mgp00026.html
http://www.ruby-lang.org/en/oopsla2002/

···

On Thu, Feb 27, 2003 at 05:25:15PM +0900, Daniel Carrera wrote:

What is Rite?
Where can I learn about it?

–
_ _

__ __ | | ___ _ __ ___ __ _ _ __
'_ \ / | __/ __| '_ _ \ / ` | ’ \
) | (| | |__ \ | | | | | (| | | | |
.__/ _,|_|/| || ||_,|| |_|
Running Debian GNU/Linux Sid (unstable)
batsman dot geo at yahoo dot com

damn my office is cold.
need a hot secretary to warm it up.
– Seen on #Linux

16

As an informal benchmark, the “Language Shootout” would seem to suggest
that Ruby’s method dispatch is indeed a good bit faster:

http://www.bagley.org/~doug/shootout/bench/methcall/

Specifically, there’s over a 2x difference in the execution time for the
specific test used for that data. In addition, the ‘Object Instantiation’
test showed an even more dramatic difference, with Ruby almost 5x faster.

Of course, to be fair, in its more traditional strong areas, (regexp
matching, hash access, etc.) Perl shows an equal or better advantage.

That may be true, but it is a lot easier to optimize the regexp library (for
example) than to change the instantiation and dispatching methods.

Also, it is largely not a valid comparison, as Ruby is the only language (of
the “usual suspects” :slight_smile: ) that is in fact really OO. So, for example, Perl
is doing pseudo-OO more slowly than Ruby is doing real OO.

···

On Thursday 27 February 2003 01:45 am, Lennon Day-Reynolds wrote:

So, not too surprisingly, the performance is likely to depend far more on
the style of code you’re writing, algorithms and data structures used,
etc., than on the implementation language, at least among the “usual
suspects” (Ruby, Perl, Python, etc.).

Lennon Day-Reynolds
lennon@day-reynolds.com

On Thu, 27 Feb 2003 12:57:54 +0900 > > ptkwt@shell1.aracnet.com (Phil Tomson) wrote:

In article 20030227002438.GA3877@math.umd.edu,

Daniel Carrera dcarrera@math.umd.edu wrote:

Hello,

I was wondering about what exactly makes Perl faster than Ruby, and I
made a small test to examine this a bit. I sort of assumed that it was
because Ruby has more powerful data structures, but it seems that
compile-time optimization might be a significant factor.

Actually, at the last meeting of the Portland Rubyists we had a new
person show up who apparently does a lot of OO Perl and from what he
said, for OO programs Ruby is faster because Perl is a lot slower at
method dispatch. Anyone else got any data on this?

Phil

–
Seth Kurtzberg
M. I. S. Corp.
480-661-1849
seth@cql.com

17

“Daniel Carrera” dcarrera@math.umd.edu schrieb im Newsbeitrag
news:20030227072950.GD17232@math.umd.edu…

^Hi,

did you do this with a loop body that does really do something? I
mean,
your example is a bit artificial and optimizing this scenario would
have not
much impact for real code, because nobody would repeat a constant
operation
in a loop exept for performance measurements.

You could simply sum up a sequence of random numbers or something
similar.

Kind regards

robert

Correct me if I’m wrong, I very well might be. I think that my example
suggests that Ruby’s loops and assignments are not more expensive than
Perl’s, but Ruby’s Fixnum#+ is. We might infer that this is true for
other arithmetic operations as well. Am I right?

When it comes to performance measuring is much better than infering,
because experience shows that out intuition about bottlenecks often betrays
us.

This is only the most miniscule example of optimization, I know. But I
wonder if we can use traditional optimization techniques to (like
constant
folding) to speed up Ruby without significantly altering Ruby’s
implementation.

I doubt the “significant” for constant folding: Does constant folding
really help in many cases? If I use a constant value I will typically
assign it to a constant variable and reuse that - at least I think this is
a typical way to proceed.

But OTOH improving performance of “+” will surely help a lot.

It’s just a thought. I don’t really know much about the subject.

Me either. :slight_smile:

robert
···

On Thu, Feb 27, 2003 at 04:18:24PM +0900, Robert wrote:

18

Of course, to be fair, in its more traditional strong areas, (regexp matching, hash
access, etc.) Perl shows an equal or better advantage.

The only reason Perl’s hashes are faster than Ruby’s is because Perl uses Bob
Jenkins’ hashing algorithm, which is supposedely the best known hashing
algorithm. Take note, that Perl was using this very simple hashing function
until after version 5.005:

// Snipped out of the Ruby source code
#elif HASH_PERL
register int val = 0;

while ((c = *string++) != '\0') {
    val = val*33 + c;
}

return val + (val>>5);

#else

It wouldn’t take much to use Bob Jenkins’ algorithm in Ruby. The current Perl
implementation looks like this:

#define PERL_HASH(hash,str,len)
STMT_START {
register const char *s_PeRlHaSh_tmp = str;
register const unsigned char *s_PeRlHaSh = (const unsigned char *)s_PeRlHaSh_tmp;
register I32 i_PeRlHaSh = len;
register U32 hash_PeRlHaSh = 0;
while (i_PeRlHaSh–) {
hash_PeRlHaSh += *s_PeRlHaSh++;
hash_PeRlHaSh += (hash_PeRlHaSh << 10);
hash_PeRlHaSh ^= (hash_PeRlHaSh >> 6);
}
hash_PeRlHaSh += (hash_PeRlHaSh << 3);
hash_PeRlHaSh ^= (hash_PeRlHaSh >> 11);
(hash) = (hash_PeRlHaSh + (hash_PeRlHaSh << 15));
} STMT_END

All it would take would be converting it over to fit the variables in st.c and
adding another preprocessor conditional such as #elif HASH_JENKINS so as not to
disturb the 3 other strhash implementations. Anyway, just an idea. You can read
about Bob Jenkins hashing function at
http://burtleburtle.net/bob/hash/doobs.html

Cheers,
Travis

19

So you are suggesting that Ruby check to see if an operator is overloaded
and do constant folding if it isn’t? I think that’s a good idea.

There are several kinds of optimizations that can be done. Ruby could
check if they are “safe” and optimize accordingly.

···

On Thu, Feb 27, 2003 at 03:38:18PM +0900, Gabriel Emerson wrote:

Or don’t raise an error… I don’t think optimization should be
guaranteed. Kind of like ‘register’ in C… it’s more a suggestion than
anything else.

  1. Give Ruby a ‘-O’ option that does constant folding and raises an error
    if you either change the value of a constant or overload Fixnum#+.

–
Daniel Carrera
Graduate Teaching Assistant. Math Dept.
University of Maryland. (301) 405-5137

20
  1. Give Ruby a ‘-O’ option that does constant folding and raises an error
    if you either change the value of a constant

but how? :slight_smile:

Currently, if Ruby sees ‘MYCONST = …’ more than once, or in a context
where it’s value can change it produces a warning. I suggest that in
“optimization mode” it would stop execution instead. By guaranteeing that
the value of MYCONST doesn’t change, you can do things like constant
folding.

or overload Fixnum#+.

i have another idea - program can include statements like

“freeze Fixnum, String, Regexp”

that guarantees to optimizer that appropriate classes will be not
changed after this statements and methods of this classes can be
dispatched as “finalized” (in terms of Java)

That sounds like a good idea to me.
That might even allow more kinds of optimizations too.

···

On Thu, Feb 27, 2003 at 04:00:43PM +0900, Bulat Ziganshin wrote:

–
Daniel Carrera
Graduate Teaching Assistant. Math Dept.
University of Maryland. (301) 405-5137