Каковы ключевые варианты дизайна для создания злого быстрого компилятора?

Question

Я хочу знать, как спроектировать компилятор, который очень и очень быстро компилируется.

Во-первых, позвольте мне избежать некоторых очевидных недоразумений в моем вопросе:

1. Я не говорю о скорости кода, создаваемого компилятором. Уже есть много ресурсов, доступных для обучения, как оптимизировать сгенерированный код. У меня возникают проблемы с поиском информации о том, как сделать компилятор быстрым.

2. Меня также не интересует обсуждение того, почему компиляторы C ++ обычно работают медленнее, чем компиляторы Java (например). Мне интересно, какие методы могут быть использованы для ускорения компилятора для любого языка.

3. Я также не хочу слышать о распределенных системах компиляции, таких как Microsoft Incredibuild или Unix distcc. Эти системы не дают вам более быстрых компиляторов, они просто дают вам больше компиляторов. Что, безусловно, полезно, но это не тот вопрос, который я задаю. Я хочу знать, как разработать быстрый компилятор для одного процессора.

4. И не ccache - ответ, который я ищу. Это система, которая позволяет вам вообще не использовать компилятор, но она не делает компилятор быстрее. Опять же, это полезно; опять же, это не тот вопрос, который я задаю.

Надеюсь, мой вопрос теперь совершенно ясен. Но, возможно, какая-то история сделает это еще яснее.

Компиляторы С раньше работали очень медленно. Затем, в 1986 году, THINK Technologies представила Lightspeed C для Macintosh и почти мгновенно компилировала программы. Lightspeed C был , поэтому намного быстрее, чем все другие компиляторы C, что вряд ли можно было сравнить. (Возможно, Lightspeed C не был первым из нового поколения молниеносных компиляторов, но он был первым в моем опыте. Turbo Pascal появился ранее [1983], но у меня не было опыта с этим, поэтому я не знаю, как по сравнению, по скорости.)

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

Ответ может быть таким простым: в таких средах разработки, как Lightspeed и Turbo, встроенный редактор уже имеет исходный код в ОЗУ. Если компилятор оперирует этими данными, он устраняет дисковый ввод-вывод, который является самой медленной частью любого компилятора. Это, вероятно, очень важный вклад в улучшение скорости, если размер исходного кода мал по сравнению с объемом памяти. (В те времена размеры ОЗУ были намного меньше, но тогда были типичные размеры программ.)

Это так? Или были вовлечены другие важные нововведения? И были ли важные улучшения в скорости компилятора с тех пор?

Answer 1

• Простой синтаксис, который может быть проанализирован за один проход.
• Простой целевой код.Если вы не нацелены на машинный код напрямую, вы можете избежать многих вещей.
• Не компилировать вообще.Если вам не нужно быстрое выполнение или проектирование в основном для одного скрипта, вам не нужно тратить время на анализ кода.
• Не повторяю, не пытайтесь перехитрить вашу ОСуправление диском / кешем.Создайте Mmap весь файл и прочитайте его так, как будто вы читаете его из ОЗУ.Если у вас нет виртуальной памяти, быстрая компиляция - это наименьшее количество ваших забот.
• Избегайте создания XML DOM, подобного раздутым структурам данных для AST.Вам не нужно анимировать ваши операторские приоритеты.Сохраняйте указатели на данные mmaped вместо того, чтобы копировать их.
• Профилируйте свой код, если хотите быстро.Всегда.

Дополнение:

• Изучите разные способы разбора.Если вы не совсем уверены в своих навыках написания синтаксического анализатора, используйте проверенные инструменты генератора синтаксических анализаторов / лексеров, такие как antlr, lemon и т. Д.

Answer 2

Одна проблема заключается в том, что вы генерируете для сгенерированного кода. Вы можете потратить на оптимизацию столько времени, сколько захотите. Простое поколение, может быть, даже выглядит глупым, сэкономит ваше время. Конечно, когда я использовал Turbo Pascal и Lightspeed C, аккуратной частью было удобное получение исполняемого файла, а не его оптимизация. В то время технология настольных компиляторов серьезно отставала от технологии компиляторов мэйнфреймов.

Еще одной особенностью Turbo Pascal и Lightspeed C была интеграция. Особенно в дни перед многозадачностью домашних компьютеров это было здорово. В отличие от моего первого компилятора C (для CP / M), мне не нужно было вносить изменения в редакторе, закрывать его, выполнять компиляцию, делать ссылки, а затем выполнять. Возможно, это было частью того, что вы видели: быстрое выполнение компонентов без необходимости вводить сложные команды. Теперь я могу продублировать это, запустив несколько терминалов на рабочем столе Gnome: один для vim, один для запуска gcc и один для запуска.

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

Answer 3

Общепринято, что парсеры, основанные на рекурсивном спуске сверху вниз, работают быстрее, чем парсеры LALR (k), основанные на правилах, такие как построенные yacc - при условии, что они хорошо закодированы.Парсеры, закодированные вручную, также могут выдавать лучшие сообщения об ошибках в некоторых случаях.

OTOH, хорошая причина использовать что-то вроде yacc в том, что LALR (1) может однозначно анализировать больший класс языков, чем рекурсивный спуск - которыйэквивалентно классу языков LL (1), если я правильно помню.Для создания и пересмотра парсера в стиле yacc может потребоваться меньше времени, чем для парсера, созданного вручную.

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

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

Answer 4

Я думаю, что одним из больших изменений в Turbo Pascal было то, что во многих предыдущих компиляторах / ассемблерах / компоновщиках исходный код и объектный код были бы на диске, как и части компилятора / ассемблера / компоновщика.Попытка чтения и записи нескольких файлов одновременно на одном диске часто более чем в два раза медленнее, чем чтение или запись одного файла.Turbo Pascal держал всю систему разработки в оперативной памяти, и во многих случаях исходный или объектный код также находился в оперативной памяти.

В конце жизни Commodore 64 существовал ассемблер под названием Fast Assembler, которыйисправлен базовый интерпретатор для добавления кодов операций на ассемблере и нескольких новых директив.Директива ORG установит целевое местоположение кода и флаг «pass».Если флаг «pass» не установлен, каждый код операции будет увеличивать местоположение целевого кода на размер инструкции, но не будет генерировать какой-либо код и не будет жаловаться на ветви вне диапазона.Если установлен флаг пропуска, будет сгенерирован код.Чтобы собрать программу, нужно окружить ее циклом for / next, чтобы пройти три раза, с флагом «pass», установленным в последний раз.Поскольку все было в оперативной памяти, цикл редактирования-сборки-тестирования был чрезвычайно быстрым по сравнению с любыми более ранними ассемблерами.

Answer 5

Сегодня вы наверняка заставите свой компилятор использовать все доступные ему ядра. Я не пишу о распределенной компиляции, но параллельная компиляция - проектируйте свой компилятор с нуля, чтобы использовать несколько ядер. Одним из очевидных подходов будет конвейеризация различных этапов компилятора. Переписывание AST тоже можно распараллелить

И, пожалуйста, позаботьтесь о наборе текста и не говорите нам, что этот подход исключен вашими «правилами». Ваши правила, вероятно, запрещают использование модуля с плавающей запятой для оптимизации арифметики с плавающей запятой или запрещают использование любого процессора с тактовой частотой более 1 ГГц.

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

Answer 6

Компиляторы C ++ медленнее, чем компиляторы Java, в основном потому, что они (обычно) генерируют оптимизированный собственный код, в то время как компиляторы Java генерируют не так уж много оптимизированных байт-кодов и оставляют окончательную оптимизацию и генерацию собственного кода для JIT-компилятора (выполняется в время выполнения). Поскольку для серьезной оптимизации требуются знания нативного кода, существует предел возможностей компилятора байт-кода.

Теперь я не могу комментировать Lightspeed (так как ничего не знаю об этом), но в случае Lattice & Microsoft C (медленно) против Borland TurboC (быстро) Borland сохранил все файлы в памяти и скомпилировал их. там (если ваша программа потерпела крах, она может отключить IDE, потеряв несохраненный исходный код!). Среда разработки Micrsoft всегда сохраняет файлы на диск, а затем запускает отдельную программу для чтения и компиляции диска.

Использование заголовочных файлов прекомпилятора также помогло ускорить компиляцию c / C ++.

Еще одна вещь, которая помогает ускорить компиляцию, это язык, разработанный для обеспечения однопроходной компиляции. Например, Pascal требует, чтобы каждая используемая функция была определена (а не просто объявлена, как в C ++) перед ее использованием (поэтому основная функция должна быть последней в исходном файле)