I was experimenting with prime sieves and I wasn't able to figure out why it was performing so slow:
import tables, sequtils, math, times, strformat
type
PrimeSieve* = object
sieveSize: int64
bits: seq[bool]
myDict: Table[int64, int]
proc generateTable(): Table[int64, int] =
result[10] = 4
result[100] = 25
result[1000] = 168
result[10000] = 1229
result[100000] = 9592
result[1000000] = 78498
result[10000000] = 664579
result[100000000] = 5761455
result[1000000000] = 50847534
result[10000000000] = 455052511
const PrimeTable = generateTable()
proc countPrimes(self: PrimeSieve): int =
result = 1
var i = 3
while i < self.sieveSize:
if self.bits[i]:
result += 1
i += 2
proc validateResults(self: PrimeSieve): bool =
if not self.myDict.contains(self.sieveSize): return false
result = self.myDict[self.sieveSize] == self.countPrimes()
proc newPrimeSieve(n: int64): PrimeSieve =
result.sieveSize = n
result.myDict = PrimeTable
result.bits = true.repeat(n)
proc runSieve(self: var PrimeSieve) =
var factor = 3
let q = int(sqrt(float32(self.sieveSize)))
while factor <= q:
var num = factor
while num < self.sieveSize:
if self.bits[num]:
factor = num
break
num += 2
var n = factor * factor
while n < self.sieveSize:
self.bits[n] = false
n += factor * 2
factor += 2
proc printResults(self: PrimeSieve, showResults: bool, duration: Duration, passes: int) =
if showResults: stdout.write("2, ")
var count = 1
var num = 3
while num <= self.sieveSize:
if self.bits[num]:
count += 1
if showResults:
stdout.write($num, ", ")
num += 2
if showResults: echo()
echo fmt"Passes: {passes}, Time: {duration}, Avg: {float32(duration.inNanoseconds())/float32(passes)}, Limit: {self.sieveSize}, Count1: {count}, Count2: {self.countPrimes()}, Valid: {self.validateResults()}"
when isMainModule:
var passes = 0
let tStart = getTime()
while true:
var sieve = newPrimeSieve(1000000)
sieve.runSieve()
passes += 1
let elapsed = getTime() - tStart
if elapsed >= initDuration(seconds = 5):
sieve.printResults(false, elapsed, passes)
break
In my machine, the arc is performing slower:
$ nimble build --d:danger --gc:arc && ./PrimeNim && nim --version
Verifying dependencies for [email protected]
Building PrimeNim/PrimeNim using c backend
Passes: 3270, Time: 5 seconds, 400 microseconds, and 292 nanoseconds, Avg: 1529174.375, Limit: 1000000, Count1: 78498, Count2: 78498, Valid: true
Nim Compiler Version 1.2.6 [Linux: amd64]
Compiled at 2020-09-07
Copyright (c) 2006-2020 by Andreas Rumpf
active boot switches: -d:release
$ nimble build --d:danger && ./PrimeNim && nim --version
Verifying dependencies for [email protected]
Building PrimeNim/PrimeNim using c backend
Passes: 15109, Time: 5 seconds, 178 microseconds, and 11 nanoseconds, Avg: 330940.375, Limit: 1000000, Count1: 78498, Count2: 78498, Valid: true
Nim Compiler Version 1.2.6 [Linux: amd64]
Compiled at 2020-09-07
Copyright (c) 2006-2020 by Andreas Rumpf
active boot switches: -d:release
I reran the test a few times and the result doesn't change.
On (almost) latest devel I get:
Passes: 13452, Time: 5 seconds, 356 microseconds, and 373 nanoseconds, Avg: 371718.4375, Limit: 1000000, Count1: 78498, Count2: 78498, Valid: true
And with ARC:
Passes: 3277, Time: 5 seconds, 880 microseconds, and 635 nanoseconds, Avg: 1526054.5, Limit: 1000000, Count1: 78498, Count2: 78498, Valid: true
Now, a major fix for ARC here would be to wrap your main code in the main proc as that generally improves perf, after that I get
Passes: 10071, Time: 5 seconds, 73 microseconds, and 757 nanoseconds, Avg: 496482.34375, Limit: 1000000, Count1: 78498, Count2: 78498, Valid: true
with ARC
after that I get
These numbers make no sense...
And on my machine I get:
REFC: Passes: 6881, Time: 5 seconds and 100 nanoseconds, Avg: 726638.5625, Limit: 1000000, Count1: 78498, Count2: 78498, Valid: true
ARC: Passes: 6955, Time: 5 seconds, 998 microseconds, and 900 nanoseconds, Avg: 719050.875, Limit: 1000000, Count1: 78498, Count2: 78498, Valid: true
Now what?