Template Class ShardedMap

Nested Relationships

Nested Types

Class Documentation

template<std::copy_constructible K, std::move_constructible V, template<typename, typename, typename...> typename SeqHashMapType = std::unordered_map, UpdateFunction<K, V> UpdateFn = update_functions::Overwrite<K, V>>
class ShardedMap

A hash map that must be used by multiple threads, each thread having only having write access to a certain segment of the hash input space.

Each processor has one queue and one local hash map.

To use this map with p threads, create a shard for each thread using get_shard with thread id’s ranging from 0 to (inclusively) p-1. Each possible hash has exactly one processor that is responsible for storing that hash. Inserting an element inserts it into its responsible processor’s queue. handle_queue_sync and handle_queue_async empty the processor’s queue and insert/update all values in the local hash map. handle_queue_sync is automatically called by a processor trying to insert a value, if the responsible thread’s queue is full. So, if all threads are continuously inserting elements, it should suffice for all processors to keep calling insert without manually handling the queues.

If not all processors are inserting elements at some point, then it becomes necessary for processors to handle the queues manually using any of the two handle_queue methods.

Template Parameters:

  • K – The type of the keys in the hash map.

  • V – The type of the values in the hash map.

  • SeqHashMapType – The type of the hash map used internally. This should be compatible with std::unordered_map.

  • UpdateFn – The update function deciding how to insert or update values in the map.

Public Types

enum class Whereabouts

The whereabouts of a value in the sharded hash map.

The three variants denote, whether an element does not exist, is contained in a local hash map or is still inside a queue.

Values:

enumerator NOWHERE
enumerator IN_MAP
enumerator IN_QUEUE

Public Functions

inline ShardedMap(size_t thread_count, size_t queue_capacity)

Creates a new sharded map.

Parameters:

  • thread_count – The exact number of threads working on this map. Thread ids must be 0, 1, …, thread_count-1.

  • queue_capacity – The maximum amount of elements allowed in each queue.

inline ~ShardedMap()
inline void reset_barrier()

When the thread barrier was modified (e.g. by calling arrive_and_drop), reset it to its original state, so insertions function properly again.

inline Shard get_shard(const size_t thread_id)

Create a shard for the given thread.

Parameters:

thread_id – The id of the thread for which to create a shard.

Returns:

A shard for the given thread id.

inline size_t size() const

Returns the number of key-value pairs in the map.

Note, that this method calculates the size for each map separately and is therefore not O(1).

Returns:

The number of key-value pairs in the map.

template<std::ranges::random_access_range Range, StateCreatorFunction CreateStateFn, std::copyable State = std::result_of_t<CreateStateFn(size_t)>, StatefulGeneratorFunction<K, InputValue, std::ranges::range_reference_t<Range>, State> GeneratorFn>
inline std::vector<State> batch_insert(Range &range, CreateStateFn gen_state, GeneratorFn generate_next)

Batch inserts several elements in parallel with a thread-local state.

This iterates over a std::ranges::random_access_range (e.g. a std::vector or std:span).

The inserted elements are generated by a generator function which takes as arguments the current element of the range and a reference to the thread-local state.

This function allows creating mutable thread-local state instances of any type which are passed to each invocation of the generator function.

Parameters:

  • range – The range to iterate over.

  • gen_state – A function that takes a size_t as input which is the thread id, and returns the initial thread-local state of this thread’s invocations of the generator function. This state may be of any desired type.

  • generate_next – A function that generates key-value pairs to insert into the map. It takes a reference to the current element of the range and a reference to the current thread-local state and returns an std::pair<K,InputValue>, which is inserted into the map.

Returns:

The a vector containing the final thread-local state for each thread.

template<std::ranges::random_access_range Range, StatelessGeneratorFunction<K, InputValue, std::ranges::range_reference_t<Range>> GeneratorFn>
inline void batch_insert(Range &range, GeneratorFn generate_next)

Batch inserts several elements in parallel with a thread-local state.

This iterates over a std::ranges::random_access_range (e.g. a std::vector or std:span).

The inserted elements are generated by a generator function which takes as arguments the current element of the range and a reference to the thread-local state.

Parameters:

  • range – The range to iterate over.

  • generate_next – A function that generates key-value pairs to insert into the map. It takes the current index of the iteration as an argument and returns an std::pair<K,InputValue>, which is inserted into the map.

template<StateCreatorFunction CreateStateFn, std::copyable State = std::result_of_t<CreateStateFn(size_t)>, std::random_access_iterator Iter, StatefulGeneratorFunction<K, InputValue, std::iter_reference_t<Iter>, State> GeneratorFn>
inline std::vector<State> batch_insert(Iter begin, Iter end, CreateStateFn gen_state, GeneratorFn generate_next)

Batch inserts several elements in parallel with a thread-local state.

This iterates over a pair of std::random_access_iterator (e.g. an iterator of std::vector, std:span, std::string, etc).

The inserted elements are generated by a generator function which takes as arguments the current element returned by the iterator and a reference to the thread-local state.

This function allows creating mutable thread-local state instances of any type which are passed to each invocation of the generator function.

Parameters:

  • begin – The start iterator.

  • end – The end iterator.

  • gen_state – A function that takes a size_t as input which is the thread id, and returns the initial thread-local state of this thread’s invocations of the generator function. This state may be of any desired type.

  • generate_next – A function that generates key-value pairs to insert into the map. It takes the current index of the iteration as an argument and returns an std::pair<K,InputValue>, which is inserted into the map.

template<std::random_access_iterator Iter, StatelessGeneratorFunction<K, InputValue, std::iter_reference_t<Iter>> GeneratorFn>
inline void batch_insert(Iter begin, Iter end, GeneratorFn generate_next)

Batch inserts several elements in parallel with a thread-local state.

This iterates over a pair of std::random_access_iterator (e.g. an iterator of std::vector, std:span, std::string, etc).

The inserted elements are generated by a generator function which takes as arguments the current element returned by the iterator and a reference to the thread-local state.

Parameters:

  • begin – The start iterator.

  • end – The end iterator.

  • generate_next – A function that generates key-value pairs to insert into the map. It takes the current index of the iteration as an argument and returns an std::pair<K,InputValue>, which is inserted into the map.

template<StateCreatorFunction CreateStateFn, std::copyable State = std::result_of_t<CreateStateFn(size_t)>, std::integral StartIntType, std::integral EndIntType, StatefulGeneratorFunction<K, InputValue, util::unify_ints_t<StartIntType, EndIntType>, State> GeneratorFn>
inline std::vector<State> batch_insert(StartIntType begin, EndIntType end, CreateStateFn gen_state, GeneratorFn generate_next)

Batch inserts several elements in parallel with a thread-local state.

The inserted elements are generated by a generator function which takes as arguments the current iteration index and a reference to the thread-local state.

This function allows creating mutable thread-local state instances of any type which are passed to each invocation of the generator function.

Parameters:

  • begin – The start index if the iteration.

  • end – The (exclusive) end index of the iteration

  • gen_state – A function that takes a size_t as input which is the thread id, and returns the initial thread-local state of this thread’s invocations of the generator function. This state may be of any desired type.

  • generate_next – A function that generates key-value pairs to insert into the map. It takes the current index of the iteration and a reference to the current thread-local state and returns an std::pair<K,InputValue>, which is inserted into the map.

Returns:

The a vector containing the final thread-local state for each thread.

template<StatelessGeneratorFunction<K, InputValue, size_t> GeneratorFn>
inline void batch_insert(std::integral auto begin, std::integral auto end, GeneratorFn generate_next)

Batch inserts several elements in parallel with a thread-local state.

The inserted elements are generated by a generator function which takes as arguments the current iteration index and a reference to the thread-local state.

Parameters:

  • start – The start index if the iteration.

  • end – The (exclusive) end index of the iteration

  • gen_state – A function that takes a size_t as input which is the thread id, and returns the initial thread-local state of this thread’s invocations of the generator function. This state may be of any desired type.

  • generate_next – A function that generates key-value pairs to insert into the map. It takes the current index of the iteration as an argument and returns an std::pair<K,InputValue>, which is inserted into the map.

inline Whereabouts where(const K &k)

Searches a hash map and queue to determine whether the given key exists in the sharded hash table.

Note, that this is not efficient and only for debug purposes. The time complexity is linear in the queue size.

Parameters:

k – The key to search for.

Returns:

NOWHERE, if the element does not exist. IN_MAP, if the element exists in a hash map. IN_QUEUE, if the element exists in a queue.

inline void for_each(std::invocable<const K&, const V&> auto f) const

Runs a method for each value in the map.

The given function must take const references to a key and a value respectively.

Parameters:

f – The function or lambda to run for each value.

inline SeqHashMap::iterator end()
inline SeqHashMap::iterator find(const K &key)
inline std::vector<size_t> queue_loads() const

Returns the number of elements in each queue.

inline std::vector<size_t> map_loads() const

Returns the number of elements in each map.

inline std::barrier<decltype(FN)> &barrier()

Return a reference to the thread barrier used by this map.

Note that if you call reset_barrier, the reference returned by this function is invalidated!

class Shard

Public Functions

inline Shard(ShardedMap &sharded_map, size_t thread_id)

Create a new shard for the given thread.

Parameters:

  • sharded_map – The sharded map to which the shard belongs.

  • thread_id – The thread’s id. Must be less than thread_count in the sharded map.

inline void insert_or_update_direct(const K &k, InputValue &&in_value)

Inserts or updates a new value in the map, depending on whether.

Parameters:

  • k – The key to insert or update a value for.

  • in_value – The value with which to insert or update.

inline void handle_queue_sync(bool cause_wait = true)

Handles this thread’s queue synchronously with other threads, inserting or updating all values in its queue.

This thread will wait until all other threads also call this method before starting to handle the queues.

Parameters:

cause_wait – If true, this will force other threads to handle their queues when they call insert.

inline void handle_queue_async()

Handles this thread’s queue, inserting or updating all values in its queue.

Warning: This should not be called while other threads are inserting into this thread’s queue!

inline void insert(QueueStoredValue &&pair)

Inserts or updates a new value in the map.

If the value is inserted into the current thread’s map, it is inserted immediately. If not, then it is added to that thread’s queue. It will only be inserted into the map, once the thread comes around to handle its queue using the handle_queue method.

Parameters:

pair – The key-value pair to insert or update.

inline void insert(const K &key, InputValue value)

Inserts or updates a new value in the map.

If the value is inserted into the current thread’s map, it is inserted immediately. If not, then it is added to that thread’s queue. It will only be inserted into the map, once the thread comes around to handle its queue using the handle_queue method.

Parameters:

  • key – The key of the value to insert.

  • value – The value to associate with the key.