Return to Revisions

Looking at your code, one major performance bottleneck will be the repeated use of !! to search a list from the beginning in linear time. Another is the repeated use of mod, which is the slowest integer operation on modern CPUs if it’s in the ISA at all. You also use unfoldr, which can be slower than scanl' or a tail-recursive-modulo-cons function that strictly evaluates its arguments (bang patterns or seq).

Intuitively, you’ll probably speed up this algorithm the most by using a mutable Data.Vector instead of a list. However, that’s not really idiomatic Haskell, so you might prefer lists for that reason.

To speed up this sieve using lists, here is one approach you might try: It’s more of a true sieve of Eratosthenes that finds all primes within a given range, using Int rather than Integer. It’s therefore less flexible than what you wrote.

• Define a tail-recursive helper function sieve :: [Int] -> [Int].
• Call sieve [2..n]. You could also optimize by calling sieve with only the odd numbers between 3 and n, and prepending 2 to the result.
• If the argument to sieve is [], there are no more numbers in range to sieve. Return [].
• Within each call to sieve n (p:potentials), n is the limit of the range, p is definitely prime and potentials is a list of potential primes in range. Splitting the second argument into a head and tail is a constant-time operation.
  • If p*p > n, you have already found all composites in range. All remaining numbers you were given are prime. Return (p:potentials).
  • Otherwise:
    • Generate a list of all multiples of p in range. Do this with a well-behaved list comprehension that uses only addition (much faster than mod) and avoids creating the list as a data structure in memory.
    • Take the set difference of potentials and the multiples, optimizing based on the fact that both are ordered lists with no duplicates. This function should be tail-recursive-modulo-cons.
    • Return p:(sieve setDifference). This makes your function tail-recursive-modulo-cons.

You might convert this algorithm (and many other tail-recursive-modulo-cons algorithms) into a Data.List.scanl'. This will give you code equivalent to what an imperative language would compile a strictly-evaluated while loop that generates list from head to tail into. This is typically much faster than unfoldr.