Generating prime candidates

Question

I'd like to generate an infinite list of prime candidates of the form 6k±1, but I'm looking for the fastest possible solution.

Currently I have this:

primeCands :: [Integer]
primeCands = concatMap (\i -> [6*i-1, 6*i+1]) [1..]

but I feel that concat is wasting too much time. Using all the odd numbers is almost the same thing in terms of performance. Maybe a list is not the right datatype for this task?

Answer 1

Haskell has a great package for testing performance called Criterion. When you're trying to compare the performance between variations of the same function, head right for it.

Here's a small example with a few other versions of primeCands I dreamed up.

module Main where

import Criterion
import Criterion.Main

import Data.Ratio

primeCands_cmap :: [Integer]
primeCands_cmap = concatMap (\i -> [6*i-1, 6*i+1]) [1..]

dropThirds :: [a] -> [a]
dropThirds (a:b:_:ds) = a : b : dropThirds ds
dropThirds xs         = xs

primeCands_dropOdds :: [Integer]
primeCands_dropOdds = dropThirds [5,7..]

interleave :: [a] -> [a] -> [a]
interleave (a:as) (b:bs) = a : b : interleave as bs
interleave as     bs     = as ++ bs

primeCands_interleave :: [Integer]
primeCands_interleave = interleave [5,11..] [7,13..]

primeCands_allOdds :: [Integer]
primeCands_allOdds = [5,7..]

main :: IO ()
main = defaultMain [
         bgroup "prime candidates" 
                   [ bench "concatMap"  $ nf distantElement primeCands_cmap
                   , bench "dropThirds" $ nf distantElement primeCands_dropOdds
                   , bench "interleave" $ nf distantElement primeCands_interleave
                   ]
       , bgroup "odds" [ bench "odds" $ nf furtherElement primeCands_allOdds ]
                   ]
  where
    index = 1000000
    distantElement = (!! index)
    furtherElement = (!! (ceiling $ (fromIntegral index) * (4 % 3)))

And the results of the criterion benchmark (compiling with -O2)—

benchmarking prime candidates/concatMap
time                 6.918 ms   (6.631 ms .. 7.160 ms)
                     0.995 R²   (0.992 R² .. 0.999 R²)
mean                 6.668 ms   (6.615 ms .. 6.753 ms)
std dev              193.5 μs   (107.1 μs .. 297.1 μs)
variance introduced by outliers: 10% (moderately inflated)

benchmarking prime candidates/dropThirds
time                 4.548 ms   (4.463 ms .. 4.639 ms)
                     0.996 R²   (0.993 R² .. 0.998 R²)
mean                 4.488 ms   (4.430 ms .. 4.546 ms)
std dev              183.5 μs   (153.8 μs .. 216.7 μs)
variance introduced by outliers: 22% (moderately inflated)

benchmarking prime candidates/interleave
time                 4.100 ms   (4.030 ms .. 4.172 ms)
                     0.996 R²   (0.993 R² .. 0.998 R²)
mean                 4.484 ms   (4.399 ms .. 4.558 ms)
std dev              241.0 μs   (215.5 μs .. 271.9 μs)
variance introduced by outliers: 31% (moderately inflated)

benchmarking odds/odds
time                 5.529 ms   (5.500 ms .. 5.568 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 5.521 ms   (5.506 ms .. 5.546 ms)
std dev              54.27 μs   (34.21 μs .. 93.68 μs)

In this case you can see that the concatMap version runs a bit slower (about ⅓) than the versions that don't flatten lists. I question whether you are prematurely optimizing however, I would imagine that the slight difference in prime candidate generation timings are dwarfed by the actual prime checking function you've written.