andreaferretti / emmy Goto Github PK

This repo's implementation of sieveUpTo called by primesUpTo* has got to be one of the slowest and most wasteful of memory implementation of the Sieve of Eratosthenes of any I have seen...

The problems are as follows:

1. In using IntSet as it's base storage, it uses multiple bytes per stored composite entry, which memory use is so high that it can't sieve even up to a billion as it consumes Gigabytes of memory over that range as it uses many bytes per entry for every composite number over the range.
2. It doesn't even implement the very simple optimization of sieving "odds-only" so there are about two and a half times more culling operations than necessary (and twice as much memory is required for all the unused evens).
3. Composite culling operation execution overheads are atrocious (although constant time on the average) as it must perform a hashing operation each time.
4. Cache associativity is also atrocious as it is skipping over this huge linked memory storage.

It has the single advantage of being short. However, it can't sieve to a billion using a reasonably amount of RAM memory and even if it could it would take about a minute or so.

A much better short implementation which greatly reduces the memory consumption such that very large ranges can be sieved (although still somewhat slowly due to the hashing) is as follows:

# compile with "-d:release -d:danger"

import tables
 
type PrimeType = uint64
proc primesHashTable(): iterator(): PrimeType {.closure.} =
  iterator output(): PrimeType {.closure.} =
    # some initial values to avoid race and reduce initializations...
    yield 2.PrimeType; yield 3.PrimeType; yield 5.PrimeType; yield 7.PrimeType
    var h = initTable[PrimeType,PrimeType]()
    var n = 9.PrimeType
    let bps = primesHashTable()
    var bp = bps() # advance past 2
    bp = bps(); var q = bp * bp # to initialize with 3
    while true:
      if n >= q:
        let inc = bp + bp
        h.add(n + inc, inc)
        bp = bps(); q = bp * bp
      elif h.hasKey(n):
        var inc: PrimeType
        discard h.take(n, inc)
        var nxt = n + inc
        while h.hasKey(nxt): nxt += inc # ensure no duplicates
        h.add(nxt, inc)
      else: yield n
      n += 2.PrimeType
  output

# tested as...
from times import epochTime

let limit = 100_000_000.PrimeType
let start = epochTime()
let iter = primesHashTable()
var count = 0
for p in iter():
  if p > limit: break else: count.inc
let elpsd = (epochTime() - start) * 1000.0
echo "Found ", count, " primes up to ", limit, " in ", elpsd, " milliseconds."

This is an "incremental" Odds-Only Sieve of Eratosthenes and only stores a hash entry for each of the base primes up to the square root of the current iteration value (determined automatically by the recursive secondary base primes feed). It still takes about a minute to count the number of primes to a billion, but at least it doesn't take an excessive amount of memory to do so. Its output also doesn't consume memory as it is just an iterator over the "incrementally" found primes.

If being so short isn't a consideration, the Page Segmented Bit-Packed Odds-Only Unbounded Sieve of Eratosthenes from RosettaCode is fast as in only taking about a second to sieve to a billion, consumes even less memory, and can even relatively easily have multi-threading added, but is over a hundred lines of code.