оптимизация условных выражений

Ivan8209

В последнее время стали часто появляться вопросы,
как заменить условное исполнение арифметическими и логическими действиями.
Показываю, как работать с арифметическим сравнением на примере 8086.
Процессор выбран как наиболее хорошо знакомый участникам форума.
Сравнение двух чисел A<B можно производить так,
чтобы получать определённую пару значений:
а) 0 и 1 --- как в Си;
б) 0 и "все разряды взведены" --- как в приплюснутом си.
Пример:



mov ax, A

sub ax, B ; если A<B, был заём, который запоминается как перенос

mov ax, 0

adc ax, ax ; добавляется 1, если был заём, он же --- перенос

Хитрость заключается в следующем:
кроме обычных сложения и вычитания существуют ещё
"сложение с переносом" и "вычитание с заёмом",
учитывающие состояние разряда переноса.
Все разновидности сложений и вычитаний изменяют разряд переноса.
Сравнение с нулём, которое "!A" в Си, выполняется почти точно так же:



neg ax

mov ax, 0

adc ax, ax

Все остальные виды извращений, как то получение "-1"
в качестве истины или зануление второго регистра,
остаются в качестве домашнего задания.
Некоторые процессоры поддерживают условное исполнение
не только переходов (ветвлений но и других действий,
например, пересылку данных.
Некоторые процессоры поддерживают условное исполнение чего угодно.
---
"Расширь своё сознание!"

RED-GREEN

отцы, объясните лучше, как это работает

Chupa

разве там что-то непонятно?

bleyman

Ничего не понимаю...

mov eax,dword ptr [ecx] ; read 4 bytes

mov edx,7efefeffh

add edx,eax

xor eax,-1

xor eax,edx

add ecx,4

test eax,81010100h

je short main_loop

; found zero byte in the loop

Там вычисляется прекрасное выражение (eax + 7efefeffh) ^ (eax ^ -1).
Жёппой чую - где-то ошибка. Потому что инструкция xor eax,-1 получается совершенно лишней.

sergey_m

> разве там что-то непонятно?
Зачем в ядре strlen? Точнее он там вполне может быть, но какой смысл его оптимизировать? Он часто исполняется?

Chupa

это относилось к позитивному знанию, а не к метафизическому

Chupa

> Жёппой чую - где-то ошибка.
ещё внешний цикл должен быть, т.к. старший бит eax при такой проверке игнорируется (но сохраняется в edx)

rosali

отцы, объясните лучше, как это работает

Еще strchr через этот же трюк работает... Там все _не очень_ сложно

bleyman

Хм. Внешнего цикла там по смыслу быть не должно. Разве что потом ещё выяснение конкретной длины остатка может быть, но вносить внутрь вычисления было бы совершенно неразумно.
Вообще смысл, кажется, такой: быстро-быстро проверить, нет ли в уинте нулевых байтов. Что-то очень похожее там делается. Я даже заметил один знакомый паттерн, когда попытался всё это расписать: "(al - 1) ^ al". Но блин, всё равно какая-то фигня непонятная. Залезть, что ли, в исходники...

Dasar

> Хм. Внешнего цикла там по смыслу быть не должно
это же не паскаль.
strlen - пробегает всю строку, отсюда и цикл.

bleyman

Дык вот он и есть, этот цикл. Поставь в начале main_loop: и получишь завершённый кусок кода.

Chupa

Нетрудно убедиться, что наткнувшись например на 0x80010101, цикл завершится, но нулей тут нет.

bleyman

Нетрудно убедиться, что ты грязно напиздел
mov edx,7efefeffh
add edx,eax ; edx = 80010101h + 7efefeffh = FF000000;
xor eax,-1 ; eax = 7ffefefe
xor eax,edx ; eax = 80fefefe

Chupa

а теперь test eax,81010100h сделай, долбоёба кусок

rosali

Ну это все от того, что в слове одного бита не хватает

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

то реально не нужен внешний цикл...

Chupa

на каком-нибудь risc можно было бы бит переноса не затирать, тогда действительно не нужен

bleyman

ой, я test с cmp перепутал =)

koly

А откуда у тебя 93000 сообщений? Это ж анрыл.

kruzer25

Он читер.
Как и шаллер с патником.
---
...Я работаю...

vijrel7878

в корне неправильный подход.
-Такую оптимизацию должен делать компилятор
-код должен быть понятным (легко читаемым). А если там какая-то побитовая херня поди потом догадайся, что это значит через год.
- Любая оптимизация обычно является заключительной стадией разработки. Выполнять оптимизацию по ходу разработки - пустая трата времени и сил.
(хоть явно и не сказано, когда автор предлагает заниматься преложенной оптимизацией, но косвенно можно сделать вывод что по ходу. Но оптимизация условных выражений - это бред. Оптимизировать нужно логику, а для этого нужно иметь продуманную архитектуру. А в конце искать узкие места и оптимизировать их)
Короче полный аут. Можно занести это в раздел - как не нужно программировать.

Chupa

очевидно, ты не в теме
твой поток сознания тут совсем не по делу

a10063

Такую оптимизацию должен делать компилятор

согласен. но что делать, если он не делает? мы же живем в реальном мире

код должен быть понятным (легко читаемым). А если там какая-то побитовая херня поди потом догадайся, что это значит через год.

для этого есть комментарии

но косвенно можно сделать вывод что по ходу

каким образом?

Но оптимизация условных выражений - это бред.

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

durka82

Такую оптимизацию должен делать компилятор
согласен. но что делать, если он не делает? мы же живем в реальном мире

Вариантов много:
1. найти правильный компилятор
2. найти правильную библиотеку
3. написать свою библиотеку (про написание своего компилятора не будем

)
4. отказаться от оптимизации
А вообще Quercus прав

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

Откуда возникает информация, что оптимизация вооюще нужна?
Когда у нас есть работающее приложение и мы можем тестировать его производительность, мы можем решить, устраивает ли она нас.
Если нет - вот тогда определяем самые критичные места и вперед.
При этом желательно, чтобы неоптимизированный вариант тоже оставался доступным (хотя бы для сравнения).
То есть разумно выносить функциональность, требующую оптимизации, в отдельную библиотеку. Тогда у нас в итоге получится 2 библиотеки: оптимизированная и неоптимизированная.
А оптимизация по ходу разработки лишь замедляет ее.
Да и самые значительные оптимизации как правило делаются на самом высоком уровне разработки.

для этого есть комментарии

Их надо еще и писать. Более того, писать разумные комментарии.
То есть при прочих равных это все таки увеличивает вероятность ошибок.
А оно надо?

gopnik1994

Нифига вы не понимаете!
Есть 2 типа программирование: "фундаментальное" и "прикладное".
Область ортимизации и прочие изъебства - это "фундаментализм"

Не надо путать написание софта коммерческого и софта ядреного.
Фундаментальное программирование иногда требуется при написании коммерческого софта, но не часто и только в узких областях и небольшом количестве мест.
Речь идет именно об этой узкой области, нечасто встречающихся задач.
В коммерческом софте такие задачи могут вставать только на конечном этапе разработки продукта и скорее всего даже уже после промышленного внедрения - в виде оптимизации готового. Хотя даже в таких случаях оптимизация скорее должна затрагивать вещи более высого уровня абстракции - оптимизация алгоритмов. Оптимизация же чисто процессорных инструкций с целью укорачивания, группирования и лучшей конвееризации в этом случае встречается крайне редко, если встречается вообще...
При написании некоммерческих ядреных вещей (фанаты юниха, привет!) об этом можно задумываться на самом начальном этапе, если известна четкая архитектура и платформа, на которой это планируется запускать.
Научные компьютерные расчеты в этом смысле близки к некомерческим ядреным.

Chupa

Опять причина путается со следствием.
Изначальная постановка задачи: "оптимизация необходима. как её делать?", поэтому возражения типа "нафига" к данному вопросу никакого отношения не имеют. Кроме оптимизации бывают ещё дополнительные требования к коду, особенно на всяких недопроцессорах, выполнения которых от компилятора добиться очень сложно.

Ivan8209

                                  ...Пальцы в рот да весёлый свист.

Для поддержания своей славы приведу выдержку:
"Don't decide, calculate."
Leo Brodie, "Thinking Forth," chapter 8, "Minimizing Control Structures."
---
"Расширь своё сознание!"

rosali

При написании некоммерческих ядреных вещей (фанаты юниха, привет!) об этом можно задумываться на самом начальном этапе

Вот уж в корне не согласен. Ни разу не видел чтобы бесплатное программирование "ради славы" шло по пути "фундаментального". Как раз в некомерческих проектах либо участники достаточно компетентны, чтобы понимать, что "оптимизациай потом займется кто-нибудь другой, а сейчас главное пропихать гениальную идею в массы". Либо они недостаточно компетентны для этого, тогда и говорить не о чем.

kruzer25

Ключевое слово (которое ты успешно пропустил мимо глаз)
> ядреных
---
...Я работаю...

sergey_m

Бесплатное программирование происходит вовсе не "ради славы".

rosali

Разве?

rosali

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

kruzer25

Опен-сорс?
Да пожалуйста --- например, ядра бзди, линукса и соляры.
---
...Я работаю...

sergey_m

> Ну давай кидай примеры ядерных бесплатных разработок, будем фтыкать в нереальные оптимизации...
Посмотри как вычисляется IP/TCP контрольная сумма в BSD системах.

Оставить комментарий