ndtimofeev
stg Я правильно помню, что в stg нет связывания unboxed variable с чем-то кроме переменных функции и переменных паттерна? И что сделать глобальную unboxed переменную связанную с каким-нибудь массивом нельзя?
ndtimofeev
stg mstg В догонку к #2761901. Если вносить внутрь промежуточного языка работу со стеком, то почему бы не вынести туда и стек, например? Вообще-то потому что стек как алгебраический тип, потребует того чтобы при заходе в каждый конструктор данные распаковывались на стек. Наверное это можно решить хитрым анализом строгости. Хотя я всё равно не очень представляю как выглядит эффективный двусвязный функциональный список.
ndtimofeev
stg mstg Как известно, код промежуточного языка претерпевает ряд преобразований между моментоми когда его исторгает фронтенд и переварит кодогенератор. Возникла неприличная идея ввести примопы для прямого взимодействия со стеками исполнителя. Имея их можно переписать функции любой арности в функции нулевой арности, переписать волшебные продолжения возврата как обычные функции. И всё это на относительно легко управляемом промежуточном языке.
ndtimofeev
Haskell stg Регулярно пухну от того что структура программы на stg как-то странно соотносится с формальным синтаксисом приведённым в ТОЙ САМОЙ СТАТЬЕ. Исходя из последнего expression не может быть переменной, никаких формальных ограничений на связывание примитивных операций с переменными нет. Исходя из самой статьи решительно непонятно почему у нас аж два или три вида переменных и какие с чем можно связывать.
ndtimofeev
Haskell stg mstg В mstg два стека: стек аргументов (поскольку целью кодогенератора является уже управляемый язык потребности отличать boxed и unboxed значения нет и соответственно раздельного стека A и стека B тоже нет) и стек продолжений. На вершине стека объектов всегда лежит замыкание которому передаст управление код конструктора алгебраического типа после того как закончит свои дела (разложит свои кишки по стеку аргументов, например). Это замыкание скорее всего осуществит диспетчеризацию по вычисленному значению или обновит санк значением находящимся на стеке (и передаст управление следующему замыканию со стека продолжений). К достоинству этого подхода можно отнести то что на стеке продолжений можно разместить любое вычисление. Например закинуть туда вычисление n > 1 ортогональных вычислений из цепочки вложенных case'ов с одной ветвью, а потом собрать все их значения одной внутренней вложенной функцией (примерно так как это и происходит в строгих языках: сначала вычисляем все аргументы, затем вызываем код который их использует). К недостаткам — более агрессивное верчение миниинтерпретатора. В оригинальной статье по stg всё немного не так. Есть где-нибудь более проработанный вариант такого подхода?
ndtimofeev
Haskell stg mstg В очередной раз устав воевать с производительностью выходного кода (код в который должна транслироваться программа length $ map (*3) [1..1000000] отрабатывает за 40 секунд в lua и за 10 в luajit) я решил скормить код теста ministg. Результат превзошёл все мои ожидания: он его уже 10 минут жуёт и пока края этому не видно. А вот hugs с тестом справляется секунды за 2.
ndtimofeev
stg Жизнь оно. Почему везде где пишут о компиляции case-выражений и связывания с паттернами не пишут про то как связываться с дефолтными паттернами? А там очень интересно: либо ты явным образом держишь все значения алгебраических типов в куче (что дорого), либо при связывание приходится распаковывать значения на стек и указателем на объект в куче (что тоже дорого). На самом деле можно и проще, но всё равно почему-то об этом не пишут.
ndtimofeev
Haskell Lua stg mstg Расскажу небольшой анекдот перед отъездом. Решил я от отчаяния уменьшить в нескольких тестах число обновляемых замыканий. Уменьшил. Время выполнения выросло, а число заходов в замыкания — нет. Оказалось что санком быть выгоднее чем протсо функцией без аргументов: при заходе в функцию вычитывается её арность из памяти, выделяется память под аргументы, которые снимаются со стека аргументов, создаются итераторы чтобы перебирать элементы на стеке. А санку достаточно запихнуть свой адрес в апдейт-фрейм и вычислить своё тело. Смешно вышло.
ndtimofeev
code Haskell stg
f = {} \n {} ->
    let v = {} \n {} -> ...
    in case v of
        _ -> v

Что-то у меня приступ идиотизма. Я правильно понимаю, что в данном случае v настолько реэнтерантно, что вычисляется два раза: один раз в case'е, а второй раз где-то на стороне получателя значения функции?
ndtimofeev
stg Я правильно понимаю, что вектор ветвления тоже можно держать на стеке аргументов как аргумент для специальной функции вычисленного значения?
ndtimofeev
Lua stg mstg Запилил совместимость выхлопа компилятора с luajit. На тестах где создаётся много санков и тормозов luajit показал в 3 — 4 раза лучшее время выполнения чем просто lua. Ожидаемо. При этом lua использует процентов на 5% больше памяти в пике чем luajit. Странно.
ndtimofeev
Haskell stg mstg Приехали. На всех тестах кроме тех где вычислятор наедается и считает что-нибудь по пол минуты время компиляции стало в лучшем случае сопоставимо со временем вычисления. Очень много времени уходит на чтение маленьких файлов с lua-кодом из которого собирается рантайм-система: комбинируются модели исполнения, модели управления памятью и код сборки рантайм-статистики. Если записать все варианты в один файл и читать только его, время компиляции снизится. Вопрос в том что один большой файл надо как-то хитро форматировать.
ndtimofeev
Haskell stg mstg А вот в #2725825 я не прав. Если рассматривать семантику описанную в той самой оригинальной статье, то в принципе все вычисления происходят в бесконечном цикле на уровне одного вложенного вызова и взаимодействия продолжений через глобальные состояния. Просто функции это очень маленькие. Зашёл в замыкание, а там case внутри. Выложил на control-стек альтернативы, вернул в качестве продолжения заход в case-expression и вышел. Зашёл в продолжение, выяснил что это Int, поматчил его с альтернативами на control-стек'е, вернул в качестве продолжения нужную ветку, вышел. Вот только лунный со своим «избегайте функциональных вызовов» от такого охренеет. Непонятно как при таком подходе ghc таки умудряется пробить стек, если в сложившейся ситуации его разумнее всего держать в куче и в виде односвязного списка, например.
ndtimofeev
stg Не совсем понятно кто и как должен обновлять замыкание (переписывать его значением вычисления) в self-updateable модели. Функция в общем случае не может поскольку не знает что обновлять и когда обновлять. Можно конечно генерировать для каждой функции и два тела: одно простое и одно в которое в виде первого аргумента адрес замыкания, но как реализовать диспетчеризацию между этими двумя функциями в компил-тайме я не представляю. Можно использовать для разных APPLY'а для обновляемых и необновляемых замыканий и добавить код перезаписи нужного замыкания в код который передаёт аргументы в функцию в соответствии с её арностью (у каждого замыкания свой указатель на эту функцию и если их будет две — никто не обидится), но этот код сможет только скопировать значение из уже алоцированной функцией памяти (что не очень хорошо), а кроме того должен либо сам раскручивать продолжения, либо обновлять замыкание другим замыканием что попросту бесполезно.
ndtimofeev
stg mstg В тему #2720146. Мой лунный ленивый вычислятор считает факториал 170 также медленно как питон. При этом сам факториал вычисляется на коробкованных числах путём свёртки списка от 1 до 170. Никаких оптимизаций для чисел или списков нет.
ndtimofeev
stg А за каким дьяволом в stg используется явное объявление свободных переменных? Даже в статье на которую я уже несколько раз ссылался^W^W^W^W^Wвсе ссылаются приведён набор правил позволяющий вычленить их из кода.
ndtimofeev
Haskell stg mstg В догонку к #2719650. Немного поразмыслив, решил пока особенно не колупаться со спасением от переполнения стека явно кривой программы. То есть с одной стороны я уверен, что можно снизить нагрузку на стек исполнителя путём усложнения потока исполнения и перекидывание нагрузки на кучу. С другой стороны проблема решается либо ручным форсированием вычисления аккумулятора, либо заигрыванием с анализатором строгости.
ndtimofeev
Haskell Lua stg mstg Я понял как я ломаю стек лунного: при вычислении длины списка у меня накапливаются ленивые суммирования, которые как я не крути всё равно представляют цепочку не хвостовых вызовов. Когда этих отложенных суммирований набирается 50 — 100 тысяч, а потом внешнее резко форсируется происходит несколько десятков тысяч нерекурсивных вызовов функции рантайма EVAL (вычисляющей отложенное значение и раскручивающей продолжения) и стеку лунного становится плохо. Не знаю как это чинить. Была бы это сишка, можно было бы сделать переход в EVAL в виде jump'а…
ndtimofeev
Lua stg mstg Вообще эффект переписвывание существующих таблиц в lua вместо создания новых меня ошеломил. Поскольку для реализации ADT'ов, замыканий (которые представлены таблицей с функцией и числом обозначающем арность функции), частичного применения, неба и аллаха используются таблицы, то возникает сравнительно парадоксальная ситуация: в то время как SPJ пишет о дороговизне апдейтов замыканий в системе редукции графов, мне дешевле переписывать все замыкания какие можно лишь бы не аллоцировать новые таблицы.
ndtimofeev
Lua stg В тему #2717879. Переписал рантайм-систему с учётом специфики lua и починил апдейты. Длину списка в 10 ^ 4 элементов удалось посчитать за пол секунды. На 10 ^ 5 переполнился стек. Интересно где.
ndtimofeev
stg Updatable-флаг можно выставить любой лямбда-форме. С другой стороны обновление замыкания значение осуществляется только для санка — заамыкания не зависящего от переменных. Тогда не вполне понятно как трактовать наличие данного флага у функций? В Implementing lazy functional languages on stock hardware в разделе 4.2 написано что совершенно безопасно эти флаги можно (но не нужно развесить везде), но мне тем не менее непонятно что должен сделать компилятор найдя такой флаг на верхнеуровневой функции.
ndtimofeev
Lua stg mstg Моя лунная stg-машина считала длинну сгенерированного списка пропущенного через map четыре минуты времени. В списке было 10 ^ 4 элементов. Мусорщик лунного успешно удерживал объём кучи на 40 мегабайтах. Это так мило. Впрочем у меня нахрен сломаны апдейты графа, так что может быть не всё так плохо.
ndtimofeev
stg Долго искал ошибку из-за который проваливался паттерн-матчинг по алгебраическому типу. Оказалось что я в самом stg-коде не так Nil записал.
ndtimofeev
stg mstg Модель ленивого вычислителя прекрасно отработала и вывела число созданных замыканий несмотря на то что я забыл определить примопы. Годно.
ndtimofeev
Haskell stg В понимании семантики stg у меня остались следующие отверстия: зачем нужен letrec (честно говоря я даже синтаксис letrec представляю себе не очень однозначно)? как исполняются primop'ы, насколько они далеки от ffi и могут ли возвращать коробкованные значения? в каком случае нужно форсировать вычисления связанные с раскоробкованными значениями? Последний момент вроде описан в Unboxed value as class citizens in a non-strict functional language. С остальным как-то совсем глухо.
ndtimofeev
Haskell stg Кажется вся эта петрушка с арностью функции push/enter'ом и eval/apply'ем нужна не тогда когда у функции мало аргументов, а тогда когда их больше чем нужно (точнее когда пять аргументов применяется к функции от двух, возвращающей функцию от трёх). Причём это справедливо только в особо полиморфных случаях, когда функция применяющая аргументы не очень хорошо знает к чему она их применяет. Чем же отличается функция ненасыщенная аргументами от простого замыкания, я всё равно не понимаю.
ndtimofeev
Haskell stg Я правильно понимаю что stg вообще живёт без типов и конструктор что-то вроде именованного тупла как в epic? Мне казалось что это может сделать кодогенерацию грустнее…
ndtimofeev
Haskell stg Что-то у меня какое-то недопонимание partial apply: как оно вообще оказывается на уровне stg и откуда проблемы с неизвестной арностью функции? Происходят ли какие-то редукции при частичном применение и если да, то почему?
ndtimofeev
Haskell Lua stg Кажется понял зачем нужен алгебраический тип вокруг встроеннных типов: встроенные типы unboxed и в общем случае хранить в алгебраическом типе вместо значения указатель на вычисление затруднительно. Таким образом, обёртка вокруг встроеннного типа и правда единственный способ дать ему побыть частью ленивого вычисления. Остался только один нюанс: что в терминах lua является unboxed значением?
ndtimofeev
Haskell Lua stg Моя лунная stg-машина посчитала факториал! Поскольку парсер грамматики stg я написал удивительно трансректальным образом, а сам транслятор никак не проверяет корректность AST-дерева перед переписыванием в луну, факториал видимо останется самой сложной программой которую я смог для него написать.
ndtimofeev
Haskell stg Я правильно понимаю что update flag регулирует факт переписывания замыкания после его форсирования? Но что мы можем переписать кроме замены санка на значение в экзотической ситуации когда замыкание зависит только от свободных переменных?