Жертвуем скоростью ради памяти

- Упаковка. Способы уплотненного представления данных позволяют уменьшить затраты памяти за счет быстроты обращения к этим данным.

- Интерпретаторы. Объем кода программы часто может быть уменьшен с помощью интерпретаторов, позволяющих компактно представить последовательности часто используемых операторов.

Циклы

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

- Совмещение проверок. Внутренний цикл должен содержать минимально возможное количество проверок, а лучше всего только одну. Программист должен стараться уменьшить количество условий завершения цикла их объединением.

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

- Раскрытие циклов передачи. Если большая часть внутреннего цикла состоит в тривиальных операциях присваивания, их часто можно удалить из цикла, если перепланировать использование переменных. Чтобы исключить присваивание i=j, нужно в последующем коде ставить вместо переменной i переменную j.

- Удаление безусловных переходов. В быстром цикле не должно быть безусловных переходов. Безусловный переход в конце цикла может быть удален путем «поворота» этого цикла таким образом, чтобы в конце его оказалось условное ветвление. Эта операция обычно выполняется оптимизирующими компиляторами.

- Слияние циклов. Если два соседних цикла работают с одним и тем же набором элементов, то их тела следует объединить, чтобы осталась только одна управляющая конструкция (заголовок цикла).

Логические правила

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

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

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

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

- Удаление булевских переменных. Булевские переменные могут быть убраны из программы с помощью замены операции присваивания такой переменной некоторого значения оператором if…else, в котором одна ветвь относится к случаю, когда переменная истинна, а другая – к случаю, когда эта переменная оказывается ложной.

Составление процедур

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

- Учитывать частоту ситуаций. Функции должны правильно обрабатывать все возможные ситуации и быть наиболее эффективными в наиболее часто возникающих ситуациях.

- Сопрограммы. Многопроходный алгоритм может быть переделан в однопроходный с помощью сопрограмм.

- Трансформация рекурсивных функций. Время выполнения рекурсивных функций может быть уменьшено применением следующих трансформаций:

- замена рекурсии итерацией, как в программах со списками и двоичными деревьями,

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

- если в самом конце тела функции делается вызов этой же функции, его можно заменить на безусловный переход к началу функции. Это часто называется «удалением концевой рекурсии». Такое ветвление часто может быть преобразовано в цикл,

- часто оказывается более эффективным решать небольшие подзадачи внешними процедурами, а не выполнять рекурсию до задачи размером 0 или 1.

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

Составление выражений

- Инициализация во время компиляции. Максимальное количество переменных следует инициализировать до запуска программы.

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

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

- Парное вычисление. Если два одинаковых выражения часто вычисляются подряд, их следует вынести во внешнюю функцию.

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