Slowness of Vectors

Pages: 12
Dufresne (137)
Hi all ,
I realized that , declaring and filling a 2D vector cost much more time than declaring filling a 2D arrays.
I tried to allocate and fill a 500x700 array and a 500x700 vector.
Allocating , filling( randomly) and sorting of array took about 46 miliseconds while same process took 438 miliseconds with vector.

http://www.cplusplus.com/reference/stl/vector/
says
Vector containers are implemented as dynamic arrays


So what's the main reason of this slowness?
Albatross (4553)
How are you filling your vectors? Using push_back()? If so, then of course it's going to be slower, as the vector needs to be resized each time you use it.

-Albatross
foyuliu (8)
Albatross is right, the slowness is caused by resize. but a little correction, the vector is not resized each time push_back(), it will reallocate double of current size when find that current size is not available to hold the data.

You can use vector::reserve() to explicitly indicate a capacity, so you avoid reallocations and should get good performance.

http://www.cplusplus.com/reference/stl/vector/
Reallocations may be a costly operation in terms of performance, since they generally involve the entire storage space used by the vector to be copied to a new location. Therefore, whenever large increases in size are planned for a vector, it is recommended to explicitly indicate a capacity for the vector using member function vector::reserve.
sysabod (88)
agreed .

When using the 2D array,the memory is allocated right the time you declared it ，that is compile time, but vector fashion is dynamic , which means costly due to the repeated memory allocation
helios (17607)
Also, stack (n>1)D arrays are just 1D arrays for which the compiler performs a little magic to resolve indexing. These two codes are equivalent:
1
2
3
4
5
6
7
 
//A:
T array[5][6];
array[i][j]=0;

//B:
T array[5*6];
array[i*6+j]=0; //It was either this, or i+j*5. I always forget.

If, instead of declaring a vector as std::vector<std::vector<T> > v, you declared it as std::vector<T> v and performed the indexing yourself, it would be much, much faster.
ankitsingh12 (22)
try using the reserve() function...it will be much faster
Dufresne (137)
I directly assign values to vector array , not using push_back. And before filling vector , i declare size of vector via resize member function of vector.
This is the code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
 
void arrayFun()
{
    clock_t now = clock();
    int i,j;
    int **numbers = new int*[ROW];
    
    for( i = 0 ; i < ROW  ; i++)
         numbers[i] = new int[COLUMN];
    
    for( i = 0 ; i < ROW ; i++)
         for( j= 0 ; j < COLUMN ; j++)
              numbers[i][j] = rand();
             
            
    for( i = 0 ; i < ROW ; i++)
        sort( numbers[i] , numbers[i]+COLUMN);                 
    clock_t then = clock();
    cout << "Total time for array " << difftime(then,now) << " msec." << endl;
    for( i = 0 ; i < ROW ; i++)
         delete numbers[i];
    delete []numbers;    
}
void vectorFun()
{
     clock_t now = clock();
     vector< vector<int> > numbers;
     int i,j;
     numbers.resize(ROW);
     for( i = 0 ; i < ROW ; i++)
          numbers.at(i).resize(COLUMN);
     for( i = 0 ; i< ROW ; i++)
          for( j = 0 ; j < COLUMN ; j++)
               numbers.at(i).at(j) = rand();
               
     for( i = 0 ; i< ROW ; i++)
          sort(numbers.at(i).begin() , numbers.at(i).end());
     clock_t then = clock();
     cout << "Total time for vector " << difftime(then,now) << " msec." << endl;    
}

I don't know why , but using reserve instead of resize gives run-time error.
I guess in the function vectorFun, there's no reallocation.
And result is about 8 or 9 times slower.

Helios, when i changed code as you suggested.I didn't decrease time.
I changed it as the following.
1
2
3
4
5
6
7
8
9
10
11
12
 
   clock_t now = clock();

     vector<int> numbers ;
     int i ,j ;
     numbers.resize( ROW * COLUMN );
     
     for( i = 0 ; i< ROW ; i++ )
          for( j = 0 ; j < COLUMN ; j++)
               numbers.at(i*COLUMN+j) = rand();
     sort( numbers.begin() , numbers.end());
     clock_t then = clock();
     cout << "Total time for vector " << difftime(then,now) << " msec." << endl;
Last edited on
helios (17607)
I don't know why , but using reserve instead of resize gives run-time error.
std::vector::reserve() only makes sure that the physical internal vector is at least as big as the value passed. That is, it increases capacity (if necessary), but it doesn't change the size. Also, it doesn't call constructors.

Don't use std::vector::at(). It performs bounds checking that may take an unnecessary toll on performance if you don't really need it. Use std::vector::operator[]().
Incubbus (678)
I have to forestall, that I am not an expert in this issues, but:

1. The call to numbers.resize() is also more slow than int **numbers = new int*[ROW];

2. The at()-func and the []-operator are also slower than an common array´s indexing via []

EDIT: 5% are 5%^^...

3. I would suggest to declare your clock_ts´ before you start counting, because the decalaration takes time, too... EDIT:fail... stack^^...
4. Maybe High Resolution Counters would give back an more precise result ( this is no "run time" improvement of your heuristic)...
Last edited on
helios (17607)
1. You're comparing apples and oranges. The two have entirely different semantics.
2. std::vector::operator[]() is only slightly slower than offset. IIRC, the last time I measured it, it was just 5% slower.
3. Ugh. No. No, it doesn't.
Dufresne (137)
Using operator[] instead of using at() function , a bit decreased slowness.
No reallocation , no bound checking , still x5 times slower.
helios (17607)
A 500% increase seems a bit too much. Could you post the two codes you're comparing?
Dufresne (137)
This is entire code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
 
#include <iostream>
#include <vector>
#include <list>
#include <ctime>
#include <cstdlib>
#include <algorithm>

#define ROW      500
#define COLUMN   700

using namespace std ;

void listFun()
{
     clock_t now = clock();
     list< list<int> > numbers;
     int i,j;
     numbers.resize(ROW);
     
     for( list< list<int> >::iterator it = numbers.begin(); it != numbers.end(); it++)
          it->resize(COLUMN);
          
     for( list< list<int> >::iterator it = numbers.begin(); it != numbers.end(); it++)
          for( i = 0 ; i < COLUMN ; i++)
          {
               int randnum = rand();
               it->push_back(randnum);
          }
     for( list< list<int> >::iterator it = numbers.begin() ; it != numbers.end() ; it++)
          it->sort();
     clock_t then = clock();
     cout << "Total time for list " << difftime(then,now) << " msec." << endl;    
}
void arrayFun()
{
    clock_t now = clock();
    int i,j;
    int **numbers = new int*[ROW];
    
    for( i = 0 ; i < ROW  ; i++)
         numbers[i] = new int[COLUMN];
    
    for( i = 0 ; i < ROW ; i++)
         for( j= 0 ; j < COLUMN ; j++)
              numbers[i][j] = rand();
             
            
    for( i = 0 ; i < ROW ; i++)
        sort( numbers[i] , numbers[i]+COLUMN);                 
    clock_t then = clock();
    cout << "Total time for array " << difftime(then,now) << " msec." << endl;
    for( i = 0 ; i < ROW ; i++)
         delete numbers[i];
    delete []numbers;    
}

void vectorFun()
{
          clock_t now = clock();
/*
     vector< vector<int> > numbers;
     int i,j;
     numbers.resize(ROW);
     for( i = 0 ; i < ROW ; i++)
          numbers.at(i).resize(COLUMN);

     for( i = 0 ; i< ROW ; i++)
          for( j = 0 ; j < COLUMN ; j++)
               numbers[i][j] = rand();     
     for( i = 0 ; i< ROW ; i++)
          sort(numbers.at(i).begin() , numbers.at(i).end());
     */       
     vector<int> numbers ;
     int i ,j ;
     numbers.resize( ROW * COLUMN );
     
     for( i = 0 ; i< ROW ; i++ )
          for( j = 0 ; j < COLUMN ; j++)
               numbers[i*COLUMN+j] = rand();

     for( i = 0 ; i < ROW ; i++)
          sort( numbers.begin()+COLUMN*i, numbers.begin()+COLUMN*(i+1));
     
     clock_t then = clock();
     cout << "Total time for vector " << difftime(then,now) << " msec." << endl;    
}
int main(void)
{
    srand(time(NULL));
    arrayFun();
    vectorFun();
    listFun();
    getchar();
    return ( 0 );
}
Last edited on
helios (17607)
If you use optimizations, the difference decreases to a 50% disadvantage for vector. That's as low as it gets, I think.
foyuliu (8)
One difference is that in sort:
- for list or array you are sorting ROW groups of data (length of COLUMN) separately,
- but for vector you are sorting ROW*COLUMN data together
if separate the sort of vector into ROW groups, vector's performance is about 3 times array's.

And BTW, you should compare the performance into several parts, e.g. memory allocate, assign, sort. to get a clear view of which piece of code leads to the difference.
helios (17607)
if separate the sort of vector into ROW groups, vector's performance is about 3 times array's.
Huh. You're right. I don't know how I missed that.
Average sorting time for vector:
log(500*700)*500*700 ~= 1940423.8
For array:
500*(log(700)*700) ~= 995784.3
Sorting the vector is taking about twice as long on average.
moorecm (1932)
You can pass a size to the constructor of the vector rather than explicitly calling resize after it is constructed, too. The sorting portion could also be quite different rather than blaming just the vector vs. list vs. array.
foyuliu (8)
And I think to do the comparison we should base on the same dataset, so far sort is the most time consuming compute, and sort on different dataset may need different time consume.
So, please try initialize the test dataset first and then assign them to array, list and vector, make sure we are testing on the same data.

BTW, using -O3, the most optimization option, the time is almost equal between vector and array, and sometimes vector is even faster~.

List is always the slowest, and much slower...
Dufresne (137)
- for list or array you are sorting ROW groups of data (length of COLUMN) separately,
- but for vector you are sorting ROW*COLUMN data together

You're right ,i fixed it, but it isn't the main reason of slowness here. Performance is still about 5 times of array .



Last edited on
foyuliu (8)
This is weird~, with my test, the result is about 2-3 times of array, although it changes every time.
And it's almost the same if using -O2 or -O3, i am using g++ to compile.
Pages: 12