Временная сложность компилятора

54

Меня интересует сложность времени компилятора. Ясно, что это очень сложный вопрос, так как есть много компиляторов, опций компилятора и переменных, которые необходимо учитывать. В частности, меня интересует LLVM, но меня интересуют любые мысли людей или места, где можно начать исследования. Довольно Google, кажется, мало что дает на свет.

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

Я бы сказал, что генерация дерева AST будет линейной. Генерация ИК-сигналов потребует перехода по дереву при поиске значений в постоянно растущих таблицах, поэтому или . Генерация кода и связывание будет аналогичным типом операции. Следовательно, мое предположение было бы , если бы мы удалили экспоненты переменных, которые не растут реально.O(n2)O(nlogn)O(n2)

Я могу быть совершенно не прав, хотя. У кого-нибудь есть мысли по этому поводу?

superbriggs
источник
7
Вы должны быть осторожны, когда утверждаете, что что-то является «экспоненциальным», «линейным», или . По крайней мере, для меня не совсем очевидно, как вы измеряете свой вклад (экспоненциальный в чем? Что означает ?)O(n2)O(nlogn)n
Юхо
2
Когда вы говорите LLVM, вы имеете в виду Clang? LLVM - это большой проект с несколькими различными подпроектами компилятора, поэтому он немного неоднозначен.
Nate CK
5
Для C # это как минимум экспоненциально для проблем наихудшего случая (вы можете закодировать задачу NP SAT SAT в C #). Это не просто оптимизация, это требуется для выбора правильной перегрузки функции. Для таких языков, как C ++, это будет неразрешимо, так как шаблоны завершены.
CodesInChaos
2
@ Зейн, я не понимаю твою точку зрения. Создание шаблона происходит во время компиляции. Вы можете закодировать сложные проблемы в шаблоны таким образом, чтобы компилятор решал эту проблему для получения правильного результата. Вы можете считать компилятор интерпретатором языка программирования полного шаблона Тьюринга.
CodesInChaos
3
Разрешение перегрузки C # довольно сложно, когда вы комбинируете множественные перегрузки с лямбда-выражениями. Вы можете использовать это для кодирования логической формулы таким образом, что для определения, существует ли применимая перегрузка, требуется проблема 3SAT с полным NP-выполнением. Чтобы на самом деле скомпилировать проблему, компилятор должен найти решение для этой формулы, что может быть даже сложнее. Эрик Липперт подробно рассказывает об этом в своем блоге « Лямбда-выражения против анонимных методов», часть пятая
CodesInChaos

Ответы:

50

Вероятно, лучшая книга для ответа на ваш вопрос: Cooper and Torczon, «Разработка компилятора», 2003. Если у вас есть доступ к университетской библиотеке, вы можете взять копию.

В производственном компиляторе, таком как llvm или gcc, разработчики прилагают все усилия, чтобы все алгоритмы оставались ниже где - размер ввода. Для некоторых этапов анализа «оптимизации» это означает, что вам нужно использовать эвристику, а не создавать действительно оптимальный код.O(n2)n

Лексер является конечным автоматом, поэтому по размеру ввода (в символах) и создает поток токенов, который передается парсеру.O(n)O(n)

Для многих компиляторов для многих языков синтаксическим анализатором является LALR (1), и поэтому он обрабатывает поток токенов за время в количестве входных токенов. Во время синтаксического анализа вы обычно должны отслеживать таблицу символов, но для многих языков это может быть обработано с помощью стека хеш-таблиц («словарей»). Каждый доступ к словарю - , но вам иногда приходится обходить стек, чтобы найти символ. Глубина стека составляет где - глубина вложения областей. (Так что в языках, подобных C, сколько слоев фигурных скобок у вас внутри.)O(n)O(1)O(s)s

Затем дерево разбора обычно «сплющивается» в граф потока управления. Узлы графа потока управления могут быть трехадресными инструкциями (аналогично языку ассемблера RISC), и размер графа потока управления обычно будет линейным по размеру дерева разбора.

Затем обычно применяется ряд шагов устранения избыточности (устранение общего подвыражения, движение инвариантного кода цикла, постоянное распространение и т. Д.). (Это часто называют «оптимизацией», хотя редко бывает что-либо оптимальное в результате, реальная цель состоит в том, чтобы максимально улучшить код в рамках временных и пространственных ограничений, которые мы наложили на компилятор.) Каждый шаг устранения избыточности будет как правило, требуются доказательства некоторых фактов о графе потока управления. Эти доказательства обычно делаются с использованием анализа потока данных . Большинство анализов потока данных спроектированы так, что они будут сходиться за проходов по потоковому графику, где (грубо говоря) глубина вложения цикла, а проход по потоковому графику занимает времяO(d)dO(n)где - количество трехадресных инструкций.n

Для более сложной оптимизации вы можете захотеть сделать более сложный анализ. В этот момент вы начинаете сталкиваться с компромиссами. Вы хотите, чтобы ваши алгоритмы анализа занимали намного меньше, чемO(n2)время в размере потокового графа всей программы, но это означает, что вам нужно обходиться без информации (и программ, улучшающих преобразования), которые могут оказаться дорогостоящими, чтобы доказать. Классическим примером этого является анализ псевдонимов, где для некоторой пары записей памяти вы хотели бы доказать, что эти две записи никогда не могут предназначаться для одной и той же области памяти. (Возможно, вы захотите выполнить анализ псевдонимов, чтобы увидеть, можете ли вы переместить одну инструкцию над другой.) Но для получения точной информации о псевдонимах вам может потребоваться проанализировать каждый возможный путь управления через программу, который экспоненциально по числу ветвей. в программе (и, следовательно, экспоненциально в количестве узлов в графе потока управления.)

Далее вы попадаете в регистр распределения. Распределение регистров можно сформулировать как проблему окраски графа, а раскраска графа минимальным количеством цветов известна как NP-Hard. Поэтому большинство компиляторов используют какую-то жадную эвристику в сочетании с разливом регистров с целью максимально возможного сокращения количества разливов регистров в разумные сроки.

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

Блуждающая логика
источник
4
Thirded! Между прочим, многие из проблем, которые пытаются решить компиляторы (например, распределение регистров), являются NP-сложными, но другие формально неразрешимы. Предположим, например, что у вас есть вызов p (), за которым следует вызов q (). Если p - чистая функция, то вы можете безопасно переупорядочивать вызовы, пока p () не выполняет бесконечный цикл. Чтобы доказать это, нужно решить проблему остановки. Как и в случае NP-сложных задач, разработчик компилятора может приложить столько же или меньше усилий, чтобы приблизить решение, насколько это возможно.
псевдоним
4
О, еще одна вещь: сегодня существуют системы типов, которые очень сложны в теории. Вывод типа Хиндли-Милнера известен как DEXPTIME-полный, и ML-подобные языки должны правильно его реализовывать. Однако на практике время выполнения линейно, потому что: а) патологические случаи никогда не возникают в реальных программах, и б) реальные программисты склонны вставлять аннотации типов, хотя бы для того, чтобы получать более качественные сообщения об ошибках.
псевдоним
1
Отличный ответ, единственное, что кажется пропущенным, - это простая часть объяснения, изложенная в простых терминах: компиляция программы может быть выполнена в O (n). Оптимизация программы перед компиляцией, как это делал бы любой современный компилятор, является задачей, которая практически не ограничена. Время, которое на самом деле требуется, определяется не каким-либо внутренним пределом задачи, а скорее практической необходимостью завершения компилятором в какой-то момент, прежде чем люди устают ждать. Это всегда компромисс.
аааааааааааа
@ Pseudonym, тот факт, что компилятору часто приходится решать проблему остановки (или очень неприятные сложные проблемы NP), является одной из причин, по которым стандарты дают разработчику компилятора свободу действий в предположении, что неопределенное поведение не происходит (например, бесконечные циклы и тому подобное). ).
vonbrand
15

На самом деле, некоторые языки (например, C ++, Lisp и D) во время компиляции полны по Тьюрингу, поэтому компиляция их вообще неразрешима. Для C ++ это происходит из-за рекурсивной реализации шаблона. Для Lisp и D вы можете выполнить практически любой код во время компиляции, так что вы можете бросить компилятор в бесконечный цикл, если хотите.

Деми
источник
3
Системы типов Haskell (с расширениями) и Scala также полны по Тьюрингу, а это означает, что проверка типов может занимать бесконечное количество времени. У Scala теперь также есть макросы, полные по Тьюрингу.
Jörg W Mittag
5

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

Известно, что общая задача разрешения перегрузки в C # является NP-сложной (и фактическая сложность реализации является по меньшей мере экспоненциальной).

Обработка комментариев к документации XML в источниках C # также требует оценки произвольных выражений XPath 1.0 во время компиляции, что также является экспоненциальным, AFAIK.

Владимир Решетников
источник
Что заставляет двоичные файлы C # взрываться таким образом? Для меня это звучит как языковая ошибка ...
vonbrand
1
Это способ, которым универсальные типы кодируются в метаданных. class X<A,B,C,D,E> { class Y : X<Y,Y,Y,Y,Y> { Y.Y.Y.Y.Y.Y.Y.Y.Y y; } }
Владимир Решетников
-2

Измерьте это с помощью реалистичных основ кода, таких как набор проектов с открытым исходным кодом. Если вы выводите результаты в виде (codeSize, finishTime), то вы можете построить эти графики. Если ваши данные f (x) = y равны O (n), то построение графика g = f (x) / x должно дать вам прямую линию после того, как данные станут большими.

График f (x) / x, f (x) / lg (x), f (x) / (x * lg (x)), f (x) / (x * x) и т. Д. График будет либо погружаться от нуля, увеличивается без ограничений или выравнивается. Эта идея пригодится для таких ситуаций, как измерение времени вставки, начиная с пустой базы данных (т. Е. Для поиска «утечки производительности» в течение длительного периода времени).

обкрадывать
источник
1
Эмпирическое измерение времени выполнения не устанавливает вычислительную сложность. Во-первых, сложность вычислений чаще всего выражается в терминах времени выполнения в наихудшем случае. Во-вторых, даже если вы хотите измерить какой-то средний случай, вам нужно будет установить, что ваши входные данные являются «средними» в этом смысле.
Дэвид Ричерби
Ну, конечно, это только оценка. Но простые эмпирические тесты с большим количеством реальных данных (каждый коммит на кучу репозиториев git) вполне могут побить тщательную модель. В любом случае, если функция действительно O (n ^ 3) и вы строите f (n) / (n n n), вы должны получить шумную линию с наклоном примерно равным нулю. Если вы построите только O (n ^ 3) / (n * n), вы увидите, что он растет линейно. Это действительно очевидно, если вы переоцениваете и наблюдаете, как линия быстро падает до нуля.
Роб
1
Нет. Например, быстрая сортировка выполняется во времени для большинства входных данных, но в некоторых реализациях время выполнения в худшем случае (как правило, на входе, который уже отсортирован). Однако, если вы просто нанесете график времени выполнения, у вас гораздо больше шансов столкнуться с случаями чем с . Θ ( n 2 ) Θ ( n log n ) Θ ( n 2 )Θ(nlogn)Θ(n2)Θ(nlogn)Θ(n2)
Дэвид Ричерби
Я согласен с тем, что это то, что вам нужно знать, если вы беспокоитесь о том, что злоумышленник может получить отказ в обслуживании, который вводит неверные данные, выполняя некоторый критический анализ ввода в реальном времени. Реальная функция, которая измеряет время компиляции, будет очень шумной, и дело, о котором мы заботимся, будет в реальных репозиториях кода.
Роб
1
Нет. Вопрос касается временной сложности задачи. Это обычно интерпретируется как время выполнения в худшем случае, которое категорически не является временем выполнения кода в репозиториях. Тесты, которые вы предлагаете, дают разумное представление о том, как долго вы ожидаете, что компилятор возьмет данный фрагмент кода, что полезно и полезно знать. Но они почти ничего не говорят о вычислительной сложности задачи.
Дэвид Ричерби