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
- The Haskell solution runs in 36 seconds (due to the
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
Intand the time changes to 11.1 seconds
factorCount'you have needlessly called
fromIntegral. A fix results in no change though (the compiler is smart, lucky for you).
- You used
remis faster and sufficient. This changes the time to 8.5 seconds.
factorCount'is constantly applying two extra arguments that never change (
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.
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
Word64 (C isn't the only language with a
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
- 1) Use fast (notably: unbox-able) types when possible
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.