Why Maintaining Sorted Array is faster than Vector in C++

Question

I am creating an array and vector of size 100 and generating a random value and trying to maintain both array and vector as sorted. Here is my code for the same

vector<int> myVector;
int arr[SIZE];
clock_t start, finish;
int random;
for(int i=0; i<SIZE;i++)
{
    myVector.push_back(0);
    arr[i] = 0;
}
    //testing for Array
start = clock(); 
for(int i=0; i<MAX;++i)
{
    random = getRandom(); //returns rand() % 100
    for(int j=0; j<SIZE;++j){
        if(random > arr[j])
        {
            for(int k = SIZE - 1; k > j ; --k)
            {
                arr[k] = arr[k-1];
            }
            arr[j] = random;
            break;
        }
    }
}
finish = clock();
cout << "Array Time " << finish - start << endl;

//Vector Processing
start = clock();
for(int i=0; i<MAX;++i)
{
    random = getRandom(); //returns rand() % 100
    for(int j=0; j<SIZE;++j){
        if(random > myVector[j])
        {
            for(int k = SIZE - 1; k > j ; --k)
            {
                myVector[k] = myVector[k-1];
            }
            myVector[j] = random;
            break;
        }
    }
}
finish = clock();
cout << "Vector Time " << finish - start << endl;

The output is as follows:

Array Time : 5

Vector Time: 83

I am not able to understand why vector is so slow compared to array in this case? Doesn't this contradict the thumb-rule of preferring Vector over Array.

Please Help !

What optimizations do you have on? With an optimizing compiler, the results should be nearly identical. — Chad, Jul 03 '13 at 15:15
The vector has to grow in size to match your 100 elements, I am not sure about the implementation details, but vector *might* (probably) isn't stored contiguously in memory. — Hunter McMillen, Jul 03 '13 at 15:15
Also, `std::sort` instead of whatever it is you are using... — Chad, Jul 03 '13 at 15:16
If you need to maintain a sorted container, why are you using either? Use something like `std::multiset` that keeps itself sorted. — chris, Jul 03 '13 at 15:17
I would suggest that if you are going to compare the performance you compile with maximum optimizations and with release libraries (some implementations provide different containers for debugging and production). Also for a more reliable comparison, you should generate all of the random numbers upfront (store them in an array/vector, the same for both runs) and run them in both containers (so that the sequence of operations is the same in both cases) — David Rodríguez - dribeas, Jul 03 '13 at 15:34
@DavidRodríguez-dribeas, Well, I meant for you needing it to keep it sorted when adding new elements and such, but I'd love to hear if there's a better choice for that or if it's something else, such as never inserting or removing anything, or rarely sorting it before use that you're referring to. — chris, Jul 03 '13 at 15:35
It seems GCC is basically optimizing the whole thing away because it realizes you don't use the result. Try adding a `cout << arr[0] << endl;` after processing the array. Compare [this](http://coliru.stacked-crooked.com/view?id=df1c34e40566b9b43b5c78027fe8f60b-70854cb7d61c5b883318b4d11e427bb9) (without `cout`) and [this](http://coliru.stacked-crooked.com/view?id=566f660be9113cae2d8e94a9d7c7f2e9-70854cb7d61c5b883318b4d11e427bb9) (with `cout`) — Andy Prowl, Jul 03 '13 at 15:36
Since the size is known upfront, you can call reserve on the vector. This would make the vector more performant, because each time the internal array in the vector is too small it is reallocated completely with a bigger size, followed with a memcopy. — Philip Stuyck, Jul 03 '13 at 16:44
@PhilipStuyck: Rather than that, the initialization loop could be dropped altogether if the size is given to the constructor: `std::vector v(SIZE);` can substitute the `for(...) { v.push_back(0); }` loop — David Rodríguez - dribeas, Jul 03 '13 at 16:57

Arne Mertz · Accepted Answer · 2013-07-03T16:00:44.940

First of all: Many rules of thumb in programming are not about ganing some milliseconds in performance, but about managing complexity, therefore avoiding bugs. In this case, it's about performing range checks wich most vector implementations do in debug mode, and wich arrays don't. It's also about memory management for dynamic arrays - vector does manage it's memory itself, while you have to do it manually in arrays at the risk of introducing memory leaks (ever forgot a delete[] or used delete instead? I be you have!). And it's about ease of use, e.g. resizing the vector or inserting element in the middle, wich is tedious work with manually managed arrays.
In other words, performance measurements can never ever contradict a rule of thumb, because a rule of thumb never targets performance. Performance measurements can only be one of the few possible reasons to not obey a coding guideline.

At first sight I'd guess you have not enabled optimizations. The main source of performance loss for the vector would then be index checks that many vector implementations have enabled for debug builds. Those won't kick in in optimized builds, so that should be your first concern. Rule of thumb: performance measurements without optimizations enabled are meaningless

If enabling optimizations still does show a better performance for the array, there's another difference:

The array is stored on the stack, so the compiler can directly use the adrresses and calculate address offsets at compiletime, while the vector elements are stored on the heap and the compiler will have to dereference the pointer stored in the vector. I'd expect the optimizer to dereference the pointer once and calculate the address offsets from that point on. Still, there might be a small performance penalty compared to compiletime-calculated address offsets, especially if the optimizer can unroll the loop a bit. This still does not contradict the rule of thumb, because you are comparing apples with pears here. The rule of thumb says,

Prefer std::vector over dynamic arrays, and prefer std::array over fixed arrays.

So either use a dynamically allocated array (including some kind of delete[], please) or compare the fixed size array to a std::array. In C++14, you'll have to consider new candidates in the game, namely std::dynarray and C++14 VLAs, non-resizable, runtime length arrays comparable to C's VLAs.

Update: As was pointed out in the comments, optimizers are good at identifying code that has no side effects, like the operations on the array that you never read from. std::vector implementations are complicated enough that optimizers typically won't see through those several layers of indirection and optimize away all the insert, so you'll get zero time for the array compared to some time for the vector. Reading the array contens after the loop will disable such rude optimizations.

Heap/stack should not make a difference, at least not one order of magnitude difference. This looks more like a debug library vs. a raw array — David Rodríguez - dribeas, Jul 03 '13 at 15:36
@DavidRodríguez-dribeas: I believe this is more like the compiler optimizing away a whole bunch of stuff under the as-if rule. Adding a `cout << arr[0]` after processing the array makes the processing times comparable — Andy Prowl, Jul 03 '13 at 15:43
@chris thanks for the hint. Looking it up I found that they are VLAs but not exaclty like in C: http://lists.cs.uiuc.edu/pipermail/cfe-commits/Week-of-Mon-20130415/078422.html — Arne Mertz, Jul 03 '13 at 15:44
If I set the Optimization level -O and -O1 then both vector and array take same time however in case of -O2 array again becomes faster. Any idea what causes the difference — bhavesh, Jul 03 '13 at 15:45
One more comment. Not sure if it can be relevant, but it is very likely that vector will allocate much more memory than needed attempting to give even more space for `push_back` calls. — alexrider, Jul 03 '13 at 15:47
@alexrider no, that's not relevant, because the `push_back` and resizing happens outside the measured loops. — Arne Mertz, Jul 03 '13 at 16:01
@bhavesh did you compare vector with dynamically allocated arrays this time, including a read operation on the array after the measurement? In that case I'd ask you to start a new question and post the exact code you have, including times and platform information (OS, compiler), because then the differences would be much more subtle than the ones at hand here. — Arne Mertz, Jul 03 '13 at 16:04
@ArneMertz My note not about resize cost, but about vector's capacity() that will be bigger than sizeof of array. — alexrider, Jul 03 '13 at 16:05
@alexrider once it's allocated, the capacity of the vector plays no role in the read/write accesses. In fact, in optimized builds `myVector[10000]` will happily access the memory equally fast regardless wether the vector's capacity is 10000, 1000000 or 10. It's internally just dereferencing a single pointer. (and yes, you might get an access violation if `capacity() == 10`) — Arne Mertz, Jul 03 '13 at 16:08

score -1 · Answer 2 · answered Jul 03 '13 at 15:42

-1

The vector class has to dynamically grow the memory, that may involve copying the whole thing from time to time. Also it has to call internal functions for many operations - like reallocating. Also it may have security functionality like boundary checks.

Meanwhile your array is preallocated and all your operations propably do not call any internal functions.

That is the overhead price for more functionality.

And who said that vectors should be faster than arrays in all cases? Your array does not need to grow, thats a special case where arrays are indeed faster!

answered Jul 03 '13 at 15:42

Ole Dittmann

1,764
1
14
22

vector doesn't need to grow during computations. It will grow only during initial push_back usage. – alexrider Jul 03 '13 at 15:43
Ok, right, did not see that the vector gets initially filled up. Then my tip would be the boundary checks and internal function calls – Ole Dittmann Jul 03 '13 at 15:45

score -3 · Answer 3 · edited May 23 '17 at 12:30

-3

Because arrays are native data types, whereas the compiler can manipulate it directly from memory, they are managed internally by the compiled exec.

On the other hand, you get vector that is more like a class, template as I read, and it needs some management going through another header files and libraries.

Essentially native data type can be managed withouth including any headers, which make them easier to manipulate from the program, without having to use external code. Which makes the overhead on the vector time is the need for the program to look through the code and use the methods related to vector data type.

Every time you need to add more code to your app and operate from it, it will make your app performance to drop

You can read about it, here, here and here

edited May 23 '17 at 12:30

Community

1
1

answered Jul 03 '13 at 15:24

Raziel Ravenheart

44
5

It's been pretty proven that vectors can be just as fast as arrays. Your links only reinforce that. Of course in this case, we're comparing something with dynamically allocated memory to stack-allocated memory. – chris Jul 03 '13 at 15:30
Not really. In an optimized build, and with anything else being equal a vector should have exactly the same performance as an array. The language and library was specifically designed for this – David Rodríguez - dribeas Jul 03 '13 at 15:31
The need to use the stack will always add overhead, making it slower to use. You can't say it is as fast as arrays, because it will never be, since the arrays are native data types dinamically allocable, use discouraged as it is, but nevertheless faster. – Raziel Ravenheart Jul 03 '13 at 15:40
Number of included headers does not affect program performance. C++ is not an interpreted language. Adding more code will not drop performance either. – SigTerm Jul 03 '13 at 15:41
@SigTerm Yes, you are right, I went a lot down the road, but the need to use it will add overhead, no the single action of including it, but using it. – Raziel Ravenheart Jul 03 '13 at 15:43
@RazielRavenheart A dynamically allocated array *also* needs to use the stack, to store the pointer itself. You also need to store its size somewhere. And the fact that arrays are somehow “native” is *completely* irrelevant. – Konrad Rudolph Jul 03 '13 at 15:58

Why Maintaining Sorted Array is faster than Vector in C++

3 Answers3