ConcurrentMap¶
Usage
use ConcurrentMap;
or
import ConcurrentMap;
This module provides a fast, scalable, fine-grained concurrent map.
Warning
This module relies on the AtomicObjects
package module, which
has several platform restrictions in its current state:
It relies on Chapel
extern
code blocks and so requires that the Chapel compiler is built with LLVM enabled.The implementation relies on using either
GCC
style inline assembly (for x86-64) or a GCC/clang builtin, and so is restricted to aCHPL_TARGET_COMPILER
value ofgnu
,clang
, orllvm
.The implementation does not work with
CHPL_ATOMICS=locks
.
This module was inspired by the Interlocked Hash Table [1]. It allows large critical sections that access a single table element, and can easily support multikey atomic operations. At the time of its development, ConcurrentMap outperformed Chapel’s built-in map when used in a multithreaded mode by orders of magnitude.
- config param BUCKET_NUM_ELEMS = 8¶
Maximum number of key-value pairs stored in each leaf bucket.
- config const DEFAULT_NUM_BUCKETS = 1024¶
Maximum number of child buckets for the root bucket.
- config param MULTIPLIER_NUM_BUCKETS : real = 2¶
Multiplier for child bucket size. childBucketSize = MULTIPLIER_NUM_BUCKETS * parentBucketSize
- class ConcurrentMap : Base(?), serializable¶
- proc init(type keyType, type valType)¶
- proc deinit()¶
- proc getToken() : owned TokenWrapper¶
Register the task to epoch manager.
- iter these() : (keyType, valType)¶
Serially iterates over the key-value pairs of this map.
- Yields:
A tuple whose elements are a copy of one of the key-value pairs contained in this map.
Note
While iterating the map, pre-maturely breaking the iteration loop may permanently lock the map.
- iter items() : (keyType, valType)¶
Serially iterates over the key-value pairs of this map.
- Yields:
A tuple whose elements are a copy of one of the key-value pairs contained in this map.
- iter keys() : keyType¶
Serially iterates over the keys of this map.
- Yields:
A copy of one of the keys contained in this map.
- iter values() : valType¶
Serially iterates over the values of this map.
- Yields:
A copy of one of the values contained in this map.
- iter these(param tag: iterKind) where tag == iterKind.standalone
Iterates over the key-value pairs of this map in parallel.
- Yields:
A tuple whose elements are a copy of one of the key-value pairs contained in this map.
- iter items(param tag: iterKind) where tag == iterKind.standalone
Parallelly iterates over the key-value pairs of this map.
- Yields:
A tuple whose elements are a copy of one of the key-value pairs contained in this map.
- iter keys(param tag: iterKind) where tag == iterKind.standalone
Parallelly iterates over the keys of this map.
- Yields:
A copy of one of the keys contained in this map.
- iter values(param tag: iterKind) where tag == iterKind.standalone
Parallelly iterates over the values of this map.
- Yields:
A copy of one of the values contained in this map.
- proc add(key: keyType, val: valType, tok: owned TokenWrapper = getToken()) : bool throws¶
Adds a key-value pair to the map. Method returns false if the key already exists in the map.
- Arguments:
key :
keyType
– The key to add to the mapval – The value that maps to
k
tok – Token for EpochManager
- Returns:
true if key was not in the map and added with value val. false otherwise.
- Return type:
bool
- proc set(key: keyType, in val: valType, tok: owned TokenWrapper = getToken()) : bool throws¶
Sets the value associated with a key. Method returns false if the key does not exist in the map.
- Arguments:
key :
keyType
– The key whose value needs to changeval :
valueType
– The desired value to the keykey
tok – Token for EpochManager
- Returns:
true if key was in the map and its value is updated with val. false otherwise.
- Return type:
bool
- proc getValue(key: keyType, tok: owned TokenWrapper = getToken()) : (bool, valType) throws¶
Get a copy of the element stored at position key.
- proc update(key: keyType, updater, tok: owned TokenWrapper = getToken()) throws¶
Atomically update an entry in the map in place
updater should define a this method that takes a single argument of the element type by ref intent.
If the key isn’t already present, applies the updater to a default-initialized instance of the element type.
- proc contains(const key: keyType, tok: owned TokenWrapper = getToken()) : bool throws¶
Returns true if the given key is a member of this map, and false otherwise. :arg key: The key to test for membership. :type key: keyType :arg tok: Token for EpochManager :returns: Whether or not the given key is a member of this map. :rtype: bool
- proc addOrReplace(key: keyType, val: valType, tok: owned TokenWrapper = getToken()) throws¶
If the map doesn’t contain a value at position k add one and set it to v. If the map already contains a value at position k, update it to the value v.
- proc extend(m: ConcurrentMap(keyType, valType)) throws¶
Extends this map with the contents of the other, overwriting the values for already-existing keys.
- Arguments:
m – The other map
- proc getAndRemove(key: keyType, tok: owned TokenWrapper = getToken()) throws¶
Remove the element at position key from the map and return its value
- proc remove(key: keyType, tok: owned TokenWrapper = getToken()) : bool throws¶
Removes a key-value pair from the map, with the given key.
- Arguments:
key – The key to remove from the map
tok – Token for EpochManager
- Returns:
false if key was not in the map. true if it was and removed.
- Return type:
bool
- proc clearMap(tok: owned TokenWrapper = getToken()) throws¶
Clears the contents of this map.
- proc toArray() : [] (keyType, valType) throws¶
Returns a new 0-based array containing a copy of key-value pairs as tuples.
- Returns:
A new DefaultRectangular array.
- Return type:
[] (keyType, valType)
- proc tryReclaim()¶
Trigger EpochManager to reclaim any reclaimable memory.
- proc keysToArray() : [] keyType throws¶
Returns a new 0-based array containing a copy of keys. Array is not guaranteed to be in any particular order.
- Returns:
A new DefaultRectangular array.
- Return type:
[] keyType
- proc valuesToArray() : [] valType throws¶
Returns a new 0-based array containing a copy of values. Array is not guaranteed to be in any particular order.
- Returns:
A new DefaultRectangular array.
- Return type:
[] valType
- proc ref deserialize(reader: fileReader(?), ref deserializer) throws¶
- override proc serialize(writer: fileWriter(?), ref serializer) throws¶
- operator =(ref lhs: ConcurrentMap, const ref rhs: ConcurrentMap)¶
Replace the content of this map with the other’s.
- Arguments:
lhs – The map to assign to.
rhs – The map to assign from.
- operator ==(const ref a: ConcurrentMap, const ref b: ConcurrentMap) : bool throws¶
Returns true if the contents of two maps are the same.
- Arguments:
a :
map
– A map to compare.b :
map (with same keyType and valType)
– A map to compare.
- Returns:
true if the contents of two maps are equal.
- Return type:
bool
- operator !=(const ref a: ConcurrentMap, const ref b: ConcurrentMap) : bool throws¶
Returns true if the contents of two maps are not the same.
- Arguments:
a :
map
– A map to compare.b :
map (with same keyType and valType)
– A map to compare.
- Returns:
true if the contents of two maps are not equal.
- Return type:
bool