Check if value exists across 16 containers

Question

I have 16 threads that calculate the hash of a key. I'm trying to divide up the work between the threads, because calculating the hash and checking if it exists in a linear fashion is only utilizing a fraction of my cpu power. Currently, I am using a single map container that all threads can access using mutex locking. However, since the actual hashing takes next to no time at all, the threads are mostly sitting idle, waiting on another thread to finish its business using map::count to check if the key exists in the map.

The main goal of this program is brute force checking for collisions, as I need to be sure there are none before I add it to my project.

Is there a way to use separate maps, or other containers, and determine if said key exists, rather than linearly searching through each map with each key once all the threads are finished? What about some sort of queuing system?

Edit: This is the function I'm trying to thread:

int coll = 0;
map<long, bool> mymap;
string temp;
long myhash;
for (int i = 0; i < 256; i++)
  for (int j = 0; j < 256; j++)
    for (int k = 0; k < 256; k++)
    {
      temp = i;
      temp += j;
      temp += k;
      temp += temp;
      myhash = hash(temp.c_str());

      if (mymap.count(myhash))
      {
        coll++;
        cout << "Collision at " << i << " " << j << " " << k << endl;
      }
      else
      {
        mymap[myhash] = true;
      }
  }

cout << "Number of collisions: " << coll << endl;
cout << "Map size: " << mymap.size() << endl;

Sounds like some sort of "per-bucket" locking... but does it make sense? If you only want to mutate the elements, but not the container, you can make each element lockable by itself. — Kerrek SB, May 15 '12 at 17:00
How big does this container get? You could split the map into several maps (or hashmaps) and use a hashing function that tells you which map to do the lookup on, this would be like a map/reduce approach but would only be practical if the container size got large enough for this to be worthwile so you'd need to profile — EdChum, May 15 '12 at 17:04
@EdChum Currently, I've been able to compare 256^3 values (~16 million). But I want to add a 4th key. This takes ~45 seconds to calculate and compare 256^3 keys. Increase this to 256^4, and I'm looking at about ~2.5 hours of comparison. — Drise, May 15 '12 at 17:09

score 2 · Accepted Answer · edited May 15 '12 at 17:42

2

This algorithm seems fairly easy to parallelize with OpenMP:

int coll = 0;
map<long, bool> mymap;

#pragma omp parallel for
for (int i = 0; i < 256; i++)
  for (int j = 0; j < 256; j++)
    for (int k = 0; k < 256; k++)
    {
      string temp = i;
      temp += j;
      temp += k;
      temp += temp;
      long myhash = hash(temp.c_str());

      if (mymap.count(myhash))
      {
        #pragma omp atomic
        coll++;
        cout << "Collision at " << i << " " << j << " " << k << endl;
      }
      else
      {
        #pragma omp critical
        mymap[myhash] = true;
      }
  }

Some explanation: first we start from the assumption that collisions are very rare (it would be a very poor hash table implementation if collisions were frequent). Given this, it's very unlikely that, as a thread is inserting to a certain key, another thread simultaneously inserts the exact same key because it happened to stumble upon a different value that hashes to the exact same key. Furthermore, even if this were the case, it is sufficient for only one of them to set the value true, since it cannot go back to false and subsequent "insertions" will only overwrite a true with true. Therefore, in my opinion, besides the increment of coll no further synchronization is needed.

edited May 15 '12 at 17:42

Drise

4,310
5
41
66

answered May 15 '12 at 17:01

Tudor

61,523
12
102
142

Would you mind elaborating on the #pragma's you added? And unless I did something wrong, run time is the same. – Drise May 15 '12 at 17:17
@Drise: This is the openMP parallelization library available on most (if not all) C++ compilers (at least on gcc and cl). Just `#include ` and compile with `-openmp`. The `#pragma omp parallel for` indicates that a team of threads should be created and that the iterations of the following for loop should be split among them. The other pragma is to ensure atomicity of potentially colliding operations. – Tudor May 15 '12 at 17:18
#include && g++ main.cpp -openmp -o main --> Still single threaded. – Drise May 15 '12 at 17:27
@Drise: Hmm... try with `-fopenmp`. Also try to print the result of `omp_get_num_threads()` inside the outermost for loop and see what it returns. – Tudor May 15 '12 at 17:33
@Drise: Did you make `temp` and `myhash` local inside the loops? – Tudor May 15 '12 at 17:36
I do believe you got it. Number of collisions: 0 Map size: 16777216 24.7040000000 seconds – Drise May 15 '12 at 17:38
I re-added the #pragma omp critical, otherwise I get seg faults. – Drise May 15 '12 at 17:42
@Drise: Yeah, I was pondering a bit whether that was needed or not, but I guess it's better to have it. – Tudor May 15 '12 at 17:42

score 0 · Answer 2 · answered May 15 '12 at 18:05

Although this has already be answered above, you can improve performance by replacing the std::map::count() and insert via array operator with something more effecient

One of the std::map::insert() methods returns a pair where the bool member will be false if the element already existed in the map. Something like this:

    int coll = 0;
typedef map<long, bool> MY_MAP_TYPE;
MY_MAP_TYPE mymap;
string temp;
long myhash;
for (int i = 0; i < 256; i++)
    for (int j = 0; j < 256; j++)
        for (int k = 0; k < 256; k++)
        {
            temp = i;
            temp += j;
            temp += k;
            temp += temp;
            myhash = hash(temp.c_str());
            if( mymap.insert( MY_MAP_TYPE::value_type( myhash, true ) ).second == false)
            {
                coll++;
                cout << "Collision at " << i << " " << j << " " << k << endl;
            }
        }

Thanks for the suggestion. I created a separate [question](http://stackoverflow.com/questions/10606462/optimizing-an-algorithm-using-mapcount), so you can answer there. — Drise, May 15 '12 at 18:12
A bunch of people beat me to the punch - no worries - glad to help! — Bukes, May 15 '12 at 18:31

Check if value exists across 16 containers

2 Answers2

Linked