Адресная арифметика - оптимизация или нет?

#include <iostream>
#include <ctime>

int main() {

    int **p_head;
    int **p_temp;
    int *p_curr;

    int size_x = 10000; // размеры массива
    int size_y = 10000;

    p_head = new int *[size_y]; // создаем массив указателей на "строки"
    p_temp = p_head;

//======= таймер =======
    clock_t the_time;
    int elapsed_time;
    the_time = clock();
//======================

    for (int y=0; y<size_y; y++) {
        p_head[y] = new int [size_x]; // создаем "строку"

// === Фрагмент 1 ===
// адресация посредством нотации массивов - 312 ms
        for (int x=0; x<size_x; x++) p_head[y][x] = 0; // инициализируем

// === Фрагмент 2 ===
// адресация посредством адресной арифметики - разницы в корости нет
//      for (int x=0; x<size_x; x++) *(*(p_head + y) + x) = 0;

// === Фрагмент 3 ===
// есть совсем небольшое улучшение - 296 ms
//      for (int x=0; x<size_x; x++) *(*p_temp + x) = 0;
//      p_temp++;

// === Фрагмент 4 ===
// еще чуток - 281 ms
//      p_curr = *p_temp;
//      for (int x=0; x<size_x; x++) *p_curr++ = 0;
//      p_temp++;

    }

//  for (int y=0; y<size_y; y++) delete [] p_head[y]; // удаляем "строки"
//  delete [] p_head; // удаляем массив указателей на "строки"

//======= таймер =======
    elapsed_time = clock() - the_time;
    std::cout << "Elapsed time: " << elapsed_time << " ms" << std::endl;
//======================

    return 0;
}

Как видно из примера, выигрыш по времени нарастает от фрагмента к фрагменту, но очень незначительно, в то время, как читабельность кода ухудшается весьма стремительно.

Применение спецификатора register к счетчикам вообще нивелирует разницу во времени, при этом значительно сокращая затраченное время: для любого фрагмента засечка времени показывает 203 ms.

Этот пост — результат того, что у Шилдта в «Полном справочнике по С++» (4 изд.) есть упоминание, что адресная арифметика часто используется, т.к. дает прирост производительности.

То, что в примере выше — и есть тот самый прирост, или есть вычисления с использованием массивов, в которых прирост заметен гораздо сильнее?

Оптимизация. Шилдт, по ходу, прав ;)

На самом деле, тема достаточно скользкая. Дело в том, что оптимизация происходит на многих этапах создания и работы программы:

1. Исходный код. Это как раз то, с чем ты попробовал поиграть.
2. Оптимизирующий компилятор. Разные компиляторы делают разную оптимизацию. Компиляторы делают разную оптимизацию в зависимости от указанного режима оптимизации.
3. Процессор. Сейчас эта штука тоже достаточно интеллектуальна сама по себе.

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

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

Для дальнейшей развлекухи можно посмотреть дизассемблированный код при включенной оптимизации (обычно в IDE режим Debug — без оптимизации, режим Release — с оптимизацией). А также сравнить время работы программы и дизассемблированный код разных компиляторов, например MS VS C++ и GNU g++ под Code::Blocks.

Что касается конкретно твоего примера, то фрагменты 1 и 2 при отключенной оптимизации компилятора, дают одинаковый код. Поэтому нет разницы во времени. Во фрагментах 3 и 4 ты, фактически, кэшируешь вычисленное значение одного или двух указателей. Т.е. вычисление адресов не нужно делать на каждом проходе цикла, а только загрузить из памяти. Если эти вычисленные значения адресов держать в регистре(ах) на протяжении выполнения всего цикла, то будет ещё быстрее, даже учитывая, что переменные сидят не в RAM, а в кэше процессора.

Кстати, эксперименты лучше делать с такой версией программы:

#include <iostream>
#include <ctime>

#define _FR1_
//#define _FR2_
//#define _FR3_
//#define _FR4_

int main() {

    int **p_head;
    int **p_temp3, **p_temp4;
    int *p_curr;

    int size_x = 10000; // размеры массива
    int size_y = 10000;

    p_head = new int *[size_y]; // создаем массив указателей на "строки"
    p_temp3 = p_temp4 = p_head;

    for (int y = 0; y < size_y; y++) {
        p_head[y] = new int[size_x]; // создаем "строку"
    }

    //======= таймер =======
    clock_t the_time;
    int elapsed_time;
    the_time = clock();
    //======================

    for (int y = 0; y < size_y; y++) {

#if defined _FR1_
        // === Фрагмент 1 ===
        // адресация посредством нотации массивов - 312 ms
        for (int x = 0; x < size_x; x++) 
            p_head[y][x] = 1;
#endif

#if defined _FR2_
        // === Фрагмент 2 ===
        // адресация посредством адресной арифметики - разницы в корости нет
        for (int x = 0; x < size_x; x++) 
            *(*(p_head + y) + x) = 2;
#endif

#if defined _FR3_
        // === Фрагмент 3 ===
        // есть совсем небольшое улучшение - 296 ms
        for (int x = 0; x < size_x; x++) 
            *(*p_temp3 + x) = 3;
        p_temp3++;
#endif

#if defined _FR4_
        // === Фрагмент 4 ===
        // еще чуток - 281 ms
        p_curr = *p_temp4;
        for (int x = 0; x < size_x; x++) 
            *p_curr++ = 4;
        p_temp4++;
#endif
    }


    //======= таймер =======
    elapsed_time = clock() - the_time;
    std::cout << "Elapsed time: " << elapsed_time << " ms" << std::endl;
    //======================

    for (int y = 0; y < size_y; y++) delete[] p_head[y]; // удаляем "строки"
    delete[] p_head; // удаляем массив указателей на "строки"

    return 0;
}

Cranium, спасибо! Как всегда — и рыбу и удочку :)