Closed Mazdaywik closed 4 years ago
Один из возможных подходов к решению этой задачи — перенести оптимизацию внутрь прохода обессахаривателя до «расплющивания» вложенных функций. Тогда не будет проблем с конструкцией каррирования, а подстановка будет осуществляться естественным образом.
Но проблема этого подхода в том, что выразить специализацию будет гораздо сложнее. Конструктор каррирования — это просто особый тип скобок, который при специализации «уходит» в сигнатуру, а специализированная функция будет просто принимать переменные-аргументы конструктора каррирования. Если вместо конструктора каррирования хранить тело вложенной функции, то при специализации придётся вычислять его контекст явным образом, т.е. принудительно его «сплющивать» раньше времени.
Поэтому в качестве рабочего варианта предлагается специализировать конструкторы каррирования тем же движком, который специализирует функции.
А ведь специализация функций в некотором смысле эквивалентна прогонке, и даже встраиванию.
Пусть специализируемая функция имеет вид:
$SPEC F (e.STATIC) e.dynamic;
F {
(e.Static) e.Dynamic1 = … <F (e.Static) …> …;
(e.Static) e.Dynamic2 = …;
}
Тогда её специализацию можно свести к встраиванию функции F′
:
$INLINE F′;
F′ {
e.Static = {
e.Dynamic1 = … <<F′ e.Static> …> …;
e.Dynamic2 = …;
};
}
При этом вызовы <F ([static]) [dynamic]>
надо будет заменить на <<F′ [static]> [dynamic]>
.
Но это вовсе не значит, что задача потеряла актуальность. Ведь F′
скомпилируется в каррирование некоторой другой функции (назовём её F′\1
):
$INLINE F′;
F′ {
e.Static = {{ &F′\1 (e.Static) }};
}
F′\1 {
(e.Static) e.Dynamic1 = … <<F′ e.Static> …> …;
(e.Static) e.Dynamic2 = …;
}
Вызовы <<F′ [static]> [dynamic]>
встроятся в <{{&F′\1 [static]}} [dynamic]>
, в которых придётся специализировать конструктор каррирования.
Т.е. от специализации всё равно не убежать.
Над задачей буду работать только я, поскольку Дарья ушла в академический отпуск. Соответственно, веху study spring 2018 снимаю.
Где-то ранее предлагалось все вложенные функции по умолчанию считать прогоняемыми. Предлагается также все вложенные функции считать и специализируемыми тоже — переменные контекста — это и есть специализируемые параметры. Такой взгляд будет особенно продуктивен в условиях и блоках, где эти функции непосредственно вызываются.
Специализация делает функцию на Рефале многоместной — местность, во-первых, определяется числом параметров в объявлении $SPEC
, во-вторых, уточняется подставляемыми значениями на место статических параметров. Их может быть и меньше — статический параметр константен, и больше — на место статического параметра подставляется несколько переменных.
При генерации кода требуется многоместную функцию вновь сделать одноместной. Способ известен — если есть N штук e-параметров, то достаточно (N−1) из них завернуть в скобки.
Предлагается заворачивать в скобки все e-параметры, кроме последнего — это упростит специализацию конструкторов замыканий.
Конструктор замыкания вида
{{ &Func params }}
для оптимизатора представляется в виде фиктивного вызова
<Func params e.@>
где e.@
— placeholder для фактического аргумента в момент будущего вызова. Этот параметр по определению динамический (ибо статические параметры в конктексте, т.е. внутри конструктора). И он так и останется e-переменной после преобразований. Поэтому после преобразований будет построена новая функция Func′
с новым аргументом params′ e.@
. Ей будет соответствовать фиктивный вызов
<Func′ params′ e.@>
Параметр e.@
не будет завёрнут в скобки, потому что мы заворачиваем в скобки все параметры, кроме последнего. Если мы его сотрём, и заменим угловые скобки на двойные фигурные:
{{ &Func′ params′ }}
то получим специализированный конструктор замыкания.
Исключил из вехи, в задачу диплома не входит.
Это не учебная задача. Снял метку «study».
Эту задачу имеет смысл выполнять вместе с #259 и #263.
Конкретные шаги:
$SPEC 〈переменные контекста〉 e.arg;
Динамический параметр — аргумент замыкания должен остаться не завёрнутым в скобки.
$INLINE
/$DRIVE
и $SPEC
больше не должно быть ошибкой.Func*M
, если имя Func
— специализируемое. Функция Func*M@N
должна образовываться путём вычёркивания первых M
предложений.(Spec …)
в рассахаривателе, вызывать TrySpecCall
для замыканий.Забавно, что задачу решает только пункт 5, всё остальное — доработка окружения (как часто и бывает с правками больших систем). Пункты 1 и 2 обязательны — сделать сразу последний пункт без этих правок невозможно. Тупо или не будет работать (будут получаться имена функций с двумя SUF
), или будет порождаться некорректный код при стирании не той призрачной скобки.
Пункты 3 и 4 технически избыточны, и без их выполнения всё будет работать. Разрешать одновременную прогонку и специализацию (3) имеет смысл, поскольку теперь уже это будет поддерживаться на back-end’е (замыкания ведь они неявно $DRIVE
). Синтаксическое ограничение теряет смысл. А не выполнить пункт 4 просто некрасиво, ведь если можно специализировать функцию Func
(или Func\K
), то нет никаких препятствий к специализации Func*N
(или Func\K*N
) — по формату она подходит (ибо просто вычеркнуты несколько предложений), а распространение информации при специализации углубит оптимизацию программы.
Но эту задачу следует отложить. На данный момент ведётся работа #253, которая существенно затрагивает специализатор. А выполнение данной задачи специализатор несколько усложнит.
Вопрос: что делать, если при специализации замыкания полностью исчезает контекст? Тут есть существует два варианта:
Преимуществом генерации указателя является производительность, недостатком — тонкое изменение поведения программы: указатель на функцию меняет тип. У вырожденного объекта замыкания преимущества и недостатки зеркальны генерации указателя.
В идеале все оптимизации должны быть прозрачны: оптимизированная и неоптимизированная программы различаются только быстродействием. Но оптимизация прогонки может удалять шаги рефал-машины, а значит, вызов <Step>
позволяет различать оптимизированные и неоптимизированные программы. Специализация замыканий позволит различать оптимизированные и неоптимизированные программы посредством вызова <Type s.Fn>
.
$ENTRY Test {
= <S 'abc'>;
}
$SPEC S e.ARG;
S {
e.X
= <Type { = e.X }>
: {
'Fg' s.F = <Prout 'Global function'>;
'Fc' s.C = <Prout 'Closure'>;
}
}
Вывод программы будет меняться в зависимости от ключа -OS
.
Кроме того, замена специализированного замыкания без контекста усложнит исправление #276 (см. https://github.com/bmstu-iu9/refal-5-lambda/issues/276#issuecomment-623372133),
Нужно различать два случая:
\n
, :n
, =n
),{{ &F arg }}
.Первую оптимизацию можно добавить хоть сейчас, она не помешает ничему. Функции всё равно будут оптимизироваться в позиции вызова, поэтому стирание призрачной скобки ни на что не повлияет. Вторая оптимизация требует переписывания разметки призрачных скобок.
Убрать ошибку одновременной прогонки и специализации тоже легко. Но без специализации Func*n
делать её как-то некрасиво.
Вместо того, чтобы тянуть вола за хвост, решил добить эту задачу. Правки в OptTree-Spec.ref
оказались достаточно небольшими. Ради упрощения основного кода OptTree-Spec.ref
специализация остаточных функций Func*n
была оформлена на стадии подготовки, а не на стадии анализа вызова. Вместе с каждой функцией Func
запоминаются для оптимизации все возможные Func*n
.
Альтернативный вариант: распознавать не только вызовы с совпадающими именами, но и вызовы функций с суффиксами *n
, такими, что если их удалить, получится имя специализируемой функции. Но такой вариант усложнил бы основной код, а для #253 усложнять код не надо.
Был выполнен стандартный бенчмарк на коммитах 4833a739a263efa2e9598cd04eaf8922ea93e633 (до правок), 4fa21606d2ba5ec804c511eb805fb7f3037b38bc (рефакторинг Reduce
и MapAccum
) и потом на 421f48a9b2ee7dab2fa5744e29c5e15e3f8259dc (Fetch
).
Компьютер: процессор Intel® Core™ i5-2430M? 2,40 ГГц, ОЗУ 8 Гбайт, диск SSD. ОС Windows 10 x64. Компилятор C++ — BCC 5.5.1.
Выполнялось 13 замеров со следующими опциями:
set RLMAKE_FLAGS=-X-ODS
set BENCH_FLAGS=-ODPR
Опции были выбраны из следующих соображений: -X-ODS
, т.к. тестируется специализация, а она нужна, чтобы в специализированных функциях срабатывала прогонка. Сам тестовый прогон имел флаги -ODPR
, чтобы обеспечить большее число шагов и большее покрытие кода, флаг -OS
в BENCH_FLAGS
не использовался, т.к. на разных коммитах выполнялся бы разный объём работы (без него он будет примерно одинаковый).
На первой паре замеров получился измеримый прирост производительности, преимущественно за счёт -OR
.
Замеры до:
Вторые замеры:
Прирост производительности:
(Total refal time)
: 40,495 [40,427…40,803] → 38,601 [38,454…38,852], ускорение достоверное, 4,6 %.Step count
: 47 378 468 → 42 972 636, уменьшилось на 9,2 %.Преимущество достигнуто за счёт ключа -OR
и углублённой оптимизации в GST.ref
. Профиль до оптимизации выглядел как
FilterPatternPos (9295) -> 3109.0 ms (5.42 %, += 5.42 %) rel step time 1.20
FilterResultPos (9295) -> 3085.0 ms (5.38 %, += 10.80 %) rel step time 1.30
Apply (9295) -> 3015.0 ms (5.25 %, += 16.05 %) rel step time 0.59
Map@3 (9295) -> 2320.0 ms (4.04 %, += 20.09 %) rel step time 0.87
Map (9295) -> 2132.0 ms (3.72 %, += 23.81 %) rel step time 0.88
Apply (9295) -> 4281069 (8.92 %, += 8.92 %) rel step time 0.59
Map@3 (9295) -> 2220450 (4.63 %, += 13.54 %) rel step time 0.87
FilterPatternPos (9295) -> 2163791 (4.51 %, += 18.05 %) rel step time 1.20
Map (9295) -> 2036608 (4.24 %, += 22.29 %) rel step time 0.88
FilterResultPos (9295) -> 1979949 (4.12 %, += 26.42 %) rel step time 1.30
После оптимизации:
FilterResultPos (1514) -> 3092.0 ms (5.83 %, += 5.83 %) rel step time 1.28
FilterPatternPos (1514) -> 2942.0 ms (5.55 %, += 11.37 %) rel step time 1.12
Map@3 (1514) -> 2239.0 ms (4.22 %, += 15.60 %) rel step time 0.83
OverlapItem (1514) -> 1937.0 ms (3.65 %, += 19.25 %) rel step time 1.35
Map@4 (1514) -> 1847.0 ms (3.48 %, += 22.73 %) rel step time 0.74
Map@3 (1514) -> 2222760 (5.10 %, += 5.10 %) rel step time 0.83
FilterPatternPos (1514) -> 2165982 (4.97 %, += 10.06 %) rel step time 1.12
Map@4 (1514) -> 2038816 (4.67 %, += 14.74 %) rel step time 0.74
FilterResultPos (1514) -> 1982038 (4.54 %, += 19.28 %) rel step time 1.28
Видно, что сначала были не прооптимизированы вызовы Map
и Apply
, а затем они прооптимизировались. Вот «виновная» функция:
До оптимизаций она трансформировалась так (аварийные предложения убрал для наглядности):
RejectTile {
(e.Tiles#1) e.HeavyTileItems#1
= <UnBracket <Reduce@1 (e.Tiles#1) e.HeavyTileItems#1>>;
}
Reduce@1 {
(e.#0) (s.CurIndexP#2 s.CurIndexR#2 s.ItemWeight#2 s.Ident#2) e.Tail#1
= <Reduce@1
<Fetch
<Map@3 s.CurIndexP#2 e.#0>
{{Pipe$2\1
(&Map (&FilterResultPos s.CurIndexR#2)) (&RejectTile\1\1)
}}
>
e.Tail#1
>;
t.Acc#1 = t.Acc#1;
}
RejectTile\1\1 {
e.Tiles#3 = (e.Tiles#3);
}
Map@3
это проптимизированный (&Map (&FilterPatternPos s.CurIndexP))
. Второй вызов Map
остался не оптимизирован. В оптимизированной версии мы получили:
RejectTile {
(e.Tiles#1) e.HeavyTileItems#1
= <UnBracket <Reduce@1 (e.Tiles#1) e.HeavyTileItems#1>>;
}
Reduce@1 {
(e.#0) (s.CurIndexP#2 s.CurIndexR#2 s.ItemWeight#2 s.Ident#2) e.Tail#1
= <Reduce$1=1@1
(e.Tail#1)
<Fetch <Map@3 s.CurIndexP#2 e.#0> {{&Pipe$2\1@2 s.CurIndexR#2}}>
>;
t.Acc#1 = t.Acc#1;
}
Pipe$2\1@2 {
s.CurIndexR#2 e.Arg#2
= <Fetch <Map@4 s.CurIndexR#2 e.Arg#2> &RejectTile\1\1>;
}
RejectTile\1\1 {
e.Tiles#3 = (e.Tiles#3);
}
Видно, что не смотря на то, что вызов Fetch
оптимизировать не удалось (его аргумент активный, а это пока не поддерживается — #230), замыкание {{&Pipe$2\1 …}}
оптимизировать получилось, благодаря чему проспециализировался второй вызов (&Map (&FilterResultPos s.CurIndexR))
.
И тут я подумал: а может попробовать специализировать и Fetch
? Что из этого получится? Получился коммит 421f48a9b2ee7dab2fa5744e29c5e15e3f8259dc, который измеримого прироста по времени не дал. Замеры:
Метрики:
(Total refal time)
: 38,601 [38,454…38,852] → 38,339 [38,142…39,012], 0,6 %, недостоверно. На самом деле, если посмотреть не 10-й, а 9-й по порядку замер, то верхняя граница доверительного интервала стала бы 38,488, т.е. результат был бы условно достоверным. Но даже если и так, разница слишком мала.Step count
: 42972636 → 42693427, уменьшение на те же 0,6 %.Результат предсказуемый, ведь Fetch
не является узким местом. Но трансформации кода весьма интересны (аварийные предложения не показаны):
RejectTile {
(e.Tiles#1) e.HeavyTileItems#1
= <UnBracket <Reduce@1 (e.Tiles#1) e.HeavyTileItems#1>>;
}
Reduce@1 {
(e.#0) (s.CurIndexP#2 s.CurIndexR#2 s.ItemWeight#2 s.Ident#2) e.Tail#1
= <Reduce$1=1@1
(e.Tail#1) <Fetch@3 <Map@3 s.CurIndexP#2 e.#0> s.CurIndexR#2>
>;
t.Acc#1 = t.Acc#1;
}
Fetch@3 {
e.Argument#1 s.CurIndexR#2 = <Pipe$2\1@2 s.CurIndexR#2 e.Argument#1>;
}
Pipe$2\1@2 {
s.CurIndexR#2 e.Arg#2 = <Fetch@6 <Map@4 s.CurIndexR#2 e.Arg#2>>;
}
Fetch@6 {
e.Argument#1 = (e.Argument#1);
}
Прирост производительности небольшой и только за счёт оптимизации специфического кода — стопок вызовов Pipe
, унаследованных от Простого Рефала. В последнем не было ни присваиваний, ни блоков, поэтому часто использовались Fetch
, Pipe
и вложенные функции. Коммиты этой заявки позволяют оптимизировать программы, написанные в этом устаревшем стиле.
Вообще, эта заявка скорее эстетическая, нежели практическая. Не уверен, что найдётся много кода, где эти правки дадут заметный прирост производительности. Но компилятор стал в некотором смысле цельнее:
MapAccum
и Reduce
это показал.Закрываю задачу.
Если дословно выполнить задания #122 и #126, оптимизатор не будет давать того результата, который хотелось бы (а будет немного хуже). Поясню на примере
Пример
Хотелось бы получить вот такой результат:
Во всех примерах выше была сделана подстановка переменных внутрь замыкания — были построены новые замыкания. Но в актуальной постановке задачи этого не будет. Потому что обессахариватель.
Обессахариватель преобразует программу на Рефале-5λ (или Простом Рефале) в программу на базисном Рефале с условиями (#17) и конструктором каррирования. Сейчас условия нас не интересуют, а вот конструктор каррирования играет первостепенную роль.
Каррированием в математике (лямбда-исчислении, комбинаторной логике и смежных дисциплинах) называется представление функции из N аргументов x1, x2, …, xN как функции одного аргумента x1, которая возвращает функцию одного аргумента x2, которая возвращает функцию одного аргумента x3, … , которая возвращает функцию аргумента xN, которая уже возвращает возвращаемое значение исходной функции.
Конструктором каррирования в промежуточном представлении называется узел
(#ClosureBrackets e.ClosureContext)
, который в скомпилированном коде превращается в операцию создания замыкания.e.ClosureContext
обязан начинаться с имени глобальной функции, остальная часть контекста должна быть пассивной — может состоять только из переменных, структурных и абстрактных скобок и атомов (хотя вроде ничего не должно сломаться, если там окажется вызов функции, но я не гарантирую). В псевдокоде конструктор каррирования будем обозначать как{{ &Func контекст }}
, где&Func
— имя некоторой глобальной функции.На выходе из обессахаривателя листинг 1 превратится в
Вложенные функции превратились в глобальные, при этом в левые части добавились новые параметры, соответствующие захваченным переменным. На местах вложенных функций в левых частях обессахариватель поместил конструкторы каррирования, создающие замыкания из глобальных функций путём связывания части аргумента с актуальными значениями захватываемых переменных.
После оптимизации программа приобретёт следующий вид:
Результат гораздо скромнее. Подстановки переменных повлияли только на конструктор каррирования, сами вложенные функции они не затронули никак.
Что делать
Для этого случая вполне можно создать решение ad hoc — обнаруживая подстановку в конструктор каррирования, сразу же пытаться построить специализированный вариант каррируемой функции. Задача облегчается тем, что имя переменной в конструкторе совпадает с именем переменной в каррируемой функции. Достоинство: не зависит от задачи #126, сохраняет разметку контекста для отладки. Недостаток: частично дублирующаяся логика.
Другой вариант — дождаться решения задачи #126 и для специализации каррирований использовать уже готовый механизм специализации функций. Достоинство: логика не дублируется, повторно используется более общий механизм. Недостаток: реализация специализатора может устранять константные элементы в формате, в итоге сотрётся разметка контекста.
Нюанс
Каркас оптимизатора, построенный в задаче #155, уже содержит логику оптимизации — удаляет конструкторы каррирования после угловой скобки:
В итоге каррированный объект разрушается и становится нечего специализировать.
Изначально это было сделано для упрощения оптимизации встраивания и прогонки. Вложенные функции по умолчанию являются прогоняемыми. Если снимать с них скобки каррирования внутри скобок вызова, то прогонщику достаточно будет рассматривать только вызовы вида
<F …>
. Если не снимать, то прогонщик должен рассматривать и вызовы<F …>
, и вызовы<{{&F …}} …>
.К тому же скобки каррирования впринципе избыточны внутри скобок вызова, и их в принципе снимать там полезно.
Чтобы облегчить задачу специализации, можно отказаться от снятия скобок между проходами оптимизаторов. Хуже не будет, если снимать их в самый последний момент. С другой стороны, сохранение конструктора каррирования может даже упростить прогонщик. В вызовах
<{{&F …}} …>
функцияF
будет считаться всегда прогоняемой, а значит не потребуется отдельная пометка вложенных функций прогоняемых.Важность
Пример кода выше выглядит и является надуманным, и поэтому может показаться, что специализация замыканий — интеллектуальная игра и «экономия на спичках». Это не так.
Присваивания и блоки Рефала-5λ являются синтаксическим сахаром, их рассахариватель преобразует во вложенные функции. Поэтому если оптимизированная функция содержит присваивание, то дальше присваивания оптимизация просто не пройдёт.
В
WithDriveAndAssign
вызов функцииRegex
полностью прогонится, но подстановки переменнойe.Text
за присваивание не протекут. В случаеMapReduce
всё ещё хуже: за первое присваивание не протечёт подстановкаs.Fn
— вызов во втором присваивании будет в общем положении и не будет специализирован.План
Динамический параметр — аргумент замыкания должен остаться не завёрнутым в скобки.
$INLINE
/$DRIVE
и$SPEC
больше не должно быть ошибкой.Func*M
, если имяFunc
— специализируемое. ФункцияFunc*M@N
должна образовываться путём вычёркивания первыхM
предложений.(Spec …)
в рассахаривателе.TrySpecCall
для замыканий.