c++ concurrent hash map with thread-safe find insert count erase and iterator?

[walidjames]

# concurrent container with thread-safe find insert count erase and iterator?

I am currently using tbb::unordered_map container to perform these operations find() insert() erase() count() and to iterate in this container. to increase the performance of my algorithm I need to use all of my CPU threads

so I need to use a concurrent container that permit many threads to operate a thread-safe  find() insert() erase() count() and iteration on common data.

my first attempt is using tbb::concurrent_unordered_map unfortunately this container does not provide safe_erase() function.

my second attempt is to use tbb::concurrent_hash_map as proposed in many Intel Collective section of stackoverflow posts post1  post2 post3  that provides thread-safe finding, inserting and erasing. But according to this Answer  tbb::concurrent_hash_map does not permit safe iterator and they proposed  some libraries that provide a collection of concurrent data structures

and memory reclamation algorithms such as facebook folly , xenium  that give customizable concurrent_hash_map files, when I checked the source code I got lost how to use those header files.

Also I noticed that std::unordered_map member functions find, insert, end() return an iterator while tbb::concurent_hash_map member functions return

a bool and it does not provide thread-safe iterator and   find and insert use const_accessor and accessor

this is my class that i am trying to make run in parallel:

// query.h

#define CHUNK 32

#include <array>

#include <iostream>

#include <unordered_map>

#include <vector>

class query {

  friend auto operator<<(std::ostream &, const query &) -> std::ostream &;

public:

  static size_t DT;

  query() = default;

  virtual ~query() = default;

  // Add a query point to d-tree.

  auto increase(const size_t &) -> query &;

  // Check whether a point is query point.

  auto checks(const size_t &) -> bool;

  // Remove a query point.

  auto remove(const size_t &) -> query &;

  // The number of query points.

  auto size() -> size_t;

private:

  static auto chunk_(size_t) -> size_t;

  size_t calculate_ = 0;

  std::vector<size_t> blank_;

  std::array<std::unordered_map<size_t, std::vector<size_t>>, CHUNK> container_;

};

// query.cpp

#include "query.h"

size_t query::DT = 0;

auto operator<<(std::ostream &out, const query &query) -> std::ostream & {

  for (auto &&tree : query.container_) {

    for (auto &&s: tree) { out << s.first << std::endl; }

  }

  return out;

}

auto query::increase(const size_t &s) -> query & {

  auto &&it = container_[chunk_(s)].find(s);

  if (it != container_[chunk_(s)].end()) {return *this;}

  std::vector<size_t> v;

  container_[chunk_(s)].insert(std::make_pair(s, v));

  ++calculate_;

  return *this; }

auto query::checks(const size_t &p) -> bool {

    return container_[chunk_(p)].count(p);  }

auto query::remove(const size_t &s) -> query & {

  container_[chunk_(s)].erase(s);

  --calculate_;

  return *this; }

auto query::size() -> size_t { return calculate_;}

auto query::chunk_(size_t index) -> size_t {

  return (int) index % CHUNK;   }

### things that I tried:

I am wondering if something like this would be possible:

...// add this to query.h

#include "tbb/concurrent_hash_map.h"

#include <tbb/parallel_for.h>

...

std::array<tbb::concurrent_hash_map<size_t, std::vector<size_t>>, CHUNK> container_;

... // change this in query.cpp

auto query::increase(const size_t &s) -> query & {

  tbb::concurrent_hash_map<size_t, std::vector<size_t>>::const_accessor cacc;

  tbb::concurrent_hash_map<size_t, std::vector<size_t>>::accessor acc;

  auto &&it = container_[chunk_(s)].find(cacc,s);

  if (it != container_[chunk_(s)].end()) {return *this;}

  std::vector<size_t> v;

  container_[chunk_(s)].insert(acc, std::make_pair(s, v));

  ++calculate_;

  return *this; }

...

// later these query functions will be used in other files inside for loops

...

tbb::parallel_for( tbb::blocked_range<size_t>(0,width),

                       [&](tbb::blocked_range<size_t> r)

             {

             for (size_t i=r.begin(); i<r.end(); ++i)

             {

             query.increase(window_[i]);

             }

              });    

...        

### errors that I get:

in this line: if (it != container_[chunk_(s)].end()){...}

error: no operator "!=" matches these operands operand types are: bool != ...

I think because find() returns a bool, but end() returns an iterator.

### notes that I found in SO: SO note 

it says that  you don't need a find() method for your task since insert() methods create the element if it does not exist.

What might be the problem?

What's the best way to achieve this in my code?

Thanks.

[NoorjahanSk_Intel]

Hi,

Thanks for reaching out to us.

>> tbb::concurrent_hash_map does not permit safe iterator

If we want to iterate through a container without any concurrent execution of any member function then we can use range_type to iterate in a parallel way.

Please refer to the below link for more details:

https://spec.oneapi.io/versions/latest/elements/oneTBB/source/containers/concurrent_hash_map_cls/parallel_iteration.html

could you please provide us with the OneTBB version being used and OS details?

Thanks & Regards,

Noorjahan.

[walidjames]

Thank you for your quick response.

I am using windows 10 and Intel oneAPI Base Toolkit version 2022.1.2.
Also, i am using HPC Toolkit version 2022.1.2 to use the intel c++ compiler classic

[NoorjahanSk_Intel]

Hi,

Apologies for the delay.

We are looking into your issue with the concerned team. We will get back to you soon.

Thanks & Regards,

Noorjahan.

[Pavel_K_Intel1]

Hi,

If I understood your question correctly, then the problem is that you got compile time error when you compare result of the find with end(). 
There is another problem end() is unsafe method and you can not safely use it in a concurrent environment, the good side is that we don't need to use it at all in your case, because find returns bool that true if item is found, false otherwise.

You can read more in concurrent_hash_map specification: link.

[NoorjahanSk_Intel]

Hi,

We haven't heard back from you. Could you please provide an update on your issue?

Thanka & Regards,

Noorjahan.

[NoorjahanSk_Intel]

Hi,

We have not heard back from you, so we will close this inquiry now. If you need further assistance, please post a new question.

Thanks & Regards,

Noorjahan.