c++ - 堆数组性能慢

Question

我遇到了奇怪的内存访问性能问题，有什么想法吗？

int* pixel_ptr = somewhereFromHeap;

int local_ptr[307200]; //local

//this is very slow
for(int i=0;i<307200;i++){
  pixel_ptr[i] = someCalculatedVal ;
}

//this is very slow
for(int i=0;i<307200;i++){
  pixel_ptr[i] = 1 ; //constant
}

//this is fast
for(int i=0;i<307200;i++){
  int val = pixel_ptr[i];
  local_ptr[i] = val;
}

//this is fast
for(int i=0;i<307200;i++){
  local_ptr[i] = someCalculatedVal ;
}

尝试将值合并到本地扫描线

int scanline[640]; // local

//this is very slow
for(int i=xMin;i<xMax;i++){
  int screen_pos = sy*screen_width+i;
  int val = scanline[i];
  pixel_ptr[screen_pos] = val ;
}

//this is fast
for(int i=xMin;i<xMax;i++){
  int screen_pos = sy*screen_width+i;
  int val = scanline[i];
  pixel_ptr[screen_pos] = 1 ; //constant
}

//this is fast
for(int i=xMin;i<xMax;i++){
  int screen_pos = sy*screen_width+i;
  int val = i; //or a constant
  pixel_ptr[screen_pos] = val ;
}

//this is slow
for(int i=xMin;i<xMax;i++){
  int screen_pos = sy*screen_width+i;
  int val = scanline[0];
  pixel_ptr[screen_pos] = val ;
}

有什么想法吗？我正在使用带有 cflags -01 -std=c++11 -fpermissive 的 mingw。

更新4:我不得不说，这些是我程序的片段，前后运行了大量代码/函数。扫描线 block 确实在退出前在函数末尾运行。

现在有了适当的测试程序。感谢@Iwillnotexist。

#include <stdio.h>
#include <unistd.h>
#include <sys/time.h>

#define SIZE 307200
#define SAMPLES 1000

double local_test(){
    int local_array[SIZE];

    timeval start, end;
    long cpu_time_used_sec,cpu_time_used_usec;
    double cpu_time_used;

    gettimeofday(&start, NULL);
    for(int i=0;i<SIZE;i++){
        local_array[i] = i;
    }
    gettimeofday(&end, NULL);
    cpu_time_used_sec = end.tv_sec- start.tv_sec;
    cpu_time_used_usec = end.tv_usec- start.tv_usec;
    cpu_time_used = cpu_time_used_sec*1000 + cpu_time_used_usec/1000.0;

    return cpu_time_used;
}

double heap_test(){
    int* heap_array=new int[SIZE];

    timeval start, end;
    long cpu_time_used_sec,cpu_time_used_usec;
    double cpu_time_used;

    gettimeofday(&start, NULL);
    for(int i=0;i<SIZE;i++){
        heap_array[i] = i;
    }
    gettimeofday(&end, NULL);
    cpu_time_used_sec = end.tv_sec- start.tv_sec;
    cpu_time_used_usec = end.tv_usec- start.tv_usec;
    cpu_time_used = cpu_time_used_sec*1000 + cpu_time_used_usec/1000.0;

    delete[] heap_array;

    return cpu_time_used;
}


double heap_test2(){
    static int* heap_array = NULL;

    if(heap_array==NULL){
        heap_array = new int[SIZE];
    }

    timeval start, end;
    long cpu_time_used_sec,cpu_time_used_usec;
    double cpu_time_used;

    gettimeofday(&start, NULL);
    for(int i=0;i<SIZE;i++){
        heap_array[i] = i;
    }
    gettimeofday(&end, NULL);
    cpu_time_used_sec = end.tv_sec- start.tv_sec;
    cpu_time_used_usec = end.tv_usec- start.tv_usec;
    cpu_time_used = cpu_time_used_sec*1000 + cpu_time_used_usec/1000.0;

    return cpu_time_used;
}


int main (int argc, char** argv){
    double cpu_time_used = 0;

    for(int i=0;i<SAMPLES;i++)
        cpu_time_used+=local_test();

    printf("local: %f ms\n",cpu_time_used);

    cpu_time_used = 0;

    for(int i=0;i<SAMPLES;i++)
        cpu_time_used+=heap_test();

    printf("heap_: %f ms\n",cpu_time_used);

    cpu_time_used = 0;

    for(int i=0;i<SAMPLES;i++)
        cpu_time_used+=heap_test2();

    printf("heap2: %f ms\n",cpu_time_used);

}

没有优化。

本地:577.201000 毫秒

堆_:826.802000 毫秒

堆 2:686.401000 毫秒

使用 new 和 delete 的第一个堆测试慢了 2 倍。 (按照建议分页？)

具有重用堆数组的第二个堆仍然慢 1.2 倍。但我想第二个测试不太实用，因为至少在我的情况下，在前后运行其他代码。对于我的情况，我的 pixel_ptr 当然只分配一次程序初始化。

但如果有人有加快速度的解决方案/想法，请回复!

我仍然很困惑为什么堆写入比堆栈段慢得多。肯定有一些技巧可以使堆更适合 cpu/缓存。

最终更新？

我重新访问，再次反汇编，这一次，突然我知道为什么我的一些断点不要激活。该程序看起来短得可疑，因此我怀疑编译器可能删除了我放入的冗余虚拟代码，这解释了为什么本地数组神奇地快了很多倍。

Answer 1

我有点好奇所以我做了测试，我确实可以测量堆栈和堆访问之间的差异。

第一个猜测是生成的程序集不一样，但仔细一看，堆和栈其实是一样的(有道理，内存不应该有区别)。

如果程序集相同，那么差异一定来自paging mechanism .猜测是在堆栈上，页面已经分配，​​但在堆上，第一次访问导致页面错误和页面分配(看不见，这一切都发生在内核级别)。为了验证这一点，我做了同样的测试，但首先我会在测量之前访问堆一次。测试给出了堆栈和堆相同的时间。可以肯定的是，我也做了一个测试，我首先访问了堆，但只是每 4096 字节(每 1024 int)，然后是 8192，因为页面通常是 4096 字节长。结果是，仅访问每 4096 个字节也为堆和堆栈提供了相同的时间，但访问每 8192 个字节提供了差异，但没有以前完全没有访问那么多。这是因为只有一半的页面被预先访问和分配。

所以答案是，在堆栈上，内存页面已经分配，​​但在堆上，页面是动态分配的。这取决于操作系统的分页策略，但所有主要的 PC 操作系统可能都有类似的策略。

对于所有测试，我使用的是 Windows，以及针对 x64 的 MS 编译器。

编辑:为了测试，我测量了一个更大的循环，因此每个内存位置只有一次访问。 delete数组并多次测量同一个循环应该为堆栈和堆提供相似的时间，因为deleteing 内存可能不会取消分配页面，并且它们已经为下一个循环分配了(如果下一个new分配在相同的空间)。