Re: [racket-dev] Implementation of bit vectors
On Sat, Nov 24, 2012 at 8:33 PM, Jens Axel Søgaard jensa...@soegaard.net wrote: Hi All, I have written an implementation of bit vectors intended to be part of the data collection. https://github.com/plt/racket/pull/176 Any comments on the implementation and documentation are welcome. The bit vector is represented as a vector of fixnums (packaged in a struct of course). I seem to understand that you do not exploit the packed representation of bits in the iteration construct, is this right? Also, you store and retrieve booleans, not bits, so the name 'bit-vector' is misleading. 'find' and 'count' operations optimized for the representation would be a useful addition. Cheers P. _ Racket Developers list: http://lists.racket-lang.org/dev
Re: [racket-dev] Implementation of bit vectors
Hi Pierpaolo, 2012/11/27 Pierpaolo Bernardi olopie...@gmail.com: Any comments on the implementation and documentation are welcome. The bit vector is represented as a vector of fixnums (packaged in a struct of course). I seem to understand that you do not exploit the packed representation of bits in the iteration construct, is this right? In in-bit-vector could be improved. Currently it just calls bit-vector-ref repeatedly. Also, you store and retrieve booleans, not bits, so the name 'bit-vector' is misleading. Potato / Potato :-) http://wiki.call-cc.org/eggref/4/iset 'find' and 'count' operations optimized for the representation would be a useful addition. Good idea. I better rename the current count to size, and then use count to count ones. -- Jens Axel Søgaard _ Racket Developers list: http://lists.racket-lang.org/dev
Re: [racket-dev] Implementation of bit vectors
Hi, On Tue, Nov 27, 2012 at 2:34 PM, Jens Axel Søgaard jensa...@soegaard.net wrote: Hi Pierpaolo, 2012/11/27 Pierpaolo Bernardi olopie...@gmail.com: Also, you store and retrieve booleans, not bits, so the name 'bit-vector' is misleading. Potato / Potato :-) http://wiki.call-cc.org/eggref/4/iset Excellent! so now I can critique two libraries with only one complaint! 8^) P. _ Racket Developers list: http://lists.racket-lang.org/dev
Re: [racket-dev] Implementation of bit vectors
Nicely done. I've merged with minor changes, including renaming `bit-vector-count' to `bit-vector-length' to be more consistent with `vector' functions. At Sat, 24 Nov 2012 20:33:12 +0100, Jens Axel Søgaard wrote: Hi All, I have written an implementation of bit vectors intended to be part of the data collection. https://github.com/plt/racket/pull/176 Any comments on the implementation and documentation are welcome. The bit vector is represented as a vector of fixnums (packaged in a struct of course). -- Jens Axel Søgaard _ Racket Developers list: http://lists.racket-lang.org/dev _ Racket Developers list: http://lists.racket-lang.org/dev
Re: [racket-dev] Implementation of bit vectors
As I intend to use bitvectors to do fast set operations, and cardinality is a set operation, I wrote up a fast count bits function that should be rolled in for the vector implementation: https://gist.github.com/4154642 It depends on the fixnum representation, so I don't imagine this being adaptable to the bignum implementation. Bignums would have to support this kind of thing natively, which I don't think is the case. However, if you know the bignum is a fixnum, you could use this. -Ian - Original Message - From: Matthew Flatt mfl...@cs.utah.edu To: Jens Axel Søgaard jensa...@soegaard.net Cc: dev@racket-lang.org Sent: Tuesday, November 27, 2012 9:28:28 AM GMT -05:00 US/Canada Eastern Subject: Re: [racket-dev] Implementation of bit vectors Nicely done. I've merged with minor changes, including renaming `bit-vector-count' to `bit-vector-length' to be more consistent with `vector' functions. At Sat, 24 Nov 2012 20:33:12 +0100, Jens Axel Søgaard wrote: Hi All, I have written an implementation of bit vectors intended to be part of the data collection. https://github.com/plt/racket/pull/176 Any comments on the implementation and documentation are welcome. The bit vector is represented as a vector of fixnums (packaged in a struct of course). -- Jens Axel Søgaard _ Racket Developers list: http://lists.racket-lang.org/dev _ Racket Developers list: http://lists.racket-lang.org/dev _ Racket Developers list: http://lists.racket-lang.org/dev
Re: [racket-dev] Implementation of bit vectors
2012/11/27 J. Ian Johnson i...@ccs.neu.edu: As I intend to use bitvectors to do fast set operations, and cardinality is a set operation, I wrote up a fast count bits function that should be rolled in for the vector implementation: https://gist.github.com/4154642 I have used your code to add a function bit-vector-count that count the number of set bits in the bit-vector. There is an issue of potential confusion over names though. In the data collection, the -count suffix normally returns the size of the data structure. For vectors the suffix -length is normally used. -- Jens Axel Søgaard _ Racket Developers list: http://lists.racket-lang.org/dev
Re: [racket-dev] Implementation of bit vectors
On Tue, Nov 27, 2012 at 1:15 PM, Jens Axel Søgaard jensa...@soegaard.net wrote: There is an issue of potential confusion over names though. In the data collection, the -count suffix normally returns the size of the data structure. For vectors the suffix -length is normally used. The name 'popcount' is commonly used for this operation, so that might be a way to differentiate this. -- sam th sa...@ccs.neu.edu _ Racket Developers list: http://lists.racket-lang.org/dev
Re: [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 _ Racket Developers list: http://lists.racket-lang.org/dev
