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

UbIvItS

C автоматами разобраться сложнее чем с ифами или кэйсами, поэтому и нажимает

 

Прочитал бурное обсуждение и решил подбросить еще пару вопросов. Может быть кто-то сумеет ответить или дать ссылку в правильном направлении:

1) Возможно ли записать любую программу в линейном виде, т. е. без переходов? Речь идет о теоретической возможности, без учета особенностей ОС, языков программирования и т.д. Полагаю, что возможно.
2) Существует ли какое-либо строгое доказательство 1) или вообще какие-нибудь работы в этой области?
3) Существуют ли какие-либо практические разработки на эту тему? Т.е. что-то вроде "линеаризатора" программного кода.

 

UbIvItS
Да нормальный у меня препод, о-о-очень хороший человек! Просто старой закалки... Вот и решила узнать у Вас, как у специалистов нового поколения, насколько всё это актуально. Вот и всё! =)

А может быть кто-нибудь что-то эффективнее автоматов создал... А вдруг...

 

Stiver

int ch;
while( (ch = getch()) != EOF){
// process ch
}

 

Freya

все зависит от задачи, да и самих реализаций автоматов хватает.

 

Stiver

Существует. Есть компилятор, который компилирует код в код без переходов. Основан на записи в код. Где-то на форуме ссылка была весной-летом.

 

_basmp_

Разворачиваем цикл как описано здесь: Self-Modifying Indecent Turing Hack (задачка)

KeSqueer

Спасибо Не запомнил такой темы, но попробую поискать.

 

Stiver

:-D Эту ссылку я и имел ввиду. Переходов нет, выполнение линейное

 

Stiver

я имел ввиду бесконечный цикл..

вобще-то не понимаю постинга. Самомод код это хорошо, но

набросал ради эксперимента на колене поиск первых 10000 простых с циклами и проч. даже секунды не ищет (~1'541'791'501 тактов).

 

Stiver

Конечно же - разворот цикла широко применяемый приём, и если он в разумных пределах, а не самоцель развернуть всю программу, то даёт существенное ускорение, например здесь, а вобще читай статьи про оптимизацию Фог, kaspersky, посты от leo

 

Пару слов по теме.
Если не пишешь код с большим числом повторений и критический по времени (компрессинг, шифровка etc), вообще нет смысла
задумываться об усложнении кода. Больше потеряешь на времени/стоимости разработок. А потом и на поддержке кода.
Если же есть узкое место - необходимо оптимизировать. Очень хороший пример - игра doom 1,2. Они не смогли бы добиться 3d (хоть и псевдо)
на слабых машинах в то время, если бы не использовали таблицы предустановленных значений.

Вообще, как написано в книге "Совершенный код" (Макконнелл): Никогда не оптимизируй код, если не доказана необходимость сего.

 

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

Компилятор безпереходного кода основаный на самомодификации написать можно, вот только зачем? Прога писаная по такому принципу будет гарантировано в разы тормознутее обычной во всех случаях кроме элементарных и перезагрузок кэша будет гораздо больше. Кроме того, переходы прийдется вставлять чтоб прога не росла непрерывно в памяти (ip читается/меняется только переходом). Имхо.

 

цикл можно развернуть только при заведомо известном колве проходов; развернуть прослушку порта невозможно по определению.

 

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

 

l_inc
хорошо, приведите пример.

 

UbIvItS
Пост 27 посмотрите.

 

l_inc

А как решить проблему конечности памяти?

 

UbIvItS
Если накладные расходы на организацию цикла соизмеримы с действиями в цикле, то его можно развернуть в 2, 3, 4, и т.п. раз чтобы эти расходы сократить, а затем довыполнить количество повторов не кратное развёртке.
Не помню как называлась статья Криса на эту тему с реальными примерами.

 

Booster
А как решить проблему ограниченности времени? Или для Вас запихнуть бесконечный цикл в программу - это обычное дело?

 

l_inc
Да понятно всё, пост 27 это так поприкалываться и не более, серьёзное применение отсутствует. Типо подгрузка в кэш лучше, чем сброс конвейера (совсем не факт, что будет сброс).