efficiency of c++ arrays vs std::vector and std::array

I don't think your tests are right. Perhaps you are running in debug mode? I don't see any way that test11() could be faster than test1() (even though it is not freeing all of its memory).

Additionally, in many of the cases above, a release mode compiler would optimize away your code because it doesn't actually do anything:

for (int i=0; i<100; ++i) { for (int j=0; j<100; ++j) { int a = arr[i][j]; } } 

Any compiler will almost certainly eliminate that because 'a' isn't used, which means that 'i' and 'j' in turn aren't used.

for (int i=0; i<100; ++i) { for (int j=0; j<100; ++j) { arr[i][j] = 3; } } 

Some compilers could even be good enough to eliminate that code since the memory is never read again, but most probably wouldn't.

I would advise not to worry about any performance overhead with vector vs. new int[]. In debug mode, you'll get free debugging aids (bounds checking) while in release mode, as long as you don't call functions that throw for out-of-range, the code will be essentially identical in performance for practical purposes. Plus, you don't have to worry about memory management (both test1() and test11() are not quite right).

Let's do some work to improve the test, and give the standard library a chance by using it properly...

#include <iostream> #include <vector> #include <array> #include <ctime> #include <memory> #include <algorithm> #include <iterator> void test1 () { auto arr = std::make_unique<int[]>(10000); std::fill(arr.get(), arr.get() + 10000, 3); for (int i=0; i<10000; ++i) { int a = arr[i]; } } void test11 () { auto arr = std::make_unique<std::unique_ptr<int[]>[]>(100); for (auto i = 0 ; i < 100 ; ++i) { arr[i] = std::make_unique<int[]>(100); } for (int i=0; i<100; ++i) { for (int j=0; j<100; ++j) { arr[i][j] = 3; } } for (int i=0; i<100; ++i) { for (int j=0; j<100; ++j) { int a = arr[i][j]; } } } void test2() { std::vector<int> arr(10000); std::fill(std::begin(arr), std::end(arr), 3); for (int i=0; i<10000; ++i) { int a = arr[i]; } } void test22() { std::vector<std::vector<int> > arr(100, std::vector<int>(100)); std::for_each(begin(arr), end(arr), [](auto& inner) { std::fill(std::begin(inner), std::end(inner), 3); }); for (int i=0; i<100; ++i) { for (int j=0; j<100; ++j) { int a = arr[i][j]; } } } void test3(int *arr, int n) { std::fill(arr, arr + n, 3); for (int i=0; i<n; ++i) { int a = arr[i]; } } void test33(const std::unique_ptr<std::unique_ptr<int[]>[]>& arr, int m, int n) { for (int i=0; i<m; ++i) { for (int j=0; j<n; ++j) { arr[i][j] = 3; } } for (int i=0; i<m; ++i) { for (int j=0; j<n; ++j) { int a = arr[i][j]; } } } void test4() { std::array<int, 10000> arr; std::fill(std::begin(arr), std::end(arr), 3); for (int i=0; i<10000; ++i) { int a = arr[i]; } } void test44() { std::array<std::array<int, 100>, 100> arr; std::for_each(begin(arr), end(arr), [](auto& inner) { std::fill(std::begin(inner), std::end(inner), 3); }); for (int i=0; i<100; ++i) { for (int j=0; j<100; ++j) int a = arr[i][j]; } } int main() { clock_t start, end; start = clock(); for (int i=0; i<1000; ++i) { test1(); } end = clock(); std::cout << "test 1 " << (double)(end - start) * 1000.0 / CLOCKS_PER_SEC << " ms" << std::endl; start = clock(); for (int i=0; i<1000; ++i) { test11(); } end = clock(); std::cout << "test 11 " << (double)(end - start) * 1000.0 / CLOCKS_PER_SEC << " ms" << std::endl; start = clock(); for (int i=0; i<1000; ++i) { test2(); } end = clock(); std::cout << "test 2 " << (double)(end - start) * 1000.0 / CLOCKS_PER_SEC << " ms" << std::endl; start = clock(); for (int i=0; i<1000; ++i) { test22(); } end = clock(); std::cout << "test 22 " << (double)(end - start) * 1000.0 / CLOCKS_PER_SEC << " ms" << std::endl; start = clock(); for (int i=0; i<1000; ++i) { int *arr = new int[10000]; test3(arr, 10000); delete [] arr; } end = clock(); std::cout << "test 3 " << (double)(end - start) * 1000.0 / CLOCKS_PER_SEC << " ms" << std::endl; start = clock(); auto arr = std::make_unique<std::unique_ptr<int[]>[]>(100); for (auto i = 0 ; i < 100 ; ++i) { arr[i] = std::make_unique<int[]>(100); } for (int i=0; i<1000; ++i) { test33(arr, 100, 100); } arr.reset(); end = clock(); std::cout << "test 33 " << (double)(end - start) * 1000.0 / CLOCKS_PER_SEC << " ms" << std::endl; start = clock(); for (int i=0; i<1000; ++i) { test4(); } end = clock(); std::cout << "test 4 " << (double)(end - start) * 1000.0 / CLOCKS_PER_SEC << " ms" << std::endl; start = clock(); for (int i=0; i<1000; ++i) { test44(); } end = clock(); std::cout << "test 44 " << (double)(end - start) * 1000.0 / CLOCKS_PER_SEC << " ms" << std::endl; } 

results on my computer when compiled with -O2:

test 1 0.002 ms test 11 13.506 ms test 2 2.753 ms test 22 13.738 ms test 3 1.42 ms test 33 1.552 ms test 4 0 ms test 44 0 ms 

Let's also note that the arrays are "small" and are being allocated and deallocated repeatedly. If you can re-use the buffers, then the difference in timing will vanish completely.

Also note: test33 is fast because it never reallocates memory - you're re-using the buffer.

When operating on plain C arrays, compiler is able recognize opportunities to unwind the loops, saving a small amount of iteration overhead. Possibly (unlikely) compiler does not optimize out access loops for STL containers because it does not know whether or not they modify any member variables.

Also my best guess as to why the test11 is outperforming test1 is that it's interweaving multiple iterations of the outer loop (taking advantage of the fact that modern x86/x64 processors are superscalar), IE:

for(int j = 0; j < 100; ++j) { for(int i = 0; i < 100; i+=4) { arr[i][j] = 3; arr[i+1][j] = 3; arr[i+2][j] = 3; arr[i+4][j] = 3; } } 

or possibly something else entirely. compilers can do some very complicated loop transformations to get the every little bit of performance.