Since I’ve got into trouble for posting these typesof things in the middle of threads about other issues, I thought I’d start putting up some dedicated threads addressing performance proofs of common or uncommon c/c++ claims and counter claims.
I’m hoping this won’t be taken the wrong way, or turned into Stack Overflow sledging sessions. I’m doing it purely in the spirit of curiosity.
I’m not a computer science graduate so whenever I see someone (on this forum) or in other c/c++ how-to/style guides say ‘x’ is the best; or ‘y’ is for newbies; or ‘z’ is the most efficient, I want to do the sort of thing I imaging Comp Sci undergrads spend all day doing. Namely wrapping bits of code with timers and seeing which one goes fastest under a variety of conditions…
I’m hoping people have other code examples, demonstrations, proofs or improvements to testing procedures to offer.
…so vectors vs arrays…
This has come up a lot on the forums, especially in relation to particle systems, threads and http requests See for instance: topic=7248.0O and topic,1146.0.html
Arturo recently wrote a super-great-guide-to-vectors-vs-c-style-arrays and I was very surprised to see that they should perform as well as an array as long as you use them right.
So like a nerd I spent (wasted?) the day writing some code to test different size and types of allocations, deletions and manipulations using arrays and vectors. The src code is attached at the bottom.
Some results with a little raw data and selected averages:
Results for items1 = 100 , items2 = 1 and 20 iterations of the test:
OF: OF_LOG_NOTICE: Fill (ints) reserved vector array-style[] access: 0.105263
OF: OF_LOG_NOTICE: Fill (ints) reserved vector push_back-style access: 0.45
OF: OF_LOG_NOTICE: Fill (ints) unreserved vector push_back-style access: 3.6
OF: OF_LOG_NOTICE: Fill (ints) unreserved vector with resize 'optimisation' access: 6.8
OF: OF_LOG_NOTICE: Fill (ints) array [] access: 0.05
OF: OF_LOG_NOTICE: Fill (custom struct) reserved vector array-style[] access: 19.65
OF: OF_LOG_NOTICE: Fill (custom struct) array [] access: 14
OF: OF_LOG_NOTICE: Fill (unsigned char*) reserved vector array-style[] access: 7426.35
OF: OF_LOG_NOTICE: Fill (unsigned char*) array[] access: 4779.7
Results for items1 = 10000 , items2 = 5 and 20 iterations of the test:
OF: OF_LOG_NOTICE: Fill (ints) reserved vector array-style[] access: 10.1053
OF: OF_LOG_NOTICE: Fill (ints) reserved vector push_back-style access: 24.2
OF: OF_LOG_NOTICE: Fill (ints) unreserved vector push_back-style access: 51.4
OF: OF_LOG_NOTICE: Fill (ints) unreserved vector with resize 'optimisation' access: 249.9
OF: OF_LOG_NOTICE: Fill (ints) array [] access: 11.3
OF: OF_LOG_NOTICE: Fill (custom struct) reserved vector array-style[] access: 1443.7
OF: OF_LOG_NOTICE: Fill (custom struct) array [] access: 1343.4
OF: OF_LOG_NOTICE: Fill (unsigned char*) reserved vector array-style[] access: 37032.6
OF: OF_LOG_NOTICE: Fill (unsigned char*) array[] access: 24771.8
Outlier was 33 for first fill of reserved vector.
Results for items1 = 100000 , items2 = 10 and 20 iterations of the test:
OF: OF_LOG_NOTICE: Fill (ints) reserved vector array-style[] access: 76.3158
OF: OF_LOG_NOTICE: Fill (ints) reserved vector push_back-style access: 236.9
OF: OF_LOG_NOTICE: Fill (ints) unreserved vector push_back-style access: 393.2
OF: OF_LOG_NOTICE: Fill (ints) unreserved vector with resize 'optimisation' access: 2454.35
OF: OF_LOG_NOTICE: Fill (ints) array [] access: 90.15
OF: OF_LOG_NOTICE: Fill (custom struct) reserved vector array-style[] access: 15337.8
OF: OF_LOG_NOTICE: Fill (custom struct) array [] access: 14368.1
OF: OF_LOG_NOTICE: Fill (unsigned char*) reserved vector array-style[] access: 66839.1
OF: OF_LOG_NOTICE: Fill (unsigned char*) array[] access: 44535.5
Outlier was 280 for first fill of reserved vector.
Results for items1 = 1000000 , items2 = 20 and 20 iterations of the test:
OF: OF_LOG_NOTICE: Fill (ints) reserved vector array-style[] access: 983.053
OF: OF_LOG_NOTICE: Fill (ints) reserved vector push_back-style access: 2280.05
OF: OF_LOG_NOTICE: Fill (ints) unreserved vector push_back-style access: 6163.5
OF: OF_LOG_NOTICE: Fill (ints) unreserved vector with resize 'optimisation' access: 25276.9
OF: OF_LOG_NOTICE: Fill (ints) array [] access: 947.35
OF: OF_LOG_NOTICE: Fill (custom struct) reserved vector array-style[] access: 196648
OF: OF_LOG_NOTICE: Fill (custom struct) array [] access: 189263
OF: OF_LOG_NOTICE: Fill (unsigned char*) reserved vector array-style[] access: 133421
OF: OF_LOG_NOTICE: Fill (unsigned char*) array[] access: 89309
Outlier was 4314 for first fill of reserved vector.
Results for items1 = 8294400 (ie., 1920*1080*4), items2 = 100 and 20 iterations of the test:
OF: OF_LOG_NOTICE: Fill (ints) reserved vector array-style[] access: 29833.6
OF: OF_LOG_NOTICE: Fill (ints) reserved vector push_back-style access: 18624.9
OF: OF_LOG_NOTICE: Fill (ints) unreserved vector push_back-style access: 72154.6
OF: OF_LOG_NOTICE: Fill (ints) unreserved vector with resize 'optimisation' access: 200904
OF: OF_LOG_NOTICE: Fill (ints) array [] access: 28400.8
OF: OF_LOG_NOTICE: Fill (custom struct) reserved vector array-style[] access: 1.73499e+06
OF: OF_LOG_NOTICE: Fill (custom struct) array [] access: 1.72908e+06
OF: OF_LOG_NOTICE: Fill (unsigned char*) reserved vector array-style[] access: 651981
OF: OF_LOG_NOTICE: Fill (unsigned char*) array[] access: 412695
One funny thing to note is the very first time I fill a reserved vector using:
for (int i = 0; i < items1; i++) {
v1[i] = i;
}
I get an outlier value much higher than the average, hence excluding the first go…
So some questions/observations for comment by the even nerdier:
* Any ideas why the first iteration is so costly?
* Seems like for small allocations there is a very minor advantage to arrays (but so minor the flexibility of the vector makes it pretty obsolete)
* Surprisingly, as we get into allocations of between 100000 to 1000000, the vector (reserved and accessed via []) actually out performs the array until the upper end of the range (and again the difference is a matter of 20-40 microseconds over literally millions of accesses)
* But once we get into ‘pixel-sized’ allocations and accesses ie 8294400+ the array begins to outperform the vector (reserved array[] access) by more significant amounts, but even more surprisingly ‘push_back’ access outperforms the array-style [] accessor for a vector by a non-trivial amount.
* Using custom data types rather than an integral type significantly changes the weighting of results -> arrays consistently out perform the vector regardless of accessor by non-trivial amounts, particularly as the number of allocations rise (obviously ‘non-trivial’ is up for grabs here -> we’re talking microseconds for 100-1000 allocations, but it does get up to seconds for 100000+…)
* And for multidimensional arrays with ‘pixel-size’ allocations [n][1920*1080*4] in these examples, the array is clearly far more efficient for any value of n.
* Finally, and this is only anecdotal (I’m trying to work out a test for this) I’ve found that vectors of more complex types (ie., ofVideoPlayer’s) perform much worse than arrays of the same types -> I remember doing a lot of tests of loading vectors of 20-30 videos vs doing the same with an array and getting much worse overall FPS…but need to check this when I have a suitable amount of videos on hand…