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;
}

Your code is optimized to the point where it's meaningless. The compiler can entirely eliminate your second loop. You aren't measuring anything. — David Schwartz
– David Schwartz, Commented Dec 2, 2012 at 11:13
You should at the very least initialize arr_time and darr_time to 0.. — juanchopanza
– juanchopanza, Commented Dec 2, 2012 at 11:17
I don't know windows. But on many OS, the first access to that memory would be slower. Static array is on stack, Dynamic is on heap. You should access them once before your benchmark. . and, ya, this "benchmark" is mostly optimized away by your compiler because it have no side effect. Leaving only the initialization code — J-16 SDiZ
– J-16 SDiZ, Commented Dec 2, 2012 at 11:18

David Schwartz · Accepted Answer · 2012-12-02 11:17:37Z

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.)

You should also be using the QuadPart rather than just the LowPart of the LARGE_INTEGER when you subtract the times.

Jason · Accepted Answer · 2012-12-02 18:17:43Z

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.

edited Dec 2, 2012 at 18:17

answered Dec 2, 2012 at 11:16

Jason

32.7k8 gold badges63 silver badges81 bronze badges

2 Comments

Jason Over a year ago

To clarify what I'm talking about, with a pointer and the [] operator, the indexing operation with no optimizations devolves into *(pointer + index * sizeof(type)). While the multiplication step is typically done at compile-time so that it's not a performance hit, the value of the address stored in the pointer variable must be fetched. That is the "extra" step that doesn't have to take place with a static array or a stack-allocated array. With the stack, the base-pointer the activation record is always in a register, and the static array uses a place-holder resolved by the linker.

Jason Over a year ago

Of course with optimizations, the pointer value is stored in a register. Thus after the caching of the pointer value, the operation devolves into the same process as a stack-based array indexing operation.

Retired Ninja · Accepted Answer · 2012-12-02 12:30:06Z

1

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;
}

answered Dec 2, 2012 at 12:30

Retired Ninja

4,9253 gold badges27 silver badges37 bronze badges

2 Comments

vivek Over a year ago

Thanks , this code shows close time for all, normal array, vector,dynamic array,boost array. i think i should go with vector(next best after static) as i need dynamic allocation.

vivek Over a year ago

code is running under vs 2012 express on windows 7 x64 , code is in release x64 mode optimize for high performance.

Collectives™ on Stack Overflow

why dynamic array are slower than static array

3 Answers 3

1 Comment

2 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related