Tips for Geeks. Часть 1

Периодически буду выкладывать тут различные советы для любителей оптимизировать все, что можно и что нельзя. :) Нередко прирост производительности от подобных решений минимален, но иногда встречаются задачи, где важен каждый такт процессорного времени. Большая часть типсов связана с программированием на C++, но могут встречаться и алгоритмические нюансы, применимые к любому языку.

Итого, первый tip. Перебор массива байт.

На первый взгляд, что может быть проще? К примеру, подсчет суммы всех байт массива на С++:

int summ(char * data, size_t length)
{
    int result = 0;
    for(size_t i=0;i<length;i++)
        result+=data[i];
    return result;
}

Нормальному человеку я порекомендую оставить этот код как есть. Он работает очень быстро на современных компьютерах и при этом идеально читабелен.
Если же вспомнить, что мы живем в эпоху 32-битных вычислений, а на пороге уже и 64-битные, то оперировать 8-битными числами получается как-то несерьёзно и расточительно.
Я опущу долгие рассуждения и приведу сразу финальный код:

int summ(char * data, size_t length)
{
    int result = 0;
    int nlength = length & ~3;

    size_t i = 0;
    for(; i < nlength; i += 4)
        for(size_t j=0; j < 4; j++)
            result += data[i + j];

    for(; i < length; i++)
        result += data[i];

    return result;
}

Как видно по коду, операция прохода по массиву выполняется в два больших цикла и когда, к примеру, length = 18, первый цикл будет идти от 0 до 15, а второй - от 16 до 17. Цикл с переменной j будет развернут в присваивания со смещением буквально любым компилятором, потому на нем можно не заострять внимание.
Приведенный код приблизительно в полтора раза быстрее побайтового перебора, но при этом гораздо менее читабелен. Еще лучше будет результат если использовать шаг не 4, а 8 байт, но тут уже прирост не так заметен. Если же стоит задача считать не просто сумму, а выполнять на лету шифрование (XOR с константой или номером элемента и пр.), то производительность уже будет зависеть именно от внутренних операций, а не от организации перебора. При этом, чем сложнее код, тем больше ошибок в нём можно допустить.

Мораль же сей басни такова:

Premature optimization is the root of all evil. (c) Knuth, Donald. 1974

Очень многим людям я бы посоветовал распечатать эту аксиому и повесить на стену в сами видном месте.