Why would array<T, N> ever be slower than vector<T>?
c++, c++11, optimization, stl
Solution
Consider the second and third tests. Conceptually, they are identical: Allocate `K * N * sizeof(double)` bytes off the heap and then access them in exactly the same way. So why the different times?
All of your "faster" tests have one thing in common: `new[]`. All of the slower tests are allocated with `new` or on the stack. `vector` probably uses `new[]` Under the Hood™. The only obvious cause for this is that `new[]` and `new` have more significantly different implementations than expected.
What I'm going to suggest is that `new[]` will fall back to `mmap` and allocate directly on a page boundary, giving you an alignment speedup, whereas the other two methods will not allocate on a page boundary.
Consider using an OS allocation function to directly map committed pages, and then place a `std::array<std::array<double, N>, K>` into it.
Problem
Today I decided to benchmark and compare some differences in gcc optimizability of `std::vector` and `std::array`. Generally, I found what I expected: performing a task on each of a collection of short arrays is much faster than performing the tasks on a collection equivalent vectors. However, I found something unexpected: using `std::vector` to store the collection of arrays is faster than using `std::array`. Just in case it was the result of some artifact of a large amount of data on the stack, I also tried allocating it as an array on the heap and in a C-style array on the heap (but the results still resemble an array of arrays on the stack and a vector of arrays). Any idea why `std::vector` would ever outperform `std::array` (on which the compiler has more compile-time information)? I compiled using `gcc-4.7 -std=c++11 -O3` (`gcc-4.6 -std=c++0x -O3` should also result in this conundrum). Runtimes were computed using the `bash`-native `time` command (user time). Code: ``` #include <array> #include <vector> #include <iostream> #include <assert.h> #include <algorithm> template <typename VEC> double fast_sq_dist(const VEC & lhs, const VEC & rhs) { assert(lhs.size() == rhs.size()); double result = 0.0; for (int k=0; k<lhs.size(); ++k) { double tmp = lhs[k] - rhs[k]; result += tmp * tmp; } return result; } int main() { const std::size_t K = 20000; const std::size_t N = 4; // declare the data structure for the collection // (uncomment exactly one of these to time it) // array of arrays // runtime: 1.32s std::array<std::array<double, N>, K > mat; // array of arrays (allocated on the heap) // runtime: 1.33s // std::array<std::array<double, N>, K > & mat = *new std::array<std::array<double, N>, K >; // C-style heap array of arrays // runtime: 0.93s // std::array<double, N> * mat = new std::array<double, N>[K]; // vector of arrays // runtime: 0.93 // std::vector<std::array<double, N> > mat(K); // vector of vectors // runtime: 2.16s // std::vector<std::vector<double> > mat(K, std::vector<double>(N)); // fill the collection with some arbitrary values for (std::size_t k=0; k<K; ++k) { for (std::size_t j=0; j<N; ++j) mat[k][j] = k*N+j; } std::cerr << "constructed" << std::endl; // compute the sum of all pairwise distances in the collection double tot = 0.0; for (std::size_t j=0; j<K; ++j) { for (std::size_t k=0; k<K; ++k) tot += fast_sq_dist(mat[j], mat[k]); } std::cout << tot << std::endl; return 0; } ``` NB 1: All versions print the same result. NB 2: And just to demonstrate that the runtime differences between `std::array<std::array<double, N>, K>`, `std::vector<std::array<double, N> >`, and `std::vector<std::vector<double> >` wasn't simply from assignment/initialization when allocating, the runtimes of simply allocating the collection (i.e. commenting out the computation and printing of `tot`) were 0.000s, 0.000s, and 0.004s, respectively. NB 3: Each method is compiled and run separately (not timed back-to-back within the same executable), to prevent unfair differences in caching. NB 4: Assembly for array of arrays: http://ideone.com/SM8dB Assembly for vector of arrays: http://ideone.com/vhpJv Assembly for vector of vectors: http://ideone.com/RZTNE NB 5: Just to be absolutely clear, I am in no way intending to criticize STL. A absolutely love STL and, not only do I use it frequently, details of effective use have taught me a lot of subtle and great features of C++. Instead, this is an intellectual pursuit: I was simply timing things to learn principles of efficient C++ design. Furthermore, it would be unsound to blame STL, because it is difficult to deconvolve the etiology of the runtime differential: With optimizations turned on, it can be from compiler optimizations that slow the code rather than quicken it. With optimizations turned off, it can be from unnecessary copy operations (that would be optimized out and never be executed in production code), which can be biased against certain data types more than others. If you are curious like me, I'd love your help figuring this out.