Why is allocation and deallocation of std::vector slower than dynamic array on my machine

Question

I was under the impression that std::vector is just a thin wrapper around dynamic arrays, and their performance should be comparable. A search on the Internet and stackoverflow itself gives the same answer as well. However, when I test it myself, I found a huge difference. The code is below. I tried both VC++ 2012 (release build) and MinGW with optimization flag -O2.

The time for new, malloc and calloc is around 0.005 sec, while std::vector takes 0.9 sec on both compilers. Is std::vector inherently slow or my code has some serious flaws?

#define _SCL_SECURE 0
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <time.h>

struct timer
{
    clock_t start;
    timer()
    {
        start=clock();
    }
    ~timer()
    {
        double t=static_cast<double>(clock()-start)/CLOCKS_PER_SEC;
        printf("%lf\n", t);
    }
};

int main()
{
    const size_t len=(1<<28);   
    {
        timer t;
        int *d=new int[len];
        printf("%d\n",d[len-1]);//prevent compiler from optimizing away 
                                //useless allocation and deallocation
        delete[] d;
    }
    {
        timer t;
        int *d=(int *)malloc(len*sizeof(int));
        printf("%d\n", d[len-1]);
        free(d);
    }

    {
        timer t;
        std::vector<int> d(len);
        printf("%d\n", d[len-1]);
    }
    {
        timer t;
        int *d=(int *)calloc(len, sizeof(int));
        printf("%d\n", d[len-1]);
        free(d);
    }

    return 0;
}

EDIT 1

Per suggestion, I test for additional ways of creating dynamic array

new: 0.005
malloc: 0.005
calloc: 0.005
malloc+memset: 1.244
vector(len): 1.231
vector(len, 0): 1.234
vector.reserve(len): 0.005

So indeed the offender is the zero initialization instead allocation or deallocation. This means that if one needs an zero-initialized array, vector is not the way to go, even if it has a constructor that default initialized all elements.

Besides, this is not just something that pop out of my head. My final project for a class is graded on the time spent, and I used a several vectors to allocate a huge memory buffer instead of new for exception safety and because our textbook encourages use of STL. Not until today did I realize that I lost some points because of this. Sad day.

EDIT 2

Today I tried Clang 3.2 on Ubuntu 13.04 x64, and std::vector no longer takes that time to initialize. In fact, vector is now the fastest! Maybe this is a compiler optimization problem after all, not inherently in design of the std::vector.

shouldn't you be running the tests through some 1000's of iterations (if not more)? — Son-Huy Pham
– Son-Huy Pham, Commented Jun 27, 2013 at 15:30
It's even worse on GCC 4.8.1 with -O3. 0.000000 for everything except the vector, which is 4.09 (and a decently lower time the second time run, which is the link). — Qaz
– Qaz, Commented Jun 27, 2013 at 15:32
You should be comparing code that does the same (i.e. did you read vector docs?). You should be comparing code that doesn't have undefined behaviour. — R. Martinho Fernandes
– R. Martinho Fernandes, Commented Jun 27, 2013 at 15:38
The important difference between the vector and the other code is that the vector is zero-initialising the memory, where the other code isn't (apart from the calloc). If you replace the new with new int[len](), it takes as long as the vector. I assume the calloc is optimised in some way (for example, it could request zeroed memory, rather than explicitly zeroing the memory itself). — Mankarse
– Mankarse, Commented Jun 27, 2013 at 15:41
The allocation of the array is generally the least recently used operation when working with it. — Chad
– Chad, Commented Jun 27, 2013 at 15:41

JoeD · Accepted Answer · 2013-06-27 15:45:08Z

4

I believe this is due to allocation of std::vector invoking a copy constructor on each element, where malloc just returns uninitialized memory.

std::vector<int> x(100);

is effectively the same as:

std::vector<int> y(100, int());

See the documentation on the constructor for std::vector http://en.cppreference.com/w/cpp/container/vector/vector

I often will do something like this:

std::vector<int> x; 
x.reserve(100);
// Insert items into x via x.push_back()

answered Jun 27, 2013 at 15:45

JoeD

1716 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

James McNellis Over a year ago

In C++11 (and Visual C++ 2012), std::vector<T> x(100); is not the same as std::vector<T> y(100, T());. The former default constructs 100 elements; the latter copy constructs 100 elements from the given T() argument. (The effect is the same for int, but not for all types.)

Siyuan Ren Over a year ago

is new for primitive types the same as malloc or calloc?

Siyuan Ren Over a year ago

@JamesMcNellis: Now that I have more understanding of the quirks of C++, I find a mistake in your wording. In C++11, std::vector value initialize its contents, not default initialize.

R. Martinho Fernandes · Accepted Answer · 2013-06-27 15:50:59Z

3

printf("%d\n",d[len-1]);//prevent compiler from optimizing away

This line reads from an uninitialised object. Instead of preventing the compiler from optimising things, it gives it leeway to do whatever it wants (i.e. the behaviour of the program is undefined).

Let's pretend we fixed that somehow and the behaviour of the program is now well-defined (maybe we added a line initialising d[len-1]).

std::vector<int> d(len);

This line initialises len objects with the value 0. This other line doesn't:

int *d=new int[len];

The only other line that does results in len objects with the value 0 is this one:

int *d=(int *)calloc(len, sizeof(int));

The only conclusion you can draw from the benchmark related to allocation and deallocation performance is that the benchmark is not fit for drawing conclusions related to allocation and deallocation performance.

edited Jun 27, 2013 at 15:50

answered Jun 27, 2013 at 15:45

R. Martinho Fernandes

236k73 gold badges443 silver badges518 bronze badges

8 Comments

Siyuan Ren Over a year ago

I know it reads from an unitialized memory. But I don't actually need the value (which may be whatever bytes left over). What undefined behavior could it be other than printing out a random value other than zero?

R. Martinho Fernandes Over a year ago

@C.R. who the hell knows. What do you think "undefined" means? It doesn't mean "defined to be whatever bytes were left over". It means "not defined".

yyny Over a year ago

@R.MartinhoFernandes As far as I know, reading from uninitialized memory is not undefined behaviour. Correct me if I'm wrong, but I've always assumed that reading from an uninitialized block in memory is defined to return any value (a random sequence of bits, if you will).

Victor Sergienko Over a year ago

In this one example it's not UB because this variable can not be optimized to be register: stackoverflow.com/q/11962457/207791

R. Martinho Fernandes Over a year ago

@Victor It's UB because the standard says it's UB. The variable can be "optimized to be register" because it's UB. That's what UB means: anything can happen, including the variable "optimized to be register".

|

Collectives™ on Stack Overflow

Why is allocation and deallocation of std::vector slower than dynamic array on my machine

EDIT 1

EDIT 2

2 Answers 2

3 Comments

8 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

EDIT 1

EDIT 2

2 Answers 2

3 Comments

8 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related