Bit vectors vs. fixnums

[barmar@Think.COM]

   Date: Thu, 4 Oct 90 16:20 PDT
   From: charest@AI-SUN.JPL.NASA.GOV (Charest)

   I have an application in which I want to implement a set of boolean
   properties as a "array" of bits. I am doing this to minimize the 
   memory consumed. 

   I am stuck between using bit vectors or fixnums in my implementation.
   Bit vectors seem "conceptually" appropriate, but do they eat more 
   memory than a fixnum of the same size as allocated by SCL? And are the 
   bit vector bit-manipulation functions more or less efficient than 
   the fixnum bit-manipulation functions? On the other hand, is one 
   implementation more flexible than the other?

Fixnums take up no space, because they are implemented as immediate data
(they take the place of the address field in the pointer).  However,
fixnums are only useful if your array has at most 31 elements.  A bit array
with 1 to 32 elements takes up two words -- one for the array header and
another for the data.

Bignums take about the same space as bit arrays with the same number of
bits, except that bignums automatically discard high-order all-zero words.

My guess is that the performance of the two mechanisms will be similar.  At
the microcode level the objects look very similar, and it will end up doing
the same shifts and masks to test and set bits.

One difference is in consing, though: you can perform side effects on bit
arrays, but integers are not modifiable so you must always compute a new
one.  For fixnums this isn't a problem, but for bignums it can add up
pretty quickly.

The modifiability can also affect the program design.  If multiple
variables refer to the same bit array you can modify it and they'll all see
the change.  If you're using integers you must always store the modified
integer back into all the variables that expect to see the change.  You can
get around this by encapsulating the integer in a structure, but this
results in extra storage and slower accesses.