Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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.

like image 214
Siyuan Ren Avatar asked Mar 24 '23 09:03

Siyuan Ren


1 Answers

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()
like image 191
JoeD Avatar answered Apr 23 '23 15:04

JoeD