2D Dynamic Array in C: Какой из этих 3 фрагментов выполняется быстрее?

Question

gprof не работает должным образом в моей системе (MinGW), поэтому я хотел бы знать, какой из следующих фрагментов в среднем более эффективен.

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

Массив был динамически размещен в смежной памяти как 1d массив и может быть перераспределен во время выполнения (это для простой настольной игры, в которой игроку разрешено переопределять размер доски так часто, как он хочет).

Обратите внимание, что i & j должен вычисляться и передаваться в функцию set_cell () при каждой итерации цикла (gridType - это простая структура с несколькими целыми числами и указателем на другую структуру ячейки).

Заранее спасибо!

Выделить память

grid = calloc( (nrows * ncols), sizeof(gridType) );

Фрагмент # 1 (последовательно разобрать как 1D)

gridType *gp = grid;
register int i=0 ,j=0;      // we need to pass those in set_cell()

if ( !grid )
return;

for (gp=grid; gp < grid+(nrows*ncols); gp++)
{
    set_cell( gp, i, j, !G_OPENED, !G_FOUND, value, NULL );

    if (j == ncols-1) {     // last col of current row has been reached
        j=0;
        i++;
    }
    else                    // last col of current row has NOT been reached
        j++;
}

Фрагмент # 2 (разбор как 2D-массив, используя только указатели)

gridType *gp1, *gp2;

if ( !grid )
    return;

for (gp1=grid; gp1 < grid+nrows; gp1+=ncols)
    for (gp2=gp1; gp2 < gp1+ncols; gp2++)
        set_cell( gp2, (gp1-grid), (gp2-gp1), !G_OPENED, !G_FOUND, value, NULL );

Фрагмент # 3 (разобрать как 2D, используя только счетчики)

register int i,j;           // we need to pass those in set_cell()

for (i=0; i<nrows; i++)
    for (j=0; j<ncols; j++)
        set_cell( &grid[i * ncols + j], i, j, !G_OPENED, !G_FOUND, value, NULL);

Свободная память

free( grid );

EDIT: Я исправил # 2 формы gp1 ++) в gp1 + = ncols), в 1-м цикле, после поправки Пола (спасибо!)

Answer 1

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

Тем не менее, это яркий пример преждевременной оптимизации. Лучшее, что можно сделать, это выбрать фрагмент, который выглядит наиболее понятным и удобным для обслуживания. Вы получите гораздо больше пользы от этого в долгосрочной перспективе, чем от любой экономии, которую вы бы сделали, выбрав самый быстрый на вашей машине (который в любом случае может быть не самым быстрым на чужой!)

Answer 2

Ну, фрагмент 2 не совсем работает.Вам нужно другое приращение поведения;внешний цикл должен выглядеть следующим образом: for (gp1 = grid; gp1 < grid + (nrows * ncols); gp1 += ncols).

Из двух других, любой обращающий внимание компилятор почти наверняка преобразует фрагмент 3 во что-то эквивалентное фрагменту 1. Но на самом деле, нет способа узнать без их профилирования.

Также запомните слова Кнута: «Преждевременная оптимизация - корень всего зла. Я видел больше ущерба, нанесенного во имя« оптимизации », чем для всех других причин, вместе взятых», , включая явное,ошибочная глупость . "Люди, которые пишут компиляторы, умнее вас (если вы не являетесь тайным Кнутом или Хофштадтером), поэтому позвольте компилятору выполнять свою работу, и вы можете продолжать свою.Попытка написать «умный» оптимизированный код обычно приводит в замешательство компилятор, мешая ему писать еще лучший, более оптимизированный код.

Answer 3

Я бы так написал.ИМХО это короче, понятнее и проще любого из ваших способов.

int i, j;
gridType *gp = grid;

for (i = 0; i < nrows; i++)
    for (j = 0; j < ncols; j++)
        set_cell( gp++, i, j, !G_OPENED, !G_FOUND, value, NULL );

Answer 4

1. gprof не работает не реальное оправдание.Вы все еще можете установить эталонный тест и измерить время выполнения.
2. Вы не сможете измерить разницу на современных процессорах, пока nrows*ncols не станет очень большим или не произойдет перераспределение очень часто, так что вы можете оптимизировать не ту часть кода.
3. Это, конечно, микрооптимизация, так как большая часть времени выполнения, скорее всего, будет потрачена на set_cell, а все остальное можно оптимизировать длятот же или очень похожий код компилятором.

Answer 5

Вы не знаете, пока не измерите.

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