Intel® oneAPI Threading Building Blocks
Ask questions and share information about adding parallelism to your applications when using this threading library.

concurrent_hash_map gets stuck!

sinedie
Beginner
1,454 Views
Hello,
I am trying to familiarize myself with concurrent_hash_maps. I am running into problem while trying to erase. The program seems to be running at 100% CPU (from top) but none of the 2 processors show much activity. Can't understand it. X(
Can someone fix the problem with erase please? The code is given below.
TIA,
-S

[cpp]#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
using namespace tbb;

class hash_func {
	public:
		static size_t hash( const string &s)
		{
			return s.size();
		}
		static bool equal( const string &s1, const string &s2)
		{
			return s1 == s2;
		}
};

typedef concurrent_hash_map CHM;

void read_words(vector &v)
{
	string s;

	while ( cin >> s ) {
		v.push_back(s);
	}
}

int main()
{
	task_scheduler_init init(-1);

	vector words;
	CHM chm;
	CHM::accessor chm_acc;

	read_words( words );
	cout << "No. of words: " << words.size() << endl;

	for ( int i = 0; i < words.size(); i++ ) {
		if ( chm.find(chm_acc, words) )  {
			int n = chm_acc->second % 3;
			if ( n > 0 ) {
				printf("%s (%d)n", words.c_str(), n );

				chm.insert(chm_acc, words);
				chm_acc->second++;
			} else {
				printf("%s (deleted)n", words.c_str() );
				chm.erase(words);
			}
		} else {
			printf("%sn", words.c_str());

			chm.insert(chm_acc, words);
			chm_acc->second++;
		}
		chm_acc.release();

	}

	return 0;
}

[/cpp]
0 Kudos
1 Solution
jaredkeithwhite
New Contributor I
1,454 Views
What do you mean by "erasing by accessor is not supported"? Per the Reference documentation (page 51), the header file for concurrent_hash_map defines:

bool erase( const_accessor& item_accessor );

bool erase( accessor& item_accessor );


I don't have my development environment handy, or I would do my best to reproduce your problem, but it would appear to me the reason you're getting these results is because of the following:

line 42) you create a write-lock accessor (not a read-lock const_accessor)
line 48) when you successfully "find(accessor, key)", the accessor holds an implicit write lock on that key
line 57) when you subsequently attempt to "erase(key)", that is essentially trying to acquire a second write lock on the same key. For all concurrent_hash_map knows, this could be occurring in a completely separate thread, so a write lock is needed.

-- thus you are deadlocking your system

Am I completely off base in thinking this might be the case?

Worst case scenario, release your accessor and then attempt to "erase(key)".



Quoting - sinedie
erasing by accessor is not supported, and erasing with Key as I used above works fine in several other programs that I had used.

View solution in original post

0 Kudos
4 Replies
jaredkeithwhite
New Contributor I
1,454 Views

It would seem that your hash function is a bit too simplistic -- can you guarantee [for your algorithm] that all of the words will have a different length?

I typically use the "erase(accessor)" method. Have you used this one as well? Your accessor should be able to be used here in your example, rather than the actual key to be removed.




Quoting - sinedie
Hello,
I am trying to familiarize myself with concurrent_hash_maps. I am running into problem while trying to erase. The program seems to be running at 100% CPU (from top) but none of the 2 processors show much activity. Can't understand it. X(
Can someone fix the problem with erase please? The code is given below.
TIA,
-S

[cpp]#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
using namespace tbb;

class hash_func {
	public:
		static size_t hash( const string &s)
		{
			return s.size();
		}
		static bool equal( const string &s1, const string &s2)
		{
			return s1 == s2;
		}
};

typedef concurrent_hash_map CHM;

void read_words(vector &v)
{
	string s;

	while ( cin >> s ) {
		v.push_back(s);
	}
}

int main()
{
	task_scheduler_init init(-1);

	vector words;
	CHM chm;
	CHM::accessor chm_acc;

	read_words( words );
	cout << "No. of words: " << words.size() << endl;

	for ( int i = 0; i < words.size(); i++ ) {
		if ( chm.find(chm_acc, words) )  {
			int n = chm_acc->second % 3;
			if ( n > 0 ) {
				printf("%s (%d)n", words.c_str(), n );

				chm.insert(chm_acc, words);
				chm_acc->second++;
			} else {
				printf("%s (deleted)n", words.c_str() );
				chm.erase(words);
			}
		} else {
			printf("%sn", words.c_str());

			chm.insert(chm_acc, words);
			chm_acc->second++;
		}
		chm_acc.release();

	}

	return 0;
}

[/cpp]

0 Kudos
sinedie
Beginner
1,454 Views
The hash function is too simplistic only because I wanted to have the simplest program. I don't think that this should be the real reason for failure.

erasing by accessor is not supported, and erasing with Key as I used above works fine in several other programs that I had used.

In the code that I had posted, the program would stall while trying to erase the first element. I think it is a problem with lock, but can't see what. The error is reproducable.
0 Kudos
jaredkeithwhite
New Contributor I
1,455 Views
What do you mean by "erasing by accessor is not supported"? Per the Reference documentation (page 51), the header file for concurrent_hash_map defines:

bool erase( const_accessor& item_accessor );

bool erase( accessor& item_accessor );


I don't have my development environment handy, or I would do my best to reproduce your problem, but it would appear to me the reason you're getting these results is because of the following:

line 42) you create a write-lock accessor (not a read-lock const_accessor)
line 48) when you successfully "find(accessor, key)", the accessor holds an implicit write lock on that key
line 57) when you subsequently attempt to "erase(key)", that is essentially trying to acquire a second write lock on the same key. For all concurrent_hash_map knows, this could be occurring in a completely separate thread, so a write lock is needed.

-- thus you are deadlocking your system

Am I completely off base in thinking this might be the case?

Worst case scenario, release your accessor and then attempt to "erase(key)".



Quoting - sinedie
erasing by accessor is not supported, and erasing with Key as I used above works fine in several other programs that I had used.

0 Kudos
sinedie
Beginner
1,454 Views
Wow! That was one of the deadlocks I was not aware of, the one that arises due to different types (read vs write) of locks. I am following O'Reilly's book on TBB which only talks about bool erase( const Key& key ) (p. 95 and 99). Using accessor in place of Key itself did the trick. Thanks a lot.
:)
0 Kudos
Reply