Cabal revisions of hashtables-1.0.0.0
Hackage metadata revisions edit the .cabal file after upload; each diff below is one revision.
revision 1
-Name: hashtables-Version: 1.0.0.0-Synopsis: Mutable hash tables in the ST monad-Homepage: http://github.com/gregorycollins/hashtables-License: BSD3-License-file: LICENSE-Author: Gregory Collins-Maintainer: greg@gregorycollins.net-Copyright: (c) 2011, Google, Inc.-Category: Data-Build-type: Simple-Cabal-version: >= 1.8--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.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/.- .- 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>.--Extra-Source-Files:- README.md,- haddock.sh,- test/compute-overhead/ComputeOverhead.hs,- test/hashtables-test.cabal,- test/runTestsAndCoverage.sh,- test/runTestsNoCoverage.sh,- 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--Flag sse41- Description: if on, use SSE 4.1 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- hs-source-dirs: src-- if !flag(portable)- C-sources: cbits/cfuncs.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 && <5,- hashable >= 1.1 && <2,- primitive,- vector >= 0.7--- if flag(portable)- cpp-options: -DNO_C_SEARCH-- 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(sse41) && !flag(portable)- cc-options: -DUSE_SSE_4_1 -msse4.1- cpp-options: -DUSE_SSE_4_1-- ghc-prof-options: -prof -auto-all-- if impl(ghc >= 6.12.0)- ghc-options: -Wall -fwarn-tabs -funbox-strict-fields -O2- -fno-warn-unused-do-bind- else- ghc-options: -Wall -fwarn-tabs -funbox-strict-fields -O2-+Name: hashtables +Version: 1.0.0.0 +x-revision: 1 +Synopsis: Mutable hash tables in the ST monad +Homepage: http://github.com/gregorycollins/hashtables +License: BSD3 +License-file: LICENSE +Author: Gregory Collins +Maintainer: greg@gregorycollins.net +Copyright: (c) 2011, Google, Inc. +Category: Data +Build-type: Simple +Cabal-version: >= 1.8 + +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.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/. + . + 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>. + +Extra-Source-Files: + README.md, + haddock.sh, + test/compute-overhead/ComputeOverhead.hs, + test/hashtables-test.cabal, + test/runTestsAndCoverage.sh, + test/runTestsNoCoverage.sh, + 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 + +Flag sse41 + Description: if on, use SSE 4.1 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 + hs-source-dirs: src + + if !flag(portable) + C-sources: cbits/cfuncs.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 && <4.7, + hashable >= 1.1 && <2, + primitive, + vector >= 0.7 && < 0.10 + + + if flag(portable) + cpp-options: -DNO_C_SEARCH + + if !flag(portable) && flag(unsafe-tricks) && impl(ghc) + build-depends: ghc-prim + -- invalid syntax + -- cpp-options = -DUNSAFETRICKS + + if flag(debug) + cpp-options: -DDEBUG + + if flag(bounds-checking) + cpp-options: -DBOUNDS_CHECKING + + if flag(sse41) && !flag(portable) + cc-options: -DUSE_SSE_4_1 -msse4.1 + cpp-options: -DUSE_SSE_4_1 + + ghc-prof-options: -prof -auto-all + + if impl(ghc >= 6.12.0) + ghc-options: -Wall -fwarn-tabs -funbox-strict-fields -O2 + -fno-warn-unused-do-bind + else + ghc-options: -Wall -fwarn-tabs -funbox-strict-fields -O2 +
revision 2
Name: hashtables Version: 1.0.0.0 -x-revision: 1 +x-revision: 2 Synopsis: Mutable hash tables in the ST monad Homepage: http://github.com/gregorycollins/hashtables License: BSD3 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. + Haskell base library. . It is recommended to create a concrete type alias in your code when using this package, i.e.: Build-depends: base >= 4 && <4.7, hashable >= 1.1 && <2, - primitive, + primitive > 0.7, vector >= 0.7 && < 0.10
revision 3
Name: hashtables Version: 1.0.0.0 -x-revision: 2 +x-revision: 3 Synopsis: Mutable hash tables in the ST monad Homepage: http://github.com/gregorycollins/hashtables License: BSD3 Build-depends: base >= 4 && <4.7, hashable >= 1.1 && <2, - primitive > 0.7, + primitive < 0.7, vector >= 0.7 && < 0.10