# Generating prime candidates

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?

• when you see a list, remember, there is no list. </Matrix reminiscence> Aug 4, 2015 at 9:35

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.

• Thanks, this was really helpful! It could be premature optimisation, but I was curious about timings and I also learned how to use Criterion, so it was well worth it. Jul 10, 2015 at 19:00
• Glad you found it useful!
– R B
Jul 10, 2015 at 21:31
• shouldn't it be 3/2 instead of 4/3? then the timings for "odds" should be multiplied by 9/8, making it 6.22 ms. Also, one more variant to try is [x | n <- [5,11..], x <- [n,n+2]]. Aug 4, 2015 at 10:08
• (or concatMap (\i -> [i, i+2]) [5,11..] ...) Aug 4, 2015 at 10:35