Блог

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

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

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

Пожалуйста, обратите внимание, что i amp; 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( amp;grid[i * ncols   j], i, j, !G_OPENED, !G_FOUND, value, NULL);
  

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

 free( grid );
  

Редактировать:
Я исправил # 2 с gp1 ) на gp1 = ncols) в 1-м цикле, после исправления Пола (спасибо!)

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

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

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

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

Кроме того, помните слова Кнута: «Преждевременная оптимизация — КОРЕНЬ ВСЕГО ЗЛА. Я видел больше ущерба, нанесенного во имя «оптимизации», чем по всем другим причинам вместе взятым, включая явную ошибочную глупость. » Люди, которые пишут компиляторы, умнее вас (если только вы не Кнут или Хофштадтер), поэтому позвольте компилятору выполнять свою работу, а вы можете заняться своей. Попытки написать «умный» оптимизированный код обычно просто сбивают компилятор с толку, не позволяя ему написать еще лучший, более оптимизированный код.

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

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

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

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

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