benninkrs / StaticBitVectors.jl

Dense packed, stack-allocated bit vectors
0 stars 0 forks source link

StaticBitVectors.jl

Bit vectors backed by StaticVectors. By exploiting local storage and whole-word CPU operations on dense-packed bits, bitwise operations on static bit vectors can often be performed significantly faster than on other vector-of-Bool types.

Installation

pkg> add https://github.com/benninkrs/StaticBitVectors.jl

Usage

This package provides four concrete types:

BitVecs can be constructed and converted from just about any array or iterator whose elements are convertable to Bool. The functions trues and falses are extended to take a BitVec type as the first argument, which allows one to specify the output type.

BitVecs can be indexed by integers, Cartesian indices, and iterables. Logical indexing is not yet supported.

Bitwise operations on BitVecs (~, |, &, xor, nor, and nand) are implemented efficiently, leveraging whole-word CPU operations to act on 64 bits at a time. An even larger set of operations (including the bitwise operators, comparisons, min, and, max) are implemented efficiently for map and map!. Broadcasting on arrays of the same shape can also be used, with speed comparable to that of map and the inherently parallel bitwise operations. The results of such operations are BitVecs of the same type as the input (but see the next section for what happens in the case of mixed input types).

Efficient implementations of reducing operations, including count, parity, dot, and hamming (Hamming weight and Hamming distance) are also provided.

Example

julia> s = SBitCol([false, true, true, false, true])
5-element SBitCol{1}:
 0
 1
 1
 0
 1

 julia> m = SBitCol((isodd(i) for i in 0:4))
5-element MBitCol{1}:
 0
 1
 0
 1
 0

julia> s[2]
true

julia> s[4:-1:2]
3-element SBitCol{1}:
 0
 1
 1

 julia> s & m
 5-element SBitCol{1}:
 0
 1
 0
 0
 0

julia> map(<=, s, m)
 5-element SBitCol{1}:
 1
 1
 0
 1
 0

Vertical concatenation of BitCols yields another BitCol; likewise, , however, horizontal concatenation yields a (non-static) BitMatrix.

Corner Cases

For most ways of using BitVecs, the expected behavior is obvious. In a few circumstances, however, it is less clear what behavior should be expected. Some of these ambiguous circumstances and the chosen behaviors are:

Performance