why dynamic array are slower than static array

Question

in my current project i need to operate on large data array. so i do a stupid test to check which one will be better , but while trying below code i found dynamic arrays are much slower than static array why so ? or am i doing something wrong ?

here is code (i remove vector (perform equal to dynamic) and boost 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

Your code doesn't do anything with the values it computes, allowing the compiler to optimize your code to nothing. For example, the compiler likely turns 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);
}

Into this:

void arrr()
{
  LARGE_INTEGER start,end;
  QueryPerformanceCounter(&start);

  QueryPerformanceCounter(&end);

  arr_time += (end.LowPart - start.LowPart);
}

In the static array code, the compiler can tell the memory is never accessed again because once the function returns, its stack goes away. In the dynamic case, it can't because it doesn't know that once memory is freed, its value doesn't matter. The first loop likely has to stay but the second loop is likely totally removed in the dynamic case.

You aren't measuring what you think you're 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's another difference too. In the static array case, the compiler knows that no external function (like QueryPerformanceCounter) can depend on, or modify, the contents of the array. In the dynamic case, it can't know that. The position of QueryPerformanceCounter could be changed relative to the loops. For example, the compiler could move both calls to QueryPerformanceCounter together, to after the loop, in the static case but not in the dynamic case. (Unless Microsoft used some tricks to prevent this.)

Answer 2

With regards to array access in general (and not your current code), if you turn optimizations on in the compiler, then there really shouldn't be any difference between dynamic and static arrays when accessing a bunch of elements sequentially in memory. On the other-hand, if all optimizations are turned off, then for the dynamic array, there is an implicit loading of the memory address stored in the pointer variable that has to take place when you use the [] operator with the pointer before any dereferencing takes place. So that's an extra operation that is not present with static or stack-allocated arrays. But again, with any optimizations turned on, the pointer would get stored in a register and offset from there, so there would not be any difference between the two after the first access of the pointer.

Answer 3

As David said above, it is likely you're not actually measuring what you think you are due to optimization. Here is your code with some changes to make sure nothing being timed is optimized out.

With this code, in a release build with Visual Studio 2008 and 2010, the times are almost identical as is the assembly code generated by each function. The dynamic time, for me, is always slightly less than the static time, but by such a tiny amount I'd say 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;
}