[racket-dev] Implementation of bit vectors

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


-- 
Jens Axel Søgaard