[Haskell-cafe] ANN: bitwise - fast multi-dimensional unboxed bit packed Bool arrays

1 May 2012

      Hi all,

I'm pleased to announce bitwise-0.1:

http://hackage.haskell.org/package/bitwise

--8<-- excerpt from the hackage page

Unboxed multidimensional bit packed Bool arrays with fast aggregate 
operations based on lifting Bool operations to bitwise operations.

There are many other bit packed structures out there, but none met all 
of these requirements:
   1.  unboxed bit packed Bool array,
   2.  multi-dimensional indexing,
   3.  fast (de)serialization, or interoperable with foreign code,
   4.  fast aggregate operations (fold, map, zip).

--8<-- end excerpt

bitwise has been tested in hugs -98, ghc-7.0.4, ghc-7.4.1.

Bool data structures comparison (features numbered as excerpt above):
     package      features     additional notes
                  1  2  3  4
     array        Y  Y  n  n
     bitarray     Y  n  n  ?   based on array
     bitstream    n  n  ?  ?   based on vector
     bitstring    Y  n  ?  ?   based on bytestring
     bit-vector   n  n  Y  ?   based on vector
     bitwise      Y  Y  Y  Y
     repa         n  Y  Y  ?   based on vector
     uvector      Y  n  ?  ?   deprecated
     vector       n  n  Y  ?   uses a Word8 for each Bool

Known shortcomings of this first release of bitwise:
   * missing common instances (Eq, Ord, Read, Show, ...);
   * missing additional functions (counting, searching, ...);
   * missing documentation on ByteString format: the bits are taken
     from the array and packed into Word8s, with the first bit (in array
     order) becoming the least significant bit of the first Word8; the
     last Word8 is padded with 0 at the most-significant-bit end;
   * PBM reading is not compliant to the official specification;
   * misleading benchmark (bitwise zipWith is fast, but there may be a
     faster way to zipWith UArray ix Bool than the one I used).

What I'm using bitwise for at the moment:
   A building block for fractal imaging: an image is made up of cells,
   each cell can be in one of 4 states (represented with 2 bits):
     * cell is 100% interior to a set of points in the plane
     * cell is 100% exterior
     * partially interior and partially exterior (ie, on the boundary)
     * unknown
   with recursive subdivision of cells into images taking place only
   when the cell is on the boundary of the set being imaged.

Thanks,

Claude

[Haskell-cafe] ANN: bitwise - fast multi-dimensional unboxed bit packed Bool arrays

Claude Heiland-Allen