1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
|
name: bitvec
version: 1.1.5.0
cabal-version: 2.0
build-type: Simple
license: BSD3
license-file: LICENSE
copyright: 2019-2022 Andrew Lelechenko, 2012-2016 James Cook
maintainer: Andrew Lelechenko <andrew.lelechenko@gmail.com>
homepage: https://github.com/Bodigrim/bitvec
synopsis: Space-efficient bit vectors
description:
A newtype over 'Bool' with a better 'Vector' instance: 8x less memory, up to 3500x faster.
.
The <https://hackage.haskell.org/package/vector vector>
package represents unboxed arrays of 'Bool's
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
.
* <https://hackage.haskell.org/package/bv bv> and
<https://hackage.haskell.org/package/bv-little bv-little>
do not offer mutable vectors.
.
* <https://hackage.haskell.org/package/array array>
is memory-efficient for 'Bool', but lacks
a handy 'Vector' interface and is not thread-safe.
category: Data, Bit Vectors
author: Andrew Lelechenko <andrew.lelechenko@gmail.com>,
James Cook <mokus@deepbondi.net>
tested-with: GHC ==8.4.4 GHC ==8.6.5 GHC ==8.8.1 GHC ==8.8.2 GHC ==8.8.4 GHC ==8.10.7 GHC ==9.0.2 GHC ==9.2.7 GHC ==9.4.4 GHC ==9.6.1
extra-doc-files:
changelog.md
README.md
source-repository head
type: git
location: git://github.com/Bodigrim/bitvec.git
flag simd
description:
Use a C SIMD implementation for the ultimate performance of `zipBits`, `invertBits` and `countBits`.
Disable this flag if there are problems with the C FFI.
default: True
manual: True
library
exposed-modules:
Data.Bit
Data.Bit.ThreadSafe
build-depends:
base >=4.11 && <5,
bytestring >=0.10 && <0.13,
deepseq <1.6,
primitive >=0.5,
vector >=0.11 && <0.14
default-language: Haskell2010
hs-source-dirs: src
other-modules:
Data.Bit.F2Poly
Data.Bit.F2PolyTS
Data.Bit.Immutable
Data.Bit.ImmutableTS
Data.Bit.Internal
Data.Bit.InternalTS
Data.Bit.Mutable
Data.Bit.MutableTS
Data.Bit.PdepPext
Data.Bit.Utils
ghc-options: -O2 -Wall -Wcompat
include-dirs: src
if impl(ghc <9.0)
build-depends: integer-gmp
else
build-depends: ghc-bignum
if flag(simd) && !arch(javascript) && !arch(wasm32)
c-sources: cbits/bitvec_simd.c
cc-options: -fopenmp-simd
cpp-options: -DUseSIMD
other-modules:
Data.Bit.SIMD
test-suite bitvec-tests
type: exitcode-stdio-1.0
main-is: Main.hs
build-depends:
base,
bitvec,
primitive >=0.5 && <0.9,
quickcheck-classes-base <0.7,
quickcheck-classes >=0.6.1 && <0.7,
vector >=0.11,
tasty <1.5,
tasty-quickcheck <0.11
default-language: Haskell2010
hs-source-dirs: test
other-modules:
Support
Tests.Conc
Tests.F2Poly
Tests.MVector
Tests.MVectorTS
Tests.SetOps
Tests.SetOpsTS
Tests.Vector
ghc-options: -Wall -threaded -rtsopts -Wcompat
include-dirs: test
if impl(ghc <9.0)
build-depends: integer-gmp <1.2
else
build-depends: ghc-bignum
benchmark bitvec-bench
build-depends:
base,
bitvec,
containers <0.7,
random <1.3,
tasty,
tasty-bench >=0.3.2 && <0.4,
vector
type: exitcode-stdio-1.0
main-is: Bench.hs
default-language: Haskell2010
hs-source-dirs: bench
other-modules:
Bench.BitIndex
Bench.Common
Bench.GCD
Bench.Invert
Bench.Intersection
Bench.Product
Bench.RandomFlip
Bench.RandomRead
Bench.RandomWrite
Bench.Remainder
Bench.Reverse
Bench.Sum
Bench.Union
ghc-options: -O2 -Wall -Wcompat
if impl(ghc <9.0)
build-depends: integer-gmp
else
build-depends: ghc-bignum
|
