5

Possible Duplicate:
std::vector is so much slower than plain arrays?

Looks like vector is allocated on heap instead of stack.

So should I consider using array to replace vector (if possible) when performance becomes a serious issue?

Community
  • 1
  • 1
Deqing
  • 14,098
  • 15
  • 84
  • 131
  • 2
    I dont think that will give you any noticeable improvement. – Shiplu Mokaddim Jul 26 '12 at 08:26
  • See this question http://stackoverflow.com/q/11648202/819272 for a discussion on Howard Hinnant's stack allocator for the STL containers. Used with `std::vector`, this will give you performance close (within about 10% for use in a tight inner loop e.g.) to `std::array` but it retains the flexibility of vectors by going to the heap if the stack buffer becomes full. – TemplateRex Jul 26 '12 at 09:17

3 Answers3

19

No. (to satisfy the comment pedants, no, you should not "prefer" arrays over vectors for performance, but sure, you should "consider" using arrays to replace vectors, for the specific cases outlined below)

When performance becomes a serious issue, you should base your optimizations on actual data, not second-hand stories and hearsay and superstition.

If replacing your vector with an array gives you a measurable (and necessary) speedup, then you should do it.

But note that you can only use a stack-allocated array if:

  • the size is known at compile-time, and
  • the size is small enough to fit on the stack without causing problems.
  • the size must be fixed, rather than dynamic.

In most cases, these conditions won't be true, and then the array would have to be heap-allocated anyway, and then you just lost the one advantage arrays had.

But if all those conditions are true and you can see that this heap allocation is actually hurting your performance measurably, then yes, switching to an array (or a std::array) makes sense.

Otherwise? No...

jalf
  • 243,077
  • 51
  • 345
  • 550
  • 2
    The part about "the size is known at compile-time" isn't entirely true, some compilers support stack allocation of runtime-sized arrays. (C99 required support for that in fact, but not all supported it, hence C11 made it optional). – Giel Jul 26 '12 at 08:29
  • 2
    @Giel question is about C++. C++/C++11 standards not supports VLA. – ForEveR Jul 26 '12 at 08:31
  • @Giel but it isn't an option in standard C++ (although it is available as an extension on compilers such as gcc). – juanchopanza Jul 26 '12 at 08:34
  • 1
    Question, "should I consider replacing a vector with an array". Answer: "No. If replacing a vector with an array improves things, you should do it". This seems contradictory -- how can I find out whether the array improves things without at least *considering* that change? In fact most likely I'll have to actually make the change (in a dev/test environment) in order to find out anything much about it. I guess the question title differs from the question text enough to create confusion here: I think the idea of this answer is that you *should* consider it but *should not* blindly prefer it. – Steve Jessop Jul 26 '12 at 09:10
5

If the number of elements is known in advance, in coding-time, then yes, you should prefer using array. C++11 provides this:

std::array<int,10000> arr;

But avoid using this:

int arr[10000]; //avoid it in C++11 (strictly), and possibly in C++03 also!

In C++03, you should still prefer std::vector in most of the cases (unless experiments show it is slow):

std::vector<int> arr;
arr.reserve(10000); //it is good if you know the (min) number of items!

In most cases, when vector appears to be slow, it is because programmers don't take advantage of reserve() function. Instead they rely on the repeated allocation-deallocation-copy strategy, when the vector resizes itself.

Nawaz
  • 353,942
  • 115
  • 666
  • 851
  • 1
    +1 for the compile-time guarantee remark. Note that `std::array` is not a drop-in replacement for `std::vector` because it misses `push_back`. This makes it hard to write container independent code. – TemplateRex Jul 26 '12 at 09:21
  • 10000 ints on the stack? Really? – Jonathan Wakely Jul 26 '12 at 09:22
  • @rhalbersma, most containers don't provide `push_back` either. That's not `std::array`'s problem – Jonathan Wakely Jul 26 '12 at 09:26
  • @JonathanWakely Most sequence containers (`vector`, `list`, `deque`) do, except `std::array` and `forward_list`. – TemplateRex Jul 26 '12 at 09:30
  • @Jonathan: It'll work or it won't, so why not? "Because the function is deeply recursive" and "because I'd like my code to run on restricted systems" spring to mind, but "because 40k just sounds like an *awful* lot of memory to me" isn't automatically a good reason any more ;-) That said, there isn't much you can do with 10k ints that takes so little time that a memory allocation is hugely significant. So if the array really is that big, I'd be surprised if it's saving you much compared with the vector. – Steve Jessop Jul 26 '12 at 10:53
  • @Steve, where "restricted systems" could mean high-powered machines that happen to be passing a small number to `pthread_attr_setstacksize`, which certainly allows values below 40k – Jonathan Wakely Jul 26 '12 at 17:50
  • 1
    @Jonathan: yes, for example in a massively multi-threaded environment, where thread overhead needs to be minimized. I don't think there *is* a minimum stack size value, there's no portable concept of "too much stack". If you're paranoid, don't put arrays on the stack. Unless you're sure they're smaller than the basic types that you're using anyway. – Steve Jessop Jul 26 '12 at 18:01
  • @Steve, yep, exactly. There is a minimum for pthreads: the implementation-defined value `PTHREAD_STACK_MIN` (which is 16k on my GNU/Linux system) – Jonathan Wakely Jul 27 '12 at 00:22
  • Does Posix define a minimum permissible value for `PTHREAD_STACK_MIN`, though? I've been paranoid about portability in the past where I've had to be. However, you simply cannot get good guarantees about stack size: so you more or less have to avoid stack use as far as possible (in which case you'd say "10 ints on the stack? Really?" just as you say it for 10000). For code where portability is not the most important thing, you can use the stack (that's that it's there for), and worry about tiny-stack environments if you ever meet one (YAGNI). – Steve Jessop Jul 31 '12 at 10:08
0

Unless you're running on an exceptional system (i.e. one with a slow memory allocator) it is unlikely to make a significant difference. I'd suggest you prefer using std::vector instead, for its better type safety than plain arrays.

Giel
  • 2,787
  • 2
  • 20
  • 25