Интринсики и зацикливание специализатора #320
Comments
|
На самом деле, об этой проблеме я знал давно и планировал написать эту заявку тоже давно. Но выяснилось, что автоматическая разметка почему-то не выводит формат этой функции, поэтому рабочий пример написать не получилось. Поэтому пришлось решать проблему с расстановкой меток Также я сначала думал, что проблема сугубо теоретическая. Но она оказалась практической — см. #319 (comment). |
Новая проблемаКак оказалось, предыдущий коммит решает только одну из нескольких проблем. Зацикливание остаётся, но его причина оказывается гораздо тоньше. Рассмотрим ту же функцию: Оптимизация представляет собой три вложенных цикла:
Ранее зацикливание происходило в среднем цикле — на каждой итерации строились новые экземпляры один за другим. Автоматическая разметка нужна была только для того, чтобы назначить сигнатуру для Проблему зацикливания в среднем цикле мы решили, но возникло зацикливание во внешнем цикле! Посмотрим, что получается в логе: Запуск: ..\bin\rlc-core test.ref -OADiS --log=test.log -CФункция Вызов Функция Для вызова А почему бы ему и не построиться? Внутри Следующие шаги понятны: Вот такая вот фигня. Возможные решенияОсновное решениеПроблема возникает из-за того, что теряется история. История теряется из-за того, что вызывающая функция, имевшая историю, прогоняется. Поэтому, чтобы избегать избыточных специализаций, историю нужно сохранять. Предлагается при прогонке историю прогоняемой функции «пришивать» к вызывающей. В данном случае, историю функции Но что делать, если осуществляется прогонка вызова одного экземпляра в другом или в одной функции прогоняются два разных экземпляра с двумя разными историями? Варианты:
Я пока не знаю, какой вариант выбрать. Другие возможные решенияВ актуальной реализации повторная специализация экземпляров запрещена, ибо не понятно, как в таких случаях предотвращать зацикливание. Поэтому можно строить экземпляры даже для тривиальной сигнатуры — такие вызовы повторно специализироваться не будут. Но это лютый костыль. Во-первых, некрасиво. Во-вторых, не исключена возможность специализации экземпляров в будущем (когда станет понятно, как в них можно предотвращать зацикливание). Или как-то помечать вызовы, не предназначенные для последующей прогонки. Например, что-то вроде |
Вариант, что делать с несколькими историями при прогонкеВыше предлагалось три варианта, все три плохие. Вариант с несколькими историями у одной функции неоправданно усложнит специализатор, остальные два подразумевают потерю информации. И из-за потери информации я не уверен, что будет гарантироваться остановка. Поэтому предлагается четвёртый вариант:
Конечно, при таком подходе возможно переобобщение и ложные срабатывания, но (а) вероятность представляется небольшой, (б) исключается зацикливание. Детали решения проблемыПрогонщик должен сообщать о факте прогонки специализатору. Единственная общая структура данных, через которую они взаимодействуют — дерево. Поэтому прогонщик должен оставлять «записки» в дереве, которые «подберёт» специализатор.
|
• Оформление кода. • Длинные строки. На самом деле там нужно много чего переделывать. Здесь я поправил участок кода, с которым нужно работать в рамках #320 и длинные строки, чтобы не появлялась горизонтальная прокрутка.
• Изменены описания типов функций в комментариях. • Переименованы переменные.
Проблема не решенаОбъединение истории при прогонке решает проблему с функцией как всё летит к чертям: Много фрагментов из логаВ листингах удалены пустые строки между предложениями для наглядности. Дальше — понятно, Проблема тут возникает из-за того, что функция не проспециализирован, т.к. аргумент не соответствует формату. Формат В истории функции Таким образом, можно назвать следующие причины проблемы:
Про не до конца профакторизованные вызовыВ этой программе все вызовы И это неподвижная точка. Почему так произошло? Потому что экземпляры повторно не специализируются — автоматической разметке запрещено назначать им метки К слову, интринсики тут не причём. Проблему можно воспроизвести и с ЛистингиВ логе имеем тоже самое: Что делать?А вот не очевидно. В чём смысл трёх вложенных циклов?Сначала циклов было два — внутренний для прогонки и внешний для специализации, оба работали до неподвижной точки. Смысл был в чём? Функция может быть одновременно помечена как специализируемая и как прогоняемая. Если её вызов сначала специализировать, то прогнать далее уже не получится. Поэтому сначала прогоняем-встраиваем все те вызовы, которые можно вычислить на этапе компиляции. При правильной разметке этот процесс конечен. На неподвижной точке прогонки выполняем специализацию. Специализатор заменяет вызовы оптимизируемых функций на вызовы их экземпляров, а также создаёт новые экземпляры. Прооптимизированные функции (прогонки+специализация) уже более не могут измениться. Но в свежепостроенных экземплярах, как правило, есть что оптимизировать. Поэтому для них выполняется ещё один проход внешнего цикла — прогонки до неподвижной точки и специализация. Внешний цикл выполняется до тех пор, пока дерево не перестанет меняться, не перестанут создаваться новые экземпляры. Более полное обоснование можно найти в #263. У автоматической разметки (#252) две основные цели:
Для достижения первой цели разметку нужно запускать до проходов оптимизаций. Для достижения второй цели нужно выполнить разметку после циклов оптимизаций, разметить прогоняемые функции и их прогнать. Т.е. оптимизация с разметкой должна выполняться в следующем порядке:
Это похоже на две итерации некоего цикла, только на второй итерации не выполняется специализация. Поэтому я по аналогии с другими оптимизациями просто решил сделать ещё один цикл снаружи:
Т.е. как бы устранил дублирование кода. Но, оказалось, что это приводит к зацикливанию. Попробовал проблему решить сохранением истории при прогонке — решается лишь частично. Причины проблемы описаны выше по тексту (повторюсь):
Если суперкомпилятор выполняет перестройку сверху, то его можно сделать идемпотентным, или хотя бы достигающим неподвижной точки — остаточная программа будет идентична исходной (с точностью до имён переменных). В случае перестройки снизу суперкомпилятор Оптимизатор Рефала-5λ, вернее цикл «многократная прогонка + специализация» эквивалентен ограниченной суперкомпиляции, причём осуществляющей перестройку снизу. Поэтому он И что же делать в итоге?Отказываться от внешнего цикла, который зацикливается. Т.е. после прохода оптимизации и повторной разметки осуществлять только прогонку для устранения избыточных экземпляров. В этом случае предыдущие коммиты становятся бессмысленными. Свежепостроенные экземпляры не прогоняются, а после пометки их прогоняемыми специализация уже не будет выполняться. Так что их придётся откатить. |
|
Чтобы разорвать цепь, достаточно разрушить только одно звено.
В предыдущем комментарии предлагается избавиться от повторного вызова специализации. Но можно пойти иначе — сделать перестройку сверху! Перестройка сверху и снизуЧто такое перестройка сверху и снизу в суперкомпиляции? Допустим у нас есть путь в графе вида и конфигурация Если где Если то нужно выполнять перестройку. Перестройка снизу: Нижняя конфигурация обобщается до Перестройка сверху: Кусок графа, росший от При перестройке снизу остаётся развёрнутый виток цикла между Реализация перестройки сверху в Рефале-5λВместо графа суперкомпиляции у нас граф экземпляров специализированных функций, поэтому Реализация перестройки снизу проста: вычисляем обобщение Эффективная реализация перестройки сверху до недавнего времени мне была не очевидна. Казалось, нужно откатиться к тому проходу, где был построен экземпляр На самом деле всё проще. Достаточно перезаписать экземпляр Здесь При этом историю сигнатуры Хорошо, функцию Про неподвижную точкуТаким образом, можно достаточно эффективно осуществлять перестройку сверху в специализаторе. Кроме того, можно ожидать, что оптимизатор (прогонка+специализация) будет иметь неподвижную точку. Неподвижная точка, возможно, будет вычисляться с точностью до переименования переменных в функциях, поэтому простым сравнением двух деревьев на равенство обойтись не удастся. Можно, наверное, даже разрешить повторную специализацию экземпляров. В таком случае неподвижная точка будет неизбежно строиться с точностью до имён функций — экземпляры экземпляров будут иметь другие имена. |
Новый алгоритм перенесён в OptTree-AutoMarkup-GraphExtractor.ref, поскольку в дальнейшем предполагается объединить всю логику разметки прогоняемых функций в одном файле. Функция BasicVertexes сразу вычисляет и множество функций, которые можно прогнать, множество базисных функций и множество функций, недостижимых из корня. В результате вычисление функций для прогонки, выполнявшееся в OptTree-AutoMarkup.ref, стало избыточным. Автотест на маркировку метатаблиц условно заработал. Теперь в нём нет бесконечного зацикливания при прогонке, но обнаружилось бесконечное зацикливание при авторазметке+специализации. Эта проблема известная и ей посвящена заявка #320. Для подавления бесконечной специализации добавлен шаблон с единственным динамическим аргументом.
Сравнение подходовВыше предложено два подхода к исправлению ошибки: без повторного запуска специализации и с обобщением сверху. Рассмотрим псевдокод цикла оптимизации для обоих подходов. Подход с отказом от повторной специализацииПсевдокод будет выглядеть так, ниже мы дадим комментарии по некоторым пунктам: На втором этапе, чистке транзитных экземпляров, достаточно расставлять только метки Чистка дерева от неиспользуемых функций может выполняться как одновременно с оптимизацией, так и сторонним инструментом — см. #228. Подход с повторной специализацией и перестройкой сверхуПсевдокод будет выглядеть так: Тут интересны строчки 7–10. Специализация с перестройкой сверху строит функции-обобщения и их нужно будет встраивать в точки вызова. Для этого у нас есть строчки 7–9. Для достижения неподвижной точки программы необходимо будет удалять как функции-обобщения, так и транзитные экземпляры — ведь их на входе программы не было. Заметим, что тело цикла здесь совпадает с псевдокодом для предыдущего случая. ВыводРеализация второго пути — перестройка сверху + повторение переразметки и специализации до неподвижной точки неявно подразумевает реализацию первого пути. Т.е. исправив зацикливание путём удаления внешнего цикла, мы реализуем тело цикла для второго варианта. Но полная реализация второго варианта также требует и переделки специализатора (перестройка сверху), и обязательной чистки программы от неиспользуемых функций. Таким образом, для исправления ошибки нужно разомкнуть наружный цикл. А завернуть программу в новый наружный цикл можно будет тогда, когда потребуется повторная специализация экземпляров (см. #314 (comment)). P.S. Как в эту схему включить дефорестацию (#165), я пока не придумал. |
Порядок, в котором взаимодействуют различные проходы древесных оптимизаций, описан при помощи Scheme-подобного интерпретируемого языка. Такое описание гораздо нагляднее и удобнее в сопровождении, чем набор взаимно-рекурсивных функций. Данный интерпретатор может быть проспециализирован, однако, такая возможность отключена директивами $SPEC. Опыт показывает, что на специализацию интерпретатора уходит несколько десятков минут (около 40 минут с записью в лог, без лога не тестировал).
|
Мотивация написания DSL в коммите выше: листинги псевдокода из предыдущего комментария гораздо нагляднее, чем набор взаимно-рекурсивных функций. Заметим, что в тексте DSL отсутствуют упоминания дерева. Передача дерева между проходами осуществляется неявно, самим интерпретатором. Ожидаемо, что этот интерпретатор специализируется. И такой опыт был проведён: была запущена компиляция файла Два вывода по производительности:
Два вывода по архитектуре оптимизации, в контексте текущей задачи:
Рассмотрим следующий пример: При запуске на компиляцию (из папки ..\bin\rlc-core -C -OADiS test-apply.ref --log=test-apply.log --opt-tree-cycles=40получим Эту проблему можно решить, вернув код склеивания историй при прогонке, но мы так делать не будем. Для исправления этой ошибки достаточно устранить внешний цикл. Тогда в остаточной программе будет развёрнута одна итерация, что не так страшно. А вообще, стоит подумать над таким вариантом: на дно истории специализируемой функции положить тривиальную сигнатуру. Тогда они будут специализироваться, только если вызываются из какой-то другой функции, а рекурсивные вызовы будут оставаться нетронутыми. Тогда этой чепухи с функцией |
• Встраивание процедуры в скрипте. • Теперь скрипт — набор процедур, выполнение начинается с самой первой.
Цикл развёрнут в две итерации: полную со специализацией и прогонкой и усечённую с одной только прогонкой.
Теперь команда (pass e.Code) выполняет данный участок кода при ненулевом счётчике и этот счётчик декрементирует. Т.е. объединила в себе старые команды (on-cycles e.Code) и (pass s.Func e.Arg). Предыдущие команды pass заменены на call. Не рекомендуется вкладывать друг в друга операторы pass — возможны странности.
Удаляются не транзитные экземпляры, а нерекурсивные. Правильная терминология: транзитные — с одной веткой и без сужений, полутранзитные: с одной веткой. См. Немытых А.П. «Суперкомпилятор SCP4: общая структура», 2007.
UPD 20.07.2020 21:58: Проблема в стартовом топике решена (в базовом варианте). Но обнаружилась более интересная проблема — см. комментарий #320 (comment).
Проблема
Целью дипломных проектов этого года отчасти было обеспечение безопасности оптимизации. @Kaelena стремилась создать безопасную разметку для оптимизируемых функций (#252), @koshelevandrey делал специализацию безопасной (#253). Но всё испортил диплом @Cstyler’а, который добавил в компилятор интринсики (#260).
Рассмотрим такой, на первый взгляд, безобидный пример:
Это типичная функция на Рефале-5, в данном случае она подсчитывает длину строки. Подсчитывает длину с использованием аккумулятора.
Но, с включёнными оптимизациями
-OAiSполучается шляпа. Автоматическая разметка функцииDoLenназначает шаблонДа, это врождённая проблема автоматической разметки — делать аккумулятор статическим параметром. И с этим уже ничего не поделаешь.
А далее срабатывает взаимодействие специализации и интринсиков.
Отношение Хигмана-Крускала, используемое для остановки специализатора, прерывает бесконечные цепочки только в конечном алфавите символов. И без интринсиков этот механизм работает как часы: число символов в программе конечно, соответствует тому, которые были явно заданы в программе.
Но включение в компилятор интринсиков делает множество символов бесконечным — новые символы будут порождаться в процессе выполнения программы. А тут уже отношение Хигмана-Крускала бессильно.
Для примера выше будет порождаться следующая цепочка специализаций:
Аварийные предложения демонстрируют сигнатуры, для которых эта функция специализировалась. В этом примере экземпляры будут порождаться для каждого следующего значения аккумулятора.
Алфавит чисел в данной реализации формально конечен, т.к. числа не могут превышать
4294967295. Но на практике это ничего не даёт, т.к. (а) на 32-разрядной платформе не хватит адресного пространства, чтобы их перебрать, на 64-разрядной хватит, но не хватит памяти компьютера, (б) есть встроенная функцияImplode, которой можно порождать бесконечное количество идентификаторов.Решение проблемы
Проблема, как это часто бывает, имеет несколько решений. В данном случае можно рассмотреть два: частное и общее.
Есть также третье, экзотическое решение, рассматривать символы как составные объекты, последовательности байт или бит, но это не серьёзно.
Частное решение
Интринсики могут порождать бесконечное количество новых символов только трёх типов: литеры (
Chr), числа (арифметика) и идентификаторы (Implode,Implode_Ext).Наиболее распространённой причиной зацикливания являются аккумуляторы-счётчики. Во всяком случае об аккумуляторах литерах или аккумуляторах-идентификаторах я ничего не слышал. Но если встретится программа, где рекурсивно будет специализироваться функция по генерируемым литерам или символам, тогда буду разбираться.
Поэтому предлагается при проверке отношения Хигмана-Крускала значения символов-чисел просто не учитывать. На данный момент при проверке отношения сигнатуры нормируются — индексы переменных в них стираются. Предлагается точно также стирать и значения символов-чисел.
Аналогичное решение используется в экспериментальном суперкомпиляторе SCP4 (см. книжку про него, стр. 40) — любые два числа в упрощающем отношении являются похожими.
Преимущества и недостатки:
Общее решение
Общее решение — в синтаксическом дереве иметь два сорта символов: статические символы и динамические символы. Статические явно заданы в исходной программе, динамические порождаются интринсиками.
При прогонке статические и динамические символы с равными атрибутами считаются равными. Разница возникает только при вычислении отношения Хигмана-Крускала — для динамических символов стираются их значения.
При завершении древесной оптимизации динамические символы превращаются в обычные, статические.
Преимущества и недостатки:
Вывод
Вывод в том, что в первую очередь нужно ориентироваться на частное решение. А в перспективе (при развитии/переписывании алгоритма обобщённого сопоставления) — иметь ввиду общий случай.
The text was updated successfully, but these errors were encountered: