Loop optimization: Range forall slower if Range is value rather than literal

[ochafik]

From @ochafik on September 1, 2011 18:34

In Scala, if you run the test

object P005 extends App{
val t = System.currentTimeMillis

val r = (1 to 20)
def isDivis(x:Int) = r forall {x % _ == 0}
def find(n:Int):Int = if (isDivis(n)) n else find (n+2)

println (find (2))
println((System.currentTimeMillis - t)/1000.0)
}

the forall is not optimized to a while loop, and runs in the same time as without ScalaCL.

If you replace the "r" with its value (1 to 20), i.e.
def isDivis(x:Int) = (1 to 20) forall {x % _ == 0}
it is optimized and runs over 4 times faster.

I think we should be able to get the same performance in both cases, since r is immutable, we know it will still be (1 to 20).

Google Code Info:
Issue #: 76
Author: [email protected]
Created On: 2011-07-05T22:34:16.000Z
Closed On:

Copied from original issue: nativelibs4java/nativelibs4java#78

[ochafik]

Hello,

Thanks for your report !

Loops on general ranges is indeed not supported yet (only inline ranges are), because they're quite a bit more difficult to handle.

Of course in the case of ranges with constant bounds as in your example, the compiler plugin to reach the definition and proceed as usual, but things get nastier when the bounds are general expressions (which is usually the case).

In the general case we'd have to extract the start, end, step and inclusive values of the Range, and the loop code would be more complex, since the way to iterate depends on both the sign of step and the inclusive parameter. Having different loops and a dynamic switch is not an option (code bloat + JIT dispersion), so we'd have weird conditionals in the while loop's condition that would make it slower (albeit probably not that much slower)...
Given the complexity, I'm putting this under low priority, even though for sure it would be a nice to have !

Cheers

zOlive

Google Code Info:
Author: olivier.chafik
Created On: 2011-07-06T15:59:17.000Z

[ochafik]

Thanks. I hope the ScalaCL project continues to progress well, as it has great potential! The looping enhancements alone can improve performance massively. They would make a fine addition to the standard scalac implementation.

Google Code Info:
Author: [email protected]
Created On: 2011-08-19T00:37:58.000Z