Compile time constant folding?

ruby-talk
1

Here’s a quick question, now that parrot’s close to getting object
support and the cardinal folks are on their way to a working parser…

Is it valid to do compile-time constant folding as an optimization?

I know statements like

a = 1 + 2

may have interesting runtime behaviours if addition is overloaded for
fixnums, but is that guaranteed, or is it OK if the compiler reduces
that to

a = 3

?

···

–
Dan

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

2

Short answer? No.

I think you answered your own question: “interesting runtime behaviours if
addition [really the ‘+’ method] is overloaded for fixnums”. If it is
possible to overload this method at any time after compile (which it is
via eval or require), how can the compiler possibly know what to use in
the folded code?

Maybe as an option to the compiler? Sort of a contract with Parrot that you
won’t overload a specific set of commands in order to facilitate
efficiency in the resulting byte code?

-michael

···

On Sunday 05 January 2003 14:26, Dan Sugalski wrote:

Is it valid to do compile-time constant folding as an optimization?

I know statements like

a = 1 + 2

may have interesting runtime behaviours if addition is overloaded for
fixnums, but is that guaranteed, or is it OK if the compiler reduces
that to

3

Hi.

Dan Sugalski wrote in comp.lang.ruby:

Is it valid to do compile-time constant folding as an optimization?

IMO, the POLS wouldn’t be breeched if this were to happen.
Unless the overloaded operator does something completely
strange (eg redefine “+” as “*”). I guess that typing may
also be an issue.

-mark.

4

Hi,

Here’s a quick question, now that parrot’s close to getting object
support and the cardinal folks are on their way to a working parser…

Is it valid to do compile-time constant folding as an optimization?

I didn’t take it, because

  • every method may be redefined (e.g. “+”) in dynamic languages.

  • besides, foldable expressions are rather simple, so that it does
    not save much time.

The latter assumption may not be true for Parrot, which has much
faster and more optimized runtime.

						matz.
···

In message “Compile time constant folding?” on 03/01/06, Dan Sugalski dan@sidhe.org writes:

5

I can see it going either way–the interpreter could do what it’s
doing on purpose, or because the optimization just never was done.
(Or that it wasn’t ever really thought about)

It’s not like this is expensive in the simple case, but when you do
something like:

(1 / sin(2.3)) * log(4)

in a loop, well, that can add up pretty quickly.

···

At 9:19 AM +0900 1/6/03, Mark Probert wrote:

Hi.

Dan Sugalski wrote in comp.lang.ruby:

Is it valid to do compile-time constant folding as an optimization?

IMO, the POLS wouldn’t be breeched if this were to happen.
Unless the overloaded operator does something completely
strange (eg redefine “+” as “*”). I guess that typing may
also be an issue.

–
Dan

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

6

Hi,

Here’s a quick question, now that parrot’s close to getting object
support and the cardinal folks are on their way to a working parser…

Is it valid to do compile-time constant folding as an optimization?

I didn’t take it, because

  • every method may be redefined (e.g. “+”) in dynamic languages.

  • besides, foldable expressions are rather simple, so that it does
    not save much time.

You’d be surprised, especially when you factor in some other
optimizations–you can do some substitutions and inferences of
variable contents. Because of it, some expressions that look like
they’re variable, such as:

a = 12
b = 8
c = a + b

are really constant. (And yes, that is really cut down and
excessively simplified)

Still, if it’s not allowed that’s fine. The question came up and,
since I have a bunch of other things I should do first, I couldn’t
let it go without finding out.

Thanks, Matz.

The latter assumption may not be true for Parrot, which has much
faster and more optimized runtime.

We’ll see–you still need to beat us with sprite. :wink:

···

At 9:32 AM +0900 1/6/03, Yukihiro Matsumoto wrote:

In message “Compile time constant folding?” > on 03/01/06, Dan Sugalski dan@sidhe.org writes:
–
Dan

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

7

Wouldn’t it be nice to have the compiler not to fold this expressions
(because of the stated problems) but to write a profiling log containing all
the places where folding could be possible, so that the programmer can
decide afterwards to give the compiler some hints (by manually changing
code or perhaps by some function
evalct do
…
end
where the compiler is allowed to fold anything within the block (while the
interpreter just evaluates the block ignoring the evalct).

Stony
(42)

···

Yukihiro Matsumoto matz@ruby-lang.org wrote:

In message “Compile time constant folding?” > on 03/01/06, Dan Sugalski dan@sidhe.org writes:

Is it valid to do compile-time constant folding as an optimization?

I didn’t take it, because
[ redefinition etc ]

–

======================================
The Answer is 42.
And I am the Answer.
Now I am looking for the Question.

8

Dan Sugalski wrote:

It’s not like this is expensive in the simple case, but when you do
something like:

(1 / sin(2.3)) * log(4)

in a loop, well, that can add up pretty quickly.

And in this case we have to assume that sin and log are pure functions,
in addition to assuming that they will never be redefined. Sure, you can
make sin and log special cases, but where do you stop?

Anyway, why would one have such a complex expression within a loop? It’s
not like in C where an apparently simple expression can be expanded by
the preprocessor into something that needs a lot of folding. The
complexity of the expression is apparent in the ruby code, and it is
telling you to move it out of the loop.

9

Could the programmer help the compiler with guessing when the
optimization is feasible?
For (imperfect) example if I use

Fixnum.freeze

in the code I am telling the compiler to optimize 3 + 5 ?

Dalibor Sramek

···

On Mon, Jan 06, 2003 at 11:15:46AM +0900, Dan Sugalski wrote:

You’d be surprised, especially when you factor in some other
optimizations–you can do some substitutions and inferences of
variable contents.

–
Dalibor Sramek insula.cz | In the eyes of cats,
dalibor.sramek@insula.cz | all things belong to cats.

10

I say: 15.002 → optimise. :wink:
Given that we know the base, and it is also constant.

This is the thing for me. Constants are, well, constants.
If someone redefines “log” to be “ln”, then it is no longer
constant and you should probably have to recompile everything
anyway. Either you meant “15.002” (log) or you meant “34.544”
(ln) when you coded this.

Or is my understanding faulty? Can you have a constant that
is context dependant, post-fact?

Regards,

-mark.

···

At 10:08 AM 1/6/2003 +0900, Dan wrote:

At 9:19 AM +0900 1/6/03, Mark Probert wrote:

Dan Sugalski wrote in comp.lang.ruby:

Is it valid to do compile-time constant folding as an optimization?

IMO, the POLS wouldn’t be breeched if this were to happen.

I can see it going either way–the interpreter could do what it’s doing on
purpose, or because the optimization just never was done. (Or that it
wasn’t ever really thought about)

It’s not like this is expensive in the simple case, but when you do
something like:

(1 / sin(2.3)) * log(4)

in a loop, well, that can add up pretty quickly.

11

Dan Sugalski wrote:

It’s not like this is expensive in the simple case, but when you do
something like:

(1 / sin(2.3)) * log(4)

in a loop, well, that can add up pretty quickly.

And in this case we have to assume that sin and log are pure
functions, in addition to assuming that they will never be
redefined. Sure, you can make sin and log special cases, but where
do you stop?

Never! Never I say–first constant expressions, next the world!
Bwahahahahaha! Erm. Sorry, nevermind… :slight_smile:

Anyway, why would one have such a complex expression within a loop?

It’s not uncommon to have expressions that look non-constant that
turn out to really be constant once surrounding code’s analyzed.

It’s not like in C where an apparently simple expression can be
expanded by the preprocessor into something that needs a lot of
folding. The complexity of the expression is apparent in the ruby
code, and it is telling you to move it out of the loop.

You’d be surprised. Anyway, Matz’s spoken, so I’m set now.

···

At 10:32 AM +0900 1/6/03, Joel VanderWerf wrote:

                                     Dan

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

12

Dan Sugalski wrote in comp.lang.ruby:

Is it valid to do compile-time constant folding as an optimization?

IMO, the POLS wouldn’t be breeched if this were to happen.

I can see it going either way–the interpreter could do what it’s doing
on
purpose, or because the optimization just never was done. (Or that it
wasn’t ever really thought about)

It’s not like this is expensive in the simple case, but when you do
something like:

(1 / sin(2.3)) * log(4)

in a loop, well, that can add up pretty quickly.

I say: 15.002 → optimise. :wink:
Given that we know the base, and it is also constant.

This is the thing for me. Constants are, well, constants.
If someone redefines “log” to be “ln”, then it is no longer
constant and you should probably have to recompile everything
anyway. Either you meant “15.002” (log) or you meant “34.544”
(ln) when you coded this.

Or is my understanding faulty? Can you have a constant that
is context dependant, post-fact?

I can’t respond to your last question, but I’ll try to address
the overall issue here.

Redefining things like Fixnum#+ to behave differently may be
bad coding style… but it is possible. As someone said, when
software prevents you from doing stupid things, it often
prevents you from doing very clever things as well.

I’m undecided about whether + and log are logically different…
the difference may be all in my head. After all, they’re both
methods.

In any case, I’m even less inclined to optimise things like
log and sin. It’s hard to explain why, but it just feels wrong
to me. What about user-defined methods? Should we
assume that a method called with a constant, e.g. foo(5), is a
constant value also?

On the other hand, maybe it would be acceptable to have an option
like “-mathopt” that would tell the compiler “I hereby certify
that this program does No Funny Business with the standard math
operators and functions, so optimize away, my little friend.”
But then we take our first step down the road to Compiler Flag
Hell. The next step, of course, might be “-stropt” or some such.

If we decide to let the compiler optimize “on its own judgment”
(which I think I’m opposed to unless it’s Turing-capable, and
that’s not coming till version 2.0), then the dynamic nature
of the language causes problems for us. If an operator is
redefined, we probably don’t want to optimize (incorrect??),
but it becomes an interesting compile-time exercise to determine
whether a certain piece of code can be executed only before the
redefinition, only after, or potentially both.

While I’m rambling, I might as well say that if the compiler can
detect such optimizing situations, it could in theory report
them to the user in the form of (optional) warnings. That might
be useful.

Just my thoughts.

Hal

···

----- Original Message -----
From: “Mark Probert” probertm@nortelnetworks.com
To: “ruby-talk ML” ruby-talk@ruby-lang.org
Sent: Monday, January 06, 2003 9:24 AM
Subject: Re: Compile time constant folding?

At 10:08 AM 1/6/2003 +0900, Dan wrote:

At 9:19 AM +0900 1/6/03, Mark Probert wrote:

13

Generally not–it seems to hurt more than it helps in places where
you can do it. Most people get that sort of thing wrong, and when
they do get it right those sorts of hints get stale quickly. It’s
better to just clearly express the semantics and let the compilers
take care of figuring out where things can be feasably optimized.

···

At 4:14 PM +0900 1/6/03, Dalibor Sramek wrote:

On Mon, Jan 06, 2003 at 11:15:46AM +0900, Dan Sugalski wrote:

You’d be surprised, especially when you factor in some other
optimizations–you can do some substitutions and inferences of
variable contents.

Could the programmer help the compiler with guessing when the
optimization is feasible?

–
Dan

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

14

Maybe, but add isn’t necessarily add–it’s the actions that need to
be taken rather than the values themselves that are in question. If
someone redefines + to be unconditional string concatenation, or
wedges in logging logic, you may well want that to happen at runtime
with the constant expression.

···

At 12:24 AM +0900 1/7/03, Mark Probert wrote:

At 10:08 AM 1/6/2003 +0900, Dan wrote:

At 9:19 AM +0900 1/6/03, Mark Probert wrote:

Dan Sugalski wrote in comp.lang.ruby:

Is it valid to do compile-time constant folding as an optimization?

IMO, the POLS wouldn’t be breeched if this were to happen.

I can see it going either way–the interpreter could do what it’s
doing on purpose, or because the optimization just never was done.
(Or that it wasn’t ever really thought about)

It’s not like this is expensive in the simple case, but when you do
something like:

(1 / sin(2.3)) * log(4)

in a loop, well, that can add up pretty quickly.

I say: 15.002 → optimise. :wink:
Given that we know the base, and it is also constant.

This is the thing for me. Constants are, well, constants.

–
Dan

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

15

Shouldn’t it be the programmer’s responsibility to find these cases and take
them outside of the loop while optimising eir code?

Tim Bates

···

On Mon, 6 Jan 2003 12:45 pm, Dan Sugalski wrote:

Anyway, why would one have such a complex expression within a loop?

It’s not uncommon to have expressions that look non-constant that
turn out to really be constant once surrounding code’s analyzed.

–
tim@bates.id.au

16

Yeah, at this point I’m thinking we need more facilities for fast
conditional optimization skipping, which may make things interesting,
but that’s fine. It falls into the same arena as type
inferencing–things that will be a major pain to implement, but it
doesn’t hurt to have the infrastructure in place so it can be done
when we have enough people with time for it.

···

At 12:56 AM +0900 1/7/03, Hal E. Fulton wrote:

While I’m rambling, I might as well say that if the compiler can
detect such optimizing situations, it could in theory report
them to the user in the form of (optional) warnings. That might
be useful.

–
Dan

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

17

Hi, Hal.

Redefining things like Fixnum#+ to behave differently may be
bad coding style… but it is possible. As someone said, when
software prevents you from doing stupid things, it often
prevents you from doing very clever things as well.

I think I now understand where my thinking is going off.

We are talking about “constant folding”. When I see the
expressions:

     a = 5
     b = 3
     c = a + b

Then I am seeing the operators (assignment and addition) as
constant as well as values (base 10). So, I can confidently
say that the above reduces to

     c = 8

However, given that I (the coder) can dynamically change the
operators, there is no way that the compiler can “guess” that
this is true. So as Dan suggested, I may later redefine “+”
as string cat and mean

     c = "53"

-laugh-

And this seems wrong to me. If I had meant that, why didn’t
I write that in the first place? Certainly as a maintainer
of code, I would want it to be very clear what is happening.
After all, these values are meant to be constants …

Ahhh … here comes Mr Ockham and his razor :wink:

-mark.

···

At 12:56 AM 1/7/2003 +0900, Hal wrote:

18

Hi,

···

In message “Re: Compile time constant folding?” on 03/01/06, Tim Bates tim@bates.id.au writes:

Shouldn’t it be the programmer’s responsibility to find these cases and take
them outside of the loop while optimising eir code?

It’s OK to make them compiler’s responsibility as long as it can be
done automagically without changing the semantics. Unfortunately, I
suspect that’s not the case for dynamic language like Ruby.

						matz.
19

It’s been my unpleasant experience that any statement that starts
“Shouldn’t it be the programmer’s responsibility” generally has as
its second sentence “Unfortunately they don’t so often that it’s
worth having the computer do it instead.”

There’s an amazing amount of redundancy that can be removed from a
program that you didn’t realize was there in the first place, and it
doesn’t take long for even a lightly maintained program to end up
with soggy bits. The compiler is also the only thing that ever truly
has a complete view of your program, if anything ever does, and so is
in a position to do things at compile time that may only be valid for
that compilation because libraries change or whatever.

Besides, programmers are human and humans have a limit, often a very
small limit, to the number of things they can juggle in their heads
at once. Computers are awfully stupid in many ways, but they can
juggle a lot of things simultaneously.

For a painful lesson, find a piece of well-written C code. (It isn’t
tough, really) Run it through the compiler, once with optimizations
on just a little (not even the really aggressive ones), and once with
them off. You’d be amazed at the speedup you get from even simple
things. Yes, C isn’t Ruby/Perl/Python/Scheme/Whatever. Still, the
comparison is valid.

···

At 11:25 AM +0900 1/6/03, Tim Bates wrote:

On Mon, 6 Jan 2003 12:45 pm, Dan Sugalski wrote:

Anyway, why would one have such a complex expression within a loop?

It’s not uncommon to have expressions that look non-constant that
turn out to really be constant once surrounding code’s analyzed.

Shouldn’t it be the programmer’s responsibility to find these cases and take
them outside of the loop while optimising eir code?

–
Dan

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