Myth busted, good work guys.
Favor vectors because they don't cost anything and they are less brittle to change.
Arrays are useful in low level situations where you are dealing directly with memory allocation anyway. If you're developing a new container class, go ahead and use arrays. If you are doing basically anything more high level than that favor vectors.
Array vs Vector Discussion :)
Quote:Original post by M2tM
Favor vectors because they don't cost anything....
No, vectors typically use three machine words of storage for the vector itself and use heap allocation for the array data, which, in addition to the allocated memory, costs the bookkeeping information for the allocation, which is typically anywhere from two to six machine words, as well as potential internal or external fragmentation from using heap allocation. There's also the potential extra cache line usage in the working set because of the indirection. This adds up to a very low cost for most use cases. However, very low is not the same as zero.
Author
Yea well it was a myth, we all tried it so we weren't sure. But anyway try this one. Its 2D this time meaning that it can't compile down to 1 instruction anymore. See what your numbers are now.
Release I'm 100 vs 400 ms.
And again debug still counts(and this one can't be inline/optimized due to the 2D nature)
450 vs 26600 ms
Release I'm 100 vs 400 ms.
And again debug still counts(and this one can't be inline/optimized due to the 2D nature)
450 vs 26600 ms
#include <vector>#include <iostream>#include <windows.h>using namespace std;#define XSIZE 10000vector<vector<int>> vecNumbers;int arrayNumbers[XSIZE][XSIZE];int main(){ vecNumbers.reserve(XSIZE); for(int i = 0; i < XSIZE; i++) { vecNumbers.push_back(vector<int>(XSIZE)); for(int j = 0; j < XSIZE; j++) { arrayNumbers[j] = 0; } }float start_time = GetTickCount(); for(int i = 0; i < XSIZE;i++) { for(int j = 0; j < XSIZE;j++) { arrayNumbers[j]++; } } cout << GetTickCount() - start_time << endl; start_time = GetTickCount(); for(int i = 0; i < XSIZE;i++) { for(int j = 0; j < XSIZE;j++) { vecNumbers[j]++; } } cout << GetTickCount() - start_time; system("pause"); return 0;}Quote:Original post by dpadam450
Yea well it was a myth, we all tried it so we weren't sure. But anyway try this one. Its 2D this time meaning that it can't compile down to 1 instruction anymore. See what your numbers are now.
*** Source Snippet Removed ***
Yes, because in such a case you're comparing a situation where the array sits in a contiguous block of memory with a case where one level of indirection is required. Of course the indirection adds complexity. In such a case, you might want to use a 1d vector and calculate the index (and in most non-trivial uses of a 2d array, you'll end up having to do this anyway).
I find, in my code, that 2d arrays are very rare, so the general coding practice of using an std::vector rather than an array still holds. It is, of course, always possible to find exceptions to any rule of thumb, but that doesn't mean one should fall back on the bad practice in the general case.
Quote:Original post by dpadam450
And again debug still counts(and this one can't be inline/optimized due to the 2D nature)
450 vs 26600 ms
It only counts if you're in the habit of doing early micro-optimizations that only benefits test builds, which is generally bad practice. If you're having practical problems with testing due to the performance hit, than sure, but its better to go back and replace the std::vector with an array if you have the performance problem and can't optimize it out rather than code with an array in the first place. That's just good programming practice (don't micro-optimize prematurely).
Quote:
Its 2D this time meaning that it can't compile down to 1 instruction anymore. See what your numbers are now.
You are comparing apples and oranges. The "2d array" is syntatic sugar for a 1d array that is indexed differently. The "2d vector" is a completely different beast of non-contiguous arrays being stored in another array. Use the same code for both, and the time will be the same. For the "2d vector" use a 1d vector with an index function like "inline int index(int x, int y) { return x + y*width }".
Or, maybe just use boost::multi_array if that suits the application better.
Author
Actually I thought about the contiguous thing, but also the point to that is you can't get a 2D vector in contiguous memory. And storing it as 1D is good, but sometimes especially in spatial things like games, you want to read x,y,z for faster clarity.
I updated the code to use the dual indirection just like the vector, results:
Release: 125 vs 390
Debug: 650 vs 26600
I'm really missing what you guys are saying about Debug not mattering and that you shouldn't optimize. What I'm saying here there is nothing significant to optimize. It is a very simple function. My option for this algorithm were array or vector. Both work just fine, but if you want to run in debug some times, it kills this algorithm if you need real-time rates.
My conclusion is that yes 1D array vs vector are the same. For 100 Million elements there wasn't a significant impact. 2D or 3D though, I would never use a vector.
I updated the code to use the dual indirection just like the vector, results:
Release: 125 vs 390
Debug: 650 vs 26600
I'm really missing what you guys are saying about Debug not mattering and that you shouldn't optimize. What I'm saying here there is nothing significant to optimize. It is a very simple function. My option for this algorithm were array or vector. Both work just fine, but if you want to run in debug some times, it kills this algorithm if you need real-time rates.
My conclusion is that yes 1D array vs vector are the same. For 100 Million elements there wasn't a significant impact. 2D or 3D though, I would never use a vector.
#include <vector>#include <iostream>#include <windows.h>using namespace std;#define XSIZE 10000vector<vector<int>> vecNumbers;int** arrayNumbers;int main(){ vecNumbers.reserve(XSIZE); arrayNumbers = new int*[XSIZE]; for(int i = 0; i < XSIZE; i++) { arrayNumbers = new int[XSIZE]; vecNumbers.push_back(vector<int>(XSIZE)); for(int j = 0; j < XSIZE; j++) { arrayNumbers[j] = 0; } }float start_time = GetTickCount(); for(int i = 0; i < XSIZE;i++) { for(int j = 0; j < XSIZE;j++) { arrayNumbers[j]++; } } cout << GetTickCount() - start_time << endl; start_time = GetTickCount(); for(int i = 0; i < XSIZE;i++) { for(int j = 0; j < XSIZE;j++) { vecNumbers[j]++; } } cout << GetTickCount() - start_time; system("pause"); return 0;}
Quote:
But anyway try this one. Its 2D this time meaning that it can't compile down to 1 instruction anymore.
I ran it five times:
Quote:
218
218
---
202
218
---
220
218
---
218
250
---
312
203
I then ran it once with a loop in it:
Quote:
328
218
---
234
203
---
219
202
---
203
234
---
219
218
The assembly output is considerably more complex for vector<> than the array this time:
Array:
mov esi, eax lea eax, DWORD PTR _arrayNumbers$[esp+400000064] mov edx, 10000 ; 00002710H npad 1$LL12@main:; 51 : {; 52 : for(int j = 0; j < XSIZE;j++) mov ecx, 10000 ; 00002710H$LL9@main:; 53 : {; 54 : arrayNumbers[j]++; inc DWORD PTR [eax] add eax, 4 dec ecx jne SHORT $LL9@main; 50 : for(int i = 0; i < XSIZE;i++) dec edx jne SHORT $LL12@mainVector:
mov ecx, DWORD PTR _vecNumbers$[esp+400000064] mov edi, eax mov esi, 10000 ; 00002710H npad 10$LL6@main:; 62 : {; 63 : for(int j = 0; j < XSIZE;j++) mov eax, 12 ; 0000000cH$LL3@main:; 64 : {; 65 : vecNumbers[j]++; mov edx, DWORD PTR [ecx] inc DWORD PTR [eax+edx-12] lea edx, DWORD PTR [eax+edx-12] mov edx, DWORD PTR [ecx] inc DWORD PTR [eax+edx-8] lea edx, DWORD PTR [eax+edx-8] mov edx, DWORD PTR [ecx] inc DWORD PTR [eax+edx-4] lea edx, DWORD PTR [eax+edx-4] mov edx, DWORD PTR [ecx] inc DWORD PTR [edx+eax] mov edx, DWORD PTR [ecx] inc DWORD PTR [eax+edx+4] lea edx, DWORD PTR [eax+edx+4] add eax, 20 ; 00000014H cmp eax, 40012 ; 00009c4cH jl SHORT $LL3@main; 61 : for(int i = 0; i < XSIZE;i++) add ecx, 16 ; 00000010H dec esi jne SHORT $LL6@mainThe compiler appears to have partially unrolled the loop for the vector.
In vanilla Debug mode std::vector is indeed (and obviously) orders of magnitude slower.
In any case, a more direct comparison might be with boost::multi_array. I have a 2 dimensional vector class that uses a contiguous std::vector<> for storage.
Quote:Original post by dpadam450
Actually I thought about the contiguous thing, but also the point to that is you can't get a 2D vector in contiguous memory. And storing it as 1D is good, but sometimes especially in spatial things like games, you want to read x,y,z for faster clarity.
"Spatial things"? Well, if you're planning on passing that array around and at least one of the dimensions isn't known at compile time, you're going to be handling that 2D array as a 1D array anyway. I suppose if you can handle it across the board as a 2D array then you might have a point, but in practice I've found this to be fairly rare.
Quote:Original post by dpadam450
I'm really missing what you guys are saying about Debug not mattering and that you shouldn't optimize.
Apparently. We're not saying "Don't optimize." We're saying "Don't micro-optimize prematurely." Picking an array based on the idea that "Its faster in debug mode!" is worrying about the wrong things. You can always change that std::vector into an array in the rare case that its a problem. But what are the chances that it will actually be an issue, and that its an issue that can't be fixed by tweaking compiler settings? Not likely, so use the correct way for now, and change it if your frame rate is too low in debug. Program for the general case, not the special case.
Quote:Original post by dpadam450
What I'm saying here there is nothing significant to optimize. It is a very simple function. My option for this algorithm were array or vector. Both work just fine, but if you want to run in debug some times, it kills this algorithm if you need real-time rates.
No, you made a generalized statement about how you should use arrays instead of vectors if you didn't need resizing because they were faster, and we called you out on it. You've made a preemptive judgement that extensive usage of vector will kill you if you need "real-time rates" in debug mode.
Quote:Original post by dpadam450
My conclusion is that yes 1D array vs vector are the same, for 100 Million elements there wasnt a significant impact. 2D or 3D though, I would never use a vector.
Never? Again, your tests are pretty arbitrary. Yes, if you don't want to treat your vector as contiguous memory and calculate indexes, you'll get a performance hit. The problem is that complex use of 2D arrays will also require the same index-calculating shenanigans. If that's the case, you might as well just use a vector.
And I'd like to note you started out this thread under the pretense of giving helpful advice, then gave potential newbies bad advice. Stop doing that, please.
Quote:
I'm really missing what you guys are saying about Debug not mattering and that you shouldn't optimize.
First off, because no-one but the developer is going to see the debug mode, you should worry about the release mode first. Also, the optimizations that happen in release are specific to your code, and can remove "bottlenecks" that aren't really there. Prematurely optimizing can actually make the compiler's job harder, resulting in poorer release code.
Secondly, don't optimize till it becomes a problem. Just because your esoteric "benchmark" code shows that arrays are faster doesn't mean anything. The array access itself may be trivial compared to some other bottleneck in the code. The difference in time between an array and a vector is perfectly trivial compared to the time spent in a memory stall from a cache miss.
Thirdly, std::vector is tested, and has lots of error checking and no manual memory management for you to screw up. Both simple things to forget when making your own arrays with new/delete.
Lastly, you also have to consider that a std::vector is a "general case" structure. It provides you with fast insertions, work with any type, has generic algorithms, etc. Your array is very specific, resulting in lots of duplicated code, magic numbers (where is std::vector::size() for your array??), and inflexibility to expantion/contraction.
ps. I'm really amazed how many times this myth comes up. I know not all programmers have had the chance to go through college yet (and thus take a compilers course and learn about optimizations), but still...
Ultimately, my experience with this kind of question is that unless you're willing to throw down an example of a compiler doing its good work people simply won't accept that vector<> can be as fast as a raw array.
In any case, you rarely know the size. Most of the times, the "size" is some heuristic guesstimate that you hope won't need to change soon, not a absolute domain constant (there are few such things). The easiest way is to write your code for the more general case. If speed is a problem, as the others have said, optimise it *then*.
The advantage of having debug bounds checking cannot be overstated. Correctness before speed. I don't like to measure performance in how fast a program crashes.
@dpadam450 Your code speaks of one who is uncertain that the compiler will do obvious optimisations. Use of the preprocessor rather than const integers hints at this. If this is really the case, then you should really think hard about whether you should be telling people what is "fast", even when your experience dictates otherwise.
Had you presented your original post as a question rather than as fact, we would have gone easier on you. The fact remains though that it is because of people like yourself who propagate outdated assumptions that this myth persists and another generation refuses to use the tools that come with the language for some vague promises of performance which they never hit.
In any case, you rarely know the size. Most of the times, the "size" is some heuristic guesstimate that you hope won't need to change soon, not a absolute domain constant (there are few such things). The easiest way is to write your code for the more general case. If speed is a problem, as the others have said, optimise it *then*.
The advantage of having debug bounds checking cannot be overstated. Correctness before speed. I don't like to measure performance in how fast a program crashes.
@dpadam450 Your code speaks of one who is uncertain that the compiler will do obvious optimisations. Use of the preprocessor rather than const integers hints at this. If this is really the case, then you should really think hard about whether you should be telling people what is "fast", even when your experience dictates otherwise.
Had you presented your original post as a question rather than as fact, we would have gone easier on you. The fact remains though that it is because of people like yourself who propagate outdated assumptions that this myth persists and another generation refuses to use the tools that come with the language for some vague promises of performance which they never hit.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
