Re: Vectors vs Arrays performance
On Jan 2, 9:46 pm, "Leigh Johnston" <le...@i42.co.uk> wrote:
OK, to be absolutely clear when using operator[] std::vector
has an *extra* dereference in addition to the actual deference
to get an element's value compared to an array *on the stack*
accessed *locally within the same scope* (not via a
pointer/reference to it). Clear now?
It's clear that you're claiming something that is in general
false.
Consider first the simple case:
int
main()
{
int a1[10];
for ( int i = 0 ; i < 10; ++ i ) {
a1[ i ] = i;
}
int* a2 = new int[ 10 ];
for ( int i = 0 ; i < 10; ++ i ) {
a2[ i ] = i;
}
// additional code which uses the arrays, to ensure
// that the compiler doesn't optimize them out.
}
Any decent compiler should generate exactly the same code for both
loops.
The second loop, of course, basically corresponds to what goes
on under the hood in std::vector, at least with regards to the
indexing. The main difference is that all of the operations in
std::vector are, in fact, function calls. Which, depending on
the compiler, may make recognizing the pattern more difficult.
[...]
As you can see from the assembler output between the
breakpoints the array [] access involves one less instruction
than the vector operator[].
In one particular case, on one particular machine, with one
particular compiler. It's certainly not a general case. And
it's not a realistic case because of the volatile and the inline
assembler (both of which affect compiler optimization
significantly).
A std::vector object contains a pointer to the controlled
sequence, not the case for an array on the stack accessed
locally from the same scope.
Both require the compiler to access through a pointer. Both
require some sort of pointer arithmetic. Beyond that, anything
you can say depends on the compiler and the machine hardware.
And the environment in which the array access occurs, which
affects how the compiler optimizes.
As mentioned in my original reply this extra instruction does
not count significantly to the timing differences observed so
other causes have to be considered (debug instead of release
build, optimizations turned off, extra bounds checking etc.)
Exactly. Other considerations which generally mean that there
won't be an extra instruction.
Aside: most sane implementations will inline std::vector<T>::operator[].
I think all do:-). On the other hand, depending on optimization
levels and other compiler options, the compiler may or may not
respect the request to inline. (Without optimization, I don't
think g++ ever inlines. But I could be wrong about that.)
--
James Kanze