Why a dynamic array is slower than a static array

Question

in my current project I need to work with a large array of data. so I am doing a stupid test to check which one will be better, but, trying under the code below, I found that dynamic arrays are much slower than static arrays, why so? or am i doing something wrong?

here is the code (I delete the vector (execute equal to dynamic) and increase the array (equal to static) from here)

result: static 8, dynamic 7493

#include<iostream> #include<vector> using namespace std; using namespace boost; double arr_time; double darr_time; void arrr() { int arr[100000]; LARGE_INTEGER start,end; QueryPerformanceCounter(&start); for(int i=0 ; i <100000 ; ++i) { arr[i] = 10 ; } for(int i=0 ; i <100000 ; ++i) { int x = arr[i]; } QueryPerformanceCounter(&end); arr_time += (end.LowPart - start.LowPart); } void darr() { int *arr = new int[100000]; LARGE_INTEGER start,end; QueryPerformanceCounter(&start); for(int i=0 ; i <100000 ; ++i) { arr[i] = 10 ; } for(int i=0 ; i <100000 ; ++i) { int x = arr[i]; } QueryPerformanceCounter(&end); darr_time += (end.LowPart - start.LowPart); delete[] arr; } int main(int argc, char** argv) { for(int i= 0 ; i <100 ; ++i) { arrr(); darr(); } cout<<"\n--------------------\n"; cout<<arr_time<<endl; cout<<darr_time<<endl; return 0; } 

Answer 1

As David said above, most likely you are not really measuring what you think is related to optimization. Here is your code with some changes to make sure nothing is in sync.

Using this code in release builds with Visual Studio 2008 and 2010, the times are almost identical, as is the build code generated by each function. Dynamic time, for me, is always slightly less than static time, but in such a tiny amount, I would say that they are equivalent.

 #include <Windows.h> #include <iostream> LONGLONG arrr() { int arr[100000], x = 0; LARGE_INTEGER start, end; QueryPerformanceCounter(&start); for(int i=0; i < 100000; ++i) arr[i] = 10; for(int i=0; i < 100000; ++i) x += arr[i]; QueryPerformanceCounter(&end); std::cout << x << std::endl; return (end.QuadPart - start.QuadPart); } LONGLONG darr() { int *arr = new int[100000], x = 0; LARGE_INTEGER start, end; QueryPerformanceCounter(&start); for(int i=0; i < 100000; ++i) arr[i] = 10; for(int i=0; i < 100000; ++i) x += arr[i]; QueryPerformanceCounter(&end); delete[] arr; std::cout << x << std::endl; return (end.QuadPart - start.QuadPart); } int main() { LONGLONG arr_time = 0, darr_time = 0; for(int i = 0; i < 100; ++i) { arr_time += arrr(); darr_time += darr(); } std::cout<<"\n--------------------\n"; std::cout << arr_time << std::endl; std::cout << darr_time << std::endl; return 0; } 

Answer 2

Your code does nothing with the values ​​it computes, allowing the compiler to optimize your code to zero. For example, the compiler will probably include this:

 void arrr() { int arr[100000]; LARGE_INTEGER start,end; QueryPerformanceCounter(&start); for(int i=0 ; i <100000 ; ++i) { arr[i] = 10 ; } for(int i=0 ; i <100000 ; ++i) { int x = arr[i]; } QueryPerformanceCounter(&end); arr_time += (end.LowPart - start.LowPart); } 

In it:

 void arrr() { LARGE_INTEGER start,end; QueryPerformanceCounter(&start); QueryPerformanceCounter(&end); arr_time += (end.LowPart - start.LowPart); } 

In the static code of the array, the compiler can say that the memory never accesses again, because as soon as the function returns, its stack leaves. In the dynamic case, this is impossible, because he does not know that when memory is freed, its value does not matter. The first cycle should probably remain, but the second cycle is probably completely removed in the dynamic case.

You do not measure what you think you are measuring.

You can try something like this:

 void arrr() { int arr[100000]; LARGE_INTEGER start,end; QueryPerformanceCounter(&start); for(int i=0 ; i <100000 ; ++i) { arr[i] = 10 ; } int x = 0; for(int i=0 ; i <100000 ; ++i) { x += arr[i]; } QueryPerformanceCounter(&end); arr_time += (end.LowPart - start.LowPart); cout << "x = " << x << endl; } 

There is another difference. In the case of a static array, the compiler knows that no external function (for example, QueryPerformanceCounter ) can depend on the contents of the array or modify it. In the dynamic case, he cannot know this. The position of the QueryPerformanceCounter can be changed relative to the loops. For example, the compiler can move both calls to the QueryPerformanceCounter together, after a loop, in the static case, but not in the dynamic case. (If Microsoft has not used some tricks to prevent this.)

Answer 3

As for access to the array in general (and not your current code), if you enable optimization in the compiler, then there really should not be any difference between dynamic and static arrays when accessing a set of elements sequentially in memory, On the other hand, if all optimizations are disabled , then for a dynamic array there is an implicit load of the memory address stored in the pointer variable, which should take place when you use the [] operator with the pointer until any dereference occurs. So there’s an extra operation that is missing with static or stacked arrays. But again, when any optimization is turned on, the pointer will be stored in the register and shifted from there, so there will be no difference between the first after the first access of the pointer.