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

[GoogleCodeExporter]

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).

Original issue reported on code.google.com by bungle...@googlemail.com on 5 Jul 2011 at 10:34

[GoogleCodeExporter]

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

Original comment by olivier.chafik@gmail.com on 6 Jul 2011 at 3:59

• Added labels: Type-Enhancement, Priority-Low
• Removed labels: Type-Defect, Priority-Medium

[GoogleCodeExporter]

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.

Original comment by bungle...@googlemail.com on 19 Aug 2011 at 12:37

[GoogleCodeExporter]

Hi,
This issue moved to Github :
https://github.com/ochafik/nativelibs4java/issues/78

Thanks for not updating this page anymore and adding further comments on Github.
Cheers
--
zOlive

Original comment by olivier.chafik@gmail.com on 1 Sep 2011 at 7:32

• Changed state: MigratedToGitHub