Asp Forum - Common Lisp bit vectors and their size in SBCL

Malice

3/11/2016 10:07:00 PM

I would like to ask if there's any standard defining how big should bit vectors be. Since bit vectors consist only of bits, these could be defined as series of integers at lower level. Is this how they work? Are operations on these as fast as bitwise operations on integers?

2 Answers

Pascal J. Bourguignon

3/20/2016 12:28:00 AM

Malice <gwmaniak@gmail.com> writes:

> I would like to ask if there's any standard defining how big should
> bit vectors be. Since bit vectors consist only of bits, these could be
> defined as series of integers at lower level. Is this how they work?
> Are operations on these as fast as bitwise operations on integers?

Obviously, the intend is to provide a memory-efficient storage of the
bits. However, nothing prevents an implementation to use one word per
bit!

There's also obviously a trade off there, between accessing bits, and
performing wholesale operations. So if you have a different
implementation:

(logbitp integer index) (aref bit-vector index)

shift index indexed load of bit
indexed load of integer word
test the bit

(logand a b) (bit-and a b)

loop on words of integers loop on bits

(dpb d (byte sz pd) (replace d s :start1 pd
(ldb (byte sz ps) s)) :start2 ps :end2 (+ ps sz))

very complex loop on bits
allocates a whole new integer! mutates the old bit vector!

Some bit vectors operations could be more efficient.
And even if bit-vectors weren't space-optimized, (and therefore could
involve more memory accesses), since they're mutable, you could still
have more efficient algorithms using bit-vectors than integers.

Also, even in the case of wholesale operators such as bit-and, remember
that bit-vectors can be displaced arrays, so that you may actually be
working on subsequences, which would be even more complicated to do with
integers.

(let* ((a (map-into (make-array 80 :element-type 'bit) (lambda () (random 2))))
(b (make-array 60 :element-type 'bit :displaced-to a
:displaced-index-offset 20))
(c (make-array 60 :element-type 'bit :displaced-to a
:displaced-index-offset 0)))
(print a)
(print b)
(print c)
(bit-and c b c)
a)
#*11111100010110000110100100001011010100001101101111001010101111011111001111010110
#*100100001011010100001101101111001010101111011111001111010110
#*111111000101100001101001000010110101000011011011110010101011
#*10010000000100000000100100001000000000001101101100001000001011011111001111010110

--
__Pascal Bourguignon__ http://www.informat...
â??The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.â? -- Carl Bass CEO Autodesk

Malice

3/20/2016 10:40:00 AM

On Sunday, 20 March 2016 01:28:19 UTC+1, informatimago wrote:
> Obviously, the intend is to provide a memory-efficient storage of the
> bits. [...]

Thank you for the answer, there are some interesting insights in there.

comp.lang.lisp

Common Lisp bit vectors and their size in SBCL

Malice

Pascal J. Bourguignon

Malice

x Login to ForumsZone