Fast C++ container like the C# HashSet<T> and Dictionary<K,V>?

c++, hashmap, hashtable

Solution

Hash_map and hash_set are non-standard, unordered_map and unordered_set are the most likely soon to be standard versions. Without having a reproducer, I don't think this is going to get far though. Under the hood, they are the same data structures, so they should have similar performance.

I compiled the provided sample under MS Visual Studio 2008 v9.0.30729.1, as Visual C++ -> Win32 -> Console Application (though I rolled my own Timer class because I wasn't sure what you were using). Under debug, I got times of 1000 ms, but compiling under release was 50 ms.

#include <vector>
#include <iostream>
#include <map>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#include <windows.h>

typedef struct {
    LARGE_INTEGER start;
    LARGE_INTEGER stop;
} stopWatch;

class CStopWatch {

private:
    stopWatch timer;
    LARGE_INTEGER frequency;
    double LIToSecs( LARGE_INTEGER & L);
public:
    CStopWatch();
    void startTimer( );
    void stopTimer( );
    double getElapsedTime();
};

double CStopWatch::LIToSecs( LARGE_INTEGER & L) {
    return ((double)L.QuadPart /(double)frequency.QuadPart) ;
}

CStopWatch::CStopWatch(){
    timer.start.QuadPart=0;
    timer.stop.QuadPart=0;
    QueryPerformanceFrequency( &frequency ) ;
}

void CStopWatch::startTimer( ) {
    QueryPerformanceCounter(&timer.start) ;
}

void CStopWatch::stopTimer( ) {
    QueryPerformanceCounter(&timer.stop) ;
}

double CStopWatch::getElapsedTime() {
    LARGE_INTEGER time;
    time.QuadPart = timer.stop.QuadPart - timer.start.QuadPart;
    return LIToSecs( time) ;
}

using namespace std;
int runIntersectionTest()
{
    std::map<int,int> theMap;

    vector<int> set1;
    vector<int> set2;

    // Create 100,000 values for set1
    for ( int i = 0; i < 100000; i++ )
    {
        int value = 1000000000 + i;
        set1.push_back(value);
    }

    // Create 1,000 values for set2
    for ( int i = 0; i < 1000; i++ )
    {
        int random = rand() % 200000 + 1;
        random *= 10;

        int value = 1000000000 + random;
        set2.push_back(value);
    }

    // Now intersect the two sets by populating the map
    for ( vector<int>::iterator iterator = set1.begin(); iterator != set1.end(); iterator++ )
    {
        int value = *iterator;

        theMap[value] = 1;
    }

    int intersectionSize = 0;

    for ( vector<int>::iterator iterator = set2.begin(); iterator != set2.end(); iterator++ )
    {
        int value = *iterator;

        map<int,int>::iterator foundValue = theMap.find(value);

        if ( foundValue != theMap.end() )
        {
                theMap[value] = 2;

                intersectionSize++;
        }
    }

    return intersectionSize;

}

int main(int argc, char* argv[])
{
    srand ( time(NULL) );
    int tests = 2;
    while(tests--){
      CStopWatch timer;
      timer.startTimer();
      int intersectionSize = runIntersectionTest();
      timer.stopTimer();

      cout << "Found " << intersectionSize << " values in the intersection, in " << timer.getElapsedTime() << "s\r\n";
    }

    getchar();

    return 0;
}

(I would try with unordered_map but my version doesn't have it). I suspect there is some problem in your setup for C++.

Problem

I've used HashSet and Dictionary a lot in C#, and found them very fast... I've tried using std::map and std::hash_map and am finding them very slow in comparision. Does this sound like expected behaviour? Is there something I might be doing wrong in my use of std::hash_map? Or, is there a better C++ Hash container out there? I'm hashing int32s, usually around 100,000 of them. Update: I created a repro in C# and C++. It runs two trials, they take 19ms and 13ms in C#, and about 11,000ms in C++. There must be something really wrong with my C++ code :) (Both were run as Release builds, both are Console apps) C# Output: ``` Found 511 values in the intersection, in 19 ms Found 508 values in the intersection, in 13 ms ``` C++ Output: ``` Found 308 values in the intersection, in 11764.7ms Found 316 values in the intersection, in 11742.8ms ``` C++ Output (using stdext::hash_map instead of std::map) ``` Found 300 values in the intersection, in 383.552ms Found 306 values in the intersection, in 2277.02ms ``` C++ Output (using stdext::hash_map, a release x64 build) ``` Found 292 values in the intersection, in 1037.67ms Found 302 values in the intersection, in 3663.71ms ``` Notes: - Set2 is not getting populated quite as I wanted in C++, I was expecting it to have a 50% intersection with Set1 (as it does in C#), but I had to multiply my random number by 10 for some reason to even get them to partially not intersect C#: ``` static void Main(string[] args) { int start = DateTime.Now.Millisecond; int intersectionSize = runIntersectionTest(); int duration = DateTime.Now.Millisecond - start; Console.WriteLine(String.Format("Found {0} values in the intersection, in {1} ms", intersectionSize, duration)); start = DateTime.Now.Millisecond; intersectionSize = runIntersectionTest(); duration = DateTime.Now.Millisecond - start; Console.WriteLine(String.Format("Found {0} values in the intersection, in {1} ms", intersectionSize, duration)); Console.ReadKey(); } static int runIntersectionTest() { Random random = new Random(DateTime.Now.Millisecond); Dictionary<int,int> theMap = new Dictionary<int,int>(); List<int> set1 = new List<int>(); List<int> set2 = new List<int>(); // Create 100,000 values for set1 for ( int i = 0; i < 100000; i++ ) { int value = 1000000000 + i; set1.Add(value); } // Create 1,000 values for set2 for ( int i = 0; i < 1000; i++ ) { int value = 1000000000 + (random.Next() % 200000 + 1); set2.Add(value); } // Now intersect the two sets by populating the map foreach( int value in set1 ) { theMap[value] = 1; } int intersectionSize = 0; foreach ( int value in set2 ) { int count; if ( theMap.TryGetValue(value, out count ) ) { intersectionSize++; theMap[value] = 2; } } return intersectionSize; } ``` C++: ``` int runIntersectionTest() { std::map<int,int> theMap; vector<int> set1; vector<int> set2; // Create 100,000 values for set1 for ( int i = 0; i < 100000; i++ ) { int value = 1000000000 + i; set1.push_back(value); } // Create 1,000 values for set2 for ( int i = 0; i < 1000; i++ ) { int random = rand() % 200000 + 1; random *= 10; int value = 1000000000 + random; set2.push_back(value); } // Now intersect the two sets by populating the map for ( vector<int>::iterator iterator = set1.begin(); iterator != set1.end(); iterator++ ) { int value = *iterator; theMap[value] = 1; } int intersectionSize = 0; for ( vector<int>::iterator iterator = set2.begin(); iterator != set2.end(); iterator++ ) { int value = *iterator; map<int,int>::iterator foundValue = theMap.find(value); if ( foundValue != theMap.end() ) { theMap[value] = 2; intersectionSize++; } } return intersectionSize; } int _tmain(int argc, _TCHAR* argv[]) { srand ( time(NULL) ); Timer timer; int intersectionSize = runIntersectionTest(); timer.Stop(); cout << "Found " << intersectionSize << " values in the intersection, in " << timer.GetMilliseconds() << "ms" << endl; timer.Reset(); intersectionSize = runIntersectionTest(); timer.Stop(); cout << "Found " << intersectionSize << " values in the intersection, in " << timer.GetMilliseconds() << "ms" << endl; getchar(); return 0; } ```

Original source

Related problems