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

by

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.

More Related Contents:

  1. It is more efficient to use if-return-return or if-else-return?
  2. Is doing multiplication multiple times or assigning to a variable faster?
  3. pandas loc vs. iloc vs. at vs. iat?
  4. What is the best way to generate all possible three letter strings?
  5. Why is [] faster than list()?
  6. Why is numpy’s einsum faster than numpy’s built in functions?
  7. How do I measure elapsed time in Python?
  8. Which is faster in Python: x**.5 or math.sqrt(x)?
  9. Numpy: Fix array with rows of different lengths by filling the empty elements with zeros
  10. Performance with global variables vs local
  11. Complexity of list.index(x) in Python
  12. Python faster than compiled Haskell?
  13. Python ? (conditional/ternary) operator for assignments [duplicate]
  14. Using Cython To Link Python To A Shared Library
  15. What is the fastest way to output large DataFrame into a CSV file?
  16. How expensive are Python dictionaries to handle?
  17. C++ conversion from NumPy array to Mat (OpenCV)
  18. Why shouldn’t I use PyPy over CPython if PyPy is 6.3 times faster?
  19. Why is any (True for … if cond) much faster than any (cond for …)?
  20. Fast way to copy dictionary in Python
  21. What is the most efficient way to check if a value exists in a NumPy array?
  22. Is MATLAB faster than Python?
  23. Efficient dot products of large memory-mapped arrays
  24. Embedding Python in C, linking fails with undefined reference to `Py_Initialize’
  25. Writing code translator from Python to C? [closed]
  26. Installing lxml for Python 3.4 on Windows x 86 (32 bit) with Visual Studio C++ 2010 Express
  27. Can I perform dynamic cumsum of rows in pandas?
  28. Extending python – to swig, not to swig or Cython
  29. deque.popleft() and list.pop(0). Is there performance difference?
  30. Call python code from c via cython

Leave a Comment