Должен ли я использовать умножение или деление? - PullRequest
111 голосов
/ 22 октября 2008

Вот глупый забавный вопрос:

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

y = x / 2.0;
// or...
y = x * 0.5;

Предполагая, что мы используем стандартные операторы, предоставляемые с языком, какой из них имеет лучшую производительность?

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

Хотя лично мне интересен ответ для Python 2.4-2.5, не стесняйтесь также публиковать ответ и для других языков! И если вы хотите, не стесняйтесь публиковать и другие причудливые способы (например, используя операторы побитового сдвига).

Ответы [ 25 ]

73 голосов
/ 22 октября 2008

Python:

time python -c 'for i in xrange(int(1e8)): t=12341234234.234 / 2.0'
real    0m26.676s
user    0m25.154s
sys     0m0.076s

time python -c 'for i in xrange(int(1e8)): t=12341234234.234 * 0.5'
real    0m17.932s
user    0m16.481s
sys     0m0.048s

умножение на 33% быстрее

Lua:

time lua -e 'for i=1,1e8 do t=12341234234.234 / 2.0 end'
real    0m7.956s
user    0m7.332s
sys     0m0.032s

time lua -e 'for i=1,1e8 do t=12341234234.234 * 0.5 end'
real    0m7.997s
user    0m7.516s
sys     0m0.036s

=> нет реальной разницы

LuaJIT:

time luajit -O -e 'for i=1,1e8 do t=12341234234.234 / 2.0 end'
real    0m1.921s
user    0m1.668s
sys     0m0.004s

time luajit -O -e 'for i=1,1e8 do t=12341234234.234 * 0.5 end'
real    0m1.843s
user    0m1.676s
sys     0m0.000s

=> это всего на 5% быстрее

выводы: в Python умножать быстрее, чем делить, но когда вы приближаетесь к ЦП с помощью более совершенных виртуальных машин или JIT, преимущество исчезает. Вполне возможно, что будущая Python VM сделает его неактуальным

62 голосов
/ 22 октября 2008

Всегда используйте то, что самое ясное. Все, что вы делаете, пытается перехитрить компилятор. Если компилятор достаточно интеллектуален, он сделает все возможное, чтобы оптимизировать результат, но ничто не сможет заставить следующего парня не ненавидеть вас за ваше дерьмовое решение с бит-смещением (кстати, мне нравится манипулирование битами, это весело. Но весело! = Читабельно) )

Преждевременная оптимизация - корень всего зла. Всегда помните три правила оптимизации!

  1. Не оптимизировать.
  2. Если вы эксперт, см. Правило № 1
  3. Если вы эксперт и можете обосновать необходимость, используйте следующую процедуру:

    • Код неоптимизированный
    • определить, насколько быстро «достаточно быстро» - обратите внимание, какое требование / история пользователя требует этот показатель.
    • Написать тест скорости
    • Проверка существующего кода - если он достаточно быстрый, все готово.
    • Перекодировать его оптимизировано
    • Проверка оптимизированного кода. Если он не соответствует метрике, выбросьте его и сохраните оригинал.
    • Если он соответствует требованиям теста, сохраните исходный код в виде комментариев

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

47 голосов
/ 22 октября 2008

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

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

37 голосов
/ 22 октября 2008

Умножение быстрее, деление более точное. Вы потеряете некоторую точность, если ваш номер не является степенью 2:

y = x / 3.0;
y = x * 0.333333;  // how many 3's should there be, and how will the compiler round?

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

x = 100.0;
x / 3.0 == x * (1.0/3.0)  // is false in the test I just performed

Проблема скорости, скорее всего, будет иметь значение только для языков C / C ++ или JIT, и даже тогда, только если операция находится в цикле при узком месте.

24 голосов
/ 18 марта 2009

Если вы хотите оптимизировать свой код, но по-прежнему ясно, попробуйте это:

y = x * (1.0 / 2.0);

Компилятор должен иметь возможность делить во время компиляции, так что вы получите умножение во время выполнения. Я ожидаю, что точность будет такой же, как в случае y = x / 2.0.

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

20 голосов
/ 27 декабря 2009

Просто собираюсь добавить что-то для опции «другие языки».
C: Поскольку это всего лишь академическое упражнение, которое на самом деле не имеет значения, я подумал, что внесу что-то другое.

Я скомпилировал сборку без оптимизации и посмотрел на результат.
Код:

int main() {

    volatile int a;
    volatile int b;

    asm("## 5/2\n");
    a = 5;
    a = a / 2;

    asm("## 5*0.5");
    b = 5;
    b = b * 0.5;

    asm("## done");

    return a + b;

}

скомпилировано с gcc tdiv.c -O1 -o tdiv.s -S

деление на 2:

movl    $5, -4(%ebp)
movl    -4(%ebp), %eax
movl    %eax, %edx
shrl    $31, %edx
addl    %edx, %eax
sarl    %eax
movl    %eax, -4(%ebp)

и умножение на 0,5:

movl    $5, -8(%ebp)
movl    -8(%ebp), %eax
pushl   %eax
fildl   (%esp)
leal    4(%esp), %esp
fmuls   LC0
fnstcw  -10(%ebp)
movzwl  -10(%ebp), %eax
orw $3072, %ax
movw    %ax, -12(%ebp)
fldcw   -12(%ebp)
fistpl  -16(%ebp)
fldcw   -10(%ebp)
movl    -16(%ebp), %eax
movl    %eax, -8(%ebp)

Однако, когда я изменил эти int с на double с (что, вероятно, и сделал бы Python), я получил это:

разделение:

flds    LC0
fstl    -8(%ebp)
fldl    -8(%ebp)
flds    LC1
fmul    %st, %st(1)
fxch    %st(1)
fstpl   -8(%ebp)
fxch    %st(1)

умножение:

fstpl   -16(%ebp)
fldl    -16(%ebp)
fmulp   %st, %st(1)
fstpl   -16(%ebp)

Я не тестировал ни один из этого кода, но просто изучив код, вы можете увидеть, что при использовании целых чисел деление на 2 короче, чем умножение на 2. При использовании двойного умножения короче, потому что компилятор использует плавающую точку процессора коды операций, которые, вероятно, работают быстрее (но на самом деле я не знаю), чем не использовать их для той же операции. Таким образом, в конечном итоге этот ответ показал, что производительность умножения на 0,5 против деления на 2 зависит от реализации языка и платформы, на которой он работает. В конечном счете, разница незначительна, и о ней вам практически никогда не следует беспокоиться, кроме как с точки зрения удобства чтения.

В качестве примечания вы можете видеть, что в моей программе main() возвращает a + b. Когда я уберу ключевое слово volatile, вы никогда не догадаетесь, как выглядит сборка (исключая настройку программы):

## 5/2

## 5*0.5
## done

movl    $5, %eax
leave
ret

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

Извините за слишком длинный ответ.

9 голосов
/ 13 сентября 2016

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

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

Если вам все еще интересно, с точки зрения оптимизации низкого уровня:

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

Как долго разница между конвейерами полностью зависит от оборудования. Последнее оборудование, которое я использовал, было что-то вроде 9 циклов для умножения FPU и 50 циклов для деления FPU. Звучит очень много, но тогда вы потеряете 1000 циклов из-за нехватки памяти, так что все может быть в перспективе.

Аналогия - положить пирог в микроволновку, пока вы смотрите телевизионное шоу. Общее время, которое у вас ушло от телешоу, - это сколько времени нужно было положить его в микроволновку и вынуть из микроволновки. Остальное время вы все еще смотрели сериал. Таким образом, если пирогу потребовалось 10 минут, а не 1 минута, на самом деле он больше не занимал ваше время просмотра телевизора.

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

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

7 голосов
/ 22 октября 2008

Напишите, что более четко указывает ваше намерение.

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

Не делай наоборот.

6 голосов
/ 22 октября 2008

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

Пусть компилятор сделает работу за вас.

4 голосов
/ 22 октября 2008

Если вы работаете с целыми числами или типами без плавающей запятой, не забывайте свои операторы сдвига битов: << >>

    int y = 10;
    y = y >> 1;
    Console.WriteLine("value halved: " + y);
    y = y << 1;
    Console.WriteLine("now value doubled: " + y);
...