Производительность медленного массива кучи

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

Есть идеи? Я использую mingw с cflags -01 -std = C++ 11 -fpermissive.

update4: Я должен сказать, что это фрагменты из моей программы, и есть тяжелые коды/функции, запущенные до и после. Блок scanline выполнялся в конце функции перед выходом.

Теперь с надлежащей программой тестирования. thks to @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 мс

heap_: 826.802000 мс

heap2: 686.401000 мс

Первый тест кучи с новым и удалить, 2x медленнее. (пейджинг, как предложено?)

Вторая куча с повторно используемым массивом кучи все еще на 1,2 раза медленнее. Но я предполагаю, что второй тест не так практичен, как правило, другие коды работают до и после, по крайней мере, для моего случая. Для моего случая мой pixel_ptr, конечно, выделяется только один раз во время инициализации prograim .

Но если у кого-то есть решения/идея ускорения, ответьте пожалуйста!

Я все еще недоумеваю, почему запись кучи намного медленнее, чем сегмент стека. Наверняка должны быть какие-то трюки, чтобы сделать кучу большего количества процессора/кеша.

Final обновление ?:

я снова, опять и разборки на этот раз, вдруг у меня есть идея, почему некоторые из моих контрольных точек не активировать. Программа выглядит подозрительно короче, поэтому я подозреваю, что корреспондент мог удалил избыточный фиктивный код, который я ввел, в котором объясняется, почему локальный массив магически во много раз быстрее.

Answer 1

Следующие два примера кода не должны отличаться в режиме исполнения с хорошей настройкой компилятора. Вероятно, ваш компилятор будет генерировать тот же код:

//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] = pixel_ptr[i]; 
} 

Попробуйте увеличить настройку оптимизации.

Answer 2

Мне было немного любопытно, поэтому я сделал тест, и действительно, я мог бы измерить разницу между стеком и кучей доступа.

Первое предположение заключается в том, что сгенерированная сборка отличается, но, взглянув на нее, она фактически идентична для кучи и стека (что имеет смысл, память не должна быть дискриминирована).

Если сборка такая же, разница должна быть от paging mechanism.Предполагается, что в стеке страницы уже выделены, но в куче первый доступ вызывает ошибку страницы и распределение страниц (невидимо, все это происходит на уровне ядра). Чтобы проверить это, я сделал тот же тест, но сначала я получил доступ к куче один раз перед измерением. Тест дал одинаковые времена для стека и кучи. Разумеется, я также выполнил тест, в котором я впервые обратился к куче, но только каждые 4096 байт (каждый 1024 int), а затем 8192, потому что страница обычно составляет 4096 байт. Результатом является то, что доступ только к каждому 4096 байт также дает одинаковое время для кучи и стека, но доступ к каждому 8192 дает разницу, но не так, как без предыдущего доступа вообще. Это связано с тем, что только половина страниц были доступны и распределены заранее.

Таким образом, ответ заключается в том, что на стеке страницы памяти уже выделены, но в куче страницы выделяются «на лету». Это зависит от политики подкачки ОС, но все основные ОС ПК, вероятно, имеют аналогичную.

Для всех тестов я использовал Windows с таргетингом на компилятор MS x64.

EDIT: Для теста я измерил одиночный, больший контур, поэтому в каждой ячейке памяти был только один доступ. delete При использовании массива и измерения одного и того же цикла множественное время должны давать одинаковые времена для стека и кучи, поскольку delete памяти, вероятно, не выделяют страницы, и они уже выделены для следующего цикла (если следующий new, выделенный на одно и то же пространство).