dev-haskell / hashtables

Mutable hash tables in the ST monad

Official package sites : https://github.com/gregorycollins/hashtables ·

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.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 <https://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 <https://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 <https://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/. This package has been tested with GHC 7.0.3, on: * a MacBook Pro running Snow Leopard with an Intel Core i5 processor, running GHC 7.0.3 in 64-bit mode. * an Arch Linux desktop with an AMD Phenom II X4 940 quad-core processor. * a MacBook Pro running Snow Leopard with an Intel Core 2 Duo processor, running GHC 6.12.3 in 32-bit mode. Please send bug reports to <https://github.com/gregorycollins/hashtables/issues>.

v1.2.1.0 :: 0/1.2.1.0 :: gentoo

Modified
License
BSD
Keywords
~alpha ~amd64 ~ia64 ~ppc ~ppc64 ~sparc ~x86
USE flags
bounds-checking doc hscolour portable profile unsafe-tricks

v1.1.2.1 :: 0/1.1.2.1 :: gentoo

Modified
License
BSD
Keywords
amd64 ppc ppc64 sparc x86 ~alpha ~ia64
USE flags
bounds-checking doc hscolour portable profile unsafe-tricks

General

bounds-checking
if on, use bounds-checking array accesses
doc
Add extra documentation (API, Javadoc, etc). It is recommended to enable per package instead of globally
hscolour
Include coloured haskell sources to generated documentation (dev-haskell/hscolour)
portable
if on, use only pure Haskell code and no GHC extensions.
profile
Add support for software performance analysis (will likely vary from ebuild to ebuild)
unsafe-tricks
turn on unsafe GHC tricks

cpu_flags_x86

sse4_1
Enable SSE4.1 instruction support
sse4_2
Enable SSE4.2 instruction support

dev-haskell / cabal : A framework for packaging Haskell software

dev-haskell / haddock : A documentation-generation tool for Haskell libraries

dev-haskell / hashable : A class for types that can be converted to a hash value

dev-haskell / hscolour : Colourise Haskell code

dev-haskell / primitive : Primitive memory-related operations

dev-haskell / vector : Efficient Arrays

dev-lang / ghc : The Glasgow Haskell Compiler

dev-haskell / hashable : A class for types that can be converted to a hash value

dev-haskell / primitive : Primitive memory-related operations

dev-haskell / vector : Efficient Arrays

dev-lang / ghc : The Glasgow Haskell Compiler

app-portage / fquery : Installed package query tool for Gentoo Linux

dev-haskell / gtk2hs-buildtools : Tools to build the Gtk2Hs suite of User Interface libraries

dev-haskell / hit : Git operations in haskell

sci-mathematics / agda : A dependently typed functional programming language and proof assistant

Robin H. Johnson · gentoo
Drop $Id$ per council decision in bug #611234.
Signed-off-by: Robin H. Johnson <robbat2@gentoo.org>
Sergei Trofimovich · gentoo
dev-haskell/hashtables: drop broken USE=debug flag, bug #584908
Reported-by: Toralf Förster Bug: https://bugs.gentoo.org/584908 Package-Manager: portage-2.3.0_rc1
Sergei Trofimovich · gentoo
dev-haskell/hashtables: simplify ranged depend
Package-Manager: portage-2.2.28
Sergei Trofimovich · gentoo
dev-haskell/hashtables: drop old
Package-Manager: portage-2.2.28
Ian Delaney · gentoo
Merge remote-tracking branch 'remotes/Coacher/mpv-verbump-to-0.15.0'
Pull request: https://github.com/gentoo/gentoo/pull/675
Sergei Trofimovich · gentoo
dev-haskell/hashtables: bump up to 1.2.1.0
Package-Manager: portage-2.2.26
Justin Lecher · gentoo
Use https by default
Signed-off-by: Justin Lecher <jlec@gentoo.org>
Robin H. Johnson · gentoo
proj/gentoo: Initial commit
This commit represents a new era for Gentoo: Storing the gentoo-x86 tree in Git, as converted from CVS. This commit is the start of the NEW history. Any historical data is intended to be grafted onto this point. Creation process: 1. Take final CVS checkout snapshot 2. Remove ALL ChangeLog* files 3. Transform all Manifests to thin 4. Remove empty Manifests 5. Convert all stale $Header$/$Id$ CVS keywords to non-expanded Git $Id$ 5.1. Do not touch files with -kb/-ko keyword flags. Signed-off-by: Robin H. Johnson <robbat2@gentoo.org> X-Thanks: Alec Warner <antarus@gentoo.org> - did the GSoC 2006 migration tests X-Thanks: Robin H. Johnson <robbat2@gentoo.org> - infra guy, herding this project X-Thanks: Nguyen Thai Ngoc Duy <pclouds@gentoo.org> - Former Gentoo developer, wrote Git features for the migration X-Thanks: Brian Harring <ferringb@gentoo.org> - wrote much python to improve cvs2svn X-Thanks: Rich Freeman <rich0@gentoo.org> - validation scripts X-Thanks: Patrick Lauer <patrick@gentoo.org> - Gentoo dev, running new 2014 work in migration X-Thanks: Michał Górny <mgorny@gentoo.org> - scripts, QA, nagging X-Thanks: All of other Gentoo developers - many ideas and lots of paint on the bikeshed