Древесные оптимизации раздувают программы #332
Comments
Пример распухания из-за специализацииРассмотрим такую программу: Откомпилируем (в папке ..\bin\rlc-core -OAS FG-bloat.ref --log=FG-bloat.log -CПолучится такой результат в логе. Полный лог(Лишние пустые строки удалены для читаемости) Для этой программы построилось 5 (пять) экземпляров функции Если включить прогонку, то некоторые из функций встроятся… Э-э-э, нет… Почему-то ни одна из функций не была помечена для прогонки, даже К слову, SCP4 на этом примере тоже даёт некрасивый результат. Некрасивый результат SCP4А вот MSCP-A даёт красивый результат: Красивый результат MSCP-AЕсть более простой пример, на котором SCP4 тоже выдаёт некрасивый результат, но Рефал-5λ и MSCP-A справляются. ПримерНекрасивый результат SCP4Приемлемый результат Рефала-5λКрасивый результат MSCP-A |
|
В последнем примере MSCP-A тупо ничего не сделал, в отличие от SCP4 :) А в первом примере злую шутку с SCP4 сыграла его особенность обобщать всё так, чтобы не было открытых переменных в обобщаемых выражениях. Имхо именно открытые переменные в обобщаемых выражениях позволили MSCP довольно адекватно свернуть программу. |
|
А во втором примере SCP4 перемудрил, выделяя выходные форматы. По-видимому, в первом тоже. На самом деле, для меня во втором примере «тупо ничего не сделать» и есть приемлемый результат. В первом, в принципе, тоже. Блин, почему же в первом примере авторазметка ни одной из функций не дала метку Я сейчас длинный текст пишу в #328. Жди, там должно быть интересно. |
|
@TonitaN, нашёл ошибку. Случайно в авторазметке запрещал прогонку всех функций. Исправил. Теперь надо заново тестировать. Может оказаться, что на максимальных настройках оптимизации всё опять не работает 😜, а заработало ранее из-за того, что одна из оптимизаций (прогонка) по факту была отключена. |
|
Ещё примеры: #319 (comment). |
|
Почему коммит выше (dfa6e5a) оказался в этой заявке? Потому что он выявляет рассматриваемую проблему! Компилятор при самоприменении задумывается и объедается по памяти (впрочем, это к #319). А делает он это из-за нашей любимой специализации по аккумулятору. Построен Небольшой примерНаблюдаются следующие истории сигнатур: Забавно появление Конечно, куки — зло, и их мы обязательно удалим (#284), но это делу мало поможет. Для решения данной проблемы в рамках #319 аккумулятор будет принудительно обобщаться. В рамках текущей задачи предстоит придумать способ борьбы с этим раздуванием аккумулятора, дабы обобщать вручную не требовалось. |
Ослабление свисткаСвисток Хигмана-Крускала, конечно, является хорошим предпорядком, но в прямой реализации порой свистит очень поздно. Это может быть оправдано в суперкомпиляторе, где требуется проводить более точный анализ программы, ведь суперкомпилятор — это прежде всего инструмент для исследования программ. Но для оптимизирующего компилятора высокая точность в ущерб времени работы и размеру создаваемой программы может быть неадекватной. Далее будем обозначать Поэтому стоит рассмотреть другие свистки:
|
|
@TonitaN, есть что прокомментировать? |
|
И ещё один свисток. Отношение Хигмана. Аргументы функций рассматриваем как строки токенов, просто стираем токены. В отличие от отношения Хигмана-Крускала, это отношение можно проверить за линейное время. |
|
Нет, не видел. Почитаю. Спасибо. |
|
@TonitaN, прочитал статью. Спасибо! Некоторые WQO более различающие (discriminative) чем другие, причём бывают строго более различающие. Например, отношение Хигмана-Крускала будет строго более различающим, чем отношение Хигмана на строках, описывающих объектные выражения как цепочки токенов. Но отношение Хигмана вычисляется быстрее. А это значит, что для ускорения анализа можно сначала проверять отношение Хигмана, а потом (если оно сработало) — более дорогое отношение Хигмана-Крускала. В статье есть схемы, как WQO относятся между собой по различающей силе. Вообще, надо исследовать разные варианты, и посмотреть, какой приемлемее для компилятора. Важно, чтобы
По-моему, оптимальным вариантом был бы вариант № 4 — вычислить MSG и сравнить длины подстановок в токенах. |
|
Скопирую отсюда: #359 (comment)
|
По-нормальному, нужно каждый случай обобщения описать, сделать выводы и решить проблему в общем случае в рамках #332. А пока я анализировал лог и подсекал наиболее явные точки распухания.
По-нормальному, нужно каждый случай обобщения описать, сделать выводы и решить проблему в общем случае в рамках #332. А пока я анализировал лог и подсекал наиболее явные точки распухания.
По-нормальному, нужно каждый случай обобщения описать, сделать выводы и решить проблему в общем случае в рамках #332. А пока я анализировал лог и подсекал наиболее явные точки распухания.
|
В комментарии #359 (comment) я написал:
Проблема в том, что благодаря #322 и #251 компилятор стал слишком умным. И там, где старый оптимизатор не был ни на что способен, этот начинает мудрить. В частности, одной из причин мудрения является неизвестность форматов функций компилятору. Рассмотрим пример: Функция
В первом предложении сформируется сигнатура В рассмотренном примере для всех новых сигнатур сработает условие остановки. Но в реальном коде, где первое предложение может быть сложнее: до остановки может пройти довольно много итераций. Возможным решением может быть вынесение вызова но это не всегда целесообразно. Предложенное в комментарии #359 (comment) поведение в некоторых случаях специализирует хуже, чем использование явно заданных форматов. Если при использовании формата внутри статического параметра было Что делать? Возможно, более целесообразным был бы специальный алгоритм обобщённого сопоставления для специализации. Решение клэшей выглядели бы так:
Предложенный алгоритм, очевидно, слабее реализованного, однако, у него два преимущества:
Но я ничего менять в алгоритме обобщённого сопоставления не буду, вместо этого сделаю принудительное обобщение участков |
По-нормальному, нужно каждый случай обобщения описать, сделать выводы и решить проблему в общем случае в рамках #332. А пока я анализировал лог и подсекал наиболее явные точки распухания. В Log-AST.ref был интересный случай квадратичного распухания, а в остальных местах — типичная специализация по аккумулятору.
Перестройка сверху при специализации и слишком большие деревьяПро перестройки сверху и снизуВ суперкомпиляции рассматривают два способа обобщения при обнаружении «опасного сходства» вдоль некоторой ветви — перестройка сверху и перестройка снизу. В обоих случаях строится обобщение двух конфигураций, которое затем развивается. Разница между ними в том, что при перестройке сверху строится стрелка от верхней конфигурации к обобщённой, граф, построенный ранее из верхней конфигурации, отбрасывается. При перестройке снизу ничего не отбрасывается, стрелка к обобщённой строится от нижней конфигурации. Оба подхода одинаково гарантируют завершение суперкомпиляции и построение конечного графа. Дальше я дам два утверждения про перестройки сверху и снизу, без доказательств, но интуитивно мне они кажутся верными. Пусть у нас есть два суперкомпилятора:
А вот неочевидные суждения, к которым у меня доказательств нет, но которым я интуитивно верю.
@TonitaN, ты как думаешь? Будем считать оба суждения истинными (upd: по-видимому, они не верны — #332 (comment)). В этом случае программа, построенная из Перестройки сверху и снизу при специализацииВ актуальной реализации при специализации используется перестройка снизу. Причина — необходимость в ограничении времени работы некоторым разумным пределом. Компилятор не суперкомпилятор. Все суперкомпиляторы на данный момент исследовательские (других не знаю), их цель — получить интересную остаточную программу для интересной входной программы. Цель компилятора — получить работающую программу на целевом языке, эквивалентную программе на исходном. Цель оптимизирующего компилятора — получить более эффективную программу, чем неоптимизированную, но при этом за разумное время. А для суперкомпиляции время работы в принципе не предсказуемо. Поэтому в актуальной реализации (до #340) был принят следующий подход: оптимизация выполняется по проходам, на каждом проходе выполняется небольшой конечный объём работы. Проходы выполняются до тех пор, пока либо программа не перестанет меняться, либо пока не исчерпается счётчик проходов. На проходах прогонки за каждый проход прогоняется ровно по одному вызову в каждом предложении. На проходе специализации строятся экземпляры для вызовов, но вызовы внутри экземпляров не оптимизируются (даже если используется специализация без прогонки). В #340 @Apakhov реализовал «ациклическую суперкомпиляцию», в ходе которой для каждого результатного выражения строится ациклический граф, который сводится к конечному набору сужений. Хотя используемый алгоритм суперкомпиляции всегда завершается, построение графа может требовать много времени. Для ограничения времени работы в код зашиты максимальная глубина дерева и максимальное количество вершин. Но об этом позже. Преимуществом перестройки снизу является то, что не требуется выполнять откатов — отбрасывать ранее построенные части графа. В терминах компилятора — не требуется стирать из дерева ставшие ненужными экземпляры и переписывать те функции, где они появились. На каждом проходе можно для новых вызовов добавлять новые экземпляры, не меняя ранее построенного синтаксического дерева. Недостаток перестройки снизу — распухание дерева, которому посвящена настоящая заявка. Для борьбы с распуханием предлагается использовать перестройку сверху при специализации. Принцип построения — примерно тот же, что и при суперкомпиляции, в частности, в #340. Рассмотрим два случая: сначала случай специализации неспециализируемой функции, а потом специализируемой. Пусть у нас есть некоторая функция
Случай оптимизации специализируемой функции отличается лишь первым пунктом:
Возможно, алгоритм не оптимален, но работать вроде будет. Ограничение специализации по времениВ описанном виде алгоритм неприемлем, т.к. может работать неопределённо долго. Предлагается ввести ограничения на глубину дерева и число узлов (новых нефиктивных экземпляров) аналогично #340. Допустим, мы стали строить дерево, и сработал один из лимитов: или получилась очень длинная ветвь, или построилось очень много новых не-фиктивных экземпляров. Что дальше делать? Можно предложить два варианта:
Недостаток первого варианта в том, что программа, очевидно, распухает. Ведь возможно, что если бы лимит был чуть побольше, то сработало бы условие остановки и дерево свернулось и стало бы более компактным, а вместо этого в остаточную программу вывалился немеряно распухший полуфабрикат. Недостаток второго варианта в том, что функция остаётся недооптимизированной. Не исключено, что причиной раздутого дерева является какая-то сигнатура в середине дерева, и если её не трогать, то оставшееся дерево получилось бы замкнутым и небольшим. Но вот в чём вопрос: как найти такую «проблемную» сигнатуру (или сигнатурЫ, если их несколько)? Задача, по всей видимости, разрешима только полным перебором: рассмотреть каждое подмножество из 2N всех подмножеств сигнатур и построить дерево, где выбранные сигнатуры не специализируются, как не специализируются тривиальные сигнатуры. Если подмножество сигнатур выбрано «правильно», то построенное дерево не будет выходить за лимиты. Но только как из «правильных» подмножеств выбрать подходящее? По размеру нельзя, т.к. минимальным в этом случае будет подмножество из единственной корневой сигнатуры. По размеру + (средней или минимальной) глубине? Тоже не очевидно, что такая эвристика работает. Но в любом случае полный перебор из 2N неприемлем на практике. Так что крайние варианты (отказываться специализировать корень и отказываться специализировать тот лист, на котором достигнут один из лимитов) имеют явные недостатки, а промежуточный вариант не очевиден. Поиск ответа на вопрос., что делать с превышением лимитов, важен не только для специализации, но и для прогонки, т.к. ответ на вопрос может быть приемлем и для ациклической суперкомпиляции. |
Проблема возникала на этапе прогонки экземпляров: на первой стадии оптимизации функция gen_e__ оберегала от взрывной прогонки, но на второй фазе получаются прогоняемые экземпляры gen_e__@n, которые уже ничего не защищают. И программа распухает на финальной стадии.
Распухание происходило из-за прогонки функции Inc. Решение: заменить это определение функции на пометку $INTRINSIC. Но Простой Рефал не поддерживает ключевое слово $INTRINSIC, поэтому автотест пришлось сначала перевести на Рефал-5λ двумя предыдущими коммитами.
По-нормальному, нужно каждый случай обобщения описать, сделать выводы и решить проблему в общем случае в рамках #332. А пока я анализировал лог и подсекал наиболее явные точки распухания.
|
Копипэйста из #362
|
|
Мне тоже они не очевидны, но почему-то мне кажется, что кусок истории между ними влиять Допустим, у нас есть цепочка конфигураций: Конфигурация Хотя, наверное, можно построить контрпример. Что по пути из более детальной В случае перестройки сверху тут будет Так что, по-видимому, эти утверждения не верны. Чтобы было не «по-видимому», нужно построить контрпример для этой схемы. А вообще, эти утверждения можно проверить экспериментально. Известно два простых суперкомпилятора:
Оба суперкомпилятора с открытыми исходниками. Можно дать курсовую или диплом: форкнуть один из этих суперкомпиляторов, поменять в нём вид перестройки и сравнить. А также проверить мои утверждения. |
Ранее было обнаружено, что с новым алгоритмом специализации компилятор в некоторых тестах увязает, и был добавлен грязный хак, ограничивающий максимальное число экземпляров (54c28ca, #332). Предыдущие два коммита стали строить дополнительные let-экземпляры, из-за чего порог стал достигаться раньше и глубина оптимизации снизилась. Поэтому потребовалось поднять порог. Порог был поднят до 150 по двум причинам: • В тесте saved-test-10_Mon-Aug-23-21-51-16-UTC-2021.ref (81667ba) на пороге в 100 экземпляров условие остановки не срабатывает (до let-экземпляров срабатывало). Опытным путём было выяснено, что условие установки срабатывает на пороге между 140 и 145, было выбрано круглое значение. Заметим, что этот тест в текущем коммите проходит. • Тест saved-test-77_14.08.2021_20-00-01,67-big.ref (41ce59e, #314), напротив, проходит только благодаря наличию этого лимита (на момент написания коммита 41ce59e не анализировалась проблема с непрохождением теста, просто был повышен порог). С лимитом 200 тест не проходит, с лимитом 150 проходит.
Проблема
Опыт самоприменения с глубокими оптимизациями (
-OA+ древесные) показал, что компилятор склонен раздувать программы (много примеров в #319, в свёрнутых комментариях). Программы раздуваются по двум причинам:Под переспециализированными экземплярами мы понимаем избыточное количество экземпляров, которые не способствуют каким-либо интересным нетривиальным преобразованиям. Как правило, это специализации по каким-либо аккумуляторным переменным.
Сейчас эта проблема решается ручным анализом причины каждого очередного распухания и купированием его ad hoc (много примеров — коммиты к #319, предлагается даже специальный инструмент для купирования — #331). Но это не дело.
Ожидаемое поведение
Компилятор не должен существенно раздувать программу, раздутие в общем случае должно быть умеренным, не более чем в 10 раз. Но при этом допускать интересные преобразования вроде специализации (в широком смысле) простых интерпретаторов (вроде скрипта древесных оптимизаций).
Понятно, что обеспечить эту численную характеристику (×10) для нетривиальных символьных преобразований нельзя, речь идёт о том, что на наборе типичных программ (сам Рефал-5λ без ручных разметок, MSCP-A, SCP4, другие, которые найдутся) среднее раздутие (размер RASL’а) должно быть не более, чем на порядок, чем при компиляции без древесных оптимизаций.
Но при этом возможность интересных преобразований должна допускаться.
С точки зрения математики обе цели противоречивы: допускать нетривиальные преобразования и ограничивать объём преобразованной программы. Это, вроде как, следует из теоремы Райса-Успенского. Но с точки зрения практики можно найти приемлемый компромисс, когда можно писать и специализируемые интерпретаторы, и программы распухают не сильно.
The text was updated successfully, but these errors were encountered: