scalac -optimise with surprising effect

decompile it and share the results

Am 21.08.2011 15:09, schrieb Daniel D.:
> object Test extends App{
> val ar = Array.ofDim[Int](5)
>
> var x = 0
> while(x<=5){
> println(x)
> val a = ar(x)
> x+=1
> }
> }
>
> compiling this just with scalac gives an
> ArrayIndexOutOfBoundsException, as expected.
>
> with scalac -optimize it works. What is -optimize magically doing with
> the code? Does it really check for IndexBounds?
> The same holds true if using a for loop instead of a while.
>
> I have to say I was surprised by this behavior...
>
> Dan
>

On Sun, Aug 21, 2011 at 2:09 PM, Daniel D.
wrote:
> with scalac -optimize it works. What is -optimize magically doing with
> the code?

Seems like a bug in the optimiser. It seems that the dead code
elimination phase is removing code that is not actually dead.

Best,
Ismael

On 21/08/2011 15:58, Ismael Juma wrote:
> Seems like a bug in the optimiser. It seems that the dead code
> elimination phase is removing code that is not actually dead.

Well, it is dead, since the value of a isn't used.
If it is used, eg. writing x+=1+a, the code isn't eliminated.

That's why when making microbenchmarks (eg. with Caliper), it is
recommended to use the result of the code to test. Although Caliper
detects when the results are nearly the same with different number of
iterations (suspecting empty loops).

On Sun, Aug 21, 2011 at 3:22 PM, Philippe Lhoste wrote:
> Well, it is dead, since the value of a isn't used.

It is not dead as an ArrayOutOfBoundsException is generated if the
code is not eliminated. The optimiser is changing the behaviour of the
program in a way that it should not.

> That's why when making microbenchmarks (eg. with Caliper), it is recommended
> to use the result of the code to test.

You're confusing things. The JVM would not eliminate code that throws
an exception if not eliminated. That would be a bug.

Best,
Ismael

On Sunday 21 August 2011, Philippe Lhoste wrote:
> On 21/08/2011 15:58, Ismael Juma wrote:
> > Seems like a bug in the optimiser. It seems that the dead code
> > elimination phase is removing code that is not actually dead.
>
> Well, it is dead, since the value of a isn't used.
> If it is used, eg. writing x+=1+a, the code isn't eliminated.

In addition to what Ismael wrote, the compiler cannot validly assume
that the expression ar(x) has no side effects.

> ...

Randall Schulz

On Sun, Aug 21, 2011 at 11:29 AM, Randall R Schulz <rschulz@sonic.net> wrote:

On Sunday 21 August 2011, Philippe Lhoste wrote:
> On 21/08/2011 15:58, Ismael Juma wrote:
> > Seems like a bug in the optimiser. It seems that the dead code
> > elimination phase is removing code that is not actually dead.
>
> Well, it is dead, since the value of a isn't used.
> If it is used, eg. writing x+=1+a, the code isn't eliminated.

In addition to what Ismael wrote, the compiler cannot validly assume
that the expression ar(x) has no side effects.

What side-effects does accessing an array have?

Also, I don't consider it a bug when dead code that has errors is eliminated.  You might also have run out of memory when you executed the code, so by that logic you'd never be able to eliminate allocations.  Or you might divide by zero, so you can't eliminate integer division.

  --Rex

i'd say the optimizer did not change the *desired* functions of the program. it just changed an *undesired* one. which is both funny and good.

Am 21.08.2011 19:48, schrieb Rex Kerr:

CAP_xLa0pafnsOMxsdkczwO70O5NYnugqGUL6_oRRMcWyUOtMpA [at] mail [dot] gmail [dot] com" type="cite"> On Sun, Aug 21, 2011 at 11:29 AM, Randall R Schulz <rschulz [at] sonic [dot] net" rel="nofollow">rschulz@sonic.net> wrote:

On Sunday 21 August 2011, Philippe Lhoste wrote:
> On 21/08/2011 15:58, Ismael Juma wrote:
> > Seems like a bug in the optimiser. It seems that the dead code
> > elimination phase is removing code that is not actually dead.
>
> Well, it is dead, since the value of a isn't used.
> If it is used, eg. writing x+=1+a, the code isn't eliminated.

In addition to what Ismael wrote, the compiler cannot validly assume
that the expression ar(x) has no side effects.

What side-effects does accessing an array have?

Also, I don't consider it a bug when dead code that has errors is eliminated.  You might also have run out of memory when you executed the code, so by that logic you'd never be able to eliminate allocations.  Or you might divide by zero, so you can't eliminate integer division.

  --Rex

On Sunday 21 August 2011, Rex Kerr wrote:
> On Sun, Aug 21, 2011 at 11:29 AM, Randall R Schulz
wrote:
> > On Sunday 21 August 2011, Philippe Lhoste wrote:
> > > On 21/08/2011 15:58, Ismael Juma wrote:
> > > > Seems like a bug in the optimiser. It seems that the dead code
> > > > elimination phase is removing code that is not actually dead.
> > >
> > > Well, it is dead, since the value of a isn't used.
> > > If it is used, eg. writing x+=1+a, the code isn't eliminated.
> >
> > In addition to what Ismael wrote, the compiler cannot validly
> > assume that the expression ar(x) has no side effects.
>
> What side-effects does accessing an array have?

I wouldn't expect the compiler to know about such special cases. In
general, invoking a value's apply() method through the
function-application sugar has unknown and unlimited side-effects.

> Also, I don't consider it a bug when dead code that has errors is
> eliminated.

Exceptions aren't errors. They're a guarantee from the semantics of the
language and / or its built-in classes.

> You might also have run out of memory when you executed
> the code, so by that logic you'd never be able to eliminate
> allocations.

Running out of memory _is_ an error. In particular, it's not
deterministic when it will happen nor is it indicative of anything
about the code executing when it occurs. That's why it's an Error, not
an Exception.

> Or you might divide by zero, so you can't eliminate
> integer division.

That is not an error, it's an exception and is part of the specified and
deterministic semantics of the language and / or its libraries.

> --Rex

Randall Schulz

>
> That is not an error, it's an exception and is part of the specified and
> deterministic semantics of the language and / or its libraries.
>
That is only true for checked exceptions Java.

ArrayIndexOutOfBoundsException is a RuntimeException which is
unchecked like all exceptions in Scala.

A compiler (and thus the optimizer) cannot know about runtime
exceptions otherwise it would have raise a compile time exception.

On Sunday 21 August 2011, Dave wrote:
> > That is not an error, it's an exception and is part of the
> > specified and deterministic semantics of the language and / or its
> > libraries.
>
> That is only true for checked exceptions Java.
>
> ArrayIndexOutOfBoundsException is a RuntimeException which is
> unchecked like all exceptions in Scala.
>
> A compiler (and thus the optimizer) cannot know about runtime
> exceptions otherwise it would have raise a compile time exception.

I didn't say anything about the checked / unchecked distinction.

Unchecked exceptions are still deterministic. Errors are not necessarily
so.

I actually don't know what your point is. Mine is that Ismael was right,
the compiler was wrong to eliminate the calls to ar(x).

Randall Schulz

It's normal optimizer behaviour. val a is not used and ar(x) is read
out only once for this unused val a and ar is immutable and
ArrayIndexOutOfBoundsException is a runtime exception

If an optimizer must take all possible runtime exceptions in account
then an optimizer can never do its work because a runtime exception
can occur almost everywhere.

Thus never blind trust optimized code, also test without optimizer.
Remove dead code because the only thing it can do is raising a runtime
exception.
This is also a known code smell:

Smell: Dead Code
Description: A variable, parameter, method, code fragment, class, etc
is not used anywhere (perhaps other than in tests).
Refactorings: Delete the code.

See: http://wiki.java.net/bin/view/People/SmellsToRefactorings

See here for the decompiled code
http://www.scala-lang.org/node/10711

Maybe a micro-optimization is removing line:
this.$outer.ar(); this.$outer.x();
as well

Google mailing list and forum and Scala forum sometimes don't
synchronize the threads well.

On 21 aug, 22:12, Randall R Schulz wrote:
> On Sunday 21 August 2011, Dave wrote:
>
> > > That is not an error, it's an exception and is part of the
> > > specified and deterministic semantics of the language and / or its
> > > libraries.
>
> > That is only true for checked exceptions Java.
>
> > ArrayIndexOutOfBoundsException is a RuntimeException which is
> > unchecked like all exceptions in Scala.
>
> > A compiler (and thus the optimizer) cannot know about runtime
> > exceptions otherwise it would have raise a compile time exception.
>
> I didn't say anything about the checked / unchecked distinction.
>
> Unchecked exceptions are still deterministic. Errors are not necessarily
> so.
>
> I actually don't know what your point is. Mine is that Ismael was right,
> the compiler was wrong to eliminate the calls to ar(x).
>
> Randall Schulz

On Sunday 21 August 2011, Dave wrote:
> It's normal optimizer behaviour. val a is not used and ar(x) is read
> out only once for this unused val a and ar is immutable and
> ArrayIndexOutOfBoundsException is a runtime exception

What does "ar is immutable" mean?

Immutability is not actually a Scala concept, certainly not beyond
method-call boundaries. It exists solely in the single-assignment
nature of vals.

> ...

Randall Schulz

>
> What does "ar is immutable" mean?
>
That ar cannot point to anything else than its first defined array.
It's a val ar.
It doesn't anyway, if you look in the code, but just to emphasize that
it really cannot be anything else.
So I don't see any side effects here, but if there were, it wasn't
important for the dead code 'val a' since it isn't used anyway.

On Sunday 21 August 2011, Dave wrote:
> > What does "ar is immutable" mean?
>
> That ar cannot point to anything else than its first defined array.
> It's a val ar.
> It doesn't anyway, if you look in the code, but just to emphasize
> that it really cannot be anything else.
> So I don't see any side effects here, but if there were, it wasn't
> important for the dead code 'val a' since it isn't used anyway.

You're assuming the compiler has knowledge of Array specifically.

What you can't see is not necessarily something the compiler can deduce.
The point is that there are potentially side effects in calling any
method, even if it's an apply method on an Array.

Randall Schulz

On Sun, Aug 21, 2011 at 5:32 PM, Randall R Schulz <rschulz@sonic.net> wrote:

On Sunday 21 August 2011, Dave wrote:
> > What does "ar is immutable" mean?
>
> That ar cannot point to anything else than its first defined array.
> It's a val ar.
> It doesn't anyway, if you look in the code, but just to emphasize
> that it really cannot be anything else.
> So I don't see any side effects here, but if there were, it wasn't
> important for the dead code 'val a' since it isn't used anyway.

You're assuming the compiler has knowledge of Array specifically.

What you can't see is not necessarily something the compiler can deduce.
The point is that there are potentially side effects in calling any
method, even if it's an apply method on an Array.

Huh?  Array is plain-old-Java-array (now).  Apply is just a handy way to tell the compiler to produce the appropriate *aload bytecode.  If the compiler knows the item is an array--and here it does--there is nothing else to do.

  --Rex

[Moved to scala-debate]

On 8/21/11 10:48 AM, Rex Kerr wrote:
> Also, I don't consider it a bug when dead code that has errors is
> eliminated. You might also have run out of memory when you executed
> the code, so by that logic you'd never be able to eliminate
> allocations. Or you might divide by zero, so you can't eliminate
> integer division.

The former is non-deterministic; the latter is, as far as I know, true. Hans Boehm seems likely to know:

http://gcc.gnu.org/ml/gcc-prs/2002-04/msg01136.html

"Errors" is a value judgment. You are saying it is OK to transform the following code from something which works and deterministically does exactly as the programmer intended into a program which never terminate, if they supply -optimise. The optimizer's oath should be "first, do no harm."

final class A(arr: Array[Int]) {
def size = count(0)
private def count(num: Int): Int = {
try arr(num)
catch { case _: ArrayIndexOutOfBoundsException => return num }

count(num + 1)
}
}

object Test {
def main(args: Array[String]): Unit = {
println(new A(1 to 100 toArray).size)
}
}

Maybe you should check this simple code:

object Test extends App{
for (i <- 0 to 1){
val a = Foo
}
}

object Foo{
println("hello")
}

with scalac it prints "hello"... with -optimize it does nothing.

The optimizer is clearly changing the behavior of the program, and it
has nothing to do with arrays.

On 21 Aug., 23:38, Rex Kerr wrote:
> On Sun, Aug 21, 2011 at 5:32 PM, Randall R Schulz wrote:
>
>
>
>
>
>
>
>
>
> > On Sunday 21 August 2011, Dave wrote:
> > > > What does "ar is immutable" mean?
>
> > > That ar cannot point to anything else than its first defined array.
> > > It's a val ar.
> > > It doesn't anyway, if you look in the code, but just to emphasize
> > > that it really cannot be anything else.
> > > So I don't see any side effects here, but if there were, it wasn't
> > > important for the dead code 'val a' since it isn't used anyway.
>
> > You're assuming the compiler has knowledge of Array specifically.
>
> > What you can't see is not necessarily something the compiler can deduce.
> > The point is that there are potentially side effects in calling any
> > method, even if it's an apply method on an Array.
>
> Huh?  Array is plain-old-Java-array (now).  Apply is just a handy way to
> tell the compiler to produce the appropriate *aload bytecode.  If the
> compiler knows the item is an array--and here it does--there is nothing else
> to do.
>
>   --Rex

Absurd, an optimizer shouldn't change the runtime result of the code it
optimizes, if it does it should be considered a bug. In this case the
array access should only be eliminated if the optimizer can infer that
it will NEVER cause an exception. Actually, in this case it can infer
that it will ALWAYS throw an exception when x == 5, so it could possibly
optimize for that.

I agree that you shouldn't blindly trust optimized code, but only
because optimizers usually are full of bugs. I usually trust Hotspot to
do it's job properly, but gcc for example has had a number of bugs in
it's optimizers.

/Jesper Nordenberg

Dave skrev 2011-08-21 22:35:
> It's normal optimizer behaviour. val a is not used and ar(x) is read
> out only once for this unused val a and ar is immutable and
> ArrayIndexOutOfBoundsException is a runtime exception
>
> If an optimizer must take all possible runtime exceptions in account
> then an optimizer can never do its work because a runtime exception
> can occur almost everywhere.
>
> Thus never blind trust optimized code, also test without optimizer.
> Remove dead code because the only thing it can do is raising a runtime
> exception.
> This is also a known code smell:
>
> Smell: Dead Code
> Description: A variable, parameter, method, code fragment, class, etc
> is not used anywhere (perhaps other than in tests).
> Refactorings: Delete the code.
>
> See: http://wiki.java.net/bin/view/People/SmellsToRefactorings
>
> See here for the decompiled code
> http://www.scala-lang.org/node/10711
>
> Maybe a micro-optimization is removing line:
> this.$outer.ar(); this.$outer.x();
> as well
>
> Google mailing list and forum and Scala forum sometimes don't
> synchronize the threads well.
>
>
> On 21 aug, 22:12, Randall R Schulz wrote:
>> On Sunday 21 August 2011, Dave wrote:
>>
>>>> That is not an error, it's an exception and is part of the
>>>> specified and deterministic semantics of the language and / or its
>>>> libraries.
>>
>>> That is only true for checked exceptions Java.
>>
>>> ArrayIndexOutOfBoundsException is a RuntimeException which is
>>> unchecked like all exceptions in Scala.
>>
>>> A compiler (and thus the optimizer) cannot know about runtime
>>> exceptions otherwise it would have raise a compile time exception.
>>
>> I didn't say anything about the checked / unchecked distinction.
>>
>> Unchecked exceptions are still deterministic. Errors are not necessarily
>> so.
>>
>> I actually don't know what your point is. Mine is that Ismael was right,
>> the compiler was wrong to eliminate the calls to ar(x).
>>
>> Randall Schulz
>

Since Daniel D. has demonstrated that the optimizer elides side-effecting code, this is mostly a moot point; the current behavior is broken.  But...

On Sun, Aug 21, 2011 at 6:28 PM, Paul Phillips <paulp@improving.org> wrote:

You are saying it is OK to transform the following code from something which works and deterministically does exactly as the programmer intended into a program which never terminate, if they supply -optimise.

Yes, that's exactly what I'm saying: under very well-defined conditions, -optimize may make certain strange code constructs no longer produce the same result.  For example, optimization plays all sorts of havoc with race conditions, changes timing on real-time architectures, and so on, and this is all perfectly fine (and almost part of the point).  The trick is in how to define those conditions; maybe one can't do it elegantly enough to be a good idea, even if it would enable a wider range of almost-always-the-right-thing-to-do optimizations.

  --Rex

On 22/08/2011 00:31, Daniel D. wrote:
> Maybe you should check this simple code:
>
> object Test extends App{
> for (i<- 0 to 1){
> val a = Foo
> }
> }
>
> object Foo{
> println("hello")
> }
>
>
> with scalac it prints "hello"... with -optimize it does nothing.

This one is annoying, indeed. While the following isn't compiled away:

object Test extends App {
object ar {
def apply(i: Int) = { println("ar" + i); i }
}

var x = 0
while (x <= 5) {
println(x)
val a = ar(x)
x += 1
}
}

Am Montag, 22. August 2011, 09:35:32 schrieb Philippe Lhoste:
> On 22/08/2011 00:31, Daniel D. wrote:
> > Maybe you should check this simple code:
> >
> > object Test extends App{
> >
> > for (i<- 0 to 1){
> >
> > val a = Foo
> >
> > }
> >
> > }
> >
> > object Foo{
> >
> > println("hello")
> >
> > }
> >
> >
> > with scalac it prints "hello"... with -optimize it does nothing.
>
> This one is annoying, indeed. While the following isn't compiled away:

To my eyes this is not only annoying - it is plain and simple a bug and should
be treated as such.

Trying to optimize the statement above (based on the non-use of val a) without
the prove that Foo is pure opens the door to "optimize induced nightmares".
You can't even catch it reliably by debugging. Just by staring at bytecode...

And the argument "you shouldn't do this firstplace" cannot be applied here.
It's about the promise of the optimizer not to change the semantic of your
code (or I misunderstood the general perspective of the scala optimizer).

I vote "no". [which has no implication - I know :-)]

Greetings
Bernd

The compiler (and generic optimizer) doesn't know about side-effects
and runtime-errors otherwise it needs a table to tell the difference
which kind of code produces side-effects and runtime exceptions and
which are pure code (side-effect/runtimeexception free).

From the compiler (+ optimizer) perspective:

object Test extends App{
for (i <- 0 to 1){
val a = Foo
}
}

object Foo{
println("hello")
}

is actually

object Test extends App{
for (i <- 0 to 1){
val a = Foo
}
}

object Foo{
()
}

which is doing nothing.

Otherwise there should be knowledge about println and Array that it
does something or can do something like a built-in lookup table and/or
an explicit annotation for example:

@SuppressOptimization(sideeffects={"println"})
object Test extends App{
for (i <- 0 to 1){
val a = Foo
}
}

object Foo{
println("hello")
}

@SuppressOptimization(sideeffects={"println"}
runtimeexceptions={"Array"}
)
object Test extends App{
val ar = Array.ofDim[Int](5)

var x = 0
while(x<=5){
println(x)
val a = ar(x)
x+=1
}
}

On Sun, Aug 21, 2011 at 6:48 PM, Rex Kerr wrote:
> Also, I don't consider it a bug when dead code that has errors is
> eliminated.

By that reasoning the optimiser could also remove calls to require and
assert in Predef. Code that throws exceptions is not dead! Anyway,
Paul has fixed one of the issues and filed an issue for the other:

https://codereview.scala-lang.org/fisheye/changelog/scala-svn?cs=25538
https://issues.scala-lang.org/browse/SI-4935

Best,
Ismael