Copyright	(c) Peter Robinson
License	BSD3 (see the file LICENSE)
Maintainer	Peter Robinson <pwr@lowerbound.io>
Stability	provisional
Portability	non-portable (requires concurrency, stm)
Safe Haskell	None
Language	Haskell2010

Data.HashTable.Internal

Description

You can find benchmarks and more information about the internals of this package here: https://lowerbound.io/blog/2019-10-24_concurrent_hash_table_performance.html

Synopsis

data MigrationStatus
- = NotStarted
- | Ongoing
- | Finished
data Chain k v = Chain {
- _itemsTV :: TVar [(k, v)]
- _migrationStatusTV :: TVar MigrationStatus
}
newChainIO :: IO (Chain k v)
data HashTable k v = HashTable {
- _chainsVecTV :: TVar (Vector (Chain k v))
- _totalLoad :: IORef Int
- _config :: Config k
}
data Config k = Config {
- _scaleFactor :: Float
- _threshold :: Float
- _numResizeWorkers :: Int
- _hashFunc :: k -> Int
}
mkDefaultConfig :: Hashable k => IO (Config k)
new :: Eq k => Int -> Config k -> IO (HashTable k v)
newWithDefaults :: (Eq k, Hashable k) => Int -> IO (HashTable k v)
readSizeIO :: HashTable k v -> IO Int
readSize :: HashTable k v -> STM Int
resize :: Eq k => HashTable k v -> IO ()
lookup :: Eq k => HashTable k v -> k -> IO (Maybe v)
type STMAction k v a = TVar [(k, v)] -> STM a
genericModify :: Eq k => HashTable k v -> k -> STMAction k v a -> IO a
insert :: Eq k => HashTable k v -> k -> v -> IO Bool
add :: Eq k => HashTable k v -> k -> v -> IO Bool
update :: Eq k => HashTable k v -> k -> v -> IO Bool
modify :: Eq k => HashTable k v -> k -> (v -> v) -> IO (Maybe v)
swapValues :: Eq k => HashTable k v -> k -> v -> IO v
delete :: Eq k => HashTable k v -> k -> IO Bool
atomicallyChangeLoad :: Eq k => HashTable k v -> Int -> IO ()
readLoad :: HashTable k v -> IO Int
readAssocs :: Eq k => HashTable k v -> STM [(k, v)]
readAssocsIO :: Eq k => HashTable k v -> IO [(k, v)]
deleteFirstKey :: Eq a => a -> [(a, b)] -> [(a, b)]
readChainForKeyIO :: HashTable k v -> k -> IO (Chain k v)
readChainForIndexIO :: HashTable k v -> Int -> IO (Chain k v)
readChainForIndex :: HashTable k v -> Int -> STM (Chain k v)
debug :: Show a => a -> IO ()

Documentation

data MigrationStatus Source #

Constructors

NotStarted
Ongoing
Finished

Instances

Eq MigrationStatus Source #
Instance details Defined in Data.HashTable.Internal Methods (==) :: MigrationStatus -> MigrationStatus -> Bool # (/=) :: MigrationStatus -> MigrationStatus -> Bool #
Show MigrationStatus Source #
Instance details Defined in Data.HashTable.Internal Methods showsPrec :: Int -> MigrationStatus -> ShowS # show :: MigrationStatus -> String # showList :: [MigrationStatus] -> ShowS #

data Chain k v Source #

Used for chain-hashing.

Constructors

Chain
Fields _itemsTV :: TVar [(k, v)] stores the items for this index _migrationStatusTV :: TVar MigrationStatus used internally for resizing

Instances

Eq (Chain k v) Source #
Instance details Defined in Data.HashTable.Internal Methods (==) :: Chain k v -> Chain k v -> Bool # (/=) :: Chain k v -> Chain k v -> Bool #

newChainIO :: IO (Chain k v) Source #

Create a new empty chain.

data HashTable k v Source #

A thread-safe hash table that supports dynamic resizing.

Constructors

HashTable
Fields _chainsVecTV :: TVar (Vector (Chain k v)) vector of linked lists _totalLoad :: IORef Int the current load of the hash table _config :: Config k the configuration options

data Config k Source #

Configuration options that may affect the performance of the hash table

Constructors

Config
Fields _scaleFactor :: Float scale factor for resizing _threshold :: Float load threshold for initiating resizing. _numResizeWorkers :: Int maximum number of worker threads used during resizing _hashFunc :: k -> Int

Instances

Show (Config k) Source #
Instance details Defined in Data.HashTable.Internal Methods showsPrec :: Int -> Config k -> ShowS # show :: Config k -> String # showList :: [Config k] -> ShowS #

mkDefaultConfig :: Hashable k => IO (Config k) Source #

Default configuration: scale factor = 2.0; resizing threshold = 0.75; number of worker threads for resizing = getNumCapabilities; hash function = use hashWithSalt with a random salt.

new Source #

Arguments

:: Eq k
=> Int	Initial size of the hash table
-> Config k
-> IO (HashTable k v)

Creates a new hash table with an initial size. See newWithDefaults for more details.

newWithDefaults Source #

Arguments

:: (Eq k, Hashable k)
=> Int	Initial size of the hash table
-> IO (HashTable k v)

Creates a new hash table with the given initial vector size, scale factor 2.0, a resizing load threshold of 0.75, and we use as many threads for resizing as we have cores available. This will use a hash function with a (single) random salt. For security sensitive applications, you MUST supply your own hash function. (To be replaced by universal hashing in future versions.)

readSizeIO :: HashTable k v -> IO Int Source #

Returns the size of the vector representing the hash table.

readSize :: HashTable k v -> STM Int Source #

Returns the size of the vector representing the hash table.

resize :: Eq k => HashTable k v -> IO () Source #

Increases the size of the hash table by scaling the current size it according to the _scaleFactor in the configuration.

lookup Source #

Arguments

:: Eq k
=> HashTable k v
-> k	key `k`
-> IO (Maybe v)	value for key `k` if it exists

Lookup the value for the given key in the hash table.

type STMAction k v a = TVar [(k, v)] -> STM a Source #

An action to be executed atomically for the content of the chain (i.e. list) stored at a specific table index. Used in genericModify.

genericModify Source #

Arguments

:: Eq k
=> HashTable k v
-> k	key
-> STMAction k v a	Action that will be performed for the list of items at the key's index
-> IO a	Returns the result of the `STMAction`

Used by various write-operations (e.g. insert, add, delete, update). Searches the hash table for the given key and then applies the given STMAction to the contents of the chain.

insert Source #

Arguments

:: Eq k
=> HashTable k v
-> k	key `k`
-> v	value `v`
-> IO Bool	returns `True` if and only if the size of the hash table has changed

Inserts a key-value pair k,v into the hash table. Uses chain hashing to resolve collisions. If you want to update the entry only if it already exists, use update. If you want to update the entry only if it does *not* exist, use add.

add Source #

Arguments

:: Eq k
=> HashTable k v
-> k	key
-> v	value
-> IO Bool	returns `True` if and only if the key was not yet in the table

Adds a key and value pair into the hash table only if the key does not exist yet. Returns True if the insertion was successful, i.e., the hash table does not yet contain this key. To get the same behaviour as insert, use insert. If you want to update an already-existing item, use update.

update Source #

Arguments

:: Eq k
=> HashTable k v
-> k	key
-> v	value
-> IO Bool	returns `True` if and only if the key was found

Updates the value for key k. If k is not in the hash table, it skips the update and returns False.

modify Source #

Arguments

:: Eq k
=> HashTable k v
-> k	key `k`
-> (v -> v)	update-function
-> IO (Maybe v)	returns the old value for key `k` if it existed

Applies an update-function to the value for key k. Returns the old value if it exists. If k is not in the hash table, it returns Nothing.

swapValues Source #

Arguments

:: Eq k
=> HashTable k v
-> k	key `k`
-> v	new value
-> IO v	old value

Atomically replaces the value for the given key k in the hash table with the new value. Returns the old value. Throws AssertionFailed if k is not in the hash table.

delete Source #

Arguments

:: Eq k
=> HashTable k v
-> k	key of entry that will be deleted
-> IO Bool	returns `True` if and only if the size of the hash table has changed, i.e., an item was deleted

Deletes the entry for the given key from the hash table. Returns True if and only if an entry was deleted from the table.

atomicallyChangeLoad Source #

Arguments

:: Eq k
=> HashTable k v
-> Int	increment/decrement offset; can be negative
-> IO ()

Atomically increment/decrement the table load value by adding the provided integer offest to the current value. Forks a thread that executes resize if the load passes the configured threshold.

readLoad :: HashTable k v -> IO Int Source #

The load (i.e. number of stored items) in the table. Note that this is not synchronized for performance reasons and hence might be somewhat out of date if a lot of contention is happening.

readAssocs :: Eq k => HashTable k v -> STM [(k, v)] Source #

Returns an atomic snapshot of the hash table as a list of key-value pairs. If there is a lot of contention going on, this may be very inefficient.

readAssocsIO :: Eq k => HashTable k v -> IO [(k, v)] Source #

Returns the content of the hash table as a list of key-value pairs. This is *not* an atomic operation! If you need atomicity, use readAssoc instead.

deleteFirstKey :: Eq a => a -> [(a, b)] -> [(a, b)] Source #

Takes a key k and an assocation list ys, and deletes the first entry with key k in ys. Used internally.

readChainForKeyIO :: HashTable k v -> k -> IO (Chain k v) Source #

Atomically read the chain for the given key.

readChainForIndexIO :: HashTable k v -> Int -> IO (Chain k v) Source #

Atomically read the chain for the given index. (Warning: bounds are not checked.)

readChainForIndex :: HashTable k v -> Int -> STM (Chain k v) Source #

Atomically read the chain for the given index. (Warning: bounds are not checked.)

debug :: Show a => a -> IO () Source #