?

Log in

No account? Create an account
знак на ассемблере - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

знак на ассемблере [фев. 27, 2008|11:33 am]
Anatoly Vorobey
(эта запись будет интересна только программистам)

Расс Кокс рассказывает о супероптимизации - технике поиска самого быстрого куска кода путем полного перебора инструкций процессора (конечно, это работает только для очень коротких кусков кода). Любопытный пример там - самое быстрое воплощение функции знака (-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:
[User Picture]From: zvantsev
2008-02-27 09:45 am
Жуть! Хорошо, что не приснилось тогда.
(Ответить) (Thread)
From: 2tl
2008-02-27 09:56 am
скажи пожалуйста, а как выглядит обычный код для такого действия, который бы использовало большинство программистов?
(Ответить) (Thread)
[User Picture]From: squadette
2008-02-27 10:08 am
там был бы как минимум один jump
который понятно немножечко прибивает конвейер
(Ответить) (Parent) (Thread)
[User Picture]From: dzz
2008-02-27 10:13 am
И вправду, красиво ;)

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

Edited at 2008-02-27 10:14 (UTC)
(Ответить) (Thread)
[User Picture]From: squadette
2008-02-27 10:17 am
всегда когда сработает economy of scale

если придумать сотню таких хинтов, каждый из которых даёт +0.3% к производительности -- то простой арифметикой получаем +30%, что уже неплохо ;)
(Ответить) (Parent) (Thread) (Развернуть)
From: ded_flint
2008-02-27 11:08 am
интересно было бы посмотреть на код, вычисляющий целочисленный квадратный корень
(Ответить) (Thread)
[User Picture]From: trueblacker
2008-02-27 12:56 pm
понравилось

особенно - "додуматься вручную" :)
(Ответить) (Thread)
From: baca6u
2008-02-27 01:09 pm
По ассоциации вспомнил, как давным давно бросил читать какую-то книжку про С или С++, когда встретил в описаниях "красивости" языка код а!=b!=a!=b.
Хотя конечно, для оптимизации кода можно и не так вы..вернуться, все равно его читать никто не будет.
(Ответить) (Thread)
[User Picture]From: spamsink
2008-02-27 06:30 pm
Что бы код а!=b!=a!=b делал? Если речь о перестановке двух переменных с помощью
a^=b^=a^=b, то увы, это незаконно, поскольку есть два присваивания а без sequence point между ними.
(Ответить) (Parent) (Thread) (Развернуть)
From: urbanserj
2008-02-27 01:46 pm
один из самых красивый примеров оптимизации!
(Ответить) (Thread)
From: oblomov_jerusal
2008-02-27 03:33 pm
Я видел реальный код (i << 3) + (i << 1)
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: nm_work
2008-02-27 04:40 pm
Кстати, это в вопросах на собеседовании microsoft кажцца есть.
(Ответить) (Thread)
From: ext_72902
2008-02-27 06:37 pm
В игрушке "Heroes of M∀T-M∃X" один из персонажей (преподаватель) предлагал студентам задачку - написать визуализацию байта, уместив её в 11 байт.
(Ответить) (Thread)
From: (Anonymous)
2008-02-27 09:55 pm
Одна из простейших вроде бы была - обнуление регистра через хоr
xor ax, ax

"В этих случаях нельзя использовать общие методики оптимизации."
http://www.wasm.ru/article.php?article=1010002
(Ответить) (Thread)
From: rusxg
2008-02-28 02:36 am
http://graphics.stanford.edu/~seander/bithacks.html
- тут много подобных приёмчиков
В частности для вычисления знака:
sign = +1 | (v >> (sizeof(int) * 8 - 1));
(Ответить) (Thread)
From: rusxg
2008-02-28 03:24 am
Хотя обманул, для знака в -1, 0, 1 там более сложная конструкция
(Ответить) (Parent) (Thread)