Методы компиляции и оптимизации машинных команд

← →
DevilDevil © (2012-09-18 13:09) [0]

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

Но! Раз голова горяча - есть прекрасная возможность пополнить свой багаж знаний областью, которой не владею абсолютно. А именно компиляция, и именно высокопроизводительная оптимизация.

Я прекрасно понимаю, что на форуме тонна сверх профессионалов, лично разработавших оптимизацию компилятора icc. (такие специалисты обычно знают url гугла и названия бородатых книжечек). Но тем не менее, наверное кто-то из здесь присутствующих имеет представление о разработке компилятора и знает практические подходы к разработке оптимизатора. Я достаточно часто пишу ресурсоёмкий код на ассемблере и понятия не имею, как схожей производительности добиваются С++ оптимизаторы.

Я слышал, что используют теорию графов каким-то образом. Одну и ту же последовательность ЯВУ-"команд" можно выполнить огромным числом способов, учитывая латентность и "throghput", распределение по регистрам и попадание в кэш. FPU по сравнению с Delphi-овской выполняется крайне эффективно. Раз всё это делается, значит существуют соответствующие алгоритмы и подходы.

Хотелось бы чтобы каждый этап компиляции и оптимизации был проиллюстрирован псевдокодом. Я понимаю, что врядли здесь находятся разработчики icc и gcc, а так же Intel Fortran. Но тем не менее интересно будет выслушать мысли умных людей. (только действительно умных, а не тех кто ими хочет казаться ;)

← →
DevilDevil © (2012-09-18 13:10) [1]

p.s. пролистал Н. Вирта - ничего интересного не увидел

← →
Rouse_ © (2012-09-18 13:14) [2]

Это тебе с oxffff нужно связаться, Серега как раз в этом направлении работает.

← →
Rouse_ © (2012-09-18 13:16) [3]

зы: а, ну и конечно http://rouse.drkb.ru/books.php#compilers
это именно по разработке компиляторов и оптимизации

← →
no_way (2012-09-18 13:17) [4]

начать с этого
http://ru.wikipedia.org/wiki/Книга_дракона_(компиляторы)
(в смысле с книги)

← →
DevilDevil © (2012-09-18 13:57) [5]

> Rouse_ © (18.09.12 13:14) [2]
> no_way (18.09.12 13:17) [4]

ну ништяк чё )
начинаю читать )
спасибо

кастую oxffff в ветку

← →
QAZ2 (2012-09-18 13:57) [6]

все книги бессмыслены, ибо парни их пишущие не делают процессоры
а парни которые делают процессоры (Intel) уже давно выпускают свои супер-пупер оптимизированные компиляторы под С++ и Фортран

← →
DevilDevil © (2012-09-18 14:10) [7]

> QAZ2 (18.09.12 13:57) [6]

предлагаешь начать с производства процессоров ?

← →
QAZ2 (2012-09-18 14:13) [8]

> DevilDevil © (18.09.12 14:10) [7]

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

← →
DevilDevil © (2012-09-18 14:25) [9]

> QAZ2 (18.09.12 14:13) [8]

ты что, хочешь убить во мне творца ?
не родилось ещё на Земле человека, способного сделать это со мной )

← →
QAZ2 (2012-09-18 14:31) [10]

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

← →
DevilDevil © (2012-09-18 14:41) [11]

> QAZ2 (18.09.12 14:31) [10]

в общем, как я уже сказал, инфа нужна в первую очередь для образовательных целей. Как пишется в той же самой "Книге дракона" - описанные алгоритмы применимы и в других областях. Отчасти мне обидно за уродско медленную компиляцию Delphi (в смысле не самой Delphi, а компилируемого кода). Есть ещё пару областей, в которых качественная оптимизация не помешает. Разработчики gcc к примеру не производят процессоров, а тем не менее разрабатывают оптимизаторы сравнимые с Intel-овскими. И помни, программист не может считаться программистом, пока не разработал собственный компилятор ;)) шутка конечно

← →
MBo © (2012-09-18 15:00) [12]

По кодогенерации есть большая глава в книге:
Касьянов, Евстигнеев Графы в программировании: обработка, визуализация и применение

На codeproject.com хлопец чем-то интересным занимается:
http://www.codeproject.com/Articles/192825/Bird-a-New-Optimal-Language

← →
DevilDevil © (2012-09-18 15:18) [13]

ok
спасибо

← →
Pavia © (2012-09-18 15:25) [14]

> Книга_дракона_(компиляторы)

Берём 3 издание и там черным по белому написанно, что авторы незнают как создавать оптимизатор для современных систем.

Лучше почитать по современный движок LLVM. На русском советую не читать , так как даётся искажённая, я бы даже сказал неправильная информация.

← →
Pavia © (2012-09-18 15:27) [15]

> Delphi (в смысле не самой Delphi, а компилируемого кода).

Зато у такого кода нет проблем с паралельностью. И скорость компиляции выши.

← →
DevilDevil © (2012-09-18 15:34) [16]

> Лучше почитать по современный движок LLVM

линк в студию )
на обоих языках )

← →
Pavia © (2012-09-18 15:36) [17]

На само деле код в Delphi медленный только из-за того, что хранит локальные переменные в стеки. Поэтому те компиляторы которые хранят переменные в регистрах работают быстрее раза в 2. А интеловский компилятор за счёт того что может использовать раскрутку циклов и SIMD дает ещё 2-4 кратное превосходство, к примеру над темже gcc.

Остальные трюки такого существующего выигрыша не дают.

Скорее всего дело медленности выходного кода Delphi заключается в архитектуре Delphi, которая основнна на однопроходном процессе.

← →
DevilDevil © (2012-09-18 15:45) [18]

> Pavia © (18.09.12 15:36) [17]

ты сам часто писал высокопроизводительный код на ассемблере, Delphi, С++ ? Дизассемблировал код ?

хотя это уже оффтоп

← →
no_way (2012-09-18 16:05) [19]

> Берём 3 издание и там черным по белому написанно, что авторы
> незнают как создавать оптимизатор для современных систем.
>

я же специально написал "начать"

← →
Студент (2012-09-18 16:27) [20]

Pavia © (18.09.12 15:25) [14]

>> Книга_дракона_(компиляторы)

>Берём 3 издание и там черным по белому написанно, что авторы незнают как
>создавать оптимизатор для современных систем.

>Лучше почитать по современный движок LLVM. На русском советую не читать ,
>так как даётся искажённая, я бы даже сказал неправильная информация.

Как проектировать самолеты? Вот возьми учебник 1954 года почитай. Эээ, нет там про моторные самолеты и какие то бипланы, вот лучше качни схему F-16 и Су-25 почитай и все сразу станет понятно.

← →
Студент (2012-09-18 16:32) [21]

subj
Может просто заведи девушку, на глупости время не останется, а вынос мозга тебе любая девушка в любое время суток готова устроить.

← →
Pavia © (2012-09-18 16:37) [22]

> ты сам часто писал высокопроизводительный код на ассемблере,
> Delphi, С++ ? Дизассемблировал код ?

Часто.
Пришел к вывод что хочу специфичный компилятор с оптимизацией. Но пока руки не дошли, до оптимизации ещё далеко.

← →
DevilDevil © (2012-09-18 18:13) [23]

> Может просто заведи девушку, на глупости время не останется,
> а вынос мозга тебе любая девушка в любое время суток готова
> устроить.

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

← →
Dimka Maslov © (2012-09-18 22:17) [24]

Для начала советую написать просто компилятор. Не прибегая к посторонней литературе. Чтобы он хоть как-то компилировал. Это займёт достаточно много времени. После чего можно будет ознакомиться с литературой (она ВНЕЗАПНО станет намного понятней). Затем плавно перейти к непосредственно оптимизации. Я сам делал именно так. Правда потом ограничился интерпретатором и без оптимизации. Скорость меня устраивает.

← →
Rouse_ © (2012-09-18 22:54) [25]

> Dimka Maslov © (18.09.12 22:17) [24]
> Для начала советую написать просто компилятор. Не прибегая
> к посторонней литературе. Чтобы он хоть как-то компилировал.
> Это займёт достаточно много времени.

Смотря какой - компилятор асма в простейшем приближении ленясь на коленке пишется ну... ну за 2 недели, и то если ну очень сильно лениться :)

← →
DevilDevil © (2012-09-18 23:01) [26]

> Для начала советую написать просто компилятор. Не прибегая
> к посторонней литературе.

У меня правило. "Если делать, то делать хорошо".
как-то так. просто интерпретатор у меня и так есть. Не мой правда

← →
Inovet © (2012-09-18 23:11) [27]

> [26] DevilDevil © (18.09.12 23:01)
> У меня правило. "Если делать, то делать хорошо".

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

← →
oxffff © (2012-09-19 00:11) [28]

> DevilDevil © (18.09.12 13:09)

Мои пять копеек.
Собственно есть книга Дракона.
Правда чем она свежее, тем меньше информации в ней.
У меня она с красным драконом на обложке. В ней действительно все достаточно подробно и хорошо расписано. НО в ней в общем виде.
То есть, да после этого твоя программа будет работать быстрее.
Есть множество нюансов. НО они очень!!! очень!!! трудоемкие поскольку вопросами оптимизации занимаются дяди до которых во всяком случае мне очень очень далеко в определенных вопросах. И таких дядей не 2 и 10, а больше.
Да я написал транслятор в MSIL с промежуточного представления своего языка. Но вопросами оптимизации не занимался. Поскольку понимаю бесперспективность этого занятия. Бо процессоров и архитектур много. Да и не нужно это. Поскольку

есть такой проект LLVM, есть даже примеры как использовать.
Собственно все достаточно не сложно как в него транслировать.
А уж он то оптимизировать умеет.

http://habrahabr.ru/post/47878/
http://habrahabr.ru/post/120424/
http://wiki.linuxformat.ru/index.php/LXF128:LLVM

Собственно, что касаемо компилятора Delphi.
Сейчас я бы не стал утверждать, что он сугубо однопроходной, поскольку иногда он начинает выдавать ошибки, которые всплывают как то нелогично по последовательности обнаружения. Да возможно это просто некие отложенные проверки. Он стал работать по другому после введения generics. Как они их реализовали, им только известно.

По его(dcc) эффективности все очень просто.
Они его просто банально боятся переписывать. Поскольку переписывать его надо было уже лет 10 назад. А сейчас уже поздно. Может много чего накрыться. Поскольку есть программы с ошибками, которые работают исключительно потому, что эти ошибки нивелируются ошибками в кодогенерации.
Выход у них только один(IMHO) - создать новый с новой раздельной архитектурой и сказать сообществу, вот пожалуйста используйте его для новых проектов. Поддержку старых им мы не гарантируем. И в качестве backend как докладывают наши разведчики - стоит LLVM.

IMHO.

Из http://wiki.linuxformat.ru/index.php/LXF128:LLVM

Возвращаясь к началу, повторим: система LLVM не может сделать за вас компилятор или интерпретатор, но она может помочь в той точке, где многие проекты компиляторов входят в мучительный тупик – в генерации исполняемого кода промышленного качества.

← →
Павиа (2012-09-19 08:36) [31]

> Сейчас я бы не стал утверждать, что он сугубо однопроходной,

Про новые я и не утверждаю.

> после введения generics

Сам понимаешь для вставки их в компилятор требуется переработать значительную часть компилятора я бы оценил в 20% (40% фронтенда). Вполне резонно что где-то накосячели.

> Собственно есть книга Дракона.

Читал, раз 5-6 перечитывал. Пришел к выводу что написанию компилятора она не помогает. Да информации в книге достаточно, но вот изложение неудачное.

> Есть множество нюансов. НО они очень!!! очень!!! трудоемкие
> поскольку вопросами оптимизации занимаются дяди до которых
> во всяком случае мне очень очень далеко в определенных вопросах.
> И таких дядей не 2 и 10, а больше.

вот меня такие вот умозаключения дядей и интересуют!

> есть такой проект LLVM, есть даже примеры как использовать.
> Собственно все достаточно не сложно как в него транслировать.
> А уж он то оптимизировать умеет.

это ж сколько времени на перегонку в текстовый формат и в LLVM... Кстати сколько весит его JIT если таскать с собой ?

> это ж сколько времени на перегонку в текстовый формат и
> в LLVM... Кстати сколько весит его JIT если таскать с собой
> ?

http://llvm.org/docs/

> это ж сколько времени на перегонку в текстовый формат и
> в LLVM

http://llvm.org/docs/tutorial/LangImpl4.html

> Павиа (19.09.12 08:36) [31]
>
> Читал, раз 5-6 перечитывал. Пришел к выводу что написанию
> компилятора она не помогает. Да информации в книге достаточно,
> но вот изложение неудачное.

Более того я одну страницу этой книги перечитывал раз 10. Оказалось просто было выбрано не совсем удачное слово. Помогло обращение к первоисточникам этой книги 1976года и google.
Тем не менее именно по этой книге я построил лексический и синтаксический анализаторы( SLR(1), LR(1), LALR(1)).
Про системы типов написано мало. Но для повышения знаний я использовал множество другой литературы.
Вообщем наверно было бы желание.

> 1976года

1986.

← →
jack128_ (2012-09-19 16:42) [37]

> как схожей производительности добиваются С++ оптимизаторы.

Ну для начала сам язык С++ и в особенности его стандартная библиотека - гораздо более "оптимизабельны" по сравнению с дельфёй ибо активно используют компил тайм полиморфизм на шаблонах.
В отличии от дельфи, которая активно использует рантайм полиморфизм.
А статические вызовы можно заинлайнить. А а заинлайненый код - уже можно оптимизировать как хочешь.
Так что как ты изворачивайся, но тот же дельфийский List/ObjectList/Dictionary<TKey/TValue> никогда не сможет сравниться по производительности c std:vector<>/std:hash_map<,>.

А для реальной программы её производительность очень сильно зависит от стандартной библиотеки языка.

> Вообщем наверно было бы желание.

Это всегда и во всем - ключевое слово.
+ настойчивость == успех

all,

а есть в этой ветке тот, кто реализовывал оптимизатор ?

Тебе точно не сюда и шо ты здесь суетишься ? :)

Методы компиляции и оптимизации машинных команд Найти похожие ветки