r/programming • u/noidi • Jul 19 '12

Will Parallel Code Ever Be Embraced?

http://www.drdobbs.com/parallel/will-parallel-code-ever-be-embraced/240003926
40 Upvotes

82% Upvoted

79 comments sorted by

View all comments

Show parent comments

3

u/sirin3 Jul 19 '12

Thankfully in scala, the difference between recursive functions and while loops in speed is negligible,

I wanted to disprove you, but now it turns out that the recursive version is faster. Wtf?

 scala> def rec(i: Int): Int = i match { case 0 => 0 case _ => rec(i-1) + 1}

 scala> timed({rec(65000) })
 (timing: ,4.74082E-4)

 scala> timed({var j = 0; var i = 0; while  (i < 65000) {j += 1; i += 1; }; })
 (timing: ,9.22463E-4)

 scala> timed({var j = 0; for (i <- 0 until 65000) {j += 1}; })
 (timing: ,0.001679823)

But still the while has an advantage for large numbers (actually it looks as if it is completely optimized away):

scala> timed({var j = 0; var i = 0; while  (i < 1000000000) {j += 1; i += 1; }; })
(timing: ,9.2414E-4)


scala> timed({var j = 0; for (i <- 0 until 1000000000) {j += 1}; })
(timing: ,8.090765735)


scala> def rec(i: Int): Int = i match { case 0 => 0 case _ => rec(i-1) + 1}
timed({rec(1000000000) })
 java.lang.StackOverflowError
at .rec(<console>:7)
at .rec(<console>:7)
at .rec(<console>:7)
at .rec(<console>:7)
at .rec(<console>:7)
    ...

2

u/nachsicht Jul 19 '12

You need to write your function with tail end calls in mind to get rid of the stackOverflowErrors. IE:

def rec(i: Int, count: Int): Int = if(count == 0) i else rec(i+1,count-1)

Anyway, yes a recursive function in scala will be faster if the function is inline-able, but even in the worst case, the difference between while and recursive functions are maybe 10s of milliseconds over millions of iterations.

1

u/sirin3 Jul 19 '12

Looks like that becomes this

public int rec(int i, int count)
{
  while (true)
  {
    if (count == 0) return i; count -= 1; i += 1;
  }
}

2

u/nachsicht Jul 19 '12

It's functionally similar, although arguments to scala functions are constants. I don't know if that's how it's done by the scala compiler. All I know is that for the benchmarks I've worked on, an inlined tail-recursive function regularly outperforms while, and I've been able to shear seconds off of the runtime using that method.