为什么动态数组比静态数组慢

Question

在我目前的项目中,我需要对大数据阵列进行操作.所以我做了一个愚蠢的测试来检查哪一个会更好,但在尝试下面的代码时我发现动态数组比静态数组慢得多为什么呢？或者我做错了什么？

这里是代码(我从这里删除矢量(执行等于动态)和增强数组(等于静态))

结果:静态8,动态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

您的代码不会对其计算的值执行任何操作,从而允许编译器将代码优化为零.例如,编译器可能会转为:

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 arrr()
{
  LARGE_INTEGER start,end;
  QueryPerformanceCounter(&start);

  QueryPerformanceCounter(&end);

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

在静态数组代码中,编译器可以告诉永远不再访问内存,因为一旦函数返回,它的堆栈就会消失.在动态的情况下,它不能,因为它不知道一旦释放内存,它的价值无关紧要.第一个循环可能必须保留,但第二个循环可能在动态情况下完全删除.

你没有衡量你认为你在测量的东西.

你可以尝试这样的事情:

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

还有另一个不同之处.在静态数组的情况下,编译器知道没有外部函数(例如QueryPerformanceCounter)可以依赖或修改数组的内容.在动态的情况下,它无法知道.QueryPerformanceCounter可以相对于循环改变位置.例如,编译器可以将两个调用QueryPerformanceCounter一起移动到循环之后,在静态情况下但不在动态情况下.(除非微软使用一些技巧来防止这种情况.)

Answer 2

正如大卫上面所说，你很可能实际上并没有衡量你认为优化带来的效果。这是您的代码，进行了一些更改，以确保没有任何超时被优化。

使用此代码，在 Visual Studio 2008 和 2010 的发布版本中，时间几乎与每个函数生成的汇编代码相同。对我来说，动态时间总是略小于静态时间，但我认为它们是等价的。

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