• 2021.4
  • 09/27/2021
  • Public Content
Contents

concurrent_hash_map

A
concurrent_hash_map<Key, T, HashCompare >
is a hash table that permits concurrent accesses. The table is a map from a key to a type
T
. The traits type HashCompare defines how to hash a key and how to compare two keys.
The following example builds a
concurrent_hash_map
where the keys are strings and the corresponding data is the number of times each string occurs in the array
Data
.
#include "oneapi/tbb/concurrent_hash_map.h" #include "oneapi/tbb/blocked_range.h" #include "oneapi/tbb/parallel_for.h" #include <string> using namespace oneapi::tbb; using namespace std; // Structure that defines hashing and comparison operations for user's type. struct MyHashCompare { static size_t hash( const string& x ) { size_t h = 0; for( const char* s = x.c_str(); *s; ++s ) h = (h*17)^*s; return h; } //! True if strings are equal static bool equal( const string& x, const string& y ) { return x==y; } }; // A concurrent hash table that maps strings to ints. typedef concurrent_hash_map<string,int,MyHashCompare> StringTable; // Function object for counting occurrences of strings. struct Tally { StringTable& table; Tally( StringTable& table_ ) : table(table_) {} void operator()( const blocked_range<string*> range ) const { for( string* p=range.begin(); p!=range.end(); ++p ) { StringTable::accessor a; table.insert( a, *p ); a->second += 1; } } }; const size_t N = 1000000; string Data[N]; void CountOccurrences() { // Construct empty table. StringTable table; // Put occurrences into the table parallel_for( blocked_range<string*>( Data, Data+N, 1000 ), Tally(table) ); // Display the occurrences for( StringTable::iterator i=table.begin(); i!=table.end(); ++i ) printf("%s %d\n",i->first.c_str(),i->second); }
A
concurrent_hash_map
acts as a container of elements of type
std::pair<const Key,T>
. Typically, when accessing a container element, you are interested in either updating it or reading it. The template class
concurrent_hash_map
supports these two purposes respectively with the classes
accessor
and
const_accessor
that act as smart pointers. An
accessor
represents
update
(
write
) access. As long as it points to an element, all other attempts to look up that key in the table block until the
accessor
is done. A
const_accessor
is similar, except that is represents
read-only
access. Multiple
const_accessors
can point to the same element at the same time. This feature can greatly improve concurrency in situations where elements are frequently read and infrequently updated.
The methods
find
and
insert
take an
accessor
or
const_accessor
as an argument. The choice tells
concurrent_hash_map
whether you are asking for
update
or
read-only
access. Once the method returns, the access lasts until the
accessor
or
const_accessor
is destroyed. Because having access to an element can block other threads, try to shorten the lifetime of the
accessor
or
const_accessor
. To do so, declare it in the innermost block possible. To release access even sooner than the end of the block, use method
release
. The following example is a rework of the loop body that uses
release
instead of depending upon destruction to end thread lifetime:
StringTable accessor a; for( string* p=range.begin(); p!=range.end(); ++p ) { table.insert( a, *p ); a->second += 1; a.release(); }
The method
remove(key)
can also operate concurrently. It implicitly requests write access. Therefore before removing the key, it waits on any other extant accesses on
key
.

Product and Performance Information

1

Performance varies by use, configuration and other factors. Learn more at www.Intel.com/PerformanceIndex.