Databases
StackOverflow2013
Postsdbo
POFast C++ container like the C# HashSet<T> and Dictionary<K,V>?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POFast C++ container like the C# HashSet<T> and Dictionary<K,V>?
    primarykey
    data
    text
    <p>I've used HashSet and Dictionary a lot in C#, and found them very fast... </p> <p>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?</p> <p>Or, is there a better C++ Hash container out there?</p> <p>I'm hashing int32s, usually around 100,000 of them.</p> <p>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 :)</p> <p>(Both were run as Release builds, both are Console apps)</p> <p>C# Output:</p> <pre><code>Found 511 values in the intersection, in 19 ms Found 508 values in the intersection, in 13 ms </code></pre> <p>C++ Output:</p> <pre><code>Found 308 values in the intersection, in 11764.7ms Found 316 values in the intersection, in 11742.8ms </code></pre> <p>C++ Output (using stdext::hash_map instead of std::map)</p> <pre><code>Found 300 values in the intersection, in 383.552ms Found 306 values in the intersection, in 2277.02ms </code></pre> <p>C++ Output (using stdext::hash_map, a release x64 build)</p> <pre><code>Found 292 values in the intersection, in 1037.67ms Found 302 values in the intersection, in 3663.71ms </code></pre> <p>Notes:</p> <ul> <li>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</li> </ul> <p>C#:</p> <pre><code> 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&lt;int,int&gt; theMap = new Dictionary&lt;int,int&gt;(); List&lt;int&gt; set1 = new List&lt;int&gt;(); List&lt;int&gt; set2 = new List&lt;int&gt;(); // Create 100,000 values for set1 for ( int i = 0; i &lt; 100000; i++ ) { int value = 1000000000 + i; set1.Add(value); } // Create 1,000 values for set2 for ( int i = 0; i &lt; 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; } </code></pre> <p>C++:</p> <pre><code>int runIntersectionTest() { std::map&lt;int,int&gt; theMap; vector&lt;int&gt; set1; vector&lt;int&gt; set2; // Create 100,000 values for set1 for ( int i = 0; i &lt; 100000; i++ ) { int value = 1000000000 + i; set1.push_back(value); } // Create 1,000 values for set2 for ( int i = 0; i &lt; 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&lt;int&gt;::iterator iterator = set1.begin(); iterator != set1.end(); iterator++ ) { int value = *iterator; theMap[value] = 1; } int intersectionSize = 0; for ( vector&lt;int&gt;::iterator iterator = set2.begin(); iterator != set2.end(); iterator++ ) { int value = *iterator; map&lt;int,int&gt;::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 &lt;&lt; "Found " &lt;&lt; intersectionSize &lt;&lt; " values in the intersection, in " &lt;&lt; timer.GetMilliseconds() &lt;&lt; "ms" &lt;&lt; endl; timer.Reset(); intersectionSize = runIntersectionTest(); timer.Stop(); cout &lt;&lt; "Found " &lt;&lt; intersectionSize &lt;&lt; " values in the intersection, in " &lt;&lt; timer.GetMilliseconds() &lt;&lt; "ms" &lt;&lt; endl; getchar(); return 0; } </code></pre>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USAlex Black
    1. USAlex Black
    plurals
    1. PL
      singulars
      1. LTLinked
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POFast C++ container like the C# HashSet<T> and Dictionary<K,V>?
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POFast C++ container like the C# HashSet<T> and Dictionary<K,V>?
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POFast C++ container like the C# HashSet<T> and Dictionary<K,V>?
      1. This table or related slice is empty.
      1. VTDownMod
    1. COCould you provide some benchmarks?
      singulars
      1. POFast C++ container like the C# HashSet<T> and Dictionary<K,V>?
      1. USTodd Gardner
    2. COWhat takes maybe 10ms in C# seems to take 1,000ms in C++. I'll try to do a more controlled comparison tomorrow, maybe post code for each C# and C++.
      singulars
      1. POFast C++ container like the C# HashSet<T> and Dictionary<K,V>?
      1. USAlex Black
    3. COI posted some benchmarks.
      singulars
      1. POFast C++ container like the C# HashSet<T> and Dictionary<K,V>?
      1. USAlex Black
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload