why the attached scala code is slower than python code?

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

why the attached scala code is slower than python code?

wangyc
Hi,
I am learning Scala and want to use it to calculate factorial, the code I used is

object bigint extends Application {
    def factorial(n:BigInt): BigInt = {
        def factorialAcc(acc:BigInt, n:BigInt):BigInt = {
            if (n<=1) acc
            else factorialAcc(n*acc, n-1)
        }
        factorialAcc(1,n)
    }
    println("4391!="+factorial(4391))
}

then i use scalac to compile it and "time scala bigint" to run it, and I got the following result:

real    0m0.715s
user    0m0.716s
sys     0m0.060s

Then I got a python code to do the same thing:

import sys
sys.setrecursionlimit(1000000)
def factorial(n):
    if (n==0):
        return 1
    else:
        return n*factorial(n-1)

print("4391!= %d"%factorial(4391))

I use “time python test.py":

real    0m0.202s
user    0m0.108s
sys     0m0.000s

I am wondering why scala is slower than python? I did not do something correct?

Thanks,
Tim

Reply | Threaded
Open this post in threaded view
|

Re: why the attached scala code is slower than python code?

David Hall-17
On Fri, Nov 27, 2009 at 5:17 PM, wangyc <[hidden email]> wrote:

> Hi,
> I am learning Scala and want to use it to calculate factorial, the code I
> used is
>
> object bigint extends Application {
>     def factorial(n:BigInt): BigInt = {
>         def factorialAcc(acc:BigInt, n:BigInt):BigInt = {
>             if (n<=1) acc
>             else factorialAcc(n*acc, n-1)
>         }
>         factorialAcc(1,n)
>     }
>     println("4391!="+factorial(4391))
> }
>
> then i use scalac to compile it and "time scala bigint" to run it, and I got
> the following result:
>
> real    0m0.715s
> user    0m0.716s
> sys     0m0.060s
>
> Then I got a python code to do the same thing:
>
> import sys
> sys.setrecursionlimit(1000000)
> def factorial(n):
>     if (n==0):
>         return 1
>     else:
>         return n*factorial(n-1)
>
> print("4391!= %d"%factorial(4391))
>
> I use “time python test.py":
>
> real    0m0.202s
> user    0m0.108s
> sys     0m0.000s
>
> I am wondering why scala is slower than python? I did not do something
> correct?

Many things:

1) Scala start-up time is slow. The JVM is slow to get going, and the
scala compiler is very slow. Python's startup time is minimal, and its
compiler is fast because it doesn't have to do any type-checking.
2) The JVM is going to be slower than it can be for the first 10,000
function invocations, until the JIT warms up.
3) You're really testing two different implementations of BigInts.
Scala's is based on the Java native implementation, which is known to
be slow, and I don't know what Python's is, but I'm sure it can't be
as bad as Java's :-)

-- David
Reply | Threaded
Open this post in threaded view
|

Re: why the attached scala code is slower than python code?

Randall R Schulz-2
In reply to this post by wangyc
On Friday November 27 2009, wangyc wrote:

> Hi,
> I am learning Scala and want to use it to calculate factorial, the
> code I used is
>
> object bigint extends Application {
>     def factorial(n:BigInt): BigInt = {
>         def factorialAcc(acc:BigInt, n:BigInt):BigInt = {
>             if (n<=1) acc
>             else factorialAcc(n*acc, n-1)
>         }
>         factorialAcc(1,n)
>     }
>     println("4391!="+factorial(4391))
> }
>
> then i use scalac to compile it and "time scala bigint" to run it,
> and I got the following result:
>
> real    0m0.715s
> user    0m0.716s
> sys     0m0.060s

Most of what you're measuring is the JVM start-up time.


> ...
>
> Thanks,
> Tim


Randall Schulz
Reply | Threaded
Open this post in threaded view
|

Re: why the attached scala code is slower than python code?

Aaron Harnly-2-2
> Most of what you're measuring is the JVM start-up time.

Indeed. Replacing the 4391! with 1! in each program, my measured times went from:
Scala: 0.697s to 0.497s
Python: 0.151s to 0.028s

so you can see that startup overhead is the bulk of the time you saw.

Trying to gauge Scala’s performance with ultra-micro benchmarks like that won’t tell you much very interesting, unless you’re in the habit of running extremely short, single-calculation programs a lot.

But while we’re playing that game, replacing the single-shot calculation with a loop that calculates and prints the factorial of each integer from 1 to 4000, I get:

Scala: 1m12s
Python: 2m3s

so there’s clearly an advantage, if not a huge one, for a longer calculation.

~aaron


Reply | Threaded
Open this post in threaded view
|

Re: why the attached scala code is slower than python code?

Nils Kilden-Pedersen
In reply to this post by wangyc
On Fri, Nov 27, 2009 at 7:17 PM, wangyc <[hidden email]> wrote:
object bigint extends Application {

You're using the deprecated Application, which, if I'm not mistaken, means you'll run everything inside the static initializer, which again means not nothing will be JITed.
Reply | Threaded
Open this post in threaded view
|

Re: why the attached scala code is slower than python code?

wangyc
In reply to this post by Aaron Harnly-2-2
Thanks everyone. I Googled a lot about JIT warm up and I learned a lot.

Hope to have more fun with Scala :)

Happy holidays,
Tim

On Fri, Nov 27, 2009 at 8:48 PM, Aaron Harnly <[hidden email]> wrote:
> Most of what you're measuring is the JVM start-up time.

Indeed. Replacing the 4391! with 1! in each program, my measured times went from:
Scala: 0.697s to 0.497s
Python: 0.151s to 0.028s

so you can see that startup overhead is the bulk of the time you saw.

Trying to gauge Scala’s performance with ultra-micro benchmarks like that won’t tell you much very interesting, unless you’re in the habit of running extremely short, single-calculation programs a lot.

But while we’re playing that game, replacing the single-shot calculation with a loop that calculates and prints the factorial of each integer from 1 to 4000, I get:

Scala: 1m12s
Python: 2m3s

so there’s clearly an advantage, if not a huge one, for a longer calculation.

~aaron