Hello everybody, I am a newbie to haskell. I was wondering if there are things I need to do to make the following code faster. I have tried changing the Integer to Int but did not help much.. https://gist.github.com/c1ee2d6397cd5b28ade5 Thanks in advance. Sunil.
On Friday 19 August 2011, 12:02:30, Sunil S Nandihalli wrote:
Hello everybody, I am a newbie to haskell. I was wondering if there are things I need to do to make the following code faster.
From a short look, you'll probably need a faster prime generation, try a sieve of Eratosthenes, that's pretty fast. The rest looks okay
I have tried changing the Integer to Int but did not help much..
https://gist.github.com/c1ee2d6397cd5b28ade5
Thanks in advance. Sunil.
Thanks Daniel for your response. sieve of Eratosthenes has a very
elegant 1 line implementation thanks to laziness of haskell. Here is
what I came up with
primesSieve = 2:3:5:7:11:(filter (\x->(all (\p-> 0/=(mod x p))
(takeWhile (\p-> p*p<=x) primesSieve))) [13..])
But didn't seem to make a difference in performance. I had missed the
most obvious of things.... that is adding -O2 when compiling.. It gave
a speedup of close to 100 times which was very surprising! .. I
remember people setting some compiler options in the source file
itself. Can you shed some light on that?
Thanks,
Sunil.
On Fri, Aug 19, 2011 at 3:55 PM, Daniel Fischer
On Friday 19 August 2011, 12:02:30, Sunil S Nandihalli wrote:
Hello everybody, I am a newbie to haskell. I was wondering if there are things I need to do to make the following code faster.
From a short look, you'll probably need a faster prime generation, try a sieve of Eratosthenes, that's pretty fast. The rest looks okay
I have tried changing the Integer to Int but did not help much..
https://gist.github.com/c1ee2d6397cd5b28ade5
Thanks in advance. Sunil.
On Saturday 20 August 2011, 10:50:00, Sunil S Nandihalli wrote:
Thanks Daniel for your response. sieve of Eratosthenes has a very elegant 1 line implementation thanks to laziness of haskell. Here is what I came up with
primesSieve = 2:3:5:7:11:(filter (\x->(all (\p-> 0/=(mod x p)) (takeWhile (\p-> p*p<=x) primesSieve))) [13..])
Umm, I meant a real sieve, using an array. It's more complicated to implement, but much faster.
But didn't seem to make a difference in performance. I had missed the most obvious of things.... that is adding -O2 when compiling..
I never think of people compiling without optimisations, of course that's the very first thing to do.
It gave a speedup of close to 100 times which was very surprising! ..
Not really, without optimisations, you get no specialisations etc, so instead of the appropriate operations for the type you use, you get the generic ones (with a dictionary lookup). The type-specific operations often allow further optimisations, so things often become orders of magnitude faster. If you write overloaded functions, it's generally a good idea to tell GHC to specialise them for the most commonly used types (say Int and Integer in this example), {-# SPECIALISE foo :: Int -> Int, Integer -> Integer #-} Then, when everything is compiled with optimisations, the specialised versions are used when there exists one. (In your case, since main is in the same module, GHC usually specialises the function for the type used in main by itself [with -O2, at least when the functions are not exported], so it's not immediately necessary to add a specialise-pragma.)
I remember people setting some compiler options in the source file itself. Can you shed some light on that?
A pragma {-# OPTIONS_GHC -O2 #-} at the top of the module.
Thanks, Sunil.
participants (2)
-
Daniel Fischer -
Sunil S Nandihalli