How to (zerop #*000) in common lisp?

Question

Is there an efficient way to check if a bitvector is all zeroes? (I'm using SBCL on Linux.) I've looked through the documentation but could not find a suitable function. The best I've come up with so far is:

(defun bit-zerop (array)
  (equal array (make-array (length array) :element-type 'bit)))

(bit-zerop #*000)

I've also tried

(defun bit-zerop (array)
  (dotimes (i (length array))
    (if (eql (sbit array i) 1)
        (return-from bit-zerop nil)))
  t)

but it is about 100 times slower on larger bit vectors than the first version. (Which is expected, as each 64bit word is read 64 times, I guess, instead of just once). Of course, the first version is sub-optimal as well as it must allocate a new array.

EDIT: timings for mentioned solutions.

EDIT 2: timings with type declarations.

(defun bit-zerop-1 (array)
  ;; (declare (simple-bit-vector array))
  (equal array (make-array (length array) :element-type 'bit)))

(defun bit-zerop-2 (array)
  ;; (declare (simple-bit-vector array))
  (every #'zerop array))

(defun bit-zerop-3 (array)
  ;; (declare (simple-bit-vector array))
  (loop
     for bit across array
     never (= bit 1)))

(defun bit-zerop-4 (array)
  ;; (declare (simple-bit-vector array))
  (not (find 1 array)))

(dolist (func '(bit-zerop-1 bit-zerop-2 bit-zerop-3 bit-zerop-4))
  (dolist (size '(10 100 1000))
    (let ((x (make-array size :element-type 'bit)))
      (format t "Testing ~a on ~a elements~%" func size)
      (time
       (dotimes (i 1000000)
         (funcall func x))))))

gives

===============================================
method         size 10    size 100    size 1000
------------------- untyped -------------------
bit-zerop-1    0.030 s     0.030 s      0.058 s
bit-zerop-2    0.112 s     1.000 s      9.324 s
bit-zerop-3    0.111 s     0.935 s      8.742 s
bit-zerop-4    0.047 s     0.047 s      0.063 s
-------------------- typed --------------------
bit-zerop-1    0.025 s     0.023 s      0.040 s
bit-zerop-2    0.036 s     0.315 s      3.005 s
bit-zerop-3    0.041 s     0.348 s      3.346 s
bit-zerop-4    0.010 s     0.012 s      0.026 s
===============================================

Glomerulus

(every #'zerop #*000) – Hardcastle

@coredump, thanks. That does answer my initial question, I guess, as I've asked for the idiomatic way :) It is still quite slow though. I've added the timings and changed the emphasis of the question to whether there is an efficient way. – Glomerulus

Sorry I quickly wrote a comment because I had not much time at the moment, but I see now that you have a good answer. – Hardcastle

If you want the fastest method you should mention the implementation you are using and add appropriate DECLARE forms to tell the compiler that the arguments are bitvectors (and that you want your function to be optimised). – Kowalski

@DanRobertson, fair point. I would expect the relative performance of the proposed answers to be the same whether typed or untyped, but who knows... I've added times with type declarations. – Glomerulus

I’m pretty surprised at how well the first example works. I’d have expected the allocation to make it more expensive – Kowalski

@DanRobertson, I am surprised also, but I have just discovered that, in order to set all bits of a bit-vector to zero, allocating to a fresh new array populated with 0 by (setf bit-vector (make-array size :element-type 'bit :initial-element 0)) is 60 (!) times quicker that setting successive bits to 0 by (loop for i from 0 below size do (setf (sbit bit-vector i) 0)) (SBCL on typical laptop). It is probably linked to a very efficient way to create bit-vector. – Degrading

Answer 1

Here's an option:

(defun bit-vector-zerop (bit-vector)
  (not (find 1 bit-vector)))

This does not cons and is very efficient on SBCL. It's faster if you can declare the argument to be a bit-vector.

Razor

Answer 2

I am not sure if there is any special bit logic function, see e.g. here.

But how about this?

(loop
  for bit across #*0000
  never (= bit 1))

Salacious