By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
434,914 Members | 1,123 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 434,914 IT Pros & Developers. It's quick & easy.

STL Vector vs Arrays

P: n/a
Does anyone have a benchmark for the processing overhead of the STL
Vector class, vs a C style array?
I would dearly love to use Vectors, but am paranoid about slowing my
real-time code down. Can anyone reassure?

Sep 20 '05 #1
Share this Question
Share on Google+
17 Replies


P: n/a

Havatcha skrev:
Does anyone have a benchmark for the processing overhead of the STL
Vector class, vs a C style array?
I would dearly love to use Vectors, but am paranoid about slowing my
real-time code down. Can anyone reassure?


Optimally, there should be no overhead and there are several benchmarks
that demonstrate that (look e.g. for an article in C/C++ Users Journal
by Andrew Koenig if I remember correctly). The best demonstration will
be a benchmark on your particular configuration: try that (remember to
turn all optimizations on) and then decide if std::vector is
appropriate for you.

/Peter

Sep 20 '05 #2

P: n/a
Havatcha wrote:
Does anyone have a benchmark for the processing overhead of the STL
Vector class, vs a C style array?
Even if somebody does, how can it help? Do your own.
I would dearly love to use Vectors, but am paranoid about slowing my
real-time code down. Can anyone reassure?


Nobody can reassure. Do your own profiling in _your_ application.
Anybody else's tests are not applicable to _your_particular_ use of the
containers or arrays.

Also, consider two things: (a) vectors internally store (and manipulate)
an array anyway, so do not expect much difference and (b) vector is not
to speed things up, it's for convenience of not caring about reallocating
the array yourself. The speed-up is not in run-time, it's in development-
time.

V
Sep 20 '05 #3

P: n/a
Victor Bazarov wrote:
it's for convenience of not caring about reallocating
the array yourself. The speed-up is not in run-time, it's in development-
time.


You forgot the other big speed-up. It's not only in development-time,
but in debugging-time. You don't worry as much about memory
leaks/invalid pointers/etc...
Sep 20 '05 #4

P: n/a
Havatcha wrote:
Does anyone have a benchmark for the processing overhead of the STL
Vector class, vs a C style array?
I would dearly love to use Vectors, but am paranoid about slowing my
real-time code down. Can anyone reassure?


As an embedded programmer, I use vector regularly. As Stroustrup notes,
there are many problems with arrays in C++
(http://www.research.att.com/~bs/bs_faq2.html#arrays), and the overall
development time of a project can often be reduced by using a smarter
container like vector because it helps reduce programming errors.

As for speed, since all the calls should be inlined in release mode, it
really should have little to no overhead (apart from the additional
allocation time when compared to statically declared arrays), and in
debug mode, you can automatically range checking and so forth without
cluttering your code with #ifdefs.

In any case, run some tests and see what happens. Your worries sound
like you might be prematurely optimizing, which is also a pet peeve of
Guru Sutter (http://www.gotw.ca/publications/mill09.htm):

Beware Premature Optimization

If you're a regular reader of this column, you'll already be familiar
with my regular harangues against premature optimization. The rules
boil down to: "1. Don't optimize early. 2. Don't optimize until you
know that it's needed. 3. Even then, don't optimize until you know what
needed, and where."

By and large, programmers--that includes you and me--are notoriously
bad at guessing the actual space/time performance bottlenecks in their
own code. If you don't have performance profiles or other empirical
evidence to guide you, you can easily spend days optimizing something
that doesn't need optimizing and that won't measurably affect runtime
space or time performance. What's even worse, however, is that when you
don't understand what needs optimizing you may actually end up
pessimizing (degrading your program) by of saving a small cost while
unintentionally incurring a large cost. Once you've run performance
profiles and other tests, and you actually know that a particular
optimization will help you in your particular situation, then it's the
right time to optimize.

By now, you can probably see where I'm going with this: The most
premature optimization of all is an optimization that's enshrined in
the standard. In particular, vector<bool> intentionally favors "less
space" at the expense of "slower speed"--and forces this optimization
choice on all programs. This optimization choice implicitly assumes
that virtually all users of a vector of bools will prefer "less space"
at the expense of "potentially slower speed," that they will be more
space-constrained than performance-constrained, and so on. This is
clearly untrue; on many popular implementations a bool is the same size
as an 8-bit char, and a vector of 1,000 bools consumes about 1K of
memory. Saving that 1K is unimportant in many applications. (Yes,
clearly a 1K space saving is important in some environments, such as
embedded systems, and clearly some applications may manipulate vectors
containing millions of bools where the saved megabytes are real and
significant.) The point is that the correct optimization depends on the
application: If you are writing an application that manipulates a
vector<bool> with 1,000 entries in an inner loop, it is much more
likely that you would benefit from potentially faster raw performance
due to reduced CPU workload (without the overhead of proxy objects and
bit-fiddling) than from the marginal space savings, even if the space
savings would reduce cache misses.

Cheers! --M

Sep 20 '05 #5

P: n/a
Havatcha wrote:
Does anyone have a benchmark for the processing overhead of the STL
Vector class, vs a C style array?
I would dearly love to use Vectors, but am paranoid about slowing my
real-time code down. Can anyone reassure?

I don't have a benchmark, but it shouldn't be difficult to create one
and the following may be of help when creating it.
With optimisation and using the reserve member function to allocate
enough array space for your requirements, the difference is unlikely
to be significant. That's what I did when developing an algorithm, and
reserving enough space first did improve performance. But not as much
as improved algorithm techniques to reduce loop counts. Mostly achieved
by ignoring data no longer relevant.
The other option is to implement a template class for temporary heap
arrays. I did this to allow me to use auto_ptr template and thereby
free up memory correctly when handling exceptions.
As you're probably well aware, declaring large arrays in functions
only uses up stack space, especially when used in recursive functions.

Hope this helps

JFJB
Sep 20 '05 #6

P: n/a
Havatcha wrote:
Does anyone have a benchmark for the processing overhead of the STL
Vector class, vs a C style array?
I would dearly love to use Vectors, but am paranoid about slowing my
real-time code down. Can anyone reassure?


I used to be like you...till I discovered the reserve(n) routine. Assuming
you know how big you want the Vector to be, call this function with that
size. This way you can avoid the darn thing growing on you.

Alvin
Sep 20 '05 #7

P: n/a
red floyd wrote:
Victor Bazarov wrote:
it's for convenience of not caring about reallocating
the array yourself. The speed-up is not in run-time, it's in
development-
time.


You forgot the other big speed-up. It's not only in development-time,
but in debugging-time. You don't worry as much about memory
leaks/invalid pointers/etc...


No, I didn't forget. "Development" for me starts before coding, with
design, etc., and ends at customer ship, _after_ debugging, so, the
"debugging-time" is by definition of the process included into the
"development-time".

V
Sep 20 '05 #8

P: n/a
mlimber wrote:

Beware Premature Optimization

If you're a regular reader of this column, you'll already be familiar
with my regular harangues against premature optimization. The rules
boil down to: "1. Don't optimize early. 2. Don't optimize until you
know that it's needed. 3. Even then, don't optimize until you know what
needed, and where."


Otherwise known as "Hoare's Law" - "Premature Optimization is the root
of all evil". It's also been attributed to Knuth, but I believe Knuth
gave the credit to Hoare.
Sep 20 '05 #9

P: n/a
Havatcha wrote:
Does anyone have a benchmark for the processing overhead of the STL
Vector class, vs a C style array?
I would dearly love to use Vectors, but am paranoid about slowing my
real-time code down. Can anyone reassure?

Hi, if there is many access to your array, obviously you need to use a C
array style. Otherwise a STL Vector is enough fast for common use.
Sep 20 '05 #10

P: n/a
"Kante Mamadou" <ma***********@labri.fr> wrote in message
news:dg**********@news.u-bordeaux1.fr...
Havatcha wrote:
Does anyone have a benchmark for the processing overhead of the STL
Vector class, vs a C style array?
I would dearly love to use Vectors, but am paranoid about slowing my
real-time code down. Can anyone reassure?

Hi, if there is many access to your array, obviously you need to use a C
array style.


Obviously? How is that?

There is no performance difference in accessing the objects of an array vs.
the objects of a vector.

Ali

Sep 20 '05 #11

P: n/a


Ali Çehreli wrote:
"Kante Mamadou" <ma***********@labri.fr> wrote in message
news:dg**********@news.u-bordeaux1.fr...
Havatcha wrote:
Does anyone have a benchmark for the processing overhead of the STL
Vector class, vs a C style array?
I would dearly love to use Vectors, but am paranoid about slowing my
real-time code down. Can anyone reassure?

Hi, if there is many access to your array, obviously you need to use a
C array style.

Obviously? How is that?

There is no performance difference in accessing the objects of an array
vs. the objects of a vector.

Ali

Aha! Well here is the issue. Accessing an object in a array is simply a
case of resolving a pointer, accessing an object in a vector presumably
involves bounds checking and other processes.

Still, having read the follow-ups about 'premature optimisation' it
looks like Vectors are the way forward, and only worrying about using
more primitive structures should the code fail to run fast enough.

Sep 21 '05 #12

P: n/a

Havatcha schreef:
Ali Çehreli wrote:
"Kante Mamadou" <ma***********@labri.fr> wrote in message
news:dg**********@news.u-bordeaux1.fr...
Havatcha wrote:

Does anyone have a benchmark for the processing overhead of the STL
Vector class, vs a C style array?
I would dearly love to use Vectors, but am paranoid about slowing my
real-time code down. Can anyone reassure?

Hi, if there is many access to your array, obviously you need to use a
C array style.

Obviously? How is that?

There is no performance difference in accessing the objects of an array
vs. the objects of a vector.

Ali


Aha! Well here is the issue. Accessing an object in a array is simply a
case of resolving a pointer, accessing an object in a vector presumably
involves bounds checking and other processes.


No, it doesn't - at least when you use the same syntax [index]. vector
has an additional slower method .at(index) which does check. Of course,
for debug builds even an C array might be bounds checked so don't
compare
those.

The only exception is the infamous vector<bool> which isn't a vector of
bools but a vector of bits. The bitmasking and shifting might make it
slower, but the reduced memory use (in cache, RAM and/or swap) compared
to bool[] might compensate for that.

HTH,
Michiel Salters

Sep 21 '05 #13

P: n/a
Havatcha wrote:

Ali Çehreli wrote:
"Kante Mamadou" <ma***********@labri.fr> wrote in message
news:dg**********@news.u-bordeaux1.fr...
Havatcha wrote:

Does anyone have a benchmark for the processing overhead of the STL
Vector class, vs a C style array?
I would dearly love to use Vectors, but am paranoid about slowing my
real-time code down. Can anyone reassure?

Hi, if there is many access to your array, obviously you need to use a
C array style.

Obviously? How is that?

There is no performance difference in accessing the objects of an array
vs. the objects of a vector.

Ali


Aha! Well here is the issue. Accessing an object in a array is simply a
case of resolving a pointer, accessing an object in a vector presumably
involves bounds checking and other processes.


Uhm, no.
In all known implementations, both, accessing an array dynamically allocated
with new[] and accessing an element from a vector by an ordinary index
operation, yields to exactly the same code. That is: If the optimizer is
allowed to do its work.

--
Karl Heinz Buchegger
kb******@gascad.at
Sep 21 '05 #14

P: n/a
On 2005-09-21 06:52:39 -0400, Havatcha <no****@for.me> said:


Ali Çehreli wrote:
"Kante Mamadou" <ma***********@labri.fr> wrote in message
news:dg**********@news.u-bordeaux1.fr...
Havatcha wrote:

Does anyone have a benchmark for the processing overhead of the STL
Vector class, vs a C style array?
I would dearly love to use Vectors, but am paranoid about slowing my
real-time code down. Can anyone reassure?

Hi, if there is many access to your array, obviously you need to use a
C array style.

Obviously? How is that?

There is no performance difference in accessing the objects of an array
vs. the objects of a vector.

Ali

Aha! Well here is the issue. Accessing an object in a array is simply a
case of resolving a pointer, accessing an object in a vector presumably
involves bounds checking and other processes.


You presume incorrectly. Every implementation of operator[] on
std::vector that I've seen follows one of the following basic forms:

reference operator[](size_type index)
{
return some_pointer[index];
}

reference operator[](size_type index)
{
return *(some_pointer+index);
}

reference operator[](size_type index)
{
return *(begin()+index);
}

Which, any decent compiler will optimize down to the exact same code as
accessing an object in a simple C-style array.
--
Clark S. Cox, III
cl*******@gmail.com

Sep 21 '05 #15

P: n/a
Clark S. Cox III wrote:
On 2005-09-21 06:52:39 -0400, Havatcha <no****@for.me> said:
Aha! Well here is the issue. Accessing an object in a array is simply a
case of resolving a pointer, accessing an object in a vector presumably
involves bounds checking and other processes.


You presume incorrectly. Every implementation of operator[] on
std::vector that I've seen follows one of the following basic forms:

reference operator[](size_type index)
{
return some_pointer[index];
}

reference operator[](size_type index)
{
return *(some_pointer+index);
}

reference operator[](size_type index)
{
return *(begin()+index);
}

Which, any decent compiler will optimize down to the exact same code as
accessing an object in a simple C-style array.


That's correct for release mode, but there are checked STL
implementations that do range checking in debug mode. See Tip #83 in
_C++ Coding Standards_ (available free as a sample chapter here:
http://www.informit.com/articles/art...p=373341&rl=1).

To get range checking in release mode, use vector<>::at() instead of
vector<>::operator[](). See also the Guru of the Week question #74:
"Uses and Abuses of Vector" (http://www.gotw.ca/gotw/074.htm).

Cheers! --M

Sep 21 '05 #16

P: n/a
You presume incorrectly. Every implementation of operator[] on
std::vector that I've seen follows one of the following basic forms:

reference operator[](size_type index)
{
return some_pointer[index];
}

reference operator[](size_type index)
{
return *(some_pointer+index);
}

reference operator[](size_type index)
{
return *(begin()+index);
}

Which, any decent compiler will optimize down to the exact same code as
accessing an object in a simple C-style array.
Well Vectors it is then.


Sep 21 '05 #17

P: n/a
All STL container<T>s use by default std::allocator<T> for allocation /
deallocation, which in turn by default uses operator new[], which on most
systems calls malloc.

A static C-style array is stack-allocated.

You can write your own allocator to boost vector performance. Otherwise,
boost::array is not too bad an idea.

Ben
Sep 22 '05 #18

This discussion thread is closed

Replies have been disabled for this discussion.