Интересная задача. Остаток от деления умножением

← →
DevilDevil © (2013-07-29 15:21) [40]

> Rouse_ © (29.07.13 14:44) [35]
> Оть тебе компилятор от MS

Оть тебе GCC

int DLL_EXPORT IntTest(int X) { return X / 3; } mov ecx, [esp+arg_0] mov edx, 55555556h mov eax, ecx imul edx sar ecx, 1Fh sub edx, ecx mov eax, edx retn unsigned DLL_EXPORT DwordTest(unsigned X) { return X / 3; } mov edx, 0AAAAAAABh mov eax, [esp+arg_0] mul edx shr edx, 1 mov eax, edx retn

← →
Rouse_ © (2013-07-29 15:27) [41]

> DevilDevil © (29.07.13 15:21) [40]

А смысл то какой? Дельфя всеравно все будет по старинке генерировать.

← →
DevilDevil © (2013-07-29 15:31) [42]

> Rouse_ © (29.07.13 15:27) [41]

> А смысл то какой? Дельфя всеравно все будет по старинке
> генерировать.

нет, если заменять деление на умножение со сдвигом
или перейти на асм

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

← →
Rouse_ © (2013-07-29 16:14) [43]

> Суть в том, чтобы как минимум знать, как это можно применить
> на практике.

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

← →
DevilDevil © (2013-07-29 16:31) [44]

Ни в коем случае не нужно оптимизировать всё и вся. Очевидно, бывают задачи, в которых приходится обрабатывать большой объём данных и производить различные вычисления, такие как деление например. Приведённый мной код сводит 30 тактное деление к операциям в 6 (ну 7-8 максимум) тактов. Говорить, что оптимизировать деление в программах не нужно - достаточно опрометчиво; ибо операция распространённая и отжирает немеряно тактов.

> а если просто заменить деление в коде - достаточно через
> asm вставку произвести изменения, раз уж так хочется.

в [31] как раз и поднят этот вопрос. Ибо что именно писать в "asm вставку" общественности не известно :). Можно конечно скомпилировать хорошим С++ компилятором и посмотреть у него в дизассемблере... но как то это не по мастерски что ли. Имхо

← →
Павиа (2013-07-29 16:35) [45]

Во первых твои ответы легко гуглится.
Что касается замены сдвигов, то оно всем известно. И где надо используется.
Вот только там где надо это это от силы один случай из 1000.
Преждевременная оптимизация это зло в квадрате.

← →
Inovet © (2013-07-29 16:37) [46]

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

Ну, нестандартая конструкция нужна, видимо, поэтому забили.

← →
Inovet © (2013-07-29 16:40) [47]

> [44] DevilDevil © (29.07.13 16:31)
> общественности не известно :).

Ладно, смайлик стоит. Сочтём за юмор.

← →
DevilDevil © (2013-07-29 16:42) [48]

> Павиа (29.07.13 16:35) [45]
> Во первых твои ответы легко гуглится.

ну так скопируй из гугла да приведи сюда
чтобы эти "формулы" не имели погрешностей; чтобы результат деления эмулировался однозначно

> Что касается замены сдвигов, то оно всем известно. И где надо используется.
> Вот только там где надо это это от силы один случай из 1000.

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

> Преждевременная оптимизация это зло в квадрате.
а современные конвейеры выполняют div за три такта
знаем, слышали :)

← →
Павиа (2013-07-29 16:43) [49]

> Почему нет конструкции для получения результатов этих двух
> двух операций вместе

Как это нету в модуле math лежит если не путаю divmod

← →
DevilDevil © (2013-07-29 16:44) [50]

> Inovet © (29.07.13 16:37) [46]
> Меня как-то занимал вопрос. Вот есть деление по модулю и
> целочисленное деление. Почему нет конструкции для получения
> результатов этих двух двух операций вместе, раз уж они одной
> процессорной инструкцией реализованы, да и не только инструкцией
> - по логике деления остаток всё равно где-то хранится.

справку надо читать, а не курить
div возвращает и частное и остаток

> Inovet © (29.07.13 16:40) [47]
> Ладно, смайлик стоит. Сочтём за юмор.

даже не знаю как комментировать :)
может ты просто не понял вопрос ?

← →
Павиа (2013-07-29 16:48) [51]

> а современные конвейеры выполняют div за три тактазнаем,
> слышали :)

Нет больше 9 но меньше 30.

> чтобы эти "формулы" не имели погрешностей; чтобы результат
> деления эмулировался однозначно

http://www.agner.org/optimize/optimizing_assembly.pdf
страница 140. В интернетах есть и русский перевод.

← →
DevilDevil © (2013-07-29 16:49) [52]

> Павиа (29.07.13 16:43) [49]

> Как это нету в модуле math лежит если не путаю divmod

да, но он убогий
возвращает только word-ы если не ошибаюсь
вообще мне кажется компилятор сам должен распознавать ситуации, когда в коде рядом располагаются и div и mod на одних и тех же операндах

← →
Павиа (2013-07-29 16:50) [53]

> даже не знаю как комментировать :)может ты просто не понял
> вопрос ?

Таки по поводу труб. Текут сегодня должны были почсенить. Но что-то мне не нравиться как счётчик поставили так течь начали. Уже 2 раз сантехника вызываем.

← →
DevilDevil © (2013-07-29 17:00) [54]

> http://www.agner.org/optimize/optimizing_assembly.pdf
> страница 140. В интернетах есть и русский перевод.

неплохая отправная точка
когда я листал этот документ - увидел только оптимизации с плавающей точкой
но там муторно написано. используется shr вместо sar, imul вместо mul (для unsigned). Милости прошу - отвечай на вопрос [31]. Будем тестировать

← →
Inovet © (2013-07-29 17:07) [55]

> [49] Павиа (29.07.13 16:43)
> divmod

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

← →
Inovet © (2013-07-29 17:11) [56]

> [50] DevilDevil © (29.07.13 16:44)
> div возвращает и частное и остаток

Ты о каком div?

← →
Inovet © (2013-07-29 17:11) [57]

> [50] DevilDevil © (29.07.13 16:44)
> может ты просто не понял вопрос ?

Всё я понял.

← →
Inovet © (2013-07-29 17:13) [58]

Я вот как раз сейчас услышал один принцип:
"Принцип Боба. Когда у Боба есть проблемы со всеми, главной проблемой обычно является сам Боб."

← →
DevilDevil © (2013-07-29 17:21) [59]

> Павиа
> Таки по поводу труб. Текут сегодня должны были почсенить.
> Но что-то мне не нравиться как счётчик поставили так течь
> начали. Уже 2 раз сантехника вызываем.

> Нет больше 9 но меньше 30.

http://www.agner.org/optimize/instruction_tables.pdf

у Bobcat mul/imul от 1 до 4 тактов. div/idiv - от 27 до 81
Sandy Bridge: 1-2 и 11-84 соответственно

а в каком мануале ты видел, что меньше 30 ?
не в инструкции к счётчику воды случайно ?

← →
DevilDevil © (2013-07-29 17:30) [60]

> Inovet © (29.07.13 17:07) [55]
>
> Не, то процедура ещё и асм, теряется весь смысл. Надо,чтобы
> по месту работало типа инлайн бы была.

Вот как это выглядит в цивилизованных компиляторах

int DLL_EXPORT DivModTest(int X, int Y) { return (X / Y) + (X % Y); } mov eax, [esp+arg_0] cdq idiv [esp+arg_4] add eax, edx retn

← →
Sapersky (2013-07-29 17:46) [61]

84 такта - это r64... вроде редко нужно делить что-то именно 64-битное.

DIVPS (SSE) - 10-14 тактов, 4 числа за раз, в расчёте на 1 число около 3 тактов.
RCPPS (приближённое 1/x) - 5 тактов, хотя мне в единственном случае применения точности как раз не хватило.

Понятно, что если алгоритм уже заточен под целые, то SSE с плавающей точкой вряд ли имеет смысл, конверсия форматов здорово испортит (а то и вообще убьёт) всё ускорение. С другой стороны, возможно, это повод пересмотреть формат данных:
http://blog.lexa.ru/2011/08/27/o_legacy_i_formatakh_dannykh.html

← →
DevilDevil © (2013-07-29 17:52) [62]

> Sapersky (29.07.13 17:46) [61]

ну так целочисленное деление не равно делению с плавающей точкой
в таком случае вообще делается UN_DIV_CONST = 1/const
вообще без операций деления

и зачем конвертировать alu <--> fpu, когда уже тысячу лет придумали оптимизированное целочисленное деление на константу. По сути ветка является только детализацией этого механизма, чтобы и мы при желании могли им воспользоваться в своих Delphi-проектах

← →
Sapersky (2013-07-29 19:41) [63]

А что тут детализировать...
Шаманский метод вроде [40] - это конечно замечательно, но если компилятор не поддерживает, нужно каждый раз высчитывать магические числа вручную, и ещё прикидывать какие-то исключения, с которыми это не будет работать.
Уж проще тогда написать UN_DIV_CONST = 65536 div const + умножение со сдвигом, а не хватит точности - пусть будет div, и пофиг сколько тактов.

А если переложить высчитывание магических чисел на комп, то это оправдывается, только если нужно делить массив чисел на одно и то же. У Агнера Фога [51] там дальше есть ссылка на его библиотечку с подобными функциями. Вот это в принципе имеет смысл, можно попробовать... правда делить массив на одно число нужно не так уж и часто.

← →
Inovet © (2013-07-29 19:49) [64]

> [60] DevilDevil © (29.07.13 17:30)
> Вот как это выглядит в цивилизованных компиляторах
>
> int DLL_EXPORT DivModTest(int X, int Y)
> {
> return (X / Y) + (X % Y);
> }
>
> mov eax, [esp+arg_0]
> cdq
> idiv [esp+arg_4]
> add eax, edx
> retn

Вот как это выглядит в Builder XE4
struct tdiv_test { int quot; int rem; tdiv_test(int q, int r) {quot = q; rem = r;} }; inline __fastcall tdiv_test div_test(int num, int div) { return tdiv_test(num / div, num & div); } int __fastcall DivModTest(int n, int d) { return n / d + n % d; } int __fastcall DivModTest2(int n, int d) { tdiv_test t = div_test(n, d); return t.quot + t.rem; } @DivModTest$qqrii segment virtual align 2 @@DivModTest$qqrii proc near ?live16385@0: @1: push ebx push esi mov ebx,edx mov ecx,eax ?live16385@16: ; ECX = n, EBX = d mov eax,ecx cdq idiv ebx mov esi,eax mov eax,ecx cdq idiv ebx add esi,edx mov eax,esi ?live16385@32: ; @3: @2: pop esi pop ebx ret @@DivModTest$qqrii endp @DivModTest$qqrii ends _TEXT ends _TEXT segment dword public use32 "CODE" @DivModTest2$qqrii segment virtual align 2 @@DivModTest2$qqrii proc near ?live16386@0: @4: push ebx push esi add esp,-8 ?live16386@16: ; EAX = n, EDX = d mov ecx,eax mov ebx,edx mov esi,ebx and esi,ecx mov eax,ecx cdq idiv ebx mov dword ptr [esp],eax mov eax,esi mov dword ptr [esp+4],eax ?live16386@32: ; EAX = @temp4 mov edx,dword ptr [esp] add edx,eax mov eax,edx ?live16386@48: ; @6: @5: pop ecx pop edx pop esi pop ebx ret @@DivModTest2$qqrii endp @DivModTest2$qqrii ends

← →
Inovet © (2013-07-29 20:19) [65]

> [64] Inovet © (29.07.13 19:49)
> return tdiv_test(num / div, num & div);

А чёрт. Думаю - что за фигня, а оно вон что. Вот так правильно
return tdiv_test(num / div, num % div); _TEXT segment dword public use32 "CODE" @DivModTest2$qqrii segment virtual align 2 @@DivModTest2$qqrii proc near ?live16386@0: @4: push ebx push esi add esp,-8 ?live16386@16: ; EAX = n, EDX = d mov ecx,eax mov ebx,edx mov eax,ecx cdq idiv ebx mov esi,edx mov eax,ecx cdq idiv ebx mov dword ptr [esp],eax mov eax,esi mov dword ptr [esp+4],eax ?live16386@32: ; EAX = @temp4 mov edx,dword ptr [esp] add edx,eax mov eax,edx ?live16386@48: ; @6: @5: pop ecx pop edx pop esi pop ebx ret @@DivModTest2$qqrii endp @DivModTest2$qqrii ends _TEXT ends
Короче, результат не радует. Это с дефолтными установками компилятора на Release, только отключена динамическая RTL, но здесь это пофиг.

← →
Jeer © (2013-07-29 20:34) [66]

TC - "Очередной метр".

← →
Inovet © (2013-07-29 20:39) [67]

> [66] Jeer © (29.07.13 20:34)
> "Очередной метр".

Я бы даже сказал - метроном.:)

← →
DevilDevil © (2013-07-29 21:13) [68]

> Sapersky (29.07.13 19:41) [63]

> Шаманский метод вроде [40] - это конечно замечательно, но
> если компилятор не поддерживает, нужно каждый раз высчитывать
> магические числа вручную

об том и речь

> и ещё прикидывать какие-то исключения, с которыми это не
> будет работать.

не
суть как раз в том, что если делать грамотно - он сработает для любых констант на любом диапазоне чисел (в рамках integer/cardinal конечно). А если подходить упрощено типа 2^16 - тогда естественно погрешность будет. Но зачем, если можно эмулировать деление один в один

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

не мне тебе рассказывать, что такое такты. Если в твоём цикле 3 деления реализованы рассматриваемым способом - это уже 90+ тактов экономии на одну итерацию. Взять тот же IntToStr - много делений (в последних версиях на 100).

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

> Inovet © (29.07.13 20:19) [65]

> Короче, результат не радует. Это с дефолтными установками
> компилятора на Release, только отключена динамическая RTL,
> но здесь это пофиг.

ну что и требовалось доказать
не понятно только, зачем тебе целая структура для двух значений
используй Point )))

Удалено модератором

>Сергей Батькович

Не.. я затих:)
Пусть меряет дальше спокойно.

>сейчас то что не так ?

Все нормально.
"Работа мозгом, нежели поршнями, дает больше шансов на повышение интеллекта"

P.S.
Я тоже доставал старших "глупостями", а потом - они становились в очередь за работой ко мне.

> Jeer © (29.07.13 23:45) [77]

если ты хочешь чтобы я или иной участник форума тебя похвалил - тебе следует создать собственную ветку

> Sapersky (29.07.13 19:41) [63]
> У Агнера Фога [51] там дальше есть ссылка на его библиотечку
> с подобными функциями.

да, забавно
думаю взять их за основу, только адаптировать под привычный нам register, а не cdecl :)

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

bsr ecx, ebx ; floor(log2(d-1)) ... // ахтунг ахтунг inc ecx ; L = ceil(log2(d)) sub ecx, 1 ; shift count = L - 1 adc ecx, 0 ; avoid negative shift count

как ecx может получиться отрицательный - я чёт не понимаю

← →
Sapersky (2013-07-30 17:40) [80]

Прямо перед bsr строчка:
mov ecx, -1 ; value for bsr if ebx = 0 (assuming bsr leaves dest unchanged if src = 0)
то есть странное телодвижение inc ecx/sub ecx/adc ecx - исключительно для обработки этого случая, чтобы привести ecx к 0.
Хотя в функции предварительного расчёта можно было и явный тест/джамп воткнуть, но автор как настоящий хакер не может не выпендриться...

Интересная задача. Остаток от деления умножением Найти похожие ветки