Monadoc

bitvec

Version 1.1.5.0 revision 2 uploaded by Bodigrim.

Package meta

Synopsis
Space-efficient bit vectors
Description

A newtype over Bool with a better Vector instance: 8x less memory, up to 3500x faster.

The vector package represents unboxed arrays of Bools spending 1 byte (8 bits) per boolean. This library provides a newtype wrapper Bit and a custom instance of an unboxed Vector, which packs bits densely, achieving an 8x smaller memory footprint. The performance stays mostly the same; the most significant degradation happens for random writes (up to 10% slower). On the other hand, for certain bulk bit operations Vector Bit is up to 3500x faster than Vector Bool.

Thread safety

  • Data.Bit is faster, but writes and flips are not thread-safe. This is because naive updates are not atomic: they read the whole word from memory, then modify a bit, then write the whole word back. Concurrently modifying non-intersecting slices of the same underlying array may also lead to unexpected results, since they can share a word in memory.

  • Data.Bit.ThreadSafe is slower (usually 10-20%), but writes and flips are thread-safe. Additionally, concurrently modifying non-intersecting slices of the same underlying array works as expected. However, operations that affect multiple elements are not guaranteed to be atomic.

Similar packages

  • bv and bv-little do not offer mutable vectors.

  • array is memory-efficient for Bool, but lacks a handy Vector interface and is not thread-safe.

Author
Andrew Lelechenko <andrew.lelechenko@gmail.com>, James Cook <mokus@deepbondi.net>
Bug reports
n/a
Category
Data, Bit Vectors
Copyright
2019-2022 Andrew Lelechenko, 2012-2016 James Cook
Homepage
https://github.com/Bodigrim/bitvec
Maintainer
Andrew Lelechenko <andrew.lelechenko@gmail.com>
Package URL
n/a
Stability
n/a

Components