4
\$\begingroup\$

I'm fairly new to C++, so as a learning exercise for how to use various simple data structures efficiently and what I should and shouldn't avoid, I wrote the following code:

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <queue>

void primitive_test() {
    unsigned long l = 20000000;
    std::unordered_map<int, int> map;
    std::vector<int> vec1;
    std::vector<int> vec2;
    std::vector<int> vec3;
    std::deque<int> que;
    int *array = new int[l];
    clock_t begin;

    begin = clock();
    for (int i = 0; i < l; i++) {
        map[i] = i;
    }
    std::cout << "std::unordered_map: " << clock() - begin << '\n';

    begin = clock();
    for (int i = 0; i < l; i++) {
        vec1.push_back(i);
    }
    std::cout << "std::vector (no reserve): " << clock() - begin << '\n';

    begin = clock();
    vec2.reserve(l);
    for (int i = 0; i < l; i++) {
        vec2.push_back(i);
    }
    std::cout << "std::vector (reserve): " << clock() - begin << '\n';

    begin = clock();
    vec3.resize(l);
    for (int i = 0; i < l; i++) {
        vec3[i] = i;
    }
    std::cout << "std::vector (resize): " << clock() - begin << '\n';

    begin = clock();
    for (int i = 0; i < l; i++) {
        que.push_back(i);
    }
    std::cout << "std::deque: " << clock() - begin << '\n';

    begin = clock();
    for (int i = 0; i < l; i++) {
        que.emplace_back(i);
    }
    std::cout << "std::deque (emplace): " << clock() - begin << '\n';

    begin = clock();
    for (int i = 0; i < l; i++) {
        array[i] = i;
    }
    std::cout << "array: " << clock() - begin << '\n';
}

void object_test() {
    unsigned long l = 20000000;
    std::vector<std::tuple<int>> vec1;
    std::vector<std::tuple<int>> vec2;
    std::vector<std::tuple<int>> vec3;
    std::vector<std::tuple<int>> vec4;
    std::vector<std::tuple<int>> vec5;
    std::vector<std::tuple<int>> vec6;
    std::deque<std::tuple<int>> que;
    auto *array = new std::tuple<int>[l];
    clock_t begin;

    begin = clock();
    for (int i = 0; i < l; i++) {
        std::tuple<int> p(i);
        vec1.push_back(p);
    }
    std::cout << "std::vector (no reserve): " << clock() - begin << '\n';

    begin = clock();
    vec2.reserve(l);
    for (int i = 0; i < l; i++) {
        std::tuple<int> p(i);
        vec2.push_back(p);
    }
    std::cout << "std::vector (reserve): " << clock() - begin << '\n';

    begin = clock();
    vec3.resize(l);
    for (int i = 0; i < l; i++) {
        std::tuple<int> p(i);
        vec3[i] = p;
    }
    std::cout << "std::vector (resize): " << clock() - begin << '\n';

    begin = clock();
    for (int i = 0; i < l; i++) {
        vec4.emplace_back(i);
    }
    std::cout << "std::vector (emplace, no reserve): " << clock() - begin << '\n';

    begin = clock();
    vec5.reserve(l);
    for (int i = 0; i < l; i++) {
        vec5.emplace_back(i);
    }
    std::cout << "std::vector (emplace, reserve): " << clock() - begin << '\n';

    //takes too long - is there a faster way to emplace at a particular position?
//    begin = clock();
//    vec6.resize(l);
//    for(int i = 0; i < l; i++){
//        vec6.emplace(vec6.begin()+i,i);
//    }
//    std::cout << "std::vector (emplace, resize): " << clock() - begin << '\n';

    begin = clock();
    for (int i = 0; i < l; i++) {
        std::tuple<int> p(i);
        que.push_back(p);
    }
    std::cout << "std::deque: " << clock() - begin << '\n';

    begin = clock();
    for (int i = 0; i < l; i++) {
        que.emplace_back(i);
    }
    std::cout << "std::deque (emplace): " << clock() - begin << '\n';

    begin = clock();
    for (int i = 0; i < l; i++) {
        std::tuple<int> p(i);
        array[i] = p;
    }
    std::cout << "array: " << clock() - begin << '\n';
}

int main() {
    std::cout << "\nTesting primitives.\n";
    primitive_test();
    std::cout << "\nTesting objects.\n";
    object_test();
}

The results of running the code on my machine are a bit surprising to me, which leads me to believe that I've perhaps made a mistake or am not treating each case fairly somehow (my comments in // below):

Testing primitives.
std::unordered_map: 8231979                 //wow!
std::vector (no reserve): 402252
std::vector (reserve): 328177               //why is reserving so much slower than resizing?
std::vector (resize): 132258
std::deque: 320600
std::deque (emplace): 363182                //emplacing is a bit slower?
array: 64457                                //should vector be so much slower?

Testing objects.
std::vector (no reserve): 1801645
std::vector (reserve): 551038
std::vector (resize): 1100332               //about twice the time of the above?
std::vector (emplace, no reserve): 1979130  //emplacing is slower than reserving?
std::vector (emplace, reserve): 675151      
                                            //is there a way to emplace a particular position in a vector if we've already made room for it?
std::deque: 579424                          //faster than array?
std::deque (emplace): 693743                //emplacing is slower?
array: 620844

Process finished with exit code 0

Also, here is my CMakeLists:

cmake_minimum_required(VERSION 3.12)
project(maptest)

set(CMAKE_CXX_STANDARD 11)
set(CMAKE_CXX_FLAGS_RELEASE "-O2")

add_executable(maptest main.cpp)

I am running this code on a Predator Helios 300 laptop.

Is there any way that I can improve this benchmark? Have I done something incorrectly/inefficiently or used a function that I shouldn't have used? Is it just that the methodology/approach that I'm using for testing is flawed?

Edit:
I added tests for initializing the vector length in the constructor. After JVApen's comment below, I realized I was doing a debug build. I also realized, upon further looking, that I was being a bit unfair to the vectors since I was timing their resize + reserve functions. I put those before the start of the clock and changed it to a release build and got the following code and results (the vector emplace+resize case still takes a really long time to run):

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <queue>

void primitive_test() {
    unsigned long l = 20000000;
    std::unordered_map<int, int> map;
    std::vector<int> vec1;
    std::vector<int> vec2;
    std::vector<int> vec3;
    std::vector<int> vec4(l);
    std::deque<int> que;
    int *array = new int[l];
    clock_t begin;

    begin = clock();
    for (int i = 0; i < l; i++) {
        map[i] = i;
    }
    std::cout << "std::unordered_map: " << clock() - begin << '\n';

    begin = clock();
    for (int i = 0; i < l; i++) {
        vec1.push_back(i);
    }
    std::cout << "std::vector (no reserve): " << clock() - begin << '\n';

    vec2.reserve(l);
    begin = clock();
    for (int i = 0; i < l; i++) {
        vec2.push_back(i);
    }
    std::cout << "std::vector (reserve): " << clock() - begin << '\n';

    vec3.resize(l);
    begin = clock();
    for (int i = 0; i < l; i++) {
        vec3[i] = i;
    }
    std::cout << "std::vector (resize): " << clock() - begin << '\n';

    begin = clock();
    for (int i = 0; i < l; i++) {
        vec4[i] = i;
    }
    std::cout << "std::vector (initialize): " << clock() - begin << '\n';

    begin = clock();
    for (int i = 0; i < l; i++) {
        que.push_back(i);
    }
    std::cout << "std::deque: " << clock() - begin << '\n';

    begin = clock();
    for (int i = 0; i < l; i++) {
        que.emplace_back(i);
    }
    std::cout << "std::deque (emplace): " << clock() - begin << '\n';

    begin = clock();
    for (int i = 0; i < l; i++) {
        array[i] = i;
    }
    std::cout << "array: " << clock() - begin << '\n';
}

void object_test() {
    unsigned long l = 20000000;
    std::vector<std::tuple<int>> vec1;
    std::vector<std::tuple<int>> vec2;
    std::vector<std::tuple<int>> vec3;
    std::vector<std::tuple<int>> vec4(l);
    std::vector<std::tuple<int>> vec5;
    std::vector<std::tuple<int>> vec6;
    std::vector<std::tuple<int>> vec7;
    std::vector<std::tuple<int>> vec8(l);
    std::deque<std::tuple<int>> que;
    auto *array = new std::tuple<int>[l];
    clock_t begin;

    begin = clock();
    for (int i = 0; i < l; i++) {
        std::tuple<int> p(i);
        vec1.push_back(p);
    }
    std::cout << "std::vector (no reserve): " << clock() - begin << '\n';

    vec2.reserve(l);
    begin = clock();
    for (int i = 0; i < l; i++) {
        std::tuple<int> p(i);
        vec2.push_back(p);
    }
    std::cout << "std::vector (reserve): " << clock() - begin << '\n';

    vec3.resize(l);
    begin = clock();
    for (int i = 0; i < l; i++) {
        std::tuple<int> p(i);
        vec3[i] = p;
    }
    std::cout << "std::vector (resize): " << clock() - begin << '\n';

    begin = clock();
    for (int i = 0; i < l; i++) {
        std::tuple<int> p(i);
        vec4.push_back(p);
    }
    std::cout << "std::vector (initialize): " << clock() - begin << '\n';

    begin = clock();
    for (int i = 0; i < l; i++) {
        vec5.emplace_back(i);
    }
    std::cout << "std::vector (emplace, no reserve): " << clock() - begin << '\n';

    vec6.reserve(l);
    begin = clock();
    for (int i = 0; i < l; i++) {
        vec6.emplace_back(i);
    }
    std::cout << "std::vector (emplace, reserve): " << clock() - begin << '\n';

    //takes too long - is there a faster way to emplace at a particular position?
//    vec7.resize(l);
//    begin = clock();
//    for(int i = 0; i < l; i++){
//        vec7.emplace(vec6.begin()+i,i);
//    }
//    std::cout << "std::vector (emplace, resize): " << clock() - begin << '\n';

    begin = clock();
    for(int i = 0; i < l; i++){
        vec8.emplace_back(i);
    }
    std::cout << "std::vector (emplace, initialize): " << clock() - begin << '\n';

    begin = clock();
    for (int i = 0; i < l; i++) {
        std::tuple<int> p(i);
        que.push_back(p);
    }
    std::cout << "std::deque: " << clock() - begin << '\n';

    begin = clock();
    for (int i = 0; i < l; i++) {
        que.emplace_back(i);
    }
    std::cout << "std::deque (emplace): " << clock() - begin << '\n';

    begin = clock();
    for (int i = 0; i < l; i++) {
        std::tuple<int> p(i);
        array[i] = p;
    }
    std::cout << "array: " << clock() - begin << '\n';
}

int main() {
    std::cout << "\nTesting primitives.\n";
    primitive_test();
    std::cout << "\nTesting objects.\n";
    object_test();
}
Testing primitives.
std::unordered_map: 1690288
std::vector (no reserve): 134839
std::vector (reserve): 64447
std::vector (resize): 11793
std::vector (initialize): 9261
std::deque: 61789
std::deque (emplace): 71425
array: 101057

Testing objects.
std::vector (no reserve): 68414
std::vector (reserve): 42209
std::vector (resize): 9928
std::vector (initialize): 112300
std::vector (emplace, no reserve): 101546
std::vector (emplace, reserve): 49651
std::vector (emplace, initialize): 112602
std::deque: 47545
std::deque (emplace): 47611
array: 9000

Process finished with exit code 0

It's pretty surprising to see vectors beat out arrays when resizing, especially when using primitives! Also, it also seems a bit odd that using a tuple with one int makes it run faster than just using an int directly. I guess emplace must also add some overhead too, since all the emplace cases are slower than the non-emplace cases. Also seems kind of strange that passing in a length to the constructor is actually slower than just telling the vector nothing at all and resizing later when using objects, while the reverse is true if I use primitives instead.

\$\endgroup\$
  • 1
    \$\begingroup\$ Saying you're running on a Predator Helios 300 laptop is like saying you're running it on a HAL 9000. I.e. it doesn't tell people anything about the actual performance of your computer. \$\endgroup\$ – yuri May 15 at 6:18
  • \$\begingroup\$ Welcome to Code Review! You could tag your question beginner and stl, an make the title reflect that you are doing an STL micro-benchmark. There is no need to repeat the C++ tag in the title. \$\endgroup\$ – greybeard May 15 at 6:18
  • \$\begingroup\$ Double checking: Did you build as release build? \$\endgroup\$ – JVApen May 15 at 6:57
  • \$\begingroup\$ @yuri Sorry, I didn't know that it wouldn't be helpful. I thought it would be best to provide as much relevant information as I could think of up front. \$\endgroup\$ – user200759 May 15 at 11:21
  • 1
    \$\begingroup\$ @JVApen I checked and it turns out I was doing a debug build. That solves a few of my problems! Thank you. There are still a few things that seem odd; I'll edit the question accordingly. \$\endgroup\$ – user200759 May 15 at 11:30
5
\$\begingroup\$

Side note: this is a code review site, so I'm going to at least start by reviewing your actual code. I might try to add a few points about what you tried to investigate later, but for now this is mostly just about the code itself.

Don't Repeat Yourself

Right now, your code contains main repetitions of nearly identical code:

begin = clock();
for (int i = 0; i < l; i++) {
    map[i] = i;
}
std::cout << "std::unordered_map: " << clock() - begin << '\n';

begin = clock();
for (int i = 0; i < l; i++) {
    vec1.push_back(i);
}
std::cout << "std::vector (no reserve): " << clock() - begin << '\n';

vec2.reserve(l);
begin = clock();
for (int i = 0; i < l; i++) {
    vec2.push_back(i);
}
std::cout << "std::vector (reserve): " << clock() - begin << '\n';

As a starting point, I'd try to refactor that to eliminate at least some of the repetition. I'd start with a little "timer" template, something on this general order:

template <class F>
void timer(std::string const &label, F f) {
    auto begin = clock();
    f();
    std::cout << label << clock() - begin() << '\n';
}

Then I'd use that for each of the individual tests:

void primitive_test() {
    // ...

    timer("std::unordered_map:", [&]{ for (int i=0; i<l; i++) map[i] = i; } );

    timer("std::vector (no reserve): ", [&]{ for (int i=0; i<l; i++) vec1.push_back(i); }); 

    vec2.reserve(l);
    timer("std::vector (reserve): ", [&]{ for (int i=0; i<l; i++) vec2.push_back(i); });

Improve Readability

Right now, the output isn't very readable. First of all, all the numbers immediately follow the labels, so they're not aligned with each other. When you have a different number of digits, it's not always easy to be sure whether one might be 10 times larger than another. So I'd change the code to display the output so the numbers are aligned with each other:

std::cout << std::setw(30) << label << std::setw(10) << clock() - begin << "\n";

Note that by consolidating the code as we did above, we now only have to make this change in one place.

Second, I'd try to format the numbers as the user would normally expect them to look based on the configured locale. We can do that by adding code like this at the beginning of main:

std::cout.imbue(std::locale(""));

With those changes, we get output that I find much more readable and easier to compare, like this:

Testing primitives.
           std::unordered_map: 2,240,000
    std::vector (no reserve):    130,000
       std::vector (reserve):     60,000
        std::vector (resize):     10,000
    std::vector (initialize):     10,000
                  std::deque:     50,000
        std::queue (emplace):     50,000
                       array:     50,000

Improve Timing

clock() isn't really a great way of timing things. The precision varies (widely) and getting results in a meaningful (real-world) unit is somewhat painful. I'd prefer to use something like std::chrono::high_resolution_clock. Again, having consolidated all the timing in one place makes it much easier to institute this change:

template <class F>
void timer(std::string const &label, F f) {
    using namespace std::chrono;
    auto begin = high_resolution_clock::now();
    f();
    auto end = high_resolution_clock::now();
    std::cout << std::setw(30) << label 
              << std::setw(10) << duration_cast<milliseconds>(end-begin).count() << "ms\n";
}

Now we get output like this:

Testing primitives.
           std::unordered_map:     2,266ms
    std::vector (no reserve):        126ms
       std::vector (reserve):         60ms
        std::vector (resize):         13ms
    std::vector (initialize):         10ms
                  std::deque:         45ms
        std::queue (emplace):         50ms
                       array:         41ms
\$\endgroup\$
  • 2
    \$\begingroup\$ All the clock() - begin timing calculations need to be done before any output is started or generated, otherwise the time spent doing the output can effect the results. \$\endgroup\$ – 1201ProgramAlarm May 15 at 18:59
  • \$\begingroup\$ @1201ProgramAlarm: You certainly don't want to time while you're producing output.As long as the I/O is separated from the computation, though, I haven't seen interleaving the I/O between the timed sections making a significant difference in timing. \$\endgroup\$ – Jerry Coffin May 15 at 22:32
  • \$\begingroup\$ That's what I meant - each timing section needs to have the time computed before you start the output for that section. I see I wasn't clear on that. Since the elapsed time is computed in the middle of a cout chain, some of the output time can be included in the elapsed time. \$\endgroup\$ – 1201ProgramAlarm May 15 at 23:06
  • \$\begingroup\$ @1201ProgramAlarm: If you can actually show that happening, I'll be happy to submit a bug report against the library that's doing it. But I've used all the major implementations of std::chrono::high_resolution_clock many times, and never seen any hint of it misbehaving as you've suggested it could. When/if I see it actually happen, I'll submit a bug report (but I doubt that'll arise). \$\endgroup\$ – Jerry Coffin May 16 at 6:02
  • \$\begingroup\$ @JerryCoffin Is that a bug though? we effectively have operator<<(operator<<(std::cout, "std::unordered_map: "), clock() - begin). Isn't the order of evaluation of arguments unspecified? So the first call to operator<< could be evaluated before or after clock() - begin. \$\endgroup\$ – user673679 May 16 at 7:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.