Speed comparison with Project Euler: C vs Python vs Erlang vs Haskell

Question

I have taken Problem #12 from Project Euler as a programming exercise and to compare my (surely not optimal) implementations in C, Python, Erlang and Haskell. In order to get some higher execution times, I search for the first triangle number with more than 1000 divisors instead of 500 as stated in the original problem. The result is the following: C: ``` lorenzo@enzo:~/erlang$ gcc -lm -o euler12.bin euler12.c lorenzo@enzo:~/erlang$ time ./euler12.bin 842161320 real 0m11.074s user 0m11.070s sys 0m0.000s ``` Python: ``` lorenzo@enzo:~/erlang$ time ./euler12.py 842161320 real 1m16.632s user 1m16.370s sys 0m0.250s ``` Python with PyPy: ``` lorenzo@enzo:~/Downloads/pypy-c-jit-43780-b590cf6de419-linux64/bin$ time ./pypy /home/lorenzo/erlang/euler12.py 842161320 real 0m13.082s user 0m13.050s sys 0m0.020s ``` Erlang: ``` lorenzo@enzo:~/erlang$ erlc euler12.erl lorenzo@enzo:~/erlang$ time erl -s euler12 solve Erlang R13B03 (erts-5.7.4) [source] [64-bit] [smp:4:4] [rq:4] [async-threads:0] [hip…

Accepted Answer

Using `GHC 7.0.3`, `gcc 4.4.6`, `Linux 2.6.29` on an x86_64 Core2 Duo (2.5GHz) machine, compiling using `ghc -O2 -fllvm -fforce-recomp` for Haskell and `gcc -O3 -lm` for C.

- Your C routine runs in 8.4 seconds (faster than your run probably because of `-O3`)

- The Haskell solution runs in 36 seconds (due to the `-O2` flag)

- Your `factorCount'` code isn't explicitly typed and defaulting to `Integer` (thanks to Daniel for correcting my misdiagnosis here!). Giving an explicit type signature (which is standard practice anyway) using `Int` and the time changes to 11.1 seconds

- in `factorCount'` you have needlessly called `fromIntegral`. A fix results in no change though (the compiler is smart, lucky for you).

- You used `mod` where `rem` is faster and sufficient. This changes the time to 8.5 seconds.

- `factorCount'` is constantly applying two extra arguments that never change (`number`, `sqrt`). A worker/wrapper transformation gives us:

```
 $ time ./so
 842161320

real    0m7.954s  
 user    0m7.944s  
 sys     0m0.004s  
```

That's right, 7.95 seconds. Consistently half a second faster than the C solution. Without the `-fllvm` flag I'm still getting `8.182 seconds`, so the NCG backend is doing well in this case too.

Conclusion: Haskell is awesome.

Resulting Code

```
factorCount number = factorCount' number isquare 1 0 - (fromEnum $ square == fromIntegral isquare)
    where square = sqrt $ fromIntegral number
          isquare = floor square

factorCount' :: Int -> Int -> Int -> Int -> Int
factorCount' number sqrt candidate0 count0 = go candidate0 count0
  where
  go candidate count
    | candidate > sqrt = count
    | number `rem` candidate == 0 = go (candidate + 1) (count + 2)
    | otherwise = go (candidate + 1) count

nextTriangle index triangle
    | factorCount triangle > 1000 = triangle
    | otherwise = nextTriangle (index + 1) (triangle + index + 1)

main = print $ nextTriangle 1 1
```

EDIT: So now that we've explored that, lets address the questions

Question 1: Do erlang, python and haskell lose speed due to using arbitrary length integers or don't they as long as the values are less than MAXINT?

In Haskell, using `Integer` is slower than `Int` but how much slower depends on the computations performed. Luckily (for 64 bit machines) `Int` is sufficient. For portability sake you should probably rewrite my code to use `Int64` or `Word64` (C isn't the only language with a `long`).

Question 2: Why is haskell so slow? Is there a compiler flag that turns off the brakes or is it my implementation? (The latter is quite probable as haskell is a book with seven seals to me.)

Question 3: Can you offer me some hints how to optimize these implementations without changing the way I determine the factors? Optimization in any way: nicer, faster, more "native" to the language.

That was what I answered above. The answer was

- 0) Use optimization via `-O2`

- 1) Use fast (notably: unbox-able) types when possible

- 2) `rem` not `mod` (a frequently forgotten optimization) and

- 3) worker/wrapper transformation (perhaps the most common optimization).

Question 4: Do my functional implementations permit LCO and hence avoid adding unnecessary frames onto the call stack?

Yes, that wasn't the issue. Good work and glad you considered this.

Speed comparison with Project Euler: C vs Python vs Erlang vs Haskell

Solution

Problem

Related problems