Arrays vs. vectors - performance

[Dave Theese]

Hello all,

I'm in a poition of trying to justify use of the STL from a performance
perspective. As a starting point, can anyone cite any benchmarks comparing
vectors to plain old statically-declared arrays? I'll also be looking at
the other STL containers later...

Also, I'd appreciate any comments anyone has on the suitability of the
little program below for comparing vectors and arrays. One obvious
shortcoming is that it uses array / vector indexing operations only as
lvalues, not as rvalues...

With VC++ 6.0 on a 1 GHz machine, this program produced the following
interesting results:

Release mode
---------------
Array: 109 seconds
Vector: 109 seconds

Debug mode
-------------
Array: 141 seconds
Vector: 1657 seconds

In debug mode, use of vectors is *not* justified, from a performance
perspective, by a factor of 11.75!

The identical release mode results are, I suppose, not surprising.

I'd love to hear people's thoughts or references to benchmarks more
scientific and appropriate than this little test!

Thanks,
Dave

#include <iostream>
#include <ctime>
#include <vector>

using namespace std;

namespace
{
const int NUM_ELEMENTS = 100000;
const int NUM_ITERS = 100000;
};

int main()
{
int a[NUM_ELEMENTS];
time_t finish;
int i;
int j;
int k = NUM_ELEMENTS / 2; // An arbitrary element to look up
time_t start;
vector<int> v(NUM_ELEMENTS);

// Test the array
start = time(NULL);

for (i = 0; i != NUM_ITERS; ++i)
{
for (j = 0; j != NUM_ELEMENTS; ++j)
a[j] = i + j;
}

// Try to inhibit any optimizations of the above loops.
++k;
cout << a[k] << endl;

finish = time(NULL);
cout << "Array implementation: " << difftime(finish, start) << endl;

// Test the vector
start = time(NULL);

for (i = 0; i != NUM_ITERS; ++i)
{
for (j = 0; j != NUM_ELEMENTS; ++j)
v[j] = i + j;
}

// Try to inhibit any optimizations of the above loops.
++k;
cout << v[k] << endl;

finish = time(NULL);
cout << "vector implementation: " << difftime(finish, start) << endl;

return 0;
}

 

[Victor Bazarov]

I'm in a poition of trying to justify use of the STL from a performance
perspective. As a starting point, can anyone cite any benchmarks comparing
vectors to plain old statically-declared arrays? I'll also be looking at
the other STL containers later... [...]

(a) Containers are NOT intended to outperform arrays. They have totally
different task altogether. They (just like many other things wrapped
in their own libraries) are designed to simplify development. That's
their primary designation. While they do have performance requirements
imposed on them in the C++ Standard, different implementations of the
standard library can display different results when it comes to some
kind of "performance testing".

(b) Small programs are NOT by any stretch of common sense a valid measure
for performance of something versus something in your _final_ product.
Comparing performances of different language constructs without the
rest of the system is blazing nonsense. Which brings on these two
recommendations:

(c) Do not optimise something whose speed you don't know. (And you can't
know until you have the entire system ready)

(d) Do not optimise something that although known as slow does not get
executed enough time to affect the overall performance of the system.
(again, you can't know that before you have the entire system)

If those things do not convince you to give up your attempts to find out
why and by how much containers are slower than arrays, use www.google.com
to search for whatever performance testing has already been done.

Victor

 

[Gianni Mariani]

Hello all,

I'm in a poition of trying to justify use of the STL from a performance
perspective. As a starting point, can anyone cite any benchmarks comparing
vectors to plain old statically-declared arrays? I'll also be looking at
the other STL containers later...

HOLD IT.

I think I'm a performance freak and even I don't concern myself about
this issue unless I known I have a performance problem.

What are the requirements ?

Do you know that your application is performance constained ?

If you've been asked to go figure it out without constraints you've been
duped. I suggest you make some up that you know are good enough and you
and use the rule - lies, damn lies and statistics to prove whatever you
want.

Also, I'd appreciate any comments anyone has on the suitability of the
little program below for comparing vectors and arrays.

Your code tests accessing vector elements. It does not test object
creation and destruction or resizing, passing or other things that may
possibly be more of a constraint on your code.

Vector is a great general purpose tool. However, you can define more
specialized versions that will run considerably faster in *SOME* cases.
Again, it depends on the usage pattern in your application.

Come to think of it. Here is a technique you can use. Create a copy
(or a branch) of the codebase you currently have, run through the entire
code base and implement the vector version. You'll be surprised how
quickly you could do this. Maybe you can pick a library if it's a
really huge codebase. Then run a test on the real code. If you see more
than a 10% performance hit I'll be surprised, unless it's a very complex
app that creates and destoys vectors all over the place.

One obvious

shortcoming is that it uses array / vector indexing operations only as
lvalues, not as rvalues...

Likely not significant.

With VC++ 6.0 on a 1 GHz machine, this program produced the following
interesting results:

Release mode
---------------
Array: 109 seconds
Vector: 109 seconds

Debug mode
-------------
Array: 141 seconds
Vector: 1657 seconds

In debug mode, use of vectors is *not* justified, from a performance
perspective, by a factor of 11.75!

But why do you care about debug performance ?

The identical release mode results are, I suppose, not surprising.

I'd love to hear people's thoughts or references to benchmarks more
scientific and appropriate than this little test!

If you have a heavy numerical library, there has been significant
developments. Look up C++ matrix libraries under google.

 

[Oliver S.]

Release mode

---------------
Array: 109 seconds
Vector: 109 seconds

Debug mode

Forget measuring the performance of debugging-code but incorporate
the times when the vector's capacity is about to change.

 

[Alex Vinokur]

Also, I'd appreciate any comments anyone has on the suitability of the
little program below for comparing vectors and arrays.

[snip]

Look at
http://groups.google.com/[email protected]
http://groups.google.com/[email protected]

Also
http://groups.google.com/[email protected]


=====================================
Alex Vinokur
mailto:[email protected]
http://mathforum.org/library/view/10978.html
=====================================

 

[SaltPeter]

Hello all,

I'm in a poition of trying to justify use of the STL from a performance
perspective. As a starting point, can anyone cite any benchmarks comparing
vectors to plain old statically-declared arrays? I'll also be looking at
the other STL containers later...

An array is not a container, it doesn't have the option of using iterators
and it doesn't resize itself or grow in the background while your
application runs. If an array needs to grow, you need to:

a) generate a new larger array,
b) copy the contents from the old array,
c) copy the contents of the added data into the new array,
d) and possibly delete the old array from the heap.

or

e) use a vector and push_back. Done!

And it's initial size can even be set by a member function that you never
needed to define called reserve().

If what you need is an array, use an array. If what you need is an STL
container like a vector, the array is no match. Let's face it, do you know
excatly how small or big an array you'll need?
While a vector can only grow from the top, it can sort, pushback and even
insert objects anywhere because of iterators. Try doing that with an array.
Your vector is too small? Forget it, it grows by itself.

A deque, for example, can grow in both directions, iterate through objects
with the ++ operator, can sort, insert, pop low, pop high and push because
of iterators. A deque is a Double Ended QUEue container. The indiscutable
advantage is that, except for minor differences, once you learn how to
iterate through a vector, you have all the tools required to manage a deque,
or list, stack, queue, or priority_queue and you didn't do anything except
#include the container.

Also, I'd appreciate any comments anyone has on the suitability of the
little program below for comparing vectors and arrays. One obvious
shortcoming is that it uses array / vector indexing operations only as
lvalues, not as rvalues...

In other words, it's not so much that a vector is slower or faster than an
array when what you need is to manage a dynamically resizeable container's
objects or sequence. It's the cost of recreating the same behaviour with an
array that matters here. And once you have a working relationship with a
vector, using the other STL containers costs you little in programming time
because of standard behaviours all the STL containers abide by.

The cost of programming is infinitely more important than a few nanoseconds
a released executable will loose or gain. The STL containers are "free",
thoroughly tested reusable source code.

With VC++ 6.0 on a 1 GHz machine, this program produced the following
interesting results:

Release mode
---------------
Array: 109 seconds
Vector: 109 seconds

Debug mode
-------------
Array: 141 seconds
Vector: 1657 seconds

In debug mode, use of vectors is *not* justified, from a performance
perspective, by a factor of 11.75!

The identical release mode results are, I suppose, not surprising.

I'd love to hear people's thoughts or references to benchmarks more
scientific and appropriate than this little test!

Thanks,
Dave

#include <iostream>
#include <ctime>
#include <vector>

using namespace std;

namespace
{
const int NUM_ELEMENTS = 100000;
const int NUM_ITERS = 100000;
};

int main()
{
int a[NUM_ELEMENTS];
time_t finish;
int i;
int j;
int k = NUM_ELEMENTS / 2; // An arbitrary element to look up
time_t start;
vector<int> v(NUM_ELEMENTS);

// Test the array
start = time(NULL);

for (i = 0; i != NUM_ITERS; ++i)
{
for (j = 0; j != NUM_ELEMENTS; ++j)
a[j] = i + j;
}

// Try to inhibit any optimizations of the above loops.
++k;
cout << a[k] << endl;

finish = time(NULL);
cout << "Array implementation: " << difftime(finish, start) << endl;

// Test the vector
start = time(NULL);

for (i = 0; i != NUM_ITERS; ++i)
{
for (j = 0; j != NUM_ELEMENTS; ++j)
v[j] = i + j;
}

// Try to inhibit any optimizations of the above loops.
++k;
cout << v[k] << endl;

finish = time(NULL);
cout << "vector implementation: " << difftime(finish, start) << endl;

return 0;
}

 

[Paul Thompson]

With VC++ 6.0 on a 1 GHz machine, this program produced the following
interesting results:

Release mode
---------------
Array: 109 seconds
Vector: 109 seconds

Debug mode
-------------
Array: 141 seconds
Vector: 1657 seconds

In debug mode, use of vectors is *not* justified, from a performance
perspective, by a factor of 11.75!

Debug mode isn't about performance, though, so justification or otherwise of
vectors under debug mode is totally irrelevant, surely?

Paul

 

[John Ericson]

<snip>

Paul > Debug mode isn't about performance, though, so
justification or otherwise of
Paul > vectors under debug mode is totally irrelevant,
surely?
Unless debug mode is the mode that's released...

 

[foo]

If performance is an issue, I recommed you use a vector and access the
container via iterators.
I have perform test on static C-Style arrays and compare them with
std::vector containers, and the vector out performance the C-Style
array when the data is being access via iterator.

When the data is access via operator[], that's when you get mix
results.
Some implementations have vector out performming the C-Style array,
and some have the C-Style array out performming the vector. The
difference is usually hard to measure, so it's not that signaficant.

However, I haven't found any implementation in which the C-Style array
is able to out perform a vector via iterator.

 

[Samuel Barber]

int main()
{
int a[NUM_ELEMENTS];
time_t finish;
int i;
int j;
int k = NUM_ELEMENTS / 2; // An arbitrary element to look up
time_t start;
vector<int> v(NUM_ELEMENTS);

There's a major difference here: The array 'a' is located on the
stack, while the contents of the vector are allocated from the heap.

Sam

 

[mjm]

Hello all,

I'm in a poition of trying to justify use of the STL from a performance
perspective. As a starting point, can anyone cite any benchmarks comparing
vectors to plain old statically-declared arrays? I'll also be looking at
the other STL containers later...

Also, I'd appreciate any comments anyone has on the suitability of the
little program below for comparing vectors and arrays. One obvious
shortcoming is that it uses array / vector indexing operations only as
lvalues, not as rvalues...

With VC++ 6.0 on a 1 GHz machine, this program produced the following
interesting results:

Release mode
---------------
Array: 109 seconds
Vector: 109 seconds

Debug mode
-------------
Array: 141 seconds
Vector: 1657 seconds

In debug mode, use of vectors is *not* justified, from a performance
perspective, by a factor of 11.75!

Check the STL documentation if vector in debug mode does index bounds
checking.
This would account for a 10 fold slow down on code like yours.

Get away from using raw arrays explicitly.
For a simple data structure vector is very hard to beat.

With the right compiler the blitz++ arrays library will do it but it
is certainly not simple. This is your best bet for vector - vector
operations in
small dimensions and stencils.

For linear algebra operations in larger dimensions the ATLAS BLAS is
your best bet. This one runs test suites during installation and
recompiles itself with different optimization parameters until it
finds good ones (can take hours).
There is a good paper on the net on the design (search for Jack
Donguerra and ATLAS). It is not efficient in very small dimensions
though (roughly <=20)

 

[Andrew Koenig]

Dave> With VC++ 6.0 on a 1 GHz machine, this program produced the following
Dave> interesting results:

Dave> Release mode
Dave> ---------------
Dave> Array: 109 seconds
Dave> Vector: 109 seconds

Dave> Debug mode
Dave> -------------
Dave> Array: 141 seconds
Dave> Vector: 1657 seconds

Dave> In debug mode, use of vectors is *not* justified, from a performance
Dave> perspective, by a factor of 11.75!


The reason is that in debug mode, dynamically allocated storage
(such as is used by vectors) is initialized to a recognizable bit
pattern; in release mode, it isn't.

 

[Ron Natalie]

The reason is that in debug mode, dynamically allocated storage
(such as is used by vectors) is initialized to a recognizable bit
pattern; in release mode, it isn't.

Another factor is that debug mode inhibits inlining of functions which
the STL uses heavily, especially for things like operator[]. If you
go back and twiddle the compiler settings to allow inlining in debug
mode, I suspect it gets a LOT faster.