to post messages and comments.

← All posts tagged mstg

В догонку к #2761901. Если вносить внутрь промежуточного языка работу со стеком, то почему бы не вынести туда и стек, например? Вообще-то потому что стек как алгебраический тип, потребует того чтобы при заходе в каждый конструктор данные распаковывались на стек. Наверное это можно решить хитрым анализом строгости. Хотя я всё равно не очень представляю как выглядит эффективный двусвязный функциональный список.

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

В mstg два стека: стек аргументов (поскольку целью кодогенератора является уже управляемый язык потребности отличать boxed и unboxed значения нет и соответственно раздельного стека A и стека B тоже нет) и стек продолжений. На вершине стека объектов всегда лежит замыкание которому передаст управление код конструктора алгебраического типа после того как закончит свои дела (разложит свои кишки по стеку аргументов, например). Это замыкание скорее всего осуществит диспетчеризацию по вычисленному значению или обновит санк значением находящимся на стеке (и передаст управление следующему замыканию со стека продолжений). К достоинству этого подхода можно отнести то что на стеке продолжений можно разместить любое вычисление. Например закинуть туда вычисление n > 1 ортогональных вычислений из цепочки вложенных case'ов с одной ветвью, а потом собрать все их значения одной внутренней вложенной функцией (примерно так как это и происходит в строгих языках: сначала вычисляем все аргументы, затем вызываем код который их использует). К недостаткам — более агрессивное верчение миниинтерпретатора. В оригинальной статье по stg всё немного не так. Есть где-нибудь более проработанный вариант такого подхода?

Переписал компилятор и RTS так чтобы в качестве infotable'ов использовались метатаблицы лунного. Теперь, используя debug.setmetatable, можно представлять функции в виде... функций (а не в виде таблицы со амилками на infotable и функцию). Использование этого хака позволяет генерировать код выполняющийся на 9-11% быстрее. Не плохо наверное, но я ждал больше. Давно хочу примерно также хакнуть и алгебраические типы (что для арифметики даст что-то вроде тотального анбоксинга), но без объявления ADT'ов такое не провернуть, а в stg её нет.

github.com — Пока пусть будет так. Из плохого: всё ещё не умеет примитивных типов отличных от «целого» (которое мапится в лунном на double :^)), пути к файлу рантайма зашиты в код. Из хорошего: считает факториалы и не болеет переполнением стека.

В очередной раз устав воевать с производительностью выходного кода (код в который должна транслироваться программа length $ map (*3) [1..1000000] отрабатывает за 40 секунд в lua и за 10 в luajit) я решил скормить код теста ministg. Результат превзошёл все мои ожидания: он его уже 10 минут жуёт и пока края этому не видно. А вот hugs с тестом справляется секунды за 2.

Расскажу небольшой анекдот перед отъездом. Решил я от отчаяния уменьшить в нескольких тестах число обновляемых замыканий. Уменьшил. Время выполнения выросло, а число заходов в замыкания — нет. Оказалось что санком быть выгоднее чем протсо функцией без аргументов: при заходе в функцию вычитывается её арность из памяти, выделяется память под аргументы, которые снимаются со стека аргументов, создаются итераторы чтобы перебирать элементы на стеке. А санку достаточно запихнуть свой адрес в апдейт-фрейм и вычислить своё тело. Смешно вышло.

Запилил совместимость выхлопа компилятора с luajit. На тестах где создаётся много санков и тормозов luajit показал в 3 — 4 раза лучшее время выполнения чем просто lua. Ожидаемо. При этом lua использует процентов на 5% больше памяти в пике чем luajit. Странно.

Приехали. На всех тестах кроме тех где вычислятор наедается и считает что-нибудь по пол минуты время компиляции стало в лучшем случае сопоставимо со временем вычисления. Очень много времени уходит на чтение маленьких файлов с lua-кодом из которого собирается рантайм-система: комбинируются модели исполнения, модели управления памятью и код сборки рантайм-статистики. Если записать все варианты в один файл и читать только его, время компиляции снизится. Вопрос в том что один большой файл надо как-то хитро форматировать.

А вот в #2725825 я не прав. Если рассматривать семантику описанную в той самой оригинальной статье, то в принципе все вычисления происходят в бесконечном цикле на уровне одного вложенного вызова и взаимодействия продолжений через глобальные состояния. Просто функции это очень маленькие. Зашёл в замыкание, а там case внутри. Выложил на control-стек альтернативы, вернул в качестве продолжения заход в case-expression и вышел. Зашёл в продолжение, выяснил что это Int, поматчил его с альтернативами на control-стек'е, вернул в качестве продолжения нужную ветку, вышел. Вот только лунный со своим «избегайте функциональных вызовов» от такого охренеет. Непонятно как при таком подходе ghc таки умудряется пробить стек, если в сложившейся ситуации его разумнее всего держать в куче и в виде односвязного списка, например.

В тему #2720146. Мой лунный ленивый вычислятор считает факториал 170 также медленно как питон. При этом сам факториал вычисляется на коробкованных числах путём свёртки списка от 1 до 170. Никаких оптимизаций для чисел или списков нет.

В догонку к #2719650. Немного поразмыслив, решил пока особенно не колупаться со спасением от переполнения стека явно кривой программы. То есть с одной стороны я уверен, что можно снизить нагрузку на стек исполнителя путём усложнения потока исполнения и перекидывание нагрузки на кучу. С другой стороны проблема решается либо ручным форсированием вычисления аккумулятора, либо заигрыванием с анализатором строгости.

Я понял как я ломаю стек лунного: при вычислении длины списка у меня накапливаются ленивые суммирования, которые как я не крути всё равно представляют цепочку не хвостовых вызовов. Когда этих отложенных суммирований набирается 50 — 100 тысяч, а потом внешнее резко форсируется происходит несколько десятков тысяч нерекурсивных вызовов функции рантайма EVAL (вычисляющей отложенное значение и раскручивающей продолжения) и стеку лунного становится плохо. Не знаю как это чинить. Была бы это сишка, можно было бы сделать переход в EVAL в виде jump'а…

Вообще эффект переписвывание существующих таблиц в lua вместо создания новых меня ошеломил. Поскольку для реализации ADT'ов, замыканий (которые представлены таблицей с функцией и числом обозначающем арность функции), частичного применения, неба и аллаха используются таблицы, то возникает сравнительно парадоксальная ситуация: в то время как SPJ пишет о дороговизне апдейтов замыканий в системе редукции графов, мне дешевле переписывать все замыкания какие можно лишь бы не аллоцировать новые таблицы.

Моя лунная stg-машина считала длинну сгенерированного списка пропущенного через map четыре минуты времени. В списке было 10 ^ 4 элементов. Мусорщик лунного успешно удерживал объём кучи на 40 мегабайтах. Это так мило. Впрочем у меня нахрен сломаны апдейты графа, так что может быть не всё так плохо.