Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 63
Кому интересна данная тема рекомендую «Алгоритмические трюки для программистов»
Второе издание намного отличается от первого?
Ещё вот этот труд можно почитать (на английском).
И как же в эти рассуждения вписываются команды
Без их объяснения трудно гарантировать, что это именно деление на 255, а не какая-нибудь более хитрая операция.
lea eax, [edx+ecx]
sar eax, 1Fh
sub edx, eax
Без их объяснения трудно гарантировать, что это именно деление на 255, а не какая-нибудь более хитрая операция.
То что это не какая-нибудь хитрая более операция, а деление, я вам гарантирую. Сомнения могут быть только в том, что это 255 )
Цитрованный вами код — это и есть обработка напильником ) На самом деле она такая сложная потому что используется знаковое деление. Когда деление беззнаковое, то оно заменяется беззнаковым умножением, и там работа с результатом гораздо проще и понятнее (и быстрее). Необходимости использовать именно знаковое деление в данном коде абсолютно нет, оно произошло банально от того, что исходный код оперировал int'ами, а не unsigned. Кстати, если будете использовать целочисленное деление на константы (не степени двойки) в своем коде, то имейте ввиду, что беззнаковое будет работать быстрее. При этом упаси Вас Галилей, самому имплементировать такой трюк — это успешно делает любой современный компилятор.
Без приведенных вами операций (используя только сдвиг вправо на 7), получаемый результат может отличаться от реального на единицу. Это как бы аналог округления в арифметике с фиксированной запятой.
Вот здесь немножечко подробнее об этом. При этом прошу обратить внимание, что у автора похоже произошла ошибка и под делителем в некоторых местах надо понимать делимое.
Цитрованный вами код — это и есть обработка напильником ) На самом деле она такая сложная потому что используется знаковое деление. Когда деление беззнаковое, то оно заменяется беззнаковым умножением, и там работа с результатом гораздо проще и понятнее (и быстрее). Необходимости использовать именно знаковое деление в данном коде абсолютно нет, оно произошло банально от того, что исходный код оперировал int'ами, а не unsigned. Кстати, если будете использовать целочисленное деление на константы (не степени двойки) в своем коде, то имейте ввиду, что беззнаковое будет работать быстрее. При этом упаси Вас Галилей, самому имплементировать такой трюк — это успешно делает любой современный компилятор.
Без приведенных вами операций (используя только сдвиг вправо на 7), получаемый результат может отличаться от реального на единицу. Это как бы аналог округления в арифметике с фиксированной запятой.
Вот здесь немножечко подробнее об этом. При этом прошу обратить внимание, что у автора похоже произошла ошибка и под делителем в некоторых местах надо понимать делимое.
Кстати, проверить это довольно просто. Достаточно написать функцию на С и скомпилировать с сохранением листинга ассемблера.
В кратце смотрите: 1/255 нельзя представить в фиксированной точке абсолютно точно. Придется обрезать по какому-то кол-ву разрядов. И останется некий хвост. Так вот этот хвост на самом деле тоже иногда играет роль, но он может сыграть исключительно в виде ±1 для некоторых значений делимого. Вот этот код, который вы процитировали и занимается этим.
Но для целей определения делителя, которая являлось целью данной статьи, это абсолютно не играет роли.
Но для целей определения делителя, которая являлось целью данной статьи, это абсолютно не играет роли.
Хвост на ±1 в этом примере (да и в других, которые я видел) не влияет, множитель подбирают так, чтобы для положительных чисел после сдвига результат был правильным. Второй блок команд используется, чтобы скорректировать значение для отрицательных чисел (для них и только для них результат будет на 1 меньше, чем нужно). А вот первая команда возникла из-за того, что 0x80808081 — отрицательное число, и умножение в действительности шло не на 128/255, а на -127/255.
Я обычно под дебагером такие моменты пробегаю. быстрее, да и проще.
Даже зная о том, какая математика стоит за такими преобразованиями, вычисления могут занять больше времени, чем проверка.
Даже зная о том, какая математика стоит за такими преобразованиями, вычисления могут занять больше времени, чем проверка.
потом окажется, что знаковый тип там и не был нужен, а еще чуть позже — что делить надо было на 256, и весь код сворачивался бы до сдвига на 8 разрядов.
Знаковый тип там стопудово не нужен, на счёт деления на 256 — сомневаюсь. Девайсу передаётся размер буфера в одном байте, то есть максимум 255.
Вообще даже по ассемблеру видно, что код писан какой-то школотой ) Например, в функции передаётся буфер, в который надо прочитать данные с устройства. Вместо того, чтобы отдать этот же буфер функции, которая коммуницирует с девайсом, коммуницирующей функции отдается локальный буфер на стеке, а после вызова он копируется memcpy() в оригинальный. И драйвер похоже собран без оптимизации даже )
Вообще даже по ассемблеру видно, что код писан какой-то школотой ) Например, в функции передаётся буфер, в который надо прочитать данные с устройства. Вместо того, чтобы отдать этот же буфер функции, которая коммуницирует с девайсом, коммуницирующей функции отдается локальный буфер на стеке, а после вызова он копируется memcpy() в оригинальный. И драйвер похоже собран без оптимизации даже )
Вообще‐то такие операции имеют смысл, если при некоторых условиях (например, если коммуницирующая функция завершается с ошибкой) нужно сохранить оригинальный буфер нетронутым, потому что нетронутое содержимое при этих условиях как‐то используется. (Но в большинстве случаев можно и нужно всё‐таки передать буфер, т.к. он изначально не содержит ничего полезного.)
Кстати, gcc без оптимизации всё равно переделевает деление. А clang использует деление без оптимизации. Pcc же использует деление даже с оптимизацией.
Кстати, gcc без оптимизации всё равно переделевает деление. А clang использует деление без оптимизации. Pcc же использует деление даже с оптимизацией.
А вот что у меня получилось из одного деления. Что была за константа? :) (на входе и выходе ecx)
mov eax, 4198405 ; 00401005H
mul ecx
sub ecx, edx
shr ecx, 1
add ecx, edx
shr ecx, 9
1,047,552?
Хотя весьма странно выглядит постобработка. Для беззнакового умножения в ней нет нужды.
Хотя весьма странно выглядит постобработка. Для беззнакового умножения в ней нет нужды.
Неправильно… Число небольшое, но за одно умножение+сдвиг не берётся. Мне было интересно, что сделает компилятор в этой ситуации.
да, вы правы, это 1023
Вообще интересный случай. Вы его случайно получили, или аналитически вывели?
Можно сказать, что аналитически. Я искал число X такое, чтобы K=2^N/X было чуть больше степени двойки (поэтому в качестве множителя пришлось бы брать число K, чуть большее 2^31), и чтобы остаток от деления 2^N на X был как можно меньше (тогда при округлении вверх мы проигрываем больше всего). Получилось, что X надо искать в виде 2^k-1, так, чтобы остаток от деления 31 на k был поменьше. Попробовал 1023 — получилось: для 2^32-5 ответ на единичку больше, чем надо.
Прием известный. Но то были времена 386… Не думал, что сейчас кто-то так заморачивается на реальном текущем железе. Молодцы, чего уж там. Или это уже компиляторы научились?
Еще один известный трюк, как множить любое число на любое число быстрее, чем аппаратно, но не по таблице: www.reenigne.org/blog/multiplying-faster-with-squares
Еще один известный трюк, как множить любое число на любое число быстрее, чем аппаратно, но не по таблице: www.reenigne.org/blog/multiplying-faster-with-squares
Да, это компиляторы научились. Речь идет о реверсе компилированных программ, а не писанных ручным асмом )
> но не по таблице
А что тогда вот это?
А что тогда вот это?
mov si,offset table
>> представить… в виде числа с фиксированной точкой
Целое число это частный случай числа с фиксированной точкой. Просто она зафиксирована за младшим битом.
Целое число это частный случай числа с фиксированной точкой. Просто она зафиксирована за младшим битом.
Я обычно сам в коде так и пишу
И читается хорошо, и на оптимизации компиляторов не надо полагаться.
var subradius = 1 / radius;
...
x = lon * subradius // вместо lon / radius
И читается хорошо, и на оптимизации компиляторов не надо полагаться.
Только вы по факту имеете дело с floating point, а статья про integer'ы ) А у вас один сплошной var ))
С интами мало что меняется.
Цифра (20) выбирается из желаемой точности (ну и чтобы не было переполнения).
int subradius = round(double(1 << 20) / radius)
...
x = (lon * subradius) >> 20;
Цифра (20) выбирается из желаемой точности (ну и чтобы не было переполнения).
А это уже очень может оказаться антиоптимизацией. Компилятор сделает это за вас, да ещё и абсолютно точно, и с большой вероятностью более оптимально.
А можно где-то почитать относительно «абсолютно точно»? В какой международной конвенции записано, что компилятор должен оптимизировать деление?
Что касается «более оптимально», то я это с трудом себе представляю. Компилятор абсолютно точно оптимизирует деление на константу, но не абсолютно точно оптимизирует умножение на неё?
Что касается «более оптимально», то я это с трудом себе представляю. Компилятор абсолютно точно оптимизирует деление на константу, но не абсолютно точно оптимизирует умножение на неё?
Абсолютно точно в том смысле что результат будет точный, а не приближенный.
Хотя вероятно насчет оптимальности я наверное погорячился. Если мы допускаем погрешность, то и код может быть быстрее.
Хотя вероятно насчет оптимальности я наверное погорячился. Если мы допускаем погрешность, то и код может быть быстрее.
Ну это да. Выигрыш в производительности и достигается за счет утраты точности.
В примере в статье компилятор делает оптимизацию без утраты точности. Более того, в каментах уважаемый Mrrl показал, что не всё так тупо и линейно и ваши две строчки кода будут работать не всегда эквивалентно целочисленному делению.
> В примере в статье компилятор делает оптимизацию без утраты точности.
А расскажите, пожалуйста, как можно поделить 1 на произвольное целое число без утраты точности? Мне казалось, что для чисел, не являющихся степенью двойки, этого сделать вовсе нельзя.
А расскажите, пожалуйста, как можно поделить 1 на произвольное целое число без утраты точности? Мне казалось, что для чисел, не являющихся степенью двойки, этого сделать вовсе нельзя.
Вы немного путаете тёплое с мягким. Поделить 1 без утраты точности на произвольное целое число действительно нельзя. Однако оптимизировать без потери точности целочисленное деление с остатком заменой на умножение и сдвиг(и) можно.
Если и делимое, и делитель заранее известны — то да. Можно. Просто заменив на результат.
Если же один из параметров неизвестен, то такая оптимизация возможно только при знании диапазона возможных значений и того, и другого.
Вообще не всякую пару чисел можно делить друг на друга, даже без всяких оптимизаций в виде умножения на обратное.
Если же один из параметров неизвестен, то такая оптимизация возможно только при знании диапазона возможных значений и того, и другого.
Вообще не всякую пару чисел можно делить друг на друга, даже без всяких оптимизаций в виде умножения на обратное.
Диапазон значений делимого известен — от -2^31 до 2^31-1 для знаковых и от 0 до 2^32-1 для беззнаковых чисел. Множитель и сдвиг подбирают так, чтобы для всех чисел из этого диапазона результат был таким же, как и при обычном целочисленном делении.
> Если же один из параметров неизвестен, то такая оптимизация возможно только при знании диапазона возможных значений и того, и другого.
Казалось бы, откуда бы компилятору статически типизированного языка, узнать диапазон возможных значений переменной?
Казалось бы, откуда бы компилятору статически типизированного языка, узнать диапазон возможных значений переменной?
Статическая типизация сама по себе никак не гарантирует знание диапозона возможных значений. Это возможно только в C, ассемблере и подобных им языкам, где нет ничего, кроме примитивных типов (указатели тут же) и структур из них, и нет переопределения операторов: диапозон возможных значений известен только из‐за и примитивности типов, и статической типизации.
Если взять что‐то вроде C++ или Rust, где в ряде случаев деление будет вызываться через таблицу методов, то никто ничего знать не будет. Но типизация у них тоже статическая.
Если взять что‐то вроде C++ или Rust, где в ряде случаев деление будет вызываться через таблицу методов, то никто ничего знать не будет. Но типизация у них тоже статическая.
Out of context вы правы, но мы здесь ведем дискуссию о примитивных типах.
Но если вы хотите поговорить о высоком, то ежели оператор деления переопределен, то компилятору вообще нет нужды думать о том, как это деление оптимизировать: достаточно вызвать тело переопределенного оператора, а следовательно и на диапазон возможных значений можно забить болт. Но в конечном итоге всё, так или иначе, сведется к действиям над элементарными типами. И если там будет уже настоящее целочисленное деление на константу, то мы опять вернемся сюда.
Но если вы хотите поговорить о высоком, то ежели оператор деления переопределен, то компилятору вообще нет нужды думать о том, как это деление оптимизировать: достаточно вызвать тело переопределенного оператора, а следовательно и на диапазон возможных значений можно забить болт. Но в конечном итоге всё, так или иначе, сведется к действиям над элементарными типами. И если там будет уже настоящее целочисленное деление на константу, то мы опять вернемся сюда.
Ээээ…
Вы предлагаете оптимизорвать целочисленное деление, через деление даблов?
round(double(1 << 20) / radius)
Вы предлагаете оптимизорвать целочисленное деление, через деление даблов?
Если бы этот коммент написал не автор статьи, я бы предложил ему перечитать заголовок статьи. Однако теперь я в затруднении.
Давайте поговорим об этом?
Ну давайте. В данном случае subradius — минус первая степень от той самой константы, на которую нужно делить. Её вычисление в любой схеме будет производиться честным делением (возможно, предрассчитанным). Выигрыш здесь за счёт того, что многократное деление на одно и тоже число заменяется комбинацией однократного деления и многократного умножения.
Если вы производите деление много-много раз, то безусловно такой выигрыш будет. Однако в вашем случае без дополнительных мер, возможна потеря точности для некоторых значений делителей.
В статье же описан код, сгенерированный реальным компилятором для однократного деления на целочисленную константу. Если бы делитель не был известной константой, то любые подобные оптимизации не дали бы никакого выигрыша. Хоть ручные, хоть автоматические.
В статье же описан код, сгенерированный реальным компилятором для однократного деления на целочисленную константу. Если бы делитель не был известной константой, то любые подобные оптимизации не дали бы никакого выигрыша. Хоть ручные, хоть автоматические.
Это какой-то фейспалм.
В данном случае оптимизация произошла за счёт того, что компилятор умеет предвычислять константы, т.е. производит фактический расчёт на этапе компиляции, а не исполнения. То же самое — сюрприз-сюрприз! — произойдёт и с предложенным мной кодом, компилятор точно так же рассчитает subradius и запишет его числом, а не выражением.
Оптимизировать же однократное деление — это вообще из пушки по воробьям стрелять, уж лет пятьдесят как такая оптимизация ни на что не влияет.
> Однако в вашем случае без дополнительных мер, возможна потеря точности для некоторых значений делителей.
А в вашем, будто, нет.
> Если бы делитель не был известной константой, то любые подобные оптимизации не дали бы никакого выигрыша.
Ничего подобного. Достаточно того, чтобы происходило два или более деления на одно и то же число.
Слушайте, завязывайте этот спор. Не стоит.
В данном случае оптимизация произошла за счёт того, что компилятор умеет предвычислять константы, т.е. производит фактический расчёт на этапе компиляции, а не исполнения. То же самое — сюрприз-сюрприз! — произойдёт и с предложенным мной кодом, компилятор точно так же рассчитает subradius и запишет его числом, а не выражением.
Оптимизировать же однократное деление — это вообще из пушки по воробьям стрелять, уж лет пятьдесят как такая оптимизация ни на что не влияет.
> Однако в вашем случае без дополнительных мер, возможна потеря точности для некоторых значений делителей.
А в вашем, будто, нет.
> Если бы делитель не был известной константой, то любые подобные оптимизации не дали бы никакого выигрыша.
Ничего подобного. Достаточно того, чтобы происходило два или более деления на одно и то же число.
Слушайте, завязывайте этот спор. Не стоит.
А в вашем, будто, нет.
Еще раз: тот способ, что рассматривается в статье, даёт абсолютно точный результат для любого агрумента (в пределах разрядности его типа, например от 0 до 2^32). В отличие от вашего упрощенного метода.
Скорее, это вам не стоит :-)
> То же самое — сюрприз-сюрприз! — произойдёт и с предложенным мной кодом, компилятор точно так же рассчитает subradius и запишет его числом, а не выражением.
В том-то и дело, что когда это делает компилятор, он делает это для разных констант немного по-разному. Я вам уже в третий раз пишу об этом, а вы всё ленитесь почитать каменты выше. Для разных констант существуют разные варианты. В частности, выше показано, что если делитель будет равен 1023, то ваш код будет работать, не так, как если бы Вы производили деление.
> > Однако в вашем случае без дополнительных мер, возможна потеря точности для некоторых значений делителей.
> А в вашем, будто, нет.
В нашем, это в каком? Когда это делает компилятор? Не будто, а 100% нет.
> Достаточно того, чтобы происходило два или более деления на одно и то же число.
Вы кажется читаете не внимательно. Я писал только об однократном делении. А о многократном я написал, что эффект будет.
В том-то и дело, что когда это делает компилятор, он делает это для разных констант немного по-разному. Я вам уже в третий раз пишу об этом, а вы всё ленитесь почитать каменты выше. Для разных констант существуют разные варианты. В частности, выше показано, что если делитель будет равен 1023, то ваш код будет работать, не так, как если бы Вы производили деление.
> > Однако в вашем случае без дополнительных мер, возможна потеря точности для некоторых значений делителей.
> А в вашем, будто, нет.
В нашем, это в каком? Когда это делает компилятор? Не будто, а 100% нет.
> Достаточно того, чтобы происходило два или более деления на одно и то же число.
Вы кажется читаете не внимательно. Я писал только об однократном делении. А о многократном я написал, что эффект будет.
Если делитель — не константа, но деление на одно и то же значение используется часто, можно было бы подобрать множитель и сдвиг во время выполнения, и, если удастся, действовать так же, код, созданный компилятором. Мешать будет только то, что нам нужна операция, эквивалентая (int)((__int64)a*b)>>32) — получение старшего слова произведения. Если она не выведена в качестве спецфункции, то либо придётся надеяться, что компилятор догадается обойтись одним умножением, либо мы проиграем.
Я помню, были формулы и код калькулятора в официальном руководстве по оптимизации кода от AMD. А вообще в последних поколениях процессоров целочисление деление оптимизировали и необходимости в подобных трюках больше нет.
> Я помню, были формулы и код калькулятора в официальном руководстве по оптимизации кода от AMD.
В руководстве по оптимизации AMD есть код получению множителя из делителя, но не наоборот. Математика процесса там не объяснена.
> А вообще в последних поколениях процессоров целочисление деление оптимизировали и необходимости в подобных трюках больше нет.
Вы говорите про x86. Но мир не кончается на интеле. В других архитектурах такая оптимизация тоже имеет право на жизнь. Даже там, где вообще нет инструкции деления, например, но есть умножение. Заменить надо только мнемоники инструкций.
В руководстве по оптимизации AMD есть код получению множителя из делителя, но не наоборот. Математика процесса там не объяснена.
> А вообще в последних поколениях процессоров целочисление деление оптимизировали и необходимости в подобных трюках больше нет.
Вы говорите про x86. Но мир не кончается на интеле. В других архитектурах такая оптимизация тоже имеет право на жизнь. Даже там, где вообще нет инструкции деления, например, но есть умножение. Заменить надо только мнемоники инструкций.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Реверс-инжиниринг целочисленного деления на константу