> From: Dave Tenny <truesoft.com at dtenny>
> 
> What's the philosophy on when to use integers for bit-set operations, and
when
> to use bit vectors?

You're definitely on the right lines.  And generally, implementors spend
more time optimising bignum operations than they do bit vector operations. 
If handled equally, bit vectors ought to be faster, because they offer
nonconsing operations which save time in GC.  

I worked on a system which used big sets, and we did very extensive
benchmarking of the two.  Rick Evertsz wrote a paper on this issue, "The
Trouble With Benchmarks", in the proceedings of the 1st EUROPAL conference,
1990.  Without exception, bignum operations were faster than bit array
operations when dealing with large sets.  And the difference increased
rather than decreasing with size.  Quite often, even single bit operations
were nearly as fast using logtest as using sbit.  

The difference is exemplified by something like an AND.  With integers,
people generally zap through the words, doing the ANDing directly, and
knowing that the result can be no bigger than the smallest integer. 
However, a naive implementor can get away with something on the general
lines of (map 'bit-vector #'logand v1 v2) for bitand.  Depending on what's
assessed in the benchmarks (and in the Gabriel benchmarks bignums were
assessed, but not bit vectors) you get *radical* differences in
optimisation.  

There is a paper by Henry Baker on doing fast bit vector operations.  It is
called something like "Doing fast bit vector functions in Common Lisp", and
was in SIGART or SIGPLAN or something like that, probably late 1980s or
early 1990s.  I'll dig out the full reference later, and pass it on.  If
implementors adopted these algorithms, bit vectors should be much faster
than large integers.  

Our philosophy, in the end, was to use macros to wrap up the implementation
and work out a way of choosing between the two with minimum fuss.  However,
we also talked to the implementors and worked out a way of doing
destructive operations on bignums, and that was the complete winner in
performance terms.  When we'd wrapped it all up in macros, it was pretty
elegant, too.

Regards, Stuart
_______
Knowledge Media Institute and Psychology Discipline, Open University,
Walton Hall, UK.
Email: <open.ac.uk; at S.N.K.Watt> Tel: +44 1908 654513
----------
> I need to manipulate very large bit vectors.  I want the manipulations to
be
> efficient.  Bit vectors seem like the obvious choice.  However there are
two
> things about integers and the log* functions which I also find nice:
> 
> 1) ldb and dpb seem like they might be more efficient for manipulating
ranges
>     of bits.  
> 
> 2) The ability to perform logical operations on bit sets of different
lengths
>      only works with the log*/boole functions.  
>