Хороший способ сделать быстрое разделение в C ++?

Question

Иногда я вижу и использую следующий вариант для быстрого деления в C ++ с числами с плавающей запятой.

// orig loop
double y = 44100.0;
for(int i=0; i<10000; ++i) {
double z = x / y;
}

// alternative
double y = 44100;
double y_div = 1.0 / y;

for(int i=0; i<10000; ++i) {
double z = x * y_div;
}

Но кто-то недавно намекнул, что это может быть не самый точный способ.

Есть мысли?

Answer 1

Практически на каждом процессоре деление с плавающей запятой в несколько раз дороже, чем умножение с плавающей запятой, поэтому умножение на обратное значение делителя является хорошей оптимизацией. Недостатком является то, что существует вероятность того, что вы потеряете очень небольшую долю точности на некоторых процессорах - например, на современных процессорах x86 64-битные операции с плавающей запятой фактически вычисляются внутренне с использованием 80 бит при режим FPU по умолчанию и сохранение его в переменной приведет к тому, что эти биты дополнительной точности будут усечены в соответствии с вашим режимом округления FPU (по умолчанию ближайший). Это действительно имеет значение, только если вы объединяете много операций с плавающей запятой и вам нужно беспокоиться о накоплении ошибок.

Answer 2

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

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

Answer 3

Ваш оригинал

// original loop:
double y = 44100.0;

for(int i=0; i<10000; ++i) {
    double z = x / y;
}

можно легко оптимизировать до

// haha:
double y = 44100.0;
double z = x / y;

и производительность довольно хорошая. ; -)

РЕДАКТИРОВАТЬ: Люди продолжают голосовать, так что вот не такая забавная версия:

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

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

Answer 4

В вашем примере с использованием gcc деление с параметрами -O3 -ffast-math дает тот же код, что и умножение без -ffast-math. (В тестовой среде с достаточным количеством летучих компонентов цикл все еще существует.)

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

Answer 5

При обработке аудио я предпочитаю использовать математику с фиксированной точкой. Я полагаю, это зависит от того уровня точности, который вам нужен. Но давайте предположим, что подойдут целые числа 16,16 с фиксированной запятой (то есть старшие 16 бит - это целое число, младшие 16 - дробь). Теперь все вычисления можно выполнить в виде простой целочисленной математики:

unsigned int y = 44100 << 16;
unsigned int z = x / (y >> 16);  // divisor must be the whole number portion

Или с макросами, чтобы помочь:

#define FP_INT(x) (x << 16)
#define FP_MUL(x, y) (x * (y >> 16))
#define FP_DIV(x, y) (x / (y >> 16))

unsigned int y = FP_INT(44100);
unsigned int z = FP_MUL(x, y);

Answer 6

Аудио, да? Это не просто 44 100 делений в секунду, когда у вас есть, скажем, пять звуковых дорожек одновременно. Ведь даже простой фейдер потребляет циклы. И это только для довольно скромного, минимального примера - что если вы хотите иметь, скажем, эквалайзер и компрессор? Может быть, немного реверберации? Ваш общий математический бюджет, так сказать, быстро съедается. имеет смысл в этих случаях немного увеличить производительность.

Профилировщики хороши. Профилировщики - ваш друг. Профилировщики заслуживают минетов и пудинга. Но вы уже знаете, где находится основная «горловина» в работе с аудио - именно в цикле обрабатываются сэмплы, и чем быстрее вы сможете это сделать, тем счастливее будут ваши пользователи. Используйте все, что можете! Умножьте на взаимные, сдвигайте биты всякий раз, когда это возможно (exp (x * y) = exp (x) * exp (y), в конце концов), используйте таблицы поиска, обращайтесь к переменным по ссылке вместо значений (меньше нажатия / выталкивания в стеке ), условия рефакторинга и так далее. (Если вы хороши, вы будете смеяться над этими элементарными оптимизациями.)

Answer 7

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

Answer 8

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

Answer 9

Я предполагаю из исходного поста, что x не является константой, показанной там, но, вероятно, данные из массива, так что x [i], вероятно, будет источником данных, и аналогично для вывода, он будет храниться где-то в памяти .

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

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

Answer 10

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

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

Практически никогда не стоит таких небольших микрооптимизаций.

Постарайтесь сделать ваш код простым и защищенным от идиотов. Только у вас найдется реальное узкое место (с использованием профилировщика), и вы подумаете об оптимизации в вычислениях с плавающей запятой.