Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Wheel-based prime sieve hangs with safety set to 0 #1498

Open
ak-coram opened this issue Sep 23, 2023 · 0 comments
Open

Wheel-based prime sieve hangs with safety set to 0 #1498

ak-coram opened this issue Sep 23, 2023 · 0 comments
Labels

Comments

@ak-coram
Copy link

Describe the bug
Evaluation hangs with safety set to 0.

Expected behavior
I would expect code running without errors on higher safety levels to also run with safety set to 0.

Actual behavior
Evaluating the bench function in the code below hangs the Clasp REPL indefinitely without using any CPU.

Code at issue

(declaim (optimize (speed 3) (safety 0) (debug 0)))

(defmacro loop-primes (limit sieve f)
  (let* ((xs (loop :for i fixnum :from 11 :upto 221
                   :unless (loop :for y fixnum :in '(2 3 5 7)
                                 :when (zerop (mod i y)) :return t)
                     :collect i))
         (wheel (loop :for (a b) :on xs :when b 
                      :collect (the fixnum (- (the fixnum b) (the fixnum a))))))
    `(loop :named outer :with x fixnum := 11
           :do (loop :for w fixnum :in (list ,@wheel)
                     :when (< ,limit x)
                       :do (return-from outer)
                     :when (zerop (aref ,sieve (floor x 2)))
                       :do ,f
                     :do (setf x (+ x w))))))

(declaim (inline discard-multiples)
         (ftype (function (fixnum fixnum (simple-array bit)))
                discard-multiples))
(defun discard-multiples (i limit sieve)
  (loop :for x fixnum :from (* i i) :by (* i 2)
        :while (<= x limit) :do (setf (aref sieve (floor x 2)) 1)))

(declaim (inline make-sieve)
         (ftype (function (fixnum) (simple-array bit)) make-sieve))
(defun make-sieve (n)
  (let* ((sieve (make-array (+ 6 (floor (* (1+ (floor n 210)) 210) 2))
                            :element-type 'bit :initial-element 0))
         (lower-bound (floor (sqrt n))))
    (setf (aref sieve 0) 1 (aref sieve 4) 1)
    (loop-primes lower-bound sieve (discard-multiples x n sieve))
    sieve))

(defun sieve-primes (n)
  (let* ((sieve (make-sieve n))
         (result '(7 5 3 2)))
    (loop-primes n sieve (setf result (cons x result)))
    (nreverse result)))

(defun bench () (time (progn (make-sieve 1073741824) nil)))

Context

  • Current main branch (f8265e4fb1eba8fc561783b70b7a1d3a3c853aa2)
  • x86_64 Linux
  • Performance on a modern version of SBCL is much better (more than 10 times faster) compared to Clasp (with safety set to 1)
@ak-coram ak-coram added the bug label Sep 23, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

1 participant