Why is this prime sieve implementation slower?

Question

I was just experimenting a bit with (for me) a new programming language: clojure. And I wrote a quite naive 'sieve' implementation, which I then tried to optimise a bit.

Strangely enough though (for me at least), the new implementation wasn't faster, but much slower...

Can anybody provide some insight in why this is so much slower?

I'm also interested in other tips in how to improve this algorithm...

Best regards,

Arnaud Gouder

; naive sieve. 
(defn sieve
  ([max] (sieve max (range 2 max) 2))
  ([max candidates n]
    (if (> (* n n) max)
      candidates
      (recur max (filter #(or (= % n) (not (= (mod % n) 0))) candidates) (inc n)))))

; Instead of just passing the 'candidates' list, from which I sieve-out the non-primes,
; I also pass a 'primes' list, with the already found primes
; I hoped that this would increase the speed, because:
; - Instead of sieving-out multiples of 'all' numbers, I now only sieve-out the multiples of primes.
; - The filter predicate now becomes simpler.
; However, this code seems to be approx 20x as slow.
; Note: the primes in 'primes' end up reversed, but I don't care (much). Adding a 'reverse' call makes it even slower :-(
(defn sieve2 
  ([max] (sieve2 max () (range 2 max)))
  ([max primes candidates]
    (let [n (first candidates)]
      (if (> (* n n) max)
        (concat primes candidates)
        (recur max (conj primes n) (filter #(not (= (mod % n) 0)) (rest candidates)))))))

; Another attempt to speed things up. Instead of sieving-out multiples of all numbers in the range,
; I want to sieve-out only multiples of primes.. I don't like the '(first (filter ' construct very much...
; It doesn't seem to be faster than 'sieve'.
(defn sieve3
  ([max] (sieve max (range 2 max) 2))
  ([max candidates n]
    (if (> (* n n) max)
      candidates
      (let [new_candidates (filter #(or (= % n) (not (= (mod % n) 0))) candidates)]
        (recur max new_candidates (first (filter #(> % n) new_candidates)))))))

(time (sieve 10000000))
(time (sieve 10000000))
(time (sieve2 10000000))
(time (sieve2 10000000))
(time (sieve2 10000000))
(time (sieve 10000000)) ; Strange, speeds are very different now... Must be some memory allocation thing caused by running sieve2
(time (sieve 10000000))
(time (sieve3 10000000))
(time (sieve3 10000000))
(time (sieve 10000000))

Answer 1

I have good news and bad news. The good news is that your intuitions are correct.

(time (sieve 10000)) ; "Elapsed time: 0.265311 msecs"

(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 ...)

(time (sieve2 10000)) ; "Elapsed time: 1.028353 msecs"

(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 ...)

The bad news is that both are much slower than you think

(time (count (sieve 10000))) ; "Elapsed time: 231.183055 msecs"
1229

(time (count (sieve2 10000))) ; "Elapsed time: 87.822796 msecs"
1229

What's happening is that because filter is lazy, the filtering isn't getting done until the answers need to be printed. All the first expression is counting is the time to wrap the sequence in a load of filters. Putting the count in means that the sequence actually has to be calculated within the timing expression, and then you see how long it really takes.

I think in the case without the count, sieve2 is taking longer because it is doing a bit of the work whilst constructing the filtered sequence.

When you put the count in, sieve2 is faster because it's the better algorithm.

P.S. When I try (time (sieve 10000000)), my machine crashes with a stack overflow, presumably because of the vast stack of nested filter calls it's building up. How come it ran for you?

Answer 2

Some optimization tips for this kind of Primative number heavy math:

1. use clojure 1.3
   clonjure 1.3 allows un-boxed-checked-arithmetic so you wont be casting everything to Integer.
2. type hint the function arguments Otherwise you will end up casting all the Ints/Longs to Integer for each function call. (you're not calling any hint-able functions so i'm just listing it here as general advice)
3. don't call any higher order functions. Currently (1.3) lambda functions #( ...) cant be compiled as ^static so they only take Object as arguments. so the calls to filter will require boxing of all the numbers.

You're likely loosing enough time in boxing/unboxing Integers/ints that it will make it hard to really judge the different optimizations. If you type hint (and use clojure 1.3) then you will likely get better numbers to judge your optimizations.