Предопределение часто используемых значений в вычислениях - это что-то меняет?

Question

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

В качестве простого примера, скажем, мы вычисляем что-то в форме:

#include <cmath>
double test(double x, double y) {
    const double c[9][9] = { ... }; // constants properly initialized, irrelevant
    double expr =   c[0][0]*x*y 
                  + c[1][0]*pow(x,2)*y        + ... + c[8][0]*pow(x,9)*y 
                  + c[1][1]*pow(x,2)*pow(y,2) + ... + c[8][1]*pow(x,9)*pow(y,2)
                  + ...

со всеми c[i][j] правильно инициализирован. В действительности эти выражения содержат десятки миллионов умножений и сложений.

Теперь коллега предложил - уменьшить количество вызовов pow() и кэшировать часто необходимые значения в выражениях - определить каждую степень x и y в отдельной переменной, что не составляет особого труда, так как код автоматически генерируется в любом случае, вот так:

double xp2 = pow(x,2);
double xp3 = pow(x,3);
double xp4 = pow(x,4);
// ...
// same for pow(y,n)

Однако я думаю, что это не нужно, поскольку компилятор должен позаботиться об этих оптимизациях.

К сожалению, у меня нет опыта чтения и интерпретации ассемблера, но я думаю, что вижу, что все вызовы pow() оптимизированы, верно? Кроме того, компилятор кеширует значения для pow(x,2), pow(x,3) и т. Д.?

Спасибо заранее за ваш вклад!

Answer 1

С помощью pow с целочисленными аргументами... ой! Типичные реализации pow настроены на общий случай аргументов с плавающей запятой, поэтому запись обычно медленнее

pow(x, 2) ( = exp(2 * log(x)) )

чем

x * x

То, что я здесь заявляю, очень зависит от компилятора. С одной стороны, некоторые компиляторы могут даже не знать, что pow(x, 2) даст одинаковое значение для данного x (в конце концов, внешняя функция pow может иметь побочные эффекты), поэтому у вас нет никакой гарантии, что общие подвыражения будут устранены. pow Функция, на некоторых (многих?) платформах / цепочках инструментов, предоставляется библиотекой, над которой компилятор не имеет никакого контроля.

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

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

double x2 = x * x;
double x3 = x * x2;
double x4 = x2 * x2;

Обратите внимание, что (кредиты @Stephen Canon), выполняющие повторные умножения (с вышеупомянутой схемой быстрого возведения в степень), внесут ошибку округления, величина которой пропорциональна количеству умножений (то есть O(логарифмический показатель)). Эта ошибка обычно допустима, но pow гарантирует точность в пределах одной единицы наименьшей точности.

Answer 2

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

Answer 3

Хороший способ вычисления полиномов - это правило Хорнера. (например, здесь), который не требует pow() или дополнительной памяти. Ваше выражение x*y умножается на полином по y, каждый из коэффициентов которого является полиномом по x.

Каждый из этих коэффициентов может быть рассчитан с использованием Horner с 8 умножениями и сложениями, а полиномиал по y с еще 8 умножениями и сложениями, в общей сложности 74 умножения и 72 сложения, тогда как ваш пример кода выглядит для меня как более 200 умножений и более чем сто звонков в pow().

Answer 4

pow может быть оптимизирован в зависимости от набора инструментов. Единственный способ узнать это - попробовать и посмотреть.

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

Answer 5

Профиль, узнай, где находятся узкие места.

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

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

Возможно, вы захотите изолировать вычисления в выражениях, включающих одну переменную. Компиляторы могут оптимизировать код лучше, когда используется или изменяется только одна переменная за раз. Например, заменить y переменная с выражениями, включающими x, если возможно. Это привело бы к выражению только с участием x,

Также поищите в Интернете "управляемый данными дизайн" или "ориентированный на данные дизайн". Эти сайты показывают, как оптимизировать код для приложений, ориентированных на данные.