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 a CHPL_TARGET_COMPILER value of gnu, clang, or llvm.

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(?), serializable

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)  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 map

• val – 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 change

• val : valueType – The desired value to the key key

• 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

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