CODEWITHSUNDEEP
performancehaskellfunctional-programming
jhamra
jhamra

Reputation: 39

Haskell program runs very slow

I wrote my first program calculating prime numbers. However it runs really slow, and I can't figure out why. I wrote similar code in java and for n = 10000 the java program doesn't take any time, while the Haskell program takes like 2 minutes.

import Data.List
main = do
    print "HowManyPrimes? - OnlyInteger"
    inputNumber <- getLine
    let x = (read inputNumber :: Int)
    print (firstNPrimes x)

-- prime - algorithm
primeNumber:: Int -> Bool
primeNumber 2 = True
primeNumber x = primNumberRec x (div x 2)

primNumberRec:: Int -> Int -> Bool
primNumberRec x y
      |y == 0 = False
      |y == 1 = True 
      |mod x y == 0 = False
      |otherwise = primNumberRec x (y-1)

-- prime numbers till n
primesTillN:: Int -> [Int]
primesTillN n = 2:[ x | x <- [3,5..n], primeNumber x ]


--firstNPrimes
firstNPrimes:: Int -> [Int]
firstNPrimes 0 = []
firstNPrimes n = 2: take (n-1) [x|x <- [3,5..], primeNumber x]

Thanks in advance.

Similar java code:

import java.util.Scanner;
public class PrimeNumbers{

static Scanner scan = new Scanner(System.in);

public boolean primeAlgorithm(int x){
    if (x < 2)
        return false;
    return primeAlgorithm(x, (int)Math.sqrt(x));
}

public boolean primeAlgorithm(int x, int divider){
    if (divider == 1)
        return true;
    if (x%divider == 0)
        return false;
    return primeAlgorithm(x, divider-1);
}

public static void main(String[] args){

    PrimeNumbers p = new PrimeNumbers();
    int howManyPrimes = scan.nextInt();
    int number = 3;
    while(howManyPrimes!=0){
        if(p.primeAlgorithm(number)){
            System.out.print(number+" ");
            howManyPrimes--;
        }
        number+=2;
    }

}

}

Upvotes: 2

Views: 349

Answers (2)

Daniel Wagner
Daniel Wagner

Reputation: 153342

When doing timing measurements, always compile; ghci is designed for a fast change-rebuild-run loop, not for speedy execution of the produced code. However, even after following this advice there is a huge timing difference between your two snippets.

The key difference between your java and Haskell is using sqrt instead of dividing by 2. Your originals, on my machine:

% javac Test.java && echo 10000 | /usr/bin/time java Test >/dev/null                             
0.21user 0.02system 0:00.13elapsed 186%CPU (0avgtext+0avgdata 38584maxresident)k
0inputs+0outputs (0major+5823minor)pagefaults 0swaps
% ghc -O2 test && echo 10000 | /usr/bin/time ./test >/dev/null
8.85user 0.00system 0:08.87elapsed 99%CPU (0avgtext+0avgdata 4668maxresident)k
0inputs+0outputs (0major+430minor)pagefaults 0swaps

So 0.2s for java, 8.9s for Haskell. After switching to using square root with the following change:

- primeNumber x = primNumberRec x (div x 2)
+ primeNumber x = primNumberRec x (ceiling (sqrt (fromIntegral x)))

I get the following timing for the Haskell:

% ghc -O2 test && echo 10000 | /usr/bin/time ./test >/dev/null
0.07user 0.00system 0:00.07elapsed 98%CPU (0avgtext+0avgdata 4560maxresident)k
0inputs+0outputs (0major+427minor)pagefaults 0swaps

Now 3x faster than the java code. (And of course there are significantly better algorithms that will make it even faster still.)

Upvotes: 8

Lorenzo
Lorenzo

Reputation: 2210

Compile it!

Haskell code in GHCi is far from optimised; try to compile it into a binary with ghc -o prime prime.hs or even better use -O2 optimisation. I had a script once that took 5min in GHCi but mere seconds once compiled.

Upvotes: 5

Related Questions