Why Ruby do not optimize code at all?

Hi,

I do not undertand why ruby doesn’t do any optimization at all during
parsing time.
Some optimization maybe affects debugging process.
Nevertheless, it seems “Constant folding” is not harmful but helpful.
I tried some pre-evaluation of constant or literal nodes in parsing
time.

Consider this code

i = 320 * 200 * 32

Original ruby-1.8.6 parsed it like this:

0:[NODE_BLOCK],0xb7f93ce4,p1:-9,p2:12,p3:1}
-9:[NODE_NEWLINE],0xb7f93d98,u1:0,u2:1,p3:-17}
-17:[NODE_LASGN],0xb7f93e38,u1:10473,p2:-10,u3:2}
-10:[NODE_CALL],0xb7f93dac,p1:-13,u2:42,p3:-11}
-13:[NODE_CALL],0xb7f93de8,p1:-16,u2:42,p3:-14}
-16:[NODE_LIT],0xb7f93e24,u1:641,u2:0,u3:0}
-14:[NODE_ARRAY],0xb7f93dfc,p1:-15,u2:1,u3:0}
-15:[NODE_LIT],0xb7f93e10,u1:401,u2:0,u3:0}
-11:[NODE_ARRAY],0xb7f93dc0,p1:-12,u2:1,u3:0}
-12:[NODE_LIT],0xb7f93dd4,u1:65,u2:0,u3:0}

My modified ruby parsed it like this:

0:[NODE_BLOCK],0xb7f5cd0c,p1:-9,p2:12,p3:1}
-9:[NODE_NEWLINE],0xb7f5cdc0,u1:0,u2:1,p3:-15}
-15:[NODE_LASGN],0xb7f5ce38,u1:10473,p2:-10,u3:2}
-10:[NODE_LIT],0xb7f5cdd4,u1:4096001,u2:0,u3:0}

A little more complex code

c = (12-3) * Math.sin(100) + 1.300 * (2 + 3) * Math.log(100)

Original parser:
0:[NODE_BLOCK],0xb7f35b08,p1:-9,p2:1,p3:1}
-9:[NODE_NEWLINE],0xb7f35bbc,u1:0,u2:4,p3:-38}
-38:[NODE_LASGN],0xb7f35e00,u1:10473,p2:-10,u3:2}
-10:[NODE_CALL],0xb7f35bd0,p1:-27,u2:43,p3:-11}
-27:[NODE_CALL],0xb7f35d24,p1:-33,u2:42,p3:-28}
-33:[NODE_NEWLINE],0xb7f35d9c,u1:0,u2:4,p3:-34}
-34:[NODE_CALL],0xb7f35db0,p1:-37,u2:45,p3:-35}
-37:[NODE_LIT],0xb7f35dec,u1:25,u2:0,u3:0}
-35:[NODE_ARRAY],0xb7f35dc4,p1:-36,u2:1,u3:0}
-36:[NODE_LIT],0xb7f35dd8,u1:7,u2:0,u3:0}
-28:[NODE_ARRAY],0xb7f35d38,p1:-29,u2:1,u3:0}
-29:[NODE_CALL],0xb7f35d4c,p1:-32,u2:9961,p3:-30}
-32:[NODE_CONST],0xb7f35d88,u1:9925,u2:0,u3:0}
-30:[NODE_ARRAY],0xb7f35d60,p1:-31,u2:1,u3:0}
-31:[NODE_LIT],0xb7f35d74,u1:201,u2:0,u3:0}
-11:[NODE_ARRAY],0xb7f35be4,p1:-12,u2:1,u3:0}
-12:[NODE_CALL],0xb7f35bf8,p1:-18,u2:42,p3:-13}
-18:[NODE_CALL],0xb7f35c70,p1:-25,u2:42,p3:-19}
-25:[NODE_LIT],0xb7f35cfc,p1:-26,u2:0,u3:0}
-19:[NODE_ARRAY],0xb7f35c84,p1:-20,u2:1,u3:0}
-20:[NODE_NEWLINE],0xb7f35c98,u1:0,u2:4,p3:-21}
-21:[NODE_CALL],0xb7f35cac,p1:-24,u2:43,p3:-22}
-24:[NODE_LIT],0xb7f35ce8,u1:5,u2:0,u3:0}
-22:[NODE_ARRAY],0xb7f35cc0,p1:-23,u2:1,u3:0}
-23:[NODE_LIT],0xb7f35cd4,u1:7,u2:0,u3:0}
-13:[NODE_ARRAY],0xb7f35c0c,p1:-14,u2:1,u3:0}
-14:[NODE_CALL],0xb7f35c20,p1:-17,u2:10057,p3:-15}
-17:[NODE_CONST],0xb7f35c5c,u1:9925,u2:0,u3:0}
-15:[NODE_ARRAY],0xb7f35c34,p1:-16,u2:1,u3:0}
-16:[NODE_LIT],0xb7f35c48,u1:201,u2:0,u3:0}
Modified parser:
0:[NODE_BLOCK],0xb7f0fae8,p1:-9,p2:1,p3:1}
-9:[NODE_NEWLINE],0xb7f0fb9c,u1:0,u2:4,p3:-40}
-40:[NODE_LASGN],0xb7f0fe08,u1:10473,p2:-10,u3:2}
-10:[NODE_LIT],0xb7f0fbb0,p1:-11,u2:0,u3:0}

String operation code
s = ("hello " + "world ")*100

Original parser:
0:[NODE_BLOCK],0xb7fa4c74,p1:-11,p2:1,p3:1}
-11:[NODE_NEWLINE],0xb7fa4d50,u1:0,u2:2,p3:-22}
-22:[NODE_LASGN],0xb7fa4e2c,u1:10473,p2:-12,u3:2}
-12:[NODE_CALL],0xb7fa4d64,p1:-15,u2:42,p3:-13}
-15:[NODE_NEWLINE],0xb7fa4da0,u1:0,u2:2,p3:-16}
-16:[NODE_CALL],0xb7fa4db4,p1:-19,u2:43,p3:-21}
-19:[NODE_STR],0xb7fa4df0,p1:-20,u2:0,u3:0}
-21:[NODE_ARRAY],0xb7fa4e18,p1:-17,u2:1,u3:0}
-17:[NODE_STR],0xb7fa4dc8,p1:-18,u2:0,u3:0}
-13:[NODE_ARRAY],0xb7fa4d78,p1:-14,u2:1,u3:0}
-14:[NODE_LIT],0xb7fa4d8c,u1:2001,u2:0,u3:0}

Modified parser:
0:[NODE_BLOCK],0xb7efdc6c,p1:-11,p2:1,p3:1}
-11:[NODE_NEWLINE],0xb7efdd48,u1:0,u2:2,p3:-22}
-22:[NODE_LASGN],0xb7efde24,u1:10473,p2:-12,u3:2}
-12:[NODE_STR],0xb7efdd5c,p1:-13,u2:0,u3:0}

In the loop it make considerable difference
With the code
for i in 1…10000
s = “hello”*10000
end
puts s

Original ruby:
real 0m2.591s
user 0m2.579s
sys 0m0.013s

Modified ruby:
real 0m0.010s
user 0m0.007s
sys 0m0.003s

What do you think of the minimum optimization?

Regards,

Park H.

On Fri, Mar 28, 2008 at 10:38 AM, Heesob P. [email protected] wrote:

       -14:[NODE_ARRAY],0xb7f93dfc,p1:-15,u2:1,u3:0}

       -33:[NODE_NEWLINE],0xb7f35d9c,u1:0,u2:4,p3:-34}
       -12:[NODE_CALL],0xb7f35bf8,p1:-18,u2:42,p3:-13}
             -17:[NODE_CONST],0xb7f35c5c,u1:9925,u2:0,u3:0}

     -13:[NODE_ARRAY],0xb7fa4d78,p1:-14,u2:1,u3:0}

for i in 1…10000
real 0m0.010s

I guess the first question is does Ruby with your parser changes pass
all the tests?

Second, could you post a patch for people to try out and evaluate?
We’ll need to see the actual code to really evaluate if you’ve got
something here.

Jason

On Fri, Mar 28, 2008 at 10:45 AM, Jason R. [email protected]
wrote:

     -13:[NODE_CALL],0xb7f93de8,p1:-16,u2:42,p3:-14}
 -15:[NODE_LASGN],0xb7f5ce38,u1:10473,p2:-10,u3:2}
   -10:[NODE_CALL],0xb7f35bd0,p1:-27,u2:43,p3:-11}
             -31:[NODE_LIT],0xb7f35d74,u1:201,u2:0,u3:0}
         -13:[NODE_ARRAY],0xb7f35c0c,p1:-14,u2:1,u3:0}

String operation code
-21:[NODE_ARRAY],0xb7fa4e18,p1:-17,u2:1,u3:0}
In the loop it make considerable difference

Jason

Oh, and this belongs in the Ruby Core mailing list.

Jason

Heesob P. wrote:

String operation code
s = ("hello " + "world ")*100

[…]

Modified parser:
0:[NODE_BLOCK],0xb7efdc6c,p1:-11,p2:1,p3:1}
-11:[NODE_NEWLINE],0xb7efdd48,u1:0,u2:2,p3:-22}
-22:[NODE_LASGN],0xb7efde24,u1:10473,p2:-12,u3:2}
-12:[NODE_STR],0xb7efdd5c,p1:-13,u2:0,u3:0}

What do you do, if someone write this

vgs% /usr/bin/ruby
class String
def +(x)
“#{x} #{self}”
end
end

p “a” + “b”
^D
“b a”
vgs%

I know, the example is stupid :slight_smile:

Guy Decoux

I think the problem is that you can redefine any method
of any class at any time. If some one redefined the `*’
method of Fixnum, your code won’t pass, I guess.

2008/3/28, Heesob P. [email protected]:

We can redefine Fixnum#* in Ruby.

On Fri, Mar 28, 2008 at 11:46 PM, Jason R. [email protected]
wrote:

On Fri, Mar 28, 2008 at 10:45 AM, Jason R.
[email protected] wrote:

On Fri, Mar 28, 2008 at 10:38 AM, Heesob P. [email protected]
wrote:

Hi,

I do not undertand why ruby doesn’t do any optimization at all
during

parsing time.
Some optimization maybe affects debugging process.
Nevertheless, it seems “Constant folding” is not harmful but
helpful.

So “Constant folding” is harmful.

On 28 Mar 2008, at 15:20, Chiyuan Z. wrote:

I think the problem is that you can redefine any method
of any class at any time. If some one redefined the `*’
method of Fixnum, your code won’t pass, I guess.

More than this, it may not even be a fixnum or string or whatever
instance class. Not even constants are ‘constant’.

2008/3/28, Heesob P. [email protected]:

Hi,

I do not undertand why ruby doesn’t do any optimization at all during
parsing time.

The AST defines very little, if anything, about what the code will do,
until it is considered as a whole. (Which may not be possible if there
is any eval().

Some optimization maybe affects debugging process.
Nevertheless, it seems “Constant folding” is not harmful but helpful.
I tried some pre-evaluation of constant or literal nodes in parsing
time.

As said by others, open classes means parse time != run time, at all.

Consider this code

i = 320 * 200 * 32

The only time I could see this being sensible to do is if it’s
actually closer to:

A = 320.freeze
B = 200.freeze
C = 32.freeze

i = A * B * C

However, the realistic implications are that freeze plus the discussed
optimization causes a pre-processor fixed definition of the methods
A.() and B.().

In MRI, one can unfreeze too, so this still isn’t “safe”, and the
source code does not resemble what is run.

This will kick people most, when reading someone else code.

What do you think of the minimum optimization?

I think it shows up immediately in profiling if it’s relevant, as if
it is relevant, you will highly likely see a large number of calls to
Fixnum#*, and in some of the given examples, this is exactly where
you’d manually unroll to optimize for speed, or alternatively:

BIG_NUMBER = 100_000 * 100
SOMETHING_THAT_SHOULD_BE_A_CONSTANT = BIG_NUMBER * ‘some string’

def foo
SOMETHING_THAT_SHOULD_BE_A_CONSTANT
end

Hi,
----- Original Message -----
From: “ts” [email protected]
To: “ruby-talk ML” [email protected]
Sent: Saturday, March 29, 2008 12:17 AM
Subject: Re: Why Ruby do not optimize code at all?

 -22:[NODE_LASGN],0xb7efde24,u1:10473,p2:-12,u3:2}

p “a” + “b”
^D
“b a”
vgs%

I know, the example is stupid :slight_smile:

Ok, I understand.
So ruby is never fast but flexible language :slight_smile:

Guy Decoux

Regards,
Park H.

Park H. wrote:

So ruby is never fast but flexible language :slight_smile:

Well I can give you another example of “premature” optimisation, but
for 1.9

[ruby-bugs:16163]

http://rubyforge.org/tracker/index.php?func=detail&aid=16163&group_id=426&atid=1698

it worked but a modification was made to ruby and the optimisation
break the code now

Guy Decoux

Hi,
----- Original Message -----
From: “Jason R.” [email protected]
To: “ruby-talk ML” [email protected]; [email protected]
Sent: Friday, March 28, 2008 11:53 PM
Subject: Re: Why Ruby do not optimize code at all?

On Fri, Mar 28, 2008 at 10:45 AM, Jason R. [email protected] wrote:

Oh, and this belongs in the Ruby Core mailing list.

Jason

Never mind, I gave it up.

Regards,

Park H.

On 28.03.2008 15:38, Heesob P. wrote:

I do not undertand why ruby doesn’t do any optimization at all during
parsing time.

Because, as others have pointed out already, at parse time it is not
known what the code will do.

My modified ruby parsed it like this:

0:[NODE_BLOCK],0xb7f5cd0c,p1:-9,p2:12,p3:1}
-9:[NODE_NEWLINE],0xb7f5cdc0,u1:0,u2:1,p3:-15}
-15:[NODE_LASGN],0xb7f5ce38,u1:10473,p2:-10,u3:2}
-10:[NODE_LIT],0xb7f5cdd4,u1:4096001,u2:0,u3:0}

$ ruby -e ‘class Fixnum; def *(o) 666 end;end; puts 320 * 200 * 32’
666

Ooops!

Without fiddling:

[email protected] ~
$ ruby -e ‘puts 1/2’
0

[email protected] ~
$ ruby -r mathn -e ‘puts 1/2’
1/2

       -33:[NODE_NEWLINE],0xb7f35d9c,u1:0,u2:4,p3:-34}
       -12:[NODE_CALL],0xb7f35bf8,p1:-18,u2:42,p3:-13}
             -17:[NODE_CONST],0xb7f35c5c,u1:9925,u2:0,u3:0}
             -15:[NODE_ARRAY],0xb7f35c34,p1:-16,u2:1,u3:0}
               -16:[NODE_LIT],0xb7f35c48,u1:201,u2:0,u3:0}

Modified parser:
0:[NODE_BLOCK],0xb7f0fae8,p1:-9,p2:1,p3:1}
-9:[NODE_NEWLINE],0xb7f0fb9c,u1:0,u2:4,p3:-40}
-40:[NODE_LASGN],0xb7f0fe08,u1:10473,p2:-10,u3:2}
-10:[NODE_LIT],0xb7f0fbb0,p1:-11,u2:0,u3:0}

Same story as above.

String operation code
s = ("hello " + "world ")*100

Note that in the code above the only constant is “100”. The sequence
“hello” is a String constructor - not a constant - as you can easily
see:

irb(main):012:0> (1…5).map { “hello”.object_id }
=> [1073415980, 1073415960, 1073415940, 1073415920, 1073415900]
irb(main):013:0> (1…5).map { “hello”.object_id }.uniq
=> [1073407290, 1073407270, 1073407250, 1073407230, 1073407210]

     -13:[NODE_ARRAY],0xb7fa4d78,p1:-14,u2:1,u3:0}

for i in 1…10000
real 0m0.010s
user 0m0.007s
sys 0m0.003s

What do you think of the minimum optimization?

I think: if it was that easy, Matz would have done it already. But it
ain’t that easy and if you want to have constant expressions simply
assign them to a constant and use that value.

I = 320 * 200 * 32

Kind regards

robert

On Mar 28, 2008, at 9:19 AM, ts wrote:

it worked but a modification was made to ruby and the optimisation
break the code now

Before this question is relegated to the heap of “premature
optimization” ideas, I think the value of some level of programmer-
controller optimizations would be useful in the future. Optimizations
can break code so they are always “caveat programmer.” Even in C,
where lots is known about the code, there are code-breaking
optimizations. Again, not a recommendation to do this; just a
recommendation not to dismiss it.

Just my $.02

On Mar 28, 11:21 am, “s.ross” [email protected] wrote:

http://rubyforge.org/tracker/index.php?func=detail&aid=16163&group_id
recommendation not to dismiss it.

Just my $.02

Hm, couldn’t you use method_added behind the scenes somehow? Perhaps
use the opimized parse tree unless method_added is invoked? Or cache
the parse tree?

Or am I talking nonsense?

Regards,

Dan

On 28 Mar 2008, at 21:06, Daniel B. wrote:

controller optimizations would be useful in the future. Optimizations

Or am I talking nonsense?

Probably, that would make sense for the 90th percentile of use. For
some percentile, it’ll be really bad.

obj.extend or re-opening the class inside a method could then be a
killer, which brings us right back to optimisation

I guess the problem is, the people that need it, should know how to
have the same effect on their code, those that don’t just want it.
sure it’s probably not that well defined, but in seems close to the
truth for many cases

On Mar 28, 2008, at 08:39 AM, James T. wrote:

i = 320 * 200 * 32

The only time I could see this being sensible to do is if it’s
actually closer to:

A = 320.freeze
B = 200.freeze
C = 32.freeze

i = A * B * C

#freeze is not a solution to the constant folding optimizations. It
only makes the object immutable, not it’s class, and not its
instance_variables, so methods may be redefined on you anyhow, and the
contents of ivars may also change (String#replace, etc.)

However, the realistic implications are that freeze plus the
discussed optimization causes a pre-processor fixed definition of
the methods A.() and B.().

In MRI, one can unfreeze too, so this still isn’t “safe”, and the
source code does not resemble what is run.

You can taint/untaint, but you cannot unfreeze.

On 29 Mar 2008, at 00:06, Eric H. wrote:

source code does not resemble what is run.

You can taint/untaint, but you cannot unfreeze.

Absolutely right, never use the thing, thanks for the correction.

Heesob P. wrote:

Original ruby:
real 0m2.591s
user 0m2.579s
sys 0m0.013s

Modified ruby:
real 0m0.010s
user 0m0.007s
sys 0m0.003s

What do you think of the minimum optimization?

Regards,

Park H.

The optimization is impressive. But we have to give up this kind of
optimization for flexibility in ruby…well, it is too bad. But
programming is really enjoying in ruby because because of its
flexibility…and can’t avoid for the tradeoff…I wonder how YARV doing
this kind of optimization or it is not…:slight_smile:

On 28.03.2008 18:21, s.ross wrote:

Before this question is relegated to the heap of “premature
optimization” ideas, I think the value of some level of programmer-
controller optimizations would be useful in the future.

I guess you mean “programmer controlled”, did you? In fact, there is
plenty of room for that today already. There are numerous techniques
that can be applied to code to make it faster. Often, proper design and
/ or algorithms make a huge difference. :slight_smile:

Kind regards

robert

On Mar 28, 9:06 pm, Daniel B. [email protected] wrote:

Hm, couldn’t you use method_added behind the scenes somehow? Perhaps
use the opimized parse tree unless method_added is invoked? Or cache
the parse tree?

Or am I talking nonsense?

Not sure if method_added would be the right solution, but the
interpreter can certainly do checks. For the new VM based Ruby
implementations
for example, it’d be reasonable to do JIT based optimization of it -
it’d be relatively easy bookkeeping for the VM implementations to
check
for the replacement of a specific method of a specific class, and
throw away all JIT optimized paths relying on the behavior of that
method
and revert to the original byte code.

That could be done as a quite generic optimization, which pretty much
boils down to memoization of the results of frequently occurring
subexpressions that are known to be safe to memoize (no side effects /
stored state etc.)

Vidar

On Mar 29, 2008, at 9:50 AM, Robert K. wrote:

Kind regards

robert

Yes, “controlled”. And yes, a good algo beats a machine optimization
almost every time. But still, some of the stupid optimization tricks
people have traditionally used for the last several percent destroy
the readability of code. I’ve never been terribly unhappy with the
performance of Ruby, but if I were … say … Industrial Light and
Magic and choosing between Ruby and Python to glue my effects stuff
together, I might be swayed toward Python because it preserves
bytecode (right?). It might be nice, once we figure out how to express
Ruby in an optimizable bytecode to create JIT optimizers that are
platform specific. Who knows what results that might yield.

My original point, spelling not withstanding, is that this is a topic
(along with threading) that typically gets relegated to the premature
optimizations bin, and doesn’t rise to the level of “this should be
possible one day and it should work with only the predictable
glitches.” If I were heavily invested in my Java or C programming
skills, and wanted to keep Ruby out of my shop – and there are people
who do fight to keep new technologies away – lack of optimization
might be an attack plan.

Again, just my opinion.

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

| Privacy Policy | Terms of Service | Remote Ruby Jobs