Насколько побитовые операции быстрее простого деления?

← →
TStas © (2009-05-01 00:54) [0]

Есть программа, точнее, скоро будет. В ней циклы переборов с очень большим число итераций (это такая математика хитрая). Там нужно числа брать по модулю, то есть вычислять отстаток от деления. Насколько вот такие операцияя быстрее обычного mod?
x1 := x shr n; //Divided by y
x2 := x1 shl n; //Multiplied by y
x1 := x xor x2;

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

← →
Eraser © (2009-05-01 00:56) [1]

> [0] TStas © (01.05.09 00:54)

может оказаться, что и не намного быстрее.
проще всего проверить опытным путем.

← →
Игорь Шевченко © (2009-05-01 01:23) [2]

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

← →
Кролик-Фролик (2009-05-01 01:43) [3]

> Насколько вот такие операцияя быстрее обычного mod?

нинасколько
хотя причем тут x2 := x1 shl n; //Multiplied by y и x1 := x xor x2;?

← →
Игорь Шевченко © (2009-05-01 01:46) [4]

остаток от деления на степень двойки вычисляется командой AND, причем довольно быстро.

пост [2] не в тему

← →
Pavia © (2009-05-01 01:49) [5]

Возьми и померь.

А вообще тут одного and достаточно.

← →
Кролик-Фролик (2009-05-01 01:52) [6]

примерно за четверть такта )

← →
TStas © (2009-05-01 01:52) [7]

А вы говорите про компилятор дельфей?
>Игорь Шевченко А как вычислить and"ом и быстрее?

← →
Германн © (2009-05-01 01:53) [8]

> Игорь Шевченко © (01.05.09 01:46) [4]

Бывает. :)

Вот только самой темы нет!

← →
TStas © (2009-05-01 01:55) [9]

И ещё хотеле спросить:
Что лучше писать x := x mod p или
If x >= p then x := x mod p.
Так, вроде, проверка условий добавляется, лишняя операция, но зато мод добавляется, только когда он нужен.

← →
Кролик-Фролик (2009-05-01 01:58) [10]

зависит от частоты условия >=

← →
Pavia © (2009-05-01 02:25) [11]

Так mod, а вернее деление занимает 22-80 тактов в зависимости от процессора.
Сдвиги по такту и логическии операции тоже.
Умножение в 5 раз быстрее деления.

Вот и считай восколько прирост.

if лучше неиспользовать.

← →
Кролик-Фролик (2009-05-01 02:34) [12]

> Так mod, а вернее деление занимает 22-80 тактов в зависимости
> от процессора.

да ну?
и мод 2 тоже?

← →
Pavia © (2009-05-01 02:43) [13]

> да ну?и мод 2 тоже?

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

← →
Кролик-Фролик (2009-05-01 02:45) [14]

> Pavia © (01.05.09 02:43) [13]

простите, я не понял ваш набор слов

← →
Pavia © (2009-05-01 02:56) [15]

Если мы пишем.
x:=x mod p; При этом p=2. Тут p переменная будет выполняться div (idiv) 20-80 тиков.
Если мы пишем.
x:=x mod 2; Тут 2 это константа и компилятор заменит div на and .
И будеим иметь 1 такт

← →
Кролик-Фролик (2009-05-01 03:09) [16]

> Pavia © (01.05.09 02:56) [15]

especial for you

Intel 80386

Название операции Требуемое количество тактов микропроцессора
Сложение (+) от 2 до 7
Умножение (*) от 9 до 41
Деление (/) от14 до 41

← →
Pavia © (2009-05-01 03:17) [17]

> Intel 80386

Несмеши. Это было 20 лет назад. Возьми Агнера Фога и посмотри для других процессоров.

← →
AndreyV © (2009-05-01 03:19) [18]

> [16] Кролик-Фролик (01.05.09 03:09)
> Intel 80386
>
> Название операции Требуемое количество тактов микропроцессора
> Сложение (+) от 2 до 7
на новых уже меньше такта

> Умножение (*) от 9 до 41
на новых уже меньше такта

> Деление (/) от14 до 41
тоже не столько, может как и умножение

← →
Кролик-Фролик (2009-05-01 03:22) [19]

> Несмеши. Это было 20 лет назад. Возьми Агнера Фога и посмотри
> для других процессоров.

неужели сейчас (а раньше 20 лет было 14-41) 20-80 (ваши слова) для деления?
прогресс типо?

смеятсо будем вместе?

← →
Кролик-Фролик (2009-05-01 03:23) [20]

> AndreyV © (01.05.09 03:19) [18]

так это же для Павиа. чтобы не гнал пургу

← →
Pavia © (2009-05-01 03:37) [21]

Вот из мана интел.
CPUID 0F3
AND 1
ADD 1
IMUL 15-18
IDIV 66-80
Поэтому Pentium 4 и считался провалом интел. У него многии инструкции работали дольше чем на предыдущем поколении только частота была выше за счет этого вытягивал.

CPUID 0x6F
AND 1
ADD 1
IMUL 3
IDIV 22

← →
Pavia © (2009-05-01 03:38) [22]

> так это же для Павиа. чтобы не гнал пургу

Так что если не знаешь то и нелезь.

← →
Anatoly Podgoretsky © (2009-05-01 11:30) [23]

> Кролик-Фролик (01.05.2009 3:09:16) [16]

Вытащил клиент из шкафа.
На некоторых современных процессорах Интел за ОДИН так выполняется до ПЯТИ команд.

← →
Кролик-Фролик (2009-05-01 12:45) [24]

> Anatoly Podgoretsky © (01.05.09 11:30) [23]
> Вытащил клиент из шкафа.

cм.[20]

> На некоторых современных процессорах Интел за ОДИН так выполняется
> до ПЯТИ команд.

см.[6]

← →
Pavia © (2009-05-01 13:08) [25]

> > На некоторых современных процессорах Интел за ОДИН так
> выполняется > до ПЯТИ команд.см.[6]

Непешите бреда. Это только при условии что команды независимы. А практика показывает что в среднем 2-3 команды за такт.

← →
sniknik © (2009-05-01 13:11) [26]

> А практика показывает что в среднем 2-3 команды за такт.
а что 2-3 это не ДО 5, это больше?

> Непешите бреда.

← →
KSergey © (2009-05-01 15:34) [27]

> sniknik © (01.05.09 13:11) [26]
> а что 2-3 это не ДО 5, это больше?

Предлагаю не трактовать предлог "до" в вульгарно-рекламном смысле (я про уподтребление в конкретном посте).

← →
Кролик-Фролик (2009-05-01 19:20) [28]

> KSergey © (01.05.09 15:34) [27]

а как вы предлагаете?
и как ваше предложение соответствует русскому языку?

> Кролик-Фролик (01.05.2009 12:45:24) [24]

Ну ты понял, что про скелет дело было.

> Pavia (01.05.2009 13:08:25) [25]

Не делайте бредовых выводов и все в порядке будет.

А почему if лучше не использовать? Вроде же логическая операция, или и так проверется перед тем, как мод сделать необходимость его делать?

>if лучше неиспользовать. [11]

← →
Sapersky (2009-05-02 12:33) [34]

А почему if лучше не использовать

Ветвление в худших случаях может сбрасывать конвейер, что ведёт к тормозам куда более серьёзным, чем несколько дополнительных команд. Хотя в современных CPU придумана масса способов избежать сброса, в первую очередь - предсказание ветвлений, которое действует в основном по принципу "переходим в этот раз туда же, куда перешли в предыдущий". Поэтому в наибольшей степени вредны ветвления, в которых происходит много хаотичных "прыжков" между "условие выполняется" и "не выполняется". Если ветвление хорошо предсказуемо (мало изменений состояния), оно может давать прирост скорости - хотя зависит от кол-ва/типа команд, которые стоят за if.

или и так проверется перед тем, как мод сделать необходимость его делать?

Кстати да: если числа знаковые, то при div/mod на степени двойки компилятор перед shr вставляет ещё проверку знака, т.е. пресловутый if. Поэтому лучше использовать DWord или заменять вручную на shr.

некоторые битовые операции тормозныеее...
чуть ли не тормознее деления RCL/RCR например...
а вообще - писать оба варианта, писать модуль-бенчмаркер и запускать на пару сотен тысяч итераций каждый вариант...

> чуть ли не тормознее деления RCL/RCR например...

Плохой пример. Меньше он везде.
Придется всетаки дать ссылку.
http://www.agner.org/optimize/instruction_tables.pdf

Pavia © (02.05.09 17:59) [36]
ну всяко больше умножения, и порою в два раза... просто неудачный пример с делением... деления конечно дольше, но по сравнению с умножением - эти сдвиги сопоставимы с делением...
RCR,RCL - самые длиннныеее битовые операции...

> AlexDan Да нет, не простыми. Нужно программку несложную написать, которая будет тупыми переборами число решений для неких уравнений искать. Я ух уже несколько написал, просто в данном случае можно хорошую оптимизацию сделать, вот и нужно узнать, сколько тиков занимают следующие операции:
1) Присвоение Х1 := Х2
2) Сравнение В := Х1 = Х2;
3) Умножение Х1 := Х1 * Х2;
4) Сложение Х1 := Х1 + Х2;
5) Взятие по можулю Х1 := Х1 мод Р;
6) Вычитание Х1 := Х1 - Х2;
Чтобы понять, где нужно оптимизировать, а где не нужно. Если мод занимает примерно 70 тиков, то ясно, что писать If X1 >= P then x1 := x1 mod P нужно, а если and занимает 1 тик, то добавлять проверку ненужно.
Вроде, вычитание должно больше тиков, чем сложение занимать, ведь вычитание - это сложение с обратным, но, может, в процессор уже что-то встроено.

Насколько побитовые операции быстрее простого деления? Найти похожие ветки