применение конечных автоматов

Я учусь в институте, где преподы придерживаются двух утверждений :
1) if рушит конвейер, а потому его применение в программах не желательно
2) лучше всего программы писать с помощью конечных автоматов

Хочу узнать ваше мнение по этому поводу... Актуальны ли до сих пор конечные автоматы, ведь ресурсы техники растут с каждым днем?

 

Freya

Да, конечные автоматы актуальны сейчас и останутся актуальными впредь, так как широко применяются очень во многих областях. Они содержатся например в каждом компиляторе. Существует обширная и хорошо разработанная теория автоматов, которая опять же используется каким-либо боком практически во всех областях теоретической информатики. В качестве фундаментальной идеи актуальность конечных автоматов не имеет никакого отношения к "ресурсам техники".

Но не совсем понятно, где здесь противоречие с использованием if? Конечный автомат представляет из себя, грубо говоря, связку разветвлений - больших if'ов Или высказывания 1) и 2) никак не связаны между собой?

 

Freya
это в смысле они намекают, что функция, возвращающая указатель на другую функцию работает быстрее, чем ветвления? если так, то они не читали мануалы по оптимизации. ветвления, конечно, тормозят процессор и потому от них всячески избавляются, но избавляются в основном математическим способом, а возврат указателя это - не устраненное ветвление, причем, если обычные if'ы оптимизируются как на уровне компилятора, так и на уровне проца, то в языке си объявление функции, возвращающей указатель на функцию, возвращающей указатель на функцию - весьма нетривиально, более того, как уже было показано, марковские модели с подобными извратами/возвратами можно переписать с использованием if. компилятор от HP кстати это даже пытается делать

 

Добавляя к тому, что уже сказал kaspersky. Как уже упоминал leo, вызывает перегрузку конвеера не только условный переход (if), но и любой безусловный переход и любой call (вызов подпрограммы) при первом проходе (т.е. когда переход ещё не был предсказан). Их тоже не использовать? Сделать все программы линейными? Да... математически можно развязывать ветвления (что, кстати, далеко не всегда оправдано) во избежание сброса конвеера, но это низкоуровневая оптимизация, которая ложится на компилятор высокоуровневого языка. Так что ни о каких if'ах (если речь идёт не о макросах в асме) и речи быть не может. ИМХО это бред.

 

Попробую разъяснить про if...

В далёкие-далёкие времена (лет 15 назад) была написана программа, где ветвления осуществлялись с помощью if. И работала эта программа аж 6 минут, что было весьма удручающе. Но когда в основу её положили таблицу (с состояниями, переходами, входными данными) время сократилось до 6 секунд! Таблица позволила сразу найти решение, просто взяв ответ с пересечения столбца входных данных и ряда состояния.

А техника вот причем. Мне кажется, на сегодняшний момент такого различия во времени исполнения между программами с if"ами и табличноуправляемыми не будет. Я не права?

 

Freya
Вообще в современных процессорах похожие таблицы составляются автоматически блоком предсказаний переходов. Но всегда можно подобрать критичный случай, когда в огромном цикле процессору придётся каждый раз сбрасывать конвеер. Тогда разница будет ощутимой.
P.S. Кажому случаю своё решение. Бывает, стоит в целях оптимизации убрать условный переход. Но это не значит, что вот с этого момента надо начать параноидально избавляться от всех условных переходов в программе. В большинстве случаев оптимизация не окупится.

 

Freya
1) Да рушит.
2) Не помню в чем там соль, но дело в том что конечные автоматы лучше чем ...

Тут дела не в ифах, а в алгоритме, в место того чтобы проверять ряд условий они проверяют только одно. Просто с ифами писался не оптимизированный алгоритм а введя таблицу они прооптимизировали. Если бы они эту таблицу перевели в ифы. Вот тогда новерно бы еще ускорилось.

 

ИМХО, конечный автомат выгодней использовать при большом кол-ве состояний. К примеру, в интерпретаторе некоего интерпретируемого кода, который, в свою очередь, содержит сотни вариантов команд. Применение здесь if'ов значительно снизит производительность, а таблица адресов переходов - самое оно. Ну а если вариантов не много, не более десятка-двух, смыла в таблице нет, лучше задействовать что то типа

Код (Text):

1. cmp AL,M0
2. jz L0
3. cmp AL,M1
4. jz L1
5. cmp AL,M2
6. jz L2
7. cmp AL,M3
8. jz L3
9. jmp _else_
10. L0:
11. действие0
12. jmp TheEnd
13. L1:
14. действие1
15. jmp TheEnd
16. L2:
17. действие2
18. jmp TheEnd
19. L3:
20. действие3
21. jmp TheEnd
22. _else_:
23. хз че за действие
24. TheEnd:

и еще.
Как то "держал в руках" ARM7. Там есть команды, которые позволяют выполнять улослоные действия без переходов, дабы не перегружать конвеер. Команды что то типа movcc A,B. ARM не настолько умен, что бы предсказывать будущее.

и еще.

так красившее

 

Freya
Судя по приведённым отрывочным сведениям та древняя прога решала задачу типа:
есть набор кодов-команд, каждый код должен быть обработан своей подпрограммой, коды подаются в алгоритм-обработчик в произвольном порядке, но числовые значения кодов расположены плотно друг к другу (например 1,2,3,4,5...). В этом случае если каждый раз получив код перебирать if-ами всю таблицу по принципу "угадал/не угадал" то это долго, а если просто собрать в таблицу адреса обработчиков соответсвующих коду то нужный адрес в один приём получается подстановкой кода как индекса в этой таблице В этом случае действительно отказ от if даёт огромный выигрыш.
Но если коды-команды расположены не плотно 1, 150, 300, 301, 315, 500, 1300, ... а пропущенные значения не используются совсем (такая ситуация имеет место например при обработке сообщений windows WM_xxx), то применение таблицы как выше потребует неоправданного расхода памяти, тут можно применить таблицу соответствия код-адрес в которой уже потребуется поиск, но выигрышь перед if "в лоб" будет уже незначительный.
А вообще-то такие алгоритмы обычно относятся к экзотическим либо второстепенным по значимости в общей структуре программы, и потому считать этот частный случай большого выигрыша "фундаментальным принципом программирования" имхо некоторый перебор
А потери в конвейере от if это немного из другой области если очень интересно поищи здесь посты от leo он очень часто и подробно разьяснял нюансы этих потерь.

 

Спасибо ребят за ответы... ))
У меня ещё вопрос : когда лучше использовать switch, а когда конструкцию else if ?

 

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

 

switch проверяет содержимое одной переменной на равенство одному из перечисленных значений, т.е. одно условие равенства и все.
else if допускает вариации с условиями. например

Код (Text):

1. if (a==b) {
2. ...
3. } else {
4. if (b==c) {
5. ...
6. } else {
7. ...
8. }
9. }

 

switch позволяет проверять только простые условия сводящиеся к проверке вида с == "а" или "в" или "г"
более сложные условия выбора ему не подвластны, цепочка else if в этом плане даёт более гибкие возможности для проверки.
например:
else if (a + b >= 25)
{...}
else if (a - e < 7)
{...}
и т.п.

 

Y_Mur прав: фанатично хвататься за какой -то один подход - весьма глупо: любой код - это компромисс.
Freya
кстати, вы там, помимо поругания "плохих операторов", чем ещё занимаетесь?

 

Barbos
компиляторы будут стремиться засунуть свича в двоичное дерево, что дает очччень большое ускорение и хорошо работает даже с "разряженными" кейсами. а если кейсы можно хоть как-то проидексировать, тогда составляется таблица переходов.
например: 2, 7, 17, 27. --> ((a*2 - 9) * 2 + a), плюс имеем два перехода-пустышки (12 и 22). т.е. таблицу переходов составить все-таки можно, но только рукамии. компиляторы с таким не справятся а что касается возврата указателей из функции, то иногда это упрощает программирование. например, функция проверки пароля может вернуть указатель на функцию go_ahead() когда пароль кхороший, указатель на саму себя, если пароль плохой, но счетчтик попыток еще не истек, die() - когда капец и error1(), error2(),.. при возникновении тех или иных ошибок, причем error() может как завершить управление, так и предпринять что-нидь для разруливания ситуации, вернув управление на вызывающую функцию, но тогда нам нужно еще реализовать свой собственный механизм передачи аргументов.

 

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

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

 

Да вроде как команды в конвейер пихает блок предсказаний. Но далеко не факт, что не произойдёт сброс конвейера, и совсем не по причине, что произошла ошибка в предсказании (а может и не произойти), а потому-что процессор тупо вынужден ждать результатов выполнения какой-либо инструкции. Где-то говорилось, что оптимизация под конвейер даёт средний прирост примерно в 1,5 раза, ну пускай в 2 раза. В самом худшем случае будет происходить постоянный сброс, в лучшем никакого, например на 20 ступенчатом конвейере это понянтое дело - 1, 20 раза, но это в сугубо специфических задачах, например кодировании. У AMD конвейер всегда был гораздо короче, и заточка была именно на задачах с его сбросом, например 3D, где сброс очень част по определению, и короткий конвейер очень эффективен. Так что оптимизировать это конечно хорошо, но всё подряд это совершеннейший бред. Надо оптимайзить определённый участки, где это действительно необходимо.

Зачем? Есть задачи где этот подход оправдан, а есть где совершенно противопоказан.
Да и как уже сказали, автомат как правило реализуется через switch, что противоречит первому пункту наших апрельских тезизов.

Я думаю, что в том примере что Вы привели, была именно алгоритмическая оптимизация (он был правильно выбран), и дело было совсем не в этих двух пунктах.

И ещё как Вы думаете, выполнение в каждом цикле кучи математических операций, взамен их пропуска или уменьшения кол-ва, всегда даёт лучшие результаты? Да и блок предсказания думается не тупые делали. По заявам каменщиков он даёт очень неплохие результаты.

 

UbIvItS
Я не ругаю, а учусь у тех, кто в этом больше понимает =)
Занятий у меня видимо-невидимо... Что конкретно интересует?

 

Freya
самое главное, чтоб толк от этих занятий был. позиция твоего препода:

выдаёт либо фанатика от программирования, либо бездаря. но всё же ты правильно делаешь, что собираешь мнения - ещё более правильный подход: начинай писать проги - и уже чётко будет тебе ясно: что лучше и когда.