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.Currently only
CHPL_TARGET_ARCH=x86_64
is supported as it uses the x86-64 instruction: CMPXCHG16B.The implementation relies on
GCC
style inline assembly, and so is restricted to aCHPL_TARGET_COMPILER
value ofgnu
,clang
, orllvm
.
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.
- 1
L. Jenkins, T. Zhou and M. Spear, “Redesigning Go’s Built-In Map to Support Concurrent Operations,” 2017 26th International Conference on Parallel Architectures and Compilation Techniques (PACT), 2017.
- 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¶
- proc init(type keyType, type valType)¶
- 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)
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)
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)
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)
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 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 addOrSet(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 writeThis(f) throws¶
Writes the contents of this map to a channel. The format looks like:
{k1: v1, k2: v2, .... , kn: vn}
- Arguments
ch – A channel to write to.
- 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