To test, I created a driver. The driver would vary the numbers in the input list, basically 1..N where N was varied. It would then measure the time it took to wallify the list 100 times. The JVM was the 1.5 JVM for OSX with the -server flag set. I was also giving it 1GB of memory (more on that later.) Here is what it looked like in Java:
And in Scala:
Very similar. There was no noticeable performance loss in Scala. Of course there is an obvious problem here. This algorithm should have been linear with respect to the size of the list, N. This is clearly not linear! I took the logarithms of both the size and the time, and found a correlation of about 0.996. This algorithm is actually quadratic.
I thought that maybe my algorithm just sucked. I tried a couple of other Scala ones. One provided by Jorge Ortiz and one created by the group led by Bill Venners. The both had the exact same performance characteristics as my algorithm, i.e. they were quadratic as well.
The only thing I could think of was garbage collection. I put on gc:verbose and watched a lot of garbage being collected. I upped the heap to 1 GB, but it had no effect. So I am not sure if GC is really the culprit or not.
Update: James Iry had a great insight. Java's BigInteger computation is linear once things get big. To keep them small, you can use all 1's. Here is what the performance looked like then, just for my original Scala code.
Ok, that's not quadratic anymore. I wasn't sure if it was linear (I was paranoid about compiler tricks given the list of 1's that was being multiplied) either, so I actually extended the test with more data points. With a few more data points, I got a nice correlation of 0.993 for a linear fit. This confirms that the algorithm itself is linear for small numbers, but is quadratic for larger numbers where high performance integer math becomes significant.