Why is std::vector twice as fast as raw array? Complete code included

Question

Results:

Vector time: 7051

Array time: 18944

I used MSVC release mode for this, compiled as 32 bit.

Before this test I was looking at the GCC source code for vector and was surprised because I thought operator[] checked for array-out-of-bounds, but it doesn't. However, I was not expecting the vector to be so fast?!

Complete code:

#include <iostream>
#include <vector>

int main(){
    const int size = 10000;
    unsigned long long my_array[size];
    std::vector<unsigned long long> my_vec;
    
    my_vec.resize(size);

    //Populate containers
    for(int i=0; i<size; i++){
        my_vec[i] = i;
        my_array[i] = i;
    }

    //Initialise test variables
    unsigned long long sum = 0;
    unsigned long long time = 0;
    unsigned long long start = 0;
    unsigned long long finish = 0;

    //Time the vector
    start = __rdtsc();
    for(int i=0; i<size; i++){
        sum += my_vec[i];
    }
    finish = __rdtsc();


    time = finish - start;
    std::cout << "Vector time: " << time << "     " << sum << std::endl;


    sum = 0;

    //Time the array
    start = __rdtsc();
    for(int i=0; i<size; i++){
        sum += my_array[i];
    }
    finish = __rdtsc();

    time = finish - start;
    std::cout << "Array time: " << time << "     " << sum << std::endl;

    int t = 8;
    std::cin >> t;
    return 0;
}

Answer 1

The following is using MSVC 2013.

For the vector:

0019138E  mov         edi,edi  
  for (int i = 0; i<size; i++){
00191390  lea         ecx,[ecx+20h]  
    sum += my_vec[i];
00191393  movdqu      xmm0,xmmword ptr [ecx-20h]  
00191398  paddq       xmm1,xmm0  
0019139C  movdqu      xmm0,xmmword ptr [ecx-10h]  
001913A1  paddq       xmm2,xmm0  
001913A5  dec         esi  
001913A6  jne         main+0F0h (0191390h)  
  }

For the array:

0019142D  lea         ecx,[ecx]  
  for (int i = 0; i<size; i++){
00191430  lea         ecx,[ecx+20h]  
    sum += my_array[i];
00191433  movdqu      xmm0,xmmword ptr [ecx-30h]  
00191438  paddq       xmm1,xmm0  
0019143C  movdqu      xmm0,xmmword ptr [ecx-20h]  
00191441  paddq       xmm2,xmm0  
00191445  dec         esi  
00191446  jne         main+190h (0191430h)  
  }

As you can see, the inner loops are identical. Actually, suspecting it was a hardware thing I swapped the two loops around and arrays came out faster to the same margin (so actually, neither is faster or slower than the other in the real world).

I predict this is some kind of CPU cache behavior: https://en.wikipedia.org/wiki/CPU_cache

Answer 2

We have two arrays of 80,000 bytes each. First, 160,000 bytes are filled with data in parallel. Then 80,000 of these are read, then the other 80,000 are read. Assuming a 128,000 byte cache:

When reading the first 32,000 bytes of vector, the data is not cached. The next 48,000 bytes are cached. Now the cache contains all of vector, and the last 48,000 bytes of array. But the bytes from array are the oldest, so as array is read from the start, the data at the end of it are thrown out. So all reads from array are uncached.

We therefore have 32,000 bytes uncached reads and 48,000 bytes cached reads for vector, vs. 80,000 bytes uncached reads for array.

That's for a cache size of 128,000 bytes. It will be different for other sizes. But then totally different things could happen. Your code could be switched to a different processor while it is running, at which point one processor might have to write the data to main memory, and the other processor reads it. In the other direction, the OS might have just realised that there is some action going on and turning the processor from power saving mode to some turbo mode.

Making a single measurement and drawing conclusions from it takes none of these things into account.