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

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 (в конце концов, функция extern 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.

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

Answer 4

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

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

Answer 5

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

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

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

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

Также ищите в Интернете «управляемый данными дизайн» или «ориентированный на данные дизайн». На этих сайтах показано, как оптимизировать код для приложений, ориентированных на данные.