Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

C++ STL: Array vs Vector: Raw element accessing performance

I'm building an interpreter and as I'm aiming for raw speed this time, every clock cycle matters for me in this (raw) case.

Do you have any experience or information what of the both is faster: Vector or Array? All what matters is the speed I can access an element (opcode receiving), I don't care about inserting, allocation, sorting, etc.

I'm going to lean myself out of the window now and say:

  • Arrays are at least a bit faster than vectors in terms of accessing an element i.

It seems really logical for me. With vectors you have all those security and controlling overhead which doesn't exist for arrays.

(Why) Am I wrong?

No, I can't ignore the performance difference - even if it is so small - I have already optimized and minimized every other part of the VM which executes the opcodes :)

like image 705
oh boy Avatar asked Apr 29 '10 19:04

oh boy


People also ask

Which is faster array or vector?

A std::vector can never be faster than an array, as it has (a pointer to the first element of) an array as one of its data members. But the difference in run-time speed is slim and absent in any non-trivial program. One reason for this myth to persist, are examples that compare raw arrays with mis-used std::vectors.

Is it better to use array or vector?

Vector is better for frequent insertion and deletion, whereas Arrays are much better suited for frequent access of elements scenario. Vector occupies much more memory in exchange for managing storage and growing dynamically, whereas Arrays are a memory-efficient data structure.

How much slower are vectors than arrays?

The time difference is 0.333 seconds. Or a difference of 0.000000000333 per array access. Assuming a 2.33 GHz Processor like mine that's 0.7 instruction pipeline stages per array accesses. So the vector looks like it is using one extra instruction per accesses.

Does vector use more memory than array?

Vectors are efficient and flexible. They do require a little more memory than arrays, but this tradeoff is almost always worth the benefits.


2 Answers

Element access time in a typical implementation of a std::vector is the same as element access time in an ordinary array available through a pointer object (i.e. a run-time pointer value)

std::vector<int> v; int *pa; ... v[i]; pa[i];  // Both have the same access time 

However, the access time to an element of an array available as an array object is better than both of the above accesses (equivalent to access through a compile-time pointer value)

int a[100]; ... a[i]; // Faster than both of the above 

For example, a typical read access to an int array available through a run-time pointer value will look as follows in the compiled code on x86 platform

// pa[i] mov ecx, pa // read pointer value from memory mov eax, i mov <result>, dword ptr [ecx + eax * 4] 

Access to vector element will look pretty much the same.

A typical access to a local int array available as an array object will look as follows

// a[i] mov eax, i mov <result>, dword ptr [esp + <offset constant> + eax * 4] 

A typical access to a global int array available as an array object will look as follows

// a[i] mov eax, i mov <result>, dword ptr [<absolute address constant> + eax * 4] 

The difference in performance arises from that extra mov instruction in the first variant, which has to make an extra memory access.

However, the difference is negligible. And it is easily optimized to the point of being exactly the same in multiple-access context (by loading the target address in a register).

So the statement about "arrays being a bit faster" is correct in narrow case when the array is accessible directly through the array object, not through a pointer object. But the practical value of that difference is virtually nothing.

like image 76
AnT Avatar answered Oct 19 '22 18:10

AnT


You may be barking up the wrong tree. Cache misses can be much more important than the number of instructions that get executed.

like image 44
Jive Dadson Avatar answered Oct 19 '22 19:10

Jive Dadson