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