UnorderedMap¶
Header file: <Kokkos_UnorderedMap.hpp>
Kokkos’s unordered map is designed to efficiently handle tens of thousands of concurrent insertions. Consequently, the API is significantly different from the standard unordered_map. The two key differences are fixed capacity and index based.
Fixed capacity: The capacity of the unordered_map is fixed when inside a parallel algorithm. This means that an insert can fail when the capacity of the map is exceeded. The capacity of the map can be changed (rehash) from the host.
Index based: Instead of returning pointers or iterators (which would not work when moving between memory spaces) the map uses integer indexes. This also allows the map to store data in cache friendly ways. The availability of indexes is managed by an internal atomic bitset based on uint32_t.
Key – Must be a POD (Plain Old Data type)
Value –
void indicates an unordered set. Otherwise the Value must be trivially copyable. If the map is created with the SequentialHostInit property, Value can be View.
Device – Device is any class or struct with the following public typedefs or type aliases: execution_space, memory_space, and device_type
Constructor
Create map with enough space for at least capacity_hint number of objects
Create map using the properties with enough space for at least capacity_hint number of objects
Added in version 4.2.
Changed in version 4.7: prop can now contain SequentialHostInit
Public Member Functions
Clear the map
Rehash map to given capacity, the current size is used as a lower bound O(capacity)
Current size of the map, O(capacity)
Capacity of the map, O(1)
Insert the given key into the map with a default constructed value
Insert the given key/value pair into the map and optionally specify the operator, op, used for combining values if key already exists
Return the index of the key if it exist, otherwise return invalid_index
Does the key exist in the map
Is the current index a valid key/value pair
Return the current key at the index
Return the current value at the index
Return true if the internal views (keys, values, hashmap) are allocated
For the calling UnorderedMap, allocate views to have the same capacity as src, and copy data from src.
Allocate views of the calling UnorderedMap to have the same capacity as src.
Copy data from src to the calling UnorderedMap.
Non-Member Functions
Copy an UnorderedMap from src to dst.
Warning
From Kokkos 4.4, src.capacity() == dst.capacity() is required
Create a HostMirror for an UnorderedMap.
Public Methods
Was the key/value pair successfully inserted into the map
Is the key already present in the map
Did the insert fail?
Index where the key exists in the map as long as failed() == false
ValueTypeView – The UnorderedMap value array type.
ValuesIdxType – The index type for lookups in the value array.
Public Insertion Operator Types
Insert the given key/value pair into the map
Duplicate key insertions sum values together.
UnorderedMapInsertOpTypes::NoOp¶
There are 3 potential states for every insertion which are reported by the UnorderedMapInsertResult:
success: implies that the current thread has successfully inserted its key/value pair
existing: implies that the key is already in the map and its current value is unchanged
failed means that either the capacity of the map was exhausted or that a free index was not found with a bounded search of the internal atomic bitset. A failed insertion requires the user to increase the capacity (rehash) and restart the algorithm.
// use the default NoOp insert operation
using map_op_type = Kokkos::UnorderedMapInsertOpTypes<value_view_type, size_type>;
using noop_type = typename map_op_type::NoOp;
noop_type noop;
parallel_for(N, KOKKOS_LAMBDA (uint32_t i) {
map.insert(i, values(i), noop);
});
// OR;
parallel_for(N, KOKKOS_LAMBDA (uint32_t i) {
map.insert(i, values(i));
});
Insertion using UnorderedMapInsertOpTypes::AtomicAdd¶
The behavior from Insertion using default UnorderedMapInsertOpTypes::NoOp holds true with the exception that the UnorderedMapInsertResult:
existing implies that the key is already in the map and the existing value at key was summed with the new value being inserted.
// use the AtomicAdd insert operation
using map_op_type = Kokkos::UnorderedMapInsertOpTypes<value_view_type, size_type>;
using atomic_add_type = typename map_op_type::AtomicAdd;
atomic_add_type atomic_add;
parallel_for(N, KOKKOS_LAMBDA (uint32_t i) {
map.insert(i, values(i), atomic_add);
});
Iteration¶
Iterating over Kokkos’ UnorderedMap is different from iterating over a standard container. The pattern is to iterate over the capacity of the map and check if the current index is valid.
// assume umap is an existing Kokkos::UnorderedMap
parallel_for(umap.capacity(), KOKKOS_LAMBDA (uint32_t i) {
if( umap.valid_at(i) ) {
auto key = umap.key_at(i);
auto value = umap.value_at(i);
...
}
});
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4