to post messages and comments.

← All posts tagged stg

stg

Я правильно помню, что в stg нет связывания unboxed variable с чем-то кроме переменных функции и переменных паттерна? И что сделать глобальную unboxed переменную связанную с каким-нибудь массивом нельзя?

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

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

Регулярно пухну от того что структура программы на stg как-то странно соотносится с формальным синтаксисом приведённым в ТОЙ САМОЙ СТАТЬЕ. Исходя из последнего expression не может быть переменной, никаких формальных ограничений на связывание примитивных операций с переменными нет. Исходя из самой статьи решительно непонятно почему у нас аж два или три вида переменных и какие с чем можно связывать.

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

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

stg

Жизнь оно. Почему везде где пишут о компиляции case-выражений и связывания с паттернами не пишут про то как связываться с дефолтными паттернами? А там очень интересно: либо ты явным образом держишь все значения алгебраических типов в куче (что дорого), либо при связывание приходится распаковывать значения на стек и указателем на объект в куче (что тоже дорого). На самом деле можно и проще, но всё равно почему-то об этом не пишут.

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

f = {} \n {} ->
    let v = {} \n {} -> ...
    in case v of
        _ -> v

Что-то у меня приступ идиотизма. Я правильно понимаю, что в данном случае v настолько реэнтерантно, что вычисляется два раза: один раз в case'е, а второй раз где-то на стороне получателя значения функции?

stg

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

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

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

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

stg

Не совсем понятно кто и как должен обновлять замыкание (переписывать его значением вычисления) в self-updateable модели. Функция в общем случае не может поскольку не знает что обновлять и когда обновлять. Можно конечно генерировать для каждой функции и два тела: одно простое и одно в которое в виде первого аргумента адрес замыкания, но как реализовать диспетчеризацию между этими двумя функциями в компил-тайме я не представляю. Можно использовать для разных APPLY'а для обновляемых и необновляемых замыканий и добавить код перезаписи нужного замыкания в код который передаёт аргументы в функцию в соответствии с её арностью (у каждого замыкания свой указатель на эту функцию и если их будет две — никто не обидится), но этот код сможет только скопировать значение из уже алоцированной функцией памяти (что не очень хорошо), а кроме того должен либо сам раскручивать продолжения, либо обновлять замыкание другим замыканием что попросту бесполезно.

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

stg

А за каким дьяволом в stg используется явное объявление свободных переменных? Даже в статье на которую я уже несколько раз ссылался^W^W^W^W^Wвсе ссылаются приведён набор правил позволяющий вычленить их из кода.

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

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