C # / XNA - Умножение быстрее, чем деление? - PullRequest
Новая
       14

C # / XNA - Умножение быстрее, чем деление?

9 голосов
/ 20 февраля 2011

Я недавно видел твит, который смутил меня (он был опубликован кодером XNA в контексте написания игры XNA):

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

Я был довольно удивлен, потому что я всегда думал, что компиляторы были довольно умными (например, с использованием битового сдвига), и недавно прочитал пост Шона Харгривза, в котором говорилось о том же . Мне было интересно, сколько в этом было правды, поскольку в моей игре много вычислений.

Я спросил, надеясь на образец, однако оригинальный постер не смог его дать. Он, однако, сказал это:

Не обязательно, когда это что-то вроде "center = width / 2". И я уже определил "да, оно того стоит". :)

Итак, мне любопытно ...

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

Ответы [ 5 ]

7 голосов
/ 20 февраля 2011

Большинство компиляторов могут выполнять разумную работу по оптимизации, когда вы даете им шанс. Например, если вы делите на константу , вполне вероятно, что компилятор может / будет оптимизировать это, так что это делается почти так же быстро, как и все, что вы можете разумно заменить.

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

Изменить: Ваша лучшая ставка на что-то подобное (это довольно реалистично), вероятно, будет что-то вроде: 

double scale_factor = get_input();

for (i=0; i<values.size(); i++)
    values[i] /= scale_factor;

Это относительно легко преобразовать во что-то вроде: 

scale_factor = 1.0 / scale_factor;

for (i=0; i<values.size(); i++)
    values[i] *= scale_factor;

Я не могу действительно так или иначе гарантировать, что конкретный компилятор сделает это. Это в основном сочетание снижения прочности и подъема петли. Конечно, есть оптимизаторы, которые знают, как сделать то и другое, но то, что я видел в компиляторе C #, говорит о том, что это не так (но я никогда не проверял ничего подобного, и тестирование, которое я проводил, было несколько версий назад ...)

4 голосов
/ 20 февраля 2011

Хотя компилятор может оптимизировать деления и умножения на степени 2, другие числа могут быть трудными или невозможными для оптимизации.Попробуйте оптимизировать деление на 17, и вы поймете, почему.Это, конечно, при условии, что компилятор не знает, что вы делите на 17 раньше времени (это переменная времени выполнения, а не константа).

3 голосов
/ 25 мая 2011

Немного поздно, но неважно.

Ответ на ваш вопрос - да.

Посмотрите мою статью здесь, http://www.codeproject.com/KB/cs/UniqueStringList2.aspx,, в которой используется информация, основанная на статье, упомянутой в первом комментарии к вашему вопросу.

У меня есть структура QuickDivideInfo, в которой хранится магическое число и сдвиг для данного делителя, что позволяет вычислять деление и модуль по быстрому умножению. Я предварительно вычислил (и протестировал!) QuickDivideInfos для списка золотых простых чисел. По крайней мере, для x64 метод .Divide в QuickDivideInfo является встроенным и в 3 раза быстрее, чем использование оператора деления (в i5); он работает для всех числителей, кроме int.MinValue, и не может переполниться, поскольку перед сдвигом умножение хранится в 64 битах. (Я не пробовал на x86, но если по каким-то причинам он не встроен, то аккуратность метода Divide будет потеряна, и вам придется вручную встроить его).

Таким образом, вышеприведенное будет работать во всех сценариях (кроме int.MinValue), если вы можете выполнить предварительный расчет. Если вы доверяете коду, который генерирует магическое число / сдвиг, то вы можете иметь дело с любым делителем во время выполнения.

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

Деление на кратное двух: я ожидаю, что компилятор будет иметь дело с этим (как в вашей ширине / 2) примером, поскольку он является константой. Если этого не произойдет, измените его на ширину >> 1 должно быть в порядке

0 голосов
/ 06 апреля 2019 
 while(start<=end)
    {
    int mid=(start+end)/2;
    if(mid*mid==A)
    return mid;
    if(mid*mid<A)
    {
    start=mid+1;
    ans=mid;
    }

Если я поступаю таким образом, результатом является ПРЕВЫШЕНИЕ ВРЕМЕНИ для квадратного корня из 2147483647

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

while(start<=end)
    {
    int mid=(start+end)/2;
    if(mid==A/mid)
    return mid;
    if(mid<A/mid)
    {
    start=mid+1;
    ans=mid;
    }
    else
    end=mid-1;
    }
0 голосов
/ 20 февраля 2011

Чтобы дать некоторые цифры, в этом PDF-файле

http://cs.smith.edu/dftwiki/index.php/CSC231_Pentium_Instructions_and_Flags

из Pentium мы получаем некоторые цифры, и они не очень хороши:

  • IMUL 10 или 11
  • FMUL 3 + 1
  • IDIV 46 (32-битный операнд)
  • FDIV 39

Мы говорим о БОЛЬШИХ различиях

...