dimanche 6 décembre 2015

Visual C++ 2015 std::unordered_set performance

I wrote a very simple program to benchmark the performance of std::set<int> vs std::unordered_set<int>. When I run this program on GCC, unordered_set is much faster. But if I run the same code on Visual C++ 2015, set clearly outperforms unordered_set.

Am I missing something obvious? I've searched around for anything that mentions performance problems with unordered_set on Visual C++ but I haven't found anything. Of course, I am running in Release mode with all the usual optimizations turned on.

Here are the results, the 1st column is proportional to the amount of times insert is called, set is the 2nd column and unordered_setis the 3rd. The timings are in microseconds, the lower the better.

// with GCC 4.9.2

1   23.208  11.323  
2   31.705  10.805  
3   41.113  11.671  
4   51.124  12.742  
5   60.941  13.931  
6   69.642  14.083  
7   75.245  15.151  
8   84.227  15.983  
9   93.464  17.415  
10  102.419 18.036  
11  121.212 19.979  
12  129.748 20.908  
13  140.378 22.201  
14  151.061 23.131  
15  151.483 23.289  
16  162.107 24.252  
17  170.408 24.746  
18  175.369 25.73   
19  184.257 26.835  
20  192.877 29.459  
21  214.805 30.461  
22  223.105 30.977  
23  221.382 31.037  
24  230.129 32.398

// with Visual C++ 2015

1   24.761  32.473
2   31.075  47.305
3   39.309  58.974
4   44.749  73.753
5   51.608  81.204
6   58.141  96.035
7   67.309  106.105
8   75.653  118.712
9   80.801  126.99
10  88.548  144.899
11  95.388  165.135
12  105.546 170.017
13  108.9   177.442
14  117.891 192.446
15  125.177 194.573
16  130.842 212.399
17  138.182 242.828
18  144.113 240.621
19  151.28  262.748
20  158.495 265.814
21  168.463 277.699
22  178.542 295.593
23  181.643 304.112
24  191.779 317.013

And here is the code I wrote:

#include <iostream>
#include <set>
#include <unordered_set>
#include <chrono>

template<typename T>
T InsertTest(const int count, const int repeat)
{
    T set;

    for (int k = 0; k < repeat; ++k)
    {
        for (int i = 0; i < count; ++i)
        {
            set.insert(i * (repeat + 1));
        }
    }

    return set;
}

int main()
{
    for (int repeat = 1; repeat < 25; ++repeat)
    {
        std::cout << repeat << '\t';
        {
            const auto beg = std::chrono::high_resolution_clock::now();
            InsertTest<std::set<int>>(100000, repeat);
            const auto end = std::chrono::high_resolution_clock::now();
            std::cout << std::chrono::duration_cast<std::chrono::microseconds>(end - beg).count() / 1000.0f << '\t';
        }

        {
            const auto beg = std::chrono::high_resolution_clock::now();
            InsertTest<std::unordered_set<int>>(100000, repeat);
            const auto end = std::chrono::high_resolution_clock::now();
            std::cout << std::chrono::duration_cast<std::chrono::microseconds>(end - beg).count() / 1000.0f << '\t';
        }
        std::cout << std::endl;
    }
}

Aucun commentaire:

Enregistrer un commentaire