знак на ассемблере

[avva]

(эта запись будет интересна только программистам)

Расс Кокс рассказывает о супероптимизации - технике поиска самого быстрого куска кода путем полного перебора инструкций процессора (конечно, это работает только для очень коротких кусков кода). Любопытный пример там - самое быстрое воплощение функции знака (-1, 0 или 1 в зависимости от знака аргумента) на ассемблере 80x86. До такого вручную действительно додуматься нелегко:

cwd
neg ax
adc dx, dx

Здесь начальный аргумент лежит в ax, значение помещается в dx. Работает следующим образом: сначала cwd расширяет знак ax в dx, после чего в dx лежит -1, если аргумент отрицательный, а иначе 0. neg ax меняет знак ax, но это на самом деле неважно, а важно то, что эта инструкция помещает в флаг carry единицу, только если аргумент был ненулевой.

Наконец adc dx, dx складывает dx с самим собой, добавляет carry от второй инструкции, и помещает результат в dx. В результате выходит:

- если ax<0, то dx вначале -1, carry равен 1, результат равен -1*2+1 = -1 (во как!)
- если аx=0, то dx вначале 0, carry равен 0, результат 0*2+0=0
- если ax>0, то dx вначале 0, carry равен 1, результат 0*2+1=1

Красиво!

Comments

[zvantsev.livejournal.com]

Жуть! Хорошо, что не приснилось тогда.

[2tl.livejournal.com]

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

[squadette.livejournal.com]

там был бы как минимум один jump
который понятно немножечко прибивает конвейер

[avva.livejournal.com]

проверки с прыжками.

[mikkim08.livejournal.com]

sign = (v != 0) | (v >> (sizeof(int) * 8 - 1));

[avva.livejournal.com]

Это может не сработать - C не гарантирует, что сдвиг вправо отрицательного аргумента сохраняет знак.

[mikkim08.livejournal.com]

Ну да. По-моему, даже хуже. Результат такого сдвига неопределен.

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

[muchacho.livejournal.com]

sign = (v!=0)|(-1*((v&INT_MIN)>>(sizeof(int)*8-1)));

[malaya-zemlya.livejournal.com]

Разве?
Мне казалось, что знак копируется для signed и стирается для unsigned.

На msvc и gcc это точно так:

signed int x = ffffff85;
x>>2 = ffffffe1

unsigned int y = ffffff85;
y>>2 = 3fffffe1

[mikkim08.livejournal.com]

Не. Стандарта не нашел, но вот например, что в ANSI Rationale пишут.

The Committee has affirmed the freedom in implementation granted by the Base Document in not requiring the signed right shift operation to sign extend, since such a requirement might slow down fast code and since the usefulness of sign extended shifts is marginal.

[malaya-zemlya.livejournal.com]

>...usefulness of sign extended shifts is marginal.

Ни фига себе заява =) Инструкцию SAR в процессор, оказывается, просто так пихнули.

А по поводу shift-а таки действительно:

The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of E1 / 2^E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined.

ISO/IEC 9899:TC3
http://www.open-std.org/JTC1/SC22/WG14/www/docs/n1256.pdf

[netch]

До эпохи современных процессоров - просто пачка условных переходов по проверке условия и укладывание в итоге константы в выходной регистр. Итого в среднем на 2 из 3 случаев приходится один условный переход и один безусловный.

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

Ну а приём из исходного постинга - это уже случайное чудо:), но проще их всех.

[dzz.livejournal.com]

И вправду, красиво ;)

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

[squadette.livejournal.com]

всегда когда сработает economy of scale

если придумать сотню таких хинтов, каждый из которых даёт +0.3% к производительности -- то простой арифметикой получаем +30%, что уже неплохо ;)

[avva.livejournal.com]

Это арифметика по типу "на эти 2 процента я и живу" :)

На самом деле в таком прекрасном случае +142%.

[squadette.livejournal.com]

+0.3% по сравнению с baseline'ом...

[avva.livejournal.com]

Это да - но на практике они никогда не бывают независимыми.

[avva.livejournal.com]

т.е. это если 30 хинтов, сорри. На 100 хинтов выходит +1800% :)

[squadette.livejournal.com]

странно, что когда я полез в гугль считать, правильно ли я понял шутку, я тоже почему-то сначала возвёл 1.03 в 30-ю степень.

при том что мало того, что возводить надо в 100-ю степень, так ещё и надо это делать с числом 1.003

мистика

[avva.livejournal.com]

хаха :)

[spamsink.livejournal.com]

Эти хинты сокращают время, а не увеличивают. Правильный ответ: 1 - 0.997^100 = 26% (удивительно близко к 30% !).

[psilogic.livejournal.com]

Это зависит от трюков. Функция извлечения знака применяется не очень часто, так что в данном случае это просто "красиво". А когда речь идет о часто используемых операциях, то там идет трюк на трюке - используют все, что только можно.

[spamsink.livejournal.com]

В исходниках superopt есть несколько десятков функций, для которых делается поиск, и большинство популярных лет 10 назад архитектур. С появлением операции conditional move (или выводом внутренней инструкции с аналогичной семантикой при обнаружении перехода вперед на небольшое расстояние? Я не знаю, делается ли это, но идея очевидная) привлекательность трюков уменьшилась.

[ded_flint.livejournal.com]

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

[trueblacker.livejournal.com]

понравилось

особенно - "додуматься вручную" :)

[baca6u.livejournal.com]

По ассоциации вспомнил, как давным давно бросил читать какую-то книжку про С или С++, когда встретил в описаниях "красивости" языка код а!=b!=a!=b.
Хотя конечно, для оптимизации кода можно и не так вы..вернуться, все равно его читать никто не будет.

[spamsink.livejournal.com]

Что бы код а!=b!=a!=b делал? Если речь о перестановке двух переменных с помощью
a^=b^=a^=b, то увы, это незаконно, поскольку есть два присваивания а без sequence point между ними.

[malaya-zemlya.livejournal.com]

a^=b^=a^=b
это абсолютно легальный С/С++, эквивалентный

a^=(b^=(a^=b))

Оператор a=^b возвращает новое значение a. Никаких альтернативных порядков выполнения тут нет.

[spamsink.livejournal.com]

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

t1 = a ^ b;
t2 = b ^ t1;
t3 = a ^ t2;

a = t1;
b = t2;
a = t3;

Т.к. sequence points нет, то порядок двух присваиваний a не определен. Оптимизирующий компилятор вправе выбросить любое из двух. Это не означает, что существует хоть один, который выбрасывает "нужное", но тем не менее.

[urbanserj.livejournal.com]

один из самых красивый примеров оптимизации!

[oblomov-jerusal.livejournal.com]

Я видел реальный код (i << 3) + (i << 1)

[avva.livejournal.com]

Это глупо - компилятор это делает лучше.

[oblomov-jerusal.livejournal.com]

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

[nm-work.livejournal.com]

Кстати, это в вопросах на собеседовании microsoft кажцца есть.

[migmit.vox.com (from livejournal.com)]

В игрушке "Heroes of M∀T-M∃X" один из персонажей (преподаватель) предлагал студентам задачку - написать визуализацию байта, уместив её в 11 байт.

[(Anonymous)]

Одна из простейших вроде бы была - обнуление регистра через хоr
xor ax, ax

"В этих случаях нельзя использовать общие методики оптимизации."
http://www.wasm.ru/article.php?article=1010002

[rusxg.livejournal.com]

http://graphics.stanford.edu/~seander/bithacks.html
- тут много подобных приёмчиков
В частности для вычисления знака:
sign = +1 | (v >> (sizeof(int) * 8 - 1));

[rusxg.livejournal.com]

Хотя обманул, для знака в -1, 0, 1 там более сложная конструкция

[alexcohn.livejournal.com]

спасибо, славный линк!

[pulkin.livejournal.com]

http://rsdn.ru/forum/message/2869235.1.aspx