Mutable hash tables in the ST monad
|Version on this page:||220.127.116.11|
|LTS Haskell 20.24:||1.3.1|
|Stackage Nightly 2023-06-08:||1.3.1|
|Latest on Hackage:||1.3.1|
Module documentation for 18.104.22.168
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 are located in the
This package currently contains three hash table implementations:
Data.HashTable.ST.Basiccontains 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.
Data.HashTable.ST.Cuckoocontains 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 more than 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.
Data.HashTable.ST.Linearcontains 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.HashTablefrom 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
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.
sse41, default /off/. If this flag is enabled, we use some SSE 4.1 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
Fix build with GHC 8.8.
Fix build with certain versions of
primitive (thx again Carter)
CPP fix for breakage caused by primitive 0.7 (thx Carter)
Fix some haddock syntax errors (thx Frederik Hanghøj Iversen)
Fix typo in module reference (thx Don Allen)
- Fix building with GHC <7.10 (thx Vanessa McHale)
update for Semigroup/monoid breakage with GHC 8.4 (thx Fumiaki Kinoshita)
Implement mutateST and mutateIO (thx Andy Morris)
Fix build breakage w/ “pre” function (thx Andy Morris)
- Adjusted base lower bound (it was incorrect), bumped some testsuite + benchmark bounds.
Bumped vector bounds.
Thanks to contributors:
- Vykintas Baltrušaitis.
- Franklin Chen
- Iavor Diatchki
- Eric Mertins
- Bumped vector bounds.
- Fixed an FFI import typo bug (https://github.com/gregorycollins/hashtables/pull/27), thanks to Thijs Alkemade for the fix.
- Fixed serious bug (https://github.com/gregorycollins/hashtables/issues/24) in basic hash table making it impossible to reliably store more than 64k elements (after shortening the hash code arrays to 16 bits I neglected to realize that I was storing item counts using the same array type).
Fixed bug in C code re: clang interpreting “inline” strictly according to (insane) C99 semantics: http://clang.llvm.org/compatibility.html#inline
Fixed a compile bug affecting versions of base older than 4.4.
Changed int type from Int to Word in CheapPseudoRandomBitStream to fix an integer overflow warning.
Switch to smaller hash codes to go faster and save space.
Before, in the basic and cuckoo hash tables, we were storing full machine-word-sized hash codes in the table so that we could quickly search a whole cache line for a key (or a combination of keys) without branching.
It turns out that a full machine word is not really necessary for this application; switching to a 16-bit key will very slightly increase the number of hash collisions within buckets (meaning that we’ll compare more keys), but will pay big dividends in terms of:
reduced wastage of RAM
searching more keys at once, allowing buckets to grow bigger
more cache hits on the hash codes array.
Fix definitions of forwardSearch2 and forwardSearch3 in PORTABLE mode (also used on Windows) to match C implementations.
- Fixes for GHC 7.8 compatibility.
Bump allowable versions of hashable, primitive, and vector, blacklisting some bad hashable versions
Add specialize pragmas for fromListWithSizeHint
- Use CPP to allow compilation against base 4.2/4.3.
- Re-added SPECIALIZE pragmas that were previously removed.
- Add ‘fromListWithSizeHint’
- ‘fromList’: don’t be strict in the list argument
Bump vector and primitive dependencies.
Fix bug in C FFI code (not correctly promoting CInt to Int).
Fix for benchmark suite .cabal file.
Added benchmark suite.
Bump test-framework dependency.
Bump testsuite dependencies.
Fix testsuite on Windows.
Build fix for Windows.
Bugfix for http://github.com/gregorycollins/hashtables/issues/1 (Basic.lookup loops).