[racket-dev] Implementation of bit vectors

From: Ryan Culpepper (ryan at cs.utah.edu)
Date: Mon Nov 26 15:13:33 EST 2012

There's also an implementation of bitvectors in 
db/private/generic/sql-data (sql-bits) that uses bytes, if you want to 
do a comparison. If a standard bit-vector library gets added, I'll 
switch the db library to use that instead.


On 11/26/2012 01:43 PM, Jens Axel Søgaard wrote:
> Hi All,
> I have implemented an alternative version of bit-vectors using bignums
> to represent the bits.
> As is the bignum implementation is much slower, than the vector-of-fixnum one.
> The main reason as far as I can tell is due to bit-vector-set! .
> Since bignums aren't mutable I can not simply flip a bit and need to compute
> a new bignum. Unless bignums are sharing limbs this will be slow for large
> bit-vectors.
> Another possibility is that I have missed something obvious.
> The functions bit-vector-set! is here:
> (define (bit-vector-set! bv n b)
>    ; bv is a bit-vector
>    ; n is the bit number
>    ; b is #f or #t
>    (define bits (bit-vector-bits bv))
>    (define mask (arithmetic-shift 1 n))
>    (cond
>      [b
>       (set-bit-vector-bits! bv (bitwise-ior bits mask))]
>      [(bitwise-bit-set? bits n)
>       (set-bit-vector-bits! bv (bitwise-xor bits mask))]
>      [else (void)]))
> The entire implementation is here:
> https://github.com/soegaard/racket/blob/4b299ea66a77100538940794cd799cb88929b7e3/collects/data/bit-vector-bignum.rkt
> The benchmark is here:
> https://github.com/soegaard/racket/blob/4b299ea66a77100538940794cd799cb88929b7e3/collects/data/benchmark-bit-vector-representations.rkt

Posted on the dev mailing list.