hashtables

Mutable hash tables in the ST monad

http://github.com/gregorycollins/hashtables

Version on this page:1.3.1
LTS Haskell 22.42:1.3.1@rev:1
Stackage Nightly 2024-11-22:1.3.1@rev:1
Latest on Hackage:1.4.0

See all snapshots hashtables appears in

BSD-3-Clause licensed by Gregory Collins
Maintained by [email protected], [email protected], [email protected]
This version can be pinned in stack with:hashtables-1.3.1@sha256:0c0a5620c2c1114dd63cb3130e4af4939c7b8fe624552f3ca48e66d95c75be1f,10396

Module documentation for 1.3.1

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 Data.HashTable.IO module.

This package currently contains three hash table implementations:

  1. 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.

  2. 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 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.

  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.

  • 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 unsafe-tricks and sse41 OFF.

Changes

Hashtables changelog

1.3.1

Fix Noncanonical mappend definition warning. Support more recent compilers.

1.3

Support Hashable 1.4. This new version of Hashable drops the Eq constraint, so the Eq constraint needs to be dropped in the SPECIALIZE statements in Hashtables.

1.2.4.2

Cabal file: add missing other-modules Silence import warnings. Know that we require ghc >= 7.8. Fix build with GHC 9.2

1.2.4.1

Update some test suite dep upper bounds.

1.2.4.0

  • Fix a correctness bug with cuckoo hash tables and the new mutate function introduced in 1.2.3.0.

  • Bring test suite into main .cabal file

1.2.3.4

Fix build with GHC 8.8.

1.2.3.3

Fix build with certain versions of primitive (thx again Carter)

1.2.3.2

  • 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)

1.2.3.1

  • Fix building with GHC <7.10 (thx Vanessa McHale)

1.2.3.0

  • 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)

1.2.2.1

  • Adjusted base lower bound (it was incorrect), bumped some testsuite + benchmark bounds.

1.2.2.0

  • Bumped vector bounds.

  • Added lookupIndex and nextByIndex functions.

  • Add mutate function.

Thanks to contributors:

  • Vykintas Baltrušaitis.
  • Franklin Chen
  • Iavor Diatchki
  • Eric Mertins

1.2.1.1

  • Bumped vector bounds.

1.2.1.0

1.2.0.2

  • 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).

1.2.0.1

  • 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.

1.2.0.0

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.

Other

  • Dependency bumps

  • Fix definitions of forwardSearch2 and forwardSearch3 in PORTABLE mode (also used on Windows) to match C implementations.

1.1.2.1

  • Fixes for GHC 7.8 compatibility.

1.1.2.0

  • Bump allowable versions of hashable, primitive, and vector, blacklisting some bad hashable versions

  • Add specialize pragmas for fromListWithSizeHint

1.1.0.2

  • Use CPP to allow compilation against base 4.2/4.3.

1.1.0.1

  • Re-added SPECIALIZE pragmas that were previously removed.

1.1.0.0

  • Add ‘fromListWithSizeHint’
  • ‘fromList’: don’t be strict in the list argument

1.0.1.8

Bump vector and primitive dependencies.

1.0.1.7

Fix bug in C FFI code (not correctly promoting CInt to Int).

1.0.1.6

Fix for benchmark suite .cabal file.

1.0.1.5

Added benchmark suite.

1.0.1.4

Bump test-framework dependency.

1.0.1.3

Bump testsuite dependencies.

1.0.1.2

Fix testsuite on Windows.

1.0.1.1

Build fix for Windows.

1.0.1.0

Bugfix for http://github.com/gregorycollins/hashtables/issues/1 (Basic.lookup loops).