Anyone have a rule-of-thumb about when to use a bit vector vs an
integer to represent a vector of bits. ASH seems to be the main
function of integers for which there's no corresponding function on
bit vectors. So I guess if you know you need that, an integer's the
way to go. Anything else?
-Peter
--
Peter Seibel ·····@javamonkey.com
The intellectual level needed for system design is in general
grossly underestimated. I am convinced more than ever that this
type of work is very difficult and that every effort to do it with
other than the best people is doomed to either failure or moderate
success at enormous expense. --Edsger Dijkstra
Peter Seibel <·····@javamonkey.com> writes:
> Anyone have a rule-of-thumb about when to use a bit vector vs an
> integer to represent a vector of bits. ASH seems to be the main
> function of integers for which there's no corresponding function on
> bit vectors. So I guess if you know you need that, an integer's the
> way to go. Anything else?
I'm no expert, but here's how I use the two:
I use ASH when I'm dealing with something most clearly modelled as an
integer, and bit vectors as something most clearly modelled as an
array of boolean values. :)
More seriously: I've never used ASH to pack, say, 8 boolean values
into a byte--I'd just use 8 slots or variables of type (member T NIL).
I could see myself doing this if I was going to be making millions of
instances of an object (or some other value that would make my program
heap-bound), but I've never run into this situation. The only times
I've used ASH have been when I've been manipulating integers; e.g.,
constructing a 16 bit integer from two 8-bit bytes, or printing an
ipv4 address.
I've used bit vectors when I've needed to keep track of state and
there have been *many* possibilities: Which packets in the
transmission have I received? Did this single element (out of a set
of thousands) have the property FOO (out of a set of hundreds) 185
minutes ago?
Gabe Garza
Hi,
Peter Seibel <·····@javamonkey.com> writes:
> Anyone have a rule-of-thumb about when to use a bit vector vs an
> integer to represent a vector of bits. ASH seems to be the main
> function of integers for which there's no corresponding function on
> bit vectors. So I guess if you know you need that, an integer's the
> way to go. Anything else?
When I was dealing with truth-maintenance systems (TMS, RMS),
bit-vectors were conceptually a good match. I nevertheless used big
integers, because these allow for a varying number of bits, whereas
bit-and/or/ior etc. are not defined for bit-vector arrays of different
size.
I had varying number of bits because one bit would represent a fact in
the data base and it would grow.
OTOH, bit-vector operations worked in-place, generating much less
garbage than working with integers which generates many intermediate
bignums. So I wasn't very happy with integers either.
The functions bit-and/or/xor etc. operate in-place on the first
argument. This maps nicely to linear types and data-flow models:
applying successive transformations to a data item.
Maybe if I had to redo it, I'd use bit-vectors based on resizable
arrays with fill-pointers. That would allow for growth. But then I
would not operate on simple-arrays anymore. There might be an extra
indirection involved. Timings would tell.
Gabe Garza <·······@ix.netcom.com> writes:
> The only times
> I've used ASH have been when I've been manipulating integers; e.g.,
> constructing a 16 bit integer from two 8-bit bytes, or printing an
> ipv4 address.
Then you probably didn't know about LDB ("load-byte") and friends.
It's even SETF'able.
(defun decoder (x)
(values
(ldb (byte 4 22) x)
(ldb (byte 5 17) x)
(ldb (byte 5 12) x)
(ldb (byte 6 6) x)
(ldb (byte 6 0) x)))
In C one would use >>, and & and | masks instead
Of course, you'll have to hope that your CL implementation compiles
this as efficiently as probably ASH (talking about fixnums).
BTW, isn't SUBSEQ useable as ASH to the right?
Wouldn't (REPLACE bit-vector bit-vector :start1 :start2) provide a
basis for in-place ASH in both directions (resizing the array if
needed)?
Regards,
Jorg Hohle
Telekom/T-Systems Technology Center
Joerg Hoehle <············@dont.t-systems.UCE.spam.no.com> writes:
> Then you probably didn't know about LDB ("load-byte") and friends.
> It's even SETF'able.
> (defun decoder (x)
> (values
> (ldb (byte 4 22) x)
> (ldb (byte 5 17) x)
> (ldb (byte 5 12) x)
> (ldb (byte 6 6) x)
> (ldb (byte 6 0) x)))
I do know about LDB. It's been my experience that not all compilers
compile LDB calls as well as they compile ASH, LOGAND, etc. calls.
> BTW, isn't SUBSEQ useable as ASH to the right? Wouldn't (REPLACE
> bit-vector bit-vector :start1 :start2) provide a basis for in-place
> ASH in both directions (resizing the array if needed)?
They're replacements in the sense that they produce the same value,
but for FIXNUM's (or any other type of integer then your compiler is
smart about) they're going to have *very* different performance
characteristics.
Gabe Garza
Peter Seibel <·····@javamonkey.com> writes:
> Anyone have a rule-of-thumb about when to use a bit vector vs an
> integer to represent a vector of bits.
Because bit vectors are mutable, bit-vector operations may cons
less than bignum operations. See the opt-arg argument of
BIT-AND, and SETF BIT.
Peter Seibel <·····@javamonkey.com> writes:
> Anyone have a rule-of-thumb about when to use a bit vector vs an
> integer to represent a vector of bits. ASH seems to be the main
> function of integers for which there's no corresponding function on
> bit vectors.
There are, SUBSEQ and CONCATENATE.
> So I guess if you know you need that, an integer's the
> way to go. Anything else?
As far as I can tell, conversion between integers and bit vectors is
very expensive. If you need it repeatedly, maybe you should go for
integers alone.