README.md
1This package provides a couple of different implementations of mutable hash
2tables in the ST monad, as well as a typeclass abstracting their common
3operations, and a set of wrappers to use the hash tables in the IO monad.
4
5**Quick start**: documentation for the hash table operations is provided in the
6`Data.HashTable.Class` module, and the IO wrappers are located in the
7`Data.HashTable.IO` module.
8
9This package currently contains three hash table implementations:
10
11 1. `Data.HashTable.ST.Basic` contains a basic open-addressing hash table
12 using linear probing as the collision strategy. On a pure speed basis it
13 should currently be the fastest available Haskell hash table
14 implementation for lookups, although it has a higher memory overhead
15 than the other tables and can suffer from long delays when the table is
16 resized because all of the elements in the table need to be rehashed.
17
18 2. `Data.HashTable.ST.Cuckoo` contains an implementation of "cuckoo hashing"
19 as introduced by Pagh and Rodler in 2001 (see
20 [http://en.wikipedia.org/wiki/Cuckoo\_hashing](http://en.wikipedia.org/wiki/Cuckoo_hashing)).
21 Cuckoo hashing has worst-case /O(1)/ lookups and can reach a high "load
22 factor", in which the table can perform acceptably well even when more
23 than 90% full. Randomized testing shows this implementation of cuckoo
24 hashing to be slightly faster on insert and slightly slower on lookup than
25 `Data.Hashtable.ST.Basic`, while being more space efficient by about a
26 half-word per key-value mapping. Cuckoo hashing, like the basic hash table
27 implementation using linear probing, can suffer from long delays when the
28 table is resized.
29
30 3. `Data.HashTable.ST.Linear` contains a linear hash table (see
31 [http://en.wikipedia.org/wiki/Linear\_hashing](http://en.wikipedia.org/wiki/Linear_hashing)),
32 which trades some insert and lookup performance for higher space
33 efficiency and much shorter delays when expanding the table. In most
34 cases, benchmarks show this table to be currently slightly faster than
35 `Data.HashTable` from the Haskell base library.
36
37It is recommended to create a concrete type alias in your code when using this
38package, i.e.:
39
40 import qualified Data.HashTable.IO as H
41
42 type HashTable k v = H.BasicHashTable k v
43
44 foo :: IO (HashTable Int Int)
45 foo = do
46 ht <- H.new
47 H.insert ht 1 1
48 return ht
49
50Firstly, this makes it easy to switch to a different hash table implementation,
51and secondly, using a concrete type rather than leaving your functions abstract
52in the HashTable class should allow GHC to optimize away the typeclass
53dictionaries.
54
55This package accepts a couple of different cabal flags:
56
57 * `unsafe-tricks`, default **on**. If this flag is enabled, we use some
58 unsafe GHC-specific tricks to save indirections (namely `unsafeCoerce#` and
59 `reallyUnsafePtrEquality#`. These techniques rely on assumptions about the
60 behaviour of the GHC runtime system and, although they've been tested and
61 should be safe under normal conditions, are slightly dangerous. Caveat
62 emptor. In particular, these techniques are incompatible with HPC code
63 coverage reports.
64
65 * `sse41`, default /off/. If this flag is enabled, we use some SSE 4.1
66 instructions (see
67 [http://en.wikipedia.org/wiki/SSE4](http://en.wikipedia.org/wiki/SSE4),
68 first available on Intel Core 2 processors) to speed up cache-line searches
69 for cuckoo hashing.
70
71 * `bounds-checking`, default /off/. If this flag is enabled, array accesses
72 are bounds-checked.
73
74 * `debug`, default /off/. If turned on, we'll rudely spew debug output to
75 stdout.
76
77 * `portable`, default /off/. If this flag is enabled, we use only pure
78 Haskell code and try not to use unportable GHC extensions. Turning this
79 flag on forces `unsafe-tricks` and `sse41` *OFF*.
80