Standard vector and boost array: which is faster?

Question

How the performance of boost::array compares to that of std::vector, and which factors have significant influence on it?

Solution 1

boost::array (or C++0x's std::array) should be faster than std::vector because boost::array instances are entirely on the stack. This means boost::array has no heap allocation, and it also means it can't grow past the size you specify for it at construction.

The purpose of boost::array is to serve as a thin layer around primitive arrays, so you can treat them as standard containers with .begin(), .end() etc. Good compilers should eliminate all overhead of boost::array such that it performs identically to primitive arrays.

---

All this concerning "default" setup, where you don't have custom allocators and you measure simple things like array construction, access and modification of elements. On the other hand, things can turn around in other tests, other platforms or with a clever setup. For example,

• if you create a custom allocator, perhaps acquiring a large memory pool at program startup, then constructing or resizing a std::vector might not any more be all that expensive.
• Swapping one std::vector with another is normally a very fast operation; the speed of swapping two pointers. Swapping two boost::array instances might be much more expensive; in the order of copying n elements. But then, in C++0x, of which std::array will be a part, swapping two arrays will be fast again, thanks to rvalue references and their move semantics.
• Copying a vector might be a very fast operation; as fast as copying a pointer (copy on write). Copying a boost::array might require copying each array element. Then again, sometimes copying any object is very fast, even faster than copying a pointer and even in your C++03 compiler -- thanks to copy elision.

You can profile to see which is faster for your use, but even this test will only give you an idea for a particular version of a particular compiler on a particular platform.

Solution 2

The best way to reach any conclusion is writing programs to test their performance with huge amount of data. How else one can arrive at any conclusion?

While you're at it, you may need some tools to assist you, such as VTune, or AMD CodeAnalyst Performance Analyzer, etc. Very Sleepy (free tool) is a C/C++ CPU profiler for Windows systems. You may try them!

Solution 3

Faster at what? std::vector is faster to type because it has one less character.

It doesn't matter what's faster, you're comparing two different things, a statically-sized array with a dynamically-sized array. Which to use depends on your application, and has nothing to do with speed.

Do you want to operate a plane or a car to some place? It depends on more than which is simply "faster".

---

A boost::array might be faster to allocate because it's, on typical machines, on the stack. Or std::vector might be nearly as fast because of some custom memory allocation scheme.

But that's just allocation. What about use? Well both are just indices into an array, so maybe not difference there. But what about moving or swapping? boost::array certainly cannot do that as fast, because std::vector only has to move/swap a pointer. Or maybe not, who knows?

You have to profile and look at the assembly. Nobody can magically know how things perform for you.

Solution 4

array and vector serve slightly different purposes. If you initialize a vector to the size you need and it will never be re-allocated, the performance between the two is identical. array only handles statically sized arrays (C-style arrays if you will). vector can grow if you push more objects into the container than it currently has capacity for.

View more solutions

Comments

[ypnos]

Sounds to me as you cannot use boost::array for large array sizes. Otherwise you risk a stack overflow. Correct?

[Nate]

Hey, Very Sleepy is a nice little tool! (I corrected the link for it.)

[Rob Kennedy]

If you allocate it on the stack, @Ypnos, then yes, you can expect a stack overflow (or a compiler error, if the compiler disallows types beyond a certain size). If you allocate dynamically, then you shouldn't get a stack overflow unless you mistakenly pass the array by value. (But the compiler error is still a risk, wherever you allocate the value.)

[Ferruccio]

Because vectors need to access the underlying data through a pointer, there may a slight performance advantage to arrays because vector access will have to go through one more level of indirection. I doubt this is a factor worth considering on modern hardware except in extreme cases.

[Zac Howland]

He wasn't talking about a C-style array, he was referring to the std::array (aka boost::array) template class, which has the same redirection performance "hit" as a vector (both being so minute it won't matter anyway).

[Jon Trauntvein]

faster at what? The original question is vague at best. Does he refer to access of array/vector members or is he referring to the work with filling/assigning the same?

[Dean Burge]

@JonTrauntvein I stated my assumptions.

[Dean Burge]

In my opinion it is much more helpful to give an answer with stated assumptions the to answer "that depends" and stop at that.

[T.C.]

std::vector cannot be COW regardless of the version of the standard you are using. It's prohibited by the iterator invalidation rules.

[SirGuy]

And if you have lots of data to process, the time it takes to allocate a std::vector could easily be swamped by just the time it takes to iterate through what you allocated. Especially if you start doing multiple passes through the data.