Why this function call in Scala is not optimized away?

Question

I'm running this program with Scala 2.10.3:

object Test {
  def main(args: Array[String]) { 
    def factorial(x: BigInt): BigInt = 
      if (x == 0) 1 else x * factorial(x - 1)

    val N = 1000
    val t = new Array[Long](N)
    var r: BigInt = 0

    for (i <- 0 until N) {
      val t0 = System.nanoTime()

      r = r + factorial(300)
      t(i) = System.nanoTime()-t0
    }

    val ts = t.sortWith((x, y) => x < y)

    for (i <- 0 to 10)
      print(ts(i) + "  ")

    println("***  " + ts(N/2) + "\n" + r)
  }  
}

and call to a pure function factorial with constant argument is evaluated during each loop iteration (conclusion based on timing results). Shouldn't the optimizer reuse function call result after the first call?

I'm using Scala IDE for Eclipse. Are there any optimization flags for the compiler, which may produce more efficient code?

If `*` on `BigInt` is pure then `factorial` is pure. I just spent a day reading Programming in Scala, so I my knowledge is too thin on subject of Scala compiler. My main point is that a similar code in C++ or D compiled by LLVM will have repeating calls to a function with constant argument optimized away. — Paul Jurczak, Oct 12 '13 at 11:29
@PaulJurczak by the way, can you provide link on some article, paper or something about this optimization in LLVM? I mean *similar code in C++ or D compiled by LLVM will have repeating calls to a function with constant argument optimized away* — om-nom-nom, Oct 13 '13 at 11:59
@om-nom-nom Here the link to my post to D lang forum about this optimization: http://forum.dlang.org/thread/utwrmmycxfxncflofksf@forum.dlang.org It is not the same code, but very similar circumstances. I tested `e28` function with Scala and the constant call is not optimized away. — Paul Jurczak, Oct 14 '13 at 01:25

score 6 · Accepted Answer · edited May 23 '17 at 12:21

6

Scala is not a purely functional language, so without an effect system it cannot know that factorial is pure (for example, it doesn't "know" anything about the multiplication of big ints).

You need to add your own memoization approach here. Most simply add a val f300 = factorial(300) outside your loop.

Here is a question about memoization.

edited May 23 '17 at 12:21

Community

1
1

answered Oct 11 '13 at 10:59

0__

66,707
21
171
266

1

Is there a way to let Scala compiler know that `factorial` is pure (or pure enough)? – Paul Jurczak Oct 11 '13 at 11:10
2

@PaulJurczak no simple way, unless you do all the work on your own or plug in some compiler plugin. And here is another reason -- unlike compiled languages like C++ or C, Scala and Java compilers do not perform aggressive optimizations during compilation -- they defer most of the sophisticated optimizations in a hope that JIT will do them. – om-nom-nom Oct 11 '13 at 11:16
1

There is [an effects plugin](http://lrytz.github.io/slides/lamp-lara-efftp.html#/) for Scala, but while that 'type-checks' that your effects are correctly composed, it does not attempt to deal with optimisations such as memoising function values. Probably you _could add_ a `@memoize` macro to functions and require that they be `@pure` as well... – 0__ Oct 11 '13 at 11:16
[Here is some further discussion](http://www.scala-lang.org/old/node/12361.html) if memoisation should be a language feature or not. Eugene Burmako in fact suggests a `@memo` macro... – 0__ Oct 11 '13 at 11:20
In this case I was looking for no memoisation, as it would defeat this micro-benchmark. I was surprised though, that optimizer is not smart enough. LLVM, for example, deals with situation like this with ease. – Paul Jurczak Oct 11 '13 at 11:39

Why this function call in Scala is not optimized away?

1 Answers1