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
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
|
Cabal-Version: 2.2
Name: hashtables
Version: 1.3.1
Synopsis: Mutable hash tables in the ST monad
Homepage: http://github.com/gregorycollins/hashtables
License: BSD-3-Clause
License-file: LICENSE
Author: Gregory Collins
Maintainer: greg@gregorycollins.net, mgoremeier@gmail.com, erikd@mega-nerd.com
Copyright: (c) 2011-2014, Google, Inc., 2016-present contributors
Category: Data
Build-type: Simple
tested-with:
GHC == 7.8.4
GHC == 7.10.3
GHC == 8.0.2
GHC == 8.2.2
GHC == 8.4.4
GHC == 8.6.5
GHC == 8.8.4
GHC == 8.10.7
GHC == 9.0.1
GHC == 9.2.4
GHC == 9.4.2
Description:
This package provides a couple of different implementations of mutable hash
tables in the ST monad, as well as a typeclass abstracting their common
operations, and a set of wrappers to use the hash tables in the IO monad.
.
/QUICK START/: documentation for the hash table operations is provided in the
"Data.HashTable.Class" module, and the IO wrappers (which most users will
probably prefer) are located in the "Data.HashTable.IO" module.
.
This package currently contains three hash table implementations:
.
1. "Data.HashTable.ST.Cuckoo" contains an implementation of \"cuckoo
hashing\" as introduced by Pagh and Rodler in 2001 (see
<http://en.wikipedia.org/wiki/Cuckoo_hashing>). Cuckoo hashing has
worst-case /O(1)/ lookups and can reach a high \"load factor\", in which
the table can perform acceptably well even when approaching 90% full.
Randomized testing shows this implementation of cuckoo hashing to be
slightly faster on insert and slightly slower on lookup than
"Data.HashTable.ST.Basic", while being more space efficient by about a
half-word per key-value mapping. Cuckoo hashing, like the basic hash
table implementation using linear probing, can suffer from long delays
when the table is resized.
.
2. "Data.HashTable.ST.Basic" contains a basic open-addressing hash table
using linear probing as the collision strategy. On a pure speed basis it
should currently be the fastest available Haskell hash table
implementation for lookups, although it has a higher memory overhead
than the other tables and can suffer from long delays when the table is
resized because all of the elements in the table need to be rehashed.
.
3. "Data.HashTable.ST.Linear" contains a linear hash table (see
<http://en.wikipedia.org/wiki/Linear_hashing>), which trades some insert
and lookup performance for higher space efficiency and much shorter
delays when expanding the table. In most cases, benchmarks show this
table to be currently slightly faster than @Data.HashTable@ from the
Haskell base library.
.
It is recommended to create a concrete type alias in your code when using this
package, i.e.:
.
> import qualified Data.HashTable.IO as H
>
> type HashTable k v = H.BasicHashTable k v
>
> foo :: IO (HashTable Int Int)
> foo = do
> ht <- H.new
> H.insert ht 1 1
> return ht
.
Firstly, this makes it easy to switch to a different hash table implementation,
and secondly, using a concrete type rather than leaving your functions abstract
in the HashTable class should allow GHC to optimize away the typeclass
dictionaries.
.
This package accepts a couple of different cabal flags:
.
* @unsafe-tricks@, default /ON/. If this flag is enabled, we use some
unsafe GHC-specific tricks to save indirections (namely @unsafeCoerce#@
and @reallyUnsafePtrEquality#@. These techniques rely on assumptions
about the behaviour of the GHC runtime system and, although they've been
tested and should be safe under normal conditions, are slightly
dangerous. Caveat emptor. In particular, these techniques are
incompatible with HPC code coverage reports.
.
* @sse42@, default /OFF/. If this flag is enabled, we use some SSE 4.2
instructions (see <http://en.wikipedia.org/wiki/SSE4>, first available on
Intel Core 2 processors) to speed up cache-line searches for cuckoo
hashing.
.
* @bounds-checking@, default /OFF/. If this flag is enabled, array accesses
are bounds-checked.
.
* @debug@, default /OFF/. If turned on, we'll rudely spew debug output to
stdout.
.
* @portable@, default /OFF/. If this flag is enabled, we use only pure
Haskell code and try not to use unportable GHC extensions. Turning this
flag on forces @unsafe-tricks@ and @sse42@ /OFF/.
.
Please send bug reports to
<https://github.com/gregorycollins/hashtables/issues>.
Extra-Source-Files:
README.md,
cabal.project,
haddock.sh,
benchmark/hashtable-benchmark.cabal,
benchmark/LICENSE,
benchmark/src/Criterion/Collection/Internal/Types.hs,
benchmark/src/Criterion/Collection/Chart.hs,
benchmark/src/Criterion/Collection/Main.hs,
benchmark/src/Criterion/Collection/Types.hs,
benchmark/src/Criterion/Collection/Sample.hs,
benchmark/src/Main.hs,
benchmark/src/Data/Vector/Algorithms/Shuffle.hs,
benchmark/src/Data/Benchmarks/UnorderedCollections/Distributions.hs,
benchmark/src/Data/Benchmarks/UnorderedCollections/Types.hs,
cbits/Makefile,
cbits/check.c,
cbits/defs.h,
cbits/sse-42-check.c,
changelog.md,
test/compute-overhead/ComputeOverhead.hs,
test/hashtables-test.cabal,
test/suite/Data/HashTable/Test/Common.hs,
test/suite/TestSuite.hs
------------------------------------------------------------------------------
Flag unsafe-tricks
Description: turn on unsafe GHC tricks
Default: True
Flag bounds-checking
Description: if on, use bounds-checking array accesses
Default: False
Flag debug
Description: if on, spew debugging output to stdout
Default: False
Manual: True
Flag detailed-profiling
Description: add detailed profiling information to profiled build-depends
Default: False
Manual: True
Flag sse42
Description: if on, use SSE 4.2 extensions to search cache lines very
efficiently. The portable flag forces this off.
Default: False
Flag portable
Description: if on, use only pure Haskell code and no GHC extensions.
Default: False
Library
Default-Language: Haskell2010
hs-source-dirs: src
if flag(sse42) && !flag(portable)
cc-options: -DUSE_SSE_4_2 -msse4.2
cpp-options: -DUSE_SSE_4_2
C-sources: cbits/sse-42.c
if !flag(portable) && !flag(sse42)
C-sources: cbits/default.c
if !flag(portable)
C-sources: cbits/common.c
Exposed-modules: Data.HashTable.Class,
Data.HashTable.IO,
Data.HashTable.ST.Basic,
Data.HashTable.ST.Cuckoo,
Data.HashTable.ST.Linear
Other-modules: Data.HashTable.Internal.Array,
Data.HashTable.Internal.IntArray,
Data.HashTable.Internal.CacheLine,
Data.HashTable.Internal.CheapPseudoRandomBitStream,
Data.HashTable.Internal.UnsafeTricks,
Data.HashTable.Internal.Utils,
Data.HashTable.Internal.Linear.Bucket
Build-depends: base >= 4.7 && <5,
hashable >= 1.4 && < 1.5,
primitive,
vector >= 0.7 && <0.14
if flag(portable)
cpp-options: -DNO_C_SEARCH -DPORTABLE
if !flag(portable) && flag(unsafe-tricks) && impl(ghc)
build-depends: ghc-prim
cpp-options: -DUNSAFETRICKS
if flag(debug)
cpp-options: -DDEBUG
if flag(bounds-checking)
cpp-options: -DBOUNDS_CHECKING
if flag(detailed-profiling)
if impl(ghc >= 7.4.1)
ghc-prof-options: -fprof-auto
if impl(ghc < 7.4.1)
ghc-prof-options: -auto-all
if impl(ghc >= 6.12.0)
ghc-options: -Wall -fwarn-tabs -funbox-strict-fields
-fno-warn-unused-do-bind
else
ghc-options: -Wall -fwarn-tabs -funbox-strict-fields
test-suite testsuite
Default-Language: Haskell2010
hs-source-dirs: src test/suite
main-is: TestSuite.hs
type: exitcode-stdio-1.0
other-modules:
Data.HashTable.Class
Data.HashTable.IO
Data.HashTable.Internal.Array
Data.HashTable.Internal.CacheLine
Data.HashTable.Internal.CheapPseudoRandomBitStream
Data.HashTable.Internal.IntArray
Data.HashTable.Internal.Linear.Bucket
Data.HashTable.Internal.UnsafeTricks
Data.HashTable.Internal.Utils
Data.HashTable.ST.Basic
Data.HashTable.ST.Cuckoo
Data.HashTable.ST.Linear
Data.HashTable.Test.Common
if flag(sse42) && !flag(portable)
cc-options: -DUSE_SSE_4_2 -msse4.2
cpp-options: -DUSE_SSE_4_2
C-sources: cbits/sse-42.c
if !flag(portable) && !flag(sse42)
C-sources: cbits/default.c
if !flag(portable)
C-sources: cbits/common.c
if flag(detailed-profiling)
ghc-prof-options: -auto-all
if flag(portable)
cpp-options: -DNO_C_SEARCH -DPORTABLE
if !flag(portable) && flag(unsafe-tricks) && impl(ghc)
cpp-options: -DUNSAFETRICKS
build-depends: ghc-prim
if flag(debug)
cpp-options: -DDEBUG
if flag(bounds-checking)
cpp-options: -DBOUNDS_CHECKING
Build-depends: base >= 4 && <5,
hashable >= 1.4 && < 1.5,
mwc-random >= 0.8 && <0.16,
primitive,
QuickCheck >= 2.3.0.2,
HUnit >= 1.2 && <2,
test-framework >= 0.3.1 && <0.9,
test-framework-quickcheck2 >= 0.2.6 && <0.4,
test-framework-hunit >= 0.2.6 && <3,
vector >= 0.7
cpp-options: -DTESTSUITE
if impl(ghc >= 7)
ghc-options: -rtsopts
if impl(ghc >= 6.12.0)
ghc-options: -Wall -fwarn-tabs -funbox-strict-fields
-fno-warn-unused-do-bind -threaded
else
ghc-options: -Wall -fwarn-tabs -funbox-strict-fields -threaded
source-repository head
type: git
location: https://github.com/gregorycollins/hashtables.git
|
