Использовать Mu в функциях высших порядков в LibraryEx #181

Mazdaywik · 2018-11-21T11:53:49Z

Мотивация

Во-первых, оно нужно для совместимости с ~~Рефалом-05~~ набором библиотек для Рефала-5 (там используется Mu).

Во-вторых, в этом случае библиотекой можно будет пользоваться, не зная функций высших порядков — зная только Рефал-5.

Препятствия и его обход

Задача конфликтует с задачей #91 — при непосредственном косвенном вызове (<s.F …>) проще специализировать Map в эффективную функцию. Если внутри Apply вместо косвенного вызова использовать Mu, то это Mu рискует так и остаться невстроенной в программе.

Проблема разрешима. Самый бесхитростный ad hoc вариант — объявить Mu интринстиком, распознавать оптимизатором лямбду после неё и встраивать. ~~Но, если подумать, правильнее объявлять интринстиками Type и __FindMuPtr, которые используются внутри Mu.~~

Другая проблема в том, что функция Mu выполняется за несколько шагов, которые сокрываются при помощи __Step-Start и __Step-End. Даже после встраивания и оптимизации эти две функции сохранятся в остаточной программе. Как вариант, их тоже можно сделать интринстиками, специальным ключом компилятора их вызовы просто удалять.

Неактуальные абзацы вычеркнуты, см. #254 и #260.

Но в любом случае об оптимизации думать надо будет тогда, когда ею будем заниматься. Важно, что сложности здесь технические, а не принципиальные.

The text was updated successfully, but these errors were encountered:

Mazdaywik · 2018-11-21T11:59:31Z

А вообще, __Step-Start и __Step-End не нужны. Нужна директива

$ONESTEP Func1, Func2, Func3;

которая сама добавляет эти обёртки.

И вообще, прогонка по определению выполняет шаги во время компиляции, а это значит, что значение функции Step при использовании оптимизации не определено.

Mazdaywik · 2020-05-18T07:44:36Z

Задача сводится к изменению всего одной строчки:

 */
 Apply {
-  s.Fn e.Argument = <s.Fn e.Argument>;
+  s.Fn e.Argument = <Mu s.Fn e.Argument>;

   (t.Closure e.Bounded) e.Argument
 }

Но не всё так просто. Эта замена приведёт к тому, что в функциях Map, MapAccum и Reduce на каждой итерации будет вызываться Mu, которая в свою очередь, будет вызывать __Step-Drop и __Meta_Mu (#254). Кроме того, вызов Mu блокирует возможности оптимизации прогонки в специализированных экземплярах уже упомянутых Map, MapAccum и Reduce.

Замедление программы в обычном режиме можно потерпеть, но то, что Map и другие функции не будут до конца оптимизироваться — обидно. Поэтому вставлять вызов Mu в Apply нужно не ранее базовой реализации __Meta_Mu как интринсика (#260).

Влияние на производительность

Было сделано 4 замера производительности — без правки Apply в режимах без оптимизации (RLMAKE_FLAGS=) и с оптимизацией RLMAKE_FLAGS=-ODS, и с модифицированной Apply в тех же режимах.

Выполнялось по 13 замеров с опциями BENCH_FLAGS= и RLC_FLAGS=, компилятор C++ — BCC 5.5.1, процессор Intel® Core™ i5-2430M 2,40 Ггц, ОЗУ 8 Гбайт, ОС Windows 10 x64.

Замеры:

Анализ замеров

Использовался стандартный бенчмарк, моделирующий самоприменение компилятора. Этот бенчмарк является адекватным для рассматриваемой задачи, поскольку использование функций типа Map со вложенными функциями в качестве аргументов является рекомендуемым стилем программирования на языке.

Снижение производительности `<s.Fn …>` → `<Mu s.Fn …>`

Рассматриваться будет полное время выполнения программы (Total program time), поскольку __Step-Drop и __Meta-Mu оказывают заметный вклад в производительность и сами при этом являются нативными. Хотя и чистое время Рефала ((Total refal time)) показывает заметную деградацию, связанную с вызовом функции Mu.

Без оптимизаций, Total program time: 22,047 [21,906…22,094] → 24,828 [24,766…24,953], достоверное замедление. Абсолютная разница медиан 2,781 с, относительное замедление 12 %.
Без оптимизаций, (Total refal time): 19,561 [19,351…19,785] → 21,293 [21,085…21,337], достоверное замедление. Абсолютная разница медиан 1,732 с, относительное замедление 8,8 %.
Без оптимизаций, число шагов: 23 645 377 → 32 498 394, абсолютный прирост 8 853 017, относительный прирост 37 %.
-ODS, Total program time: 17,516 [17,469…17,579] → 20,297 [20,281…20,391], достоверное замедление. Абсолютная разница медиан 2,781 с, относительное замедление 15 %.
-ODS, (Total refal time): 15,634 [15,544…15,777] → 17,312 [17,152…17,373], достоверное замедление. Абсолютная разница медиан 1,678 с, относительное замедление 10 %.
-ODS, число шагов: 16 898 749 → 24 699 624, абсолютный прирост 7 800 875, относительный прирост 46 %.

Таким образом, время самоприменения компилятора замедляется на 12–15 %.

Абсолютный прирост по времени для неоптимизированной и оптимизированной программ оказался сравним, для полного времени программы он вообще совпал (объяснимо шагом квантования), для чистого времени программы в результате оптимизации уменьшился. Объяснить это явление я затрудняюсь. Уменьшение, наверное, можно объяснить тем, что функция Mu встроилась.

Относительное замедление для режима оптимизации увеличилось, поскольку абсолютная разница осталась та же, а общее время уменьшилось.

Число шагов возросло значительно. По абсолютным значениям прирост в оптимизированной программе меньше, т.к. функция Mu встроилась. По относительным больше, т.к. меньше общее число шагов.

Эффект от оптимизации при использовании `Mu`

Вставка вызова Mu в Apply должна снизить эффект от оптимизации. Ранее, вызовы функций в функциях типа Map могли встроиться, а теперь встроиться не могут.

<s.Fn …>, Total program time: 22,047 [21,906…22,094] → 17,516 [17,469…17,579], ускорение достоверное. Абсолютная разница 4,531 с, относительное ускорение 20,6 %.
<s.Fn …>, (Total refal time): 19,561 [19,351…19,785] → 15,634 [15,544…15,777], ускорение достоверное. Абсолютная разница 3,927 с, относительное ускорение 20,0 %.
<s.Fn …>, число шагов: 23 645 377 → 16 898 749, абсолютная разница 6 746 628, относительная разница 29 %.
<Mu s.Fn …>, Total program time: 24,828 [24,766…24,953] → 20,297 [20,281…20,391], ускорение достоверное. Абсолютная разница 4,531 с, относительное ускорение 18,2 %.
<Mu s.Fn …>, (Total refal time): 21,293 [21,085…21,337] → 17,312 [17,152…17,373], ускорение достоверное. Абсолютная разница 3,981 с, относительное ускорение 18,7 %.
<Mu s.Fn …>, число шагов: 32 498 394 → 24 699 624, абсолютная разница 7 798 770, относительная разница 24 %.

Временной эффект от оптимизации незначительно меньше — около 1–2 %. Абсолютное сокращение числа шагов выше, поскольку в неоптимизированной версии добавляются вызовы встраиваемой функции Mu, которые оптимизатор устраняет. Но это «компенсируется» избыточными вызовами __Step-Drop и __Meta_Mu.

Связь с #260 (оптимизация интринсиков)

Выше была сделана оценка производительности по двум измерениям: замедление программы внедрением Mu и снижение эффекта оптимизации.

В первом замере показано, что в режиме оптимизации программа замедляется. Но если компилятор сможет оптимизировать Mu, оптимизированная программа замедляться перестанет!

Mazdaywik · 2020-05-18T07:46:34Z

@Cstyler, назначаю эту задачу Вам. Когда реализуете базовый вариант оптимизации Mu, повторите замеры, сделанные выше, и добавьте Mu в Apply.

Cstyler · 2020-06-09T13:07:06Z

@Mazdaywik мне нужно объявить __Meta_Mu как интринсик, заменить вызов в Apply на вызов Mu, а затем сделать замеры?

Mazdaywik · 2020-06-11T11:09:16Z

Да, нужно добавить объявления интринсиков в src/lib/common/refal5-builtins.refi, а в LibraryEx.refi (в той же папке) заменить в Apply вызов <s.Fn e.Argument> на <Mu s.Fn e.Argument и повторить замеры:

 */
 Apply {
-  s.Fn e.Argument = <s.Fn e.Argument>;
+  s.Fn e.Argument = <Mu s.Fn e.Argument>;

   (t.Closure e.Bounded) e.Argument
 }

После внесения правок в библиотеки нужно их пересобрать: или запустить src/lib/make.*, или src/compiler/update-lib.*.

Cstyler · 2020-06-11T17:51:24Z

@Mazdaywik
Добавил объявления для __Meta_Mu и остальных интринсиков в конец src/lib/common/refal5-builtins.refi, заменил вызов в src/lib/common/LibraryEx.refi. src/lib/make.sh выдал ошибку Function Mu is not defined. Вставил команду в LibraryEx.refi:

*$FROM Library    
$EXTERN Mu;

Библиотека и компилятор успешно скомпилировались, но итоговый компилятор падал при его использовании с ошибкой INTERNAL ERROR: unresolved external: Mu#0:0. Сделал объявление $META Mu; в LibraryEx.refi, билд библиотеки прошёл успешно, но при билде компилятора написало Function Mu is already defined. В чём может быть проблема?
Ещё я не понял, как включить флаг оптимизации интринсиков при компиляции компилятора, нашёл переменную RLC_FLAGS, но не понял, где она заполняется. Цель же в том чтобы в LibraryEx уже не было вызова Mu, видимо из-за того что флаг -Oi не указан при компиляции и возникает такая ошибка.

Mazdaywik · 2020-06-12T18:30:56Z

Это особенности скриптов сборки библиотек, библиотеки собираются без стандартного вступления. Нужно добавить не $EXTERN, а $META:

*$FROM Library
$META Mu;

Cstyler · 2020-06-12T19:06:53Z

@Mazdaywik
Использовал *$FROM Library $META Mu;. Библиотека скомпилировалась, но при сборке компилятора та же ошибка что была без $FROM: Function Mu is already defined.

Добавление определений интринсиков в refal5-builtins.refi успешно компилируется на уровне библиотеки и на уровне компилятора.

Mazdaywik · 2020-06-17T14:12:21Z

Посмотрю после экзаменов, почему там не компилируется.

Cstyler · 2020-06-17T17:35:30Z

При использовании *$FROM Library $META Mu; всё-таки ошибка ещё на компиляции либы:
../../../lib/common/LibraryEx.refi:12:7: ERROR: Function Mu is already defined
не заметил её, потому что билд в конце пишет "Compilation succeeded"

Повторил на компиляторе c ветки master, та же самая ошибка.

Mazdaywik · 2020-06-23T10:07:03Z

Не, предыдущему комментарию просьба не верить, он кривой.

Mazdaywik · 2020-06-23T10:14:24Z

Вот какие правки нужно было вносить, чтобы работало:

index b1e4e980..bc5487e5 100644
--- a/src/lib/common/LibraryEx.refi
+++ b/src/lib/common/LibraryEx.refi
@@ -9,7 +9,7 @@
   e.Arg, e.Res, e.Bounded ::= e.AnyExpr
 */
 Apply {
-  s.Fn e.Argument = <s.Fn e.Argument>;
+  s.Fn e.Argument = <Mu s.Fn e.Argument>;

   (t.Closure e.Bounded) e.Argument
     = <Apply t.Closure e.Bounded e.Argument>;
diff --git a/src/lib/make.bat b/src/lib/make.bat
index 5b47c78c..300fa75e 100644
--- a/src/lib/make.bat
+++ b/src/lib/make.bat
@@ -28,7 +28,7 @@ setlocal
   rmdir %TARGET%\x

   for %%s in (%LIBS%) do (
-    ..\..\bin\rlc-core -C %RLC_FLAGS% %%s -d common
+    ..\..\bin\rlc-core -C %RLC_FLAGS% %%s -d common --prelude=refal5-builtins.refi
     ..\..\bin\rlc-core --no-sources -R -o inco.bin --incorporated=%%~ns
     find "//FROM" < %%s.ref > %TARGET%\%%s.rasl.froms
     if exist %%s.cpp move %%s.cpp %TARGET%
diff --git a/src/lib/make.sh b/src/lib/make.sh
index 704914d6..fc65a834 100755
--- a/src/lib/make.sh
+++ b/src/lib/make.sh
@@ -11,7 +11,7 @@ compile_separated() {

   for s in ${LIBS}; do
     # shellcheck disable=SC2086
-    ../../bin/rlc-core -C ${RLC_FLAGS} "$s" -d common
+    ../../bin/rlc-core -C ${RLC_FLAGS} "$s" -d common --prelude=refal5-builtins.refi
     ../../bin/rlc-core --no-sources -R -o inco.bin --incorporated="$s"
     grep '//FROM' < "$s".ref > "$TARGET/$s".rasl.froms
     [[ -e "$s".cpp ]] && mv "$s".cpp "$TARGET"

Cstyler · 2020-06-23T14:24:19Z

@Mazdaywik Перед запуском бенчмарков для компилятора, в котором __Meta_Mu интринсик и в Apply вызов заменён, нужно собрать компилятор и библиотеку с RLMAKE_FLAGS=-X-OiDS или оставить без флагов?

Mazdaywik · 2020-06-23T21:10:46Z

Так. Что нужно сделать.

Нужно поместить в refal5-builtins.refi объявления $INTRINSIC для всех оптимизируемых функций.
Нужно внести правки из предыдущего комментария. Можно даже положить листинг в файл patch.txt и выполнить в консоли
```
git apply < patch.txt
```
Нужно повторить замеры из примера выше + замер, о котором я писал в письме. Все эти замеры войдут потом в записку.

Замечу, что ошибка со сборкой библиотек выполнить бенчмарк мне почему-то не помешала. А Вы заметили, что она есть.

в Apply. Обновление скриптов билда библиотеки #181

Cstyler · 2020-06-25T20:46:19Z

Скрипт update-lib.sh принимает флаги через переменную RLC_FLAGS. В benchmark.sh вызывается update-lib.sh без флага RLC_FLAGS. Поэтому при запуске бенчмарка помимо RLMAKE_FLAGS нужно также экспортировать переменную RLC_FLAGS, иначе Mu не оптимизируется. По крайней мере на моих замерах резко уменьшилось кол-во шагов и время компиляции после указания флага RLC_FLAGS=-OiDS.

Mazdaywik · 2020-06-27T15:51:10Z

Да, для тестов переменную RLC_FLAGS устанавливать желательно, но не обязательно. Файл refal5-builtins.refi неявно инклюдится во все файлы с расширением *.ref (в *.sref не инклюдится, но они погоды не делают). Файл LibraryEx инклюдится явно.

Поэтому без опций RLC_FLAGS не оптимизируется только Library.ref и LibraryEx.ref, но в них оптимизировать почти нечего.

в Apply. Обновление скриптов билда библиотеки #181 #260

…181 #260

После записи функции Apply через Mu компилятор стал требовать большего числа шагов для своей работы, из-за чего автотест very-big-function-jump.BAD-SYNTAX.sref стал падать на лимите шагов для компилятора. Этот коммит повышает лимит шагов.

Mazdaywik added the task label Nov 21, 2018

Mazdaywik self-assigned this Nov 21, 2018

This was referenced Aug 6, 2019

Новая реализация метафункций (Mu, Residue, Up, Ev-met) #254

Closed

Глобальная оптимизация #255

Closed

Интринсики для встроенных функций #260

Closed

Mazdaywik assigned Cstyler May 18, 2020

Mazdaywik added the study label May 18, 2020

Mazdaywik added this to the study spring 2020 milestone May 18, 2020

Mazdaywik mentioned this issue May 18, 2020

Подумать о сборке мусора #247

Open

Mazdaywik removed their assignment May 25, 2020

This comment has been minimized.

Sign in to view

Cstyler added a commit that referenced this issue Jun 25, 2020

Обновление библиотеки: добавление всех интринсиков, замена на Mu

1bc473c

в Apply. Обновление скриптов билда библиотеки #181

Cstyler mentioned this issue Jun 25, 2020

Интринсики #301

Merged

Cstyler added a commit that referenced this issue Jun 27, 2020

Обновление библиотеки: добавление всех интринсиков, замена на Mu

8266826

в Apply. Обновление скриптов билда библиотеки #181 #260

Cstyler added a commit that referenced this issue Jun 27, 2020

Обновление библиотеки: добавление интринсиков Chr, Ord, Lower, Upper. #…

3cf32f2

…181 #260

Mazdaywik closed this as completed in f893b74 Jun 29, 2020

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Использовать Mu в функциях высших порядков в LibraryEx #181

Использовать Mu в функциях высших порядков в LibraryEx #181

Mazdaywik commented Nov 21, 2018 •

edited

Loading

Mazdaywik commented Nov 21, 2018

Mazdaywik commented May 18, 2020

Mazdaywik commented May 18, 2020

Cstyler commented Jun 9, 2020

Mazdaywik commented Jun 11, 2020 •

edited

Loading

Cstyler commented Jun 11, 2020 •

edited

Loading

Mazdaywik commented Jun 12, 2020

Cstyler commented Jun 12, 2020 •

edited

Loading

Mazdaywik commented Jun 17, 2020

Cstyler commented Jun 17, 2020

This comment has been minimized.

Mazdaywik commented Jun 23, 2020

Mazdaywik commented Jun 23, 2020

Cstyler commented Jun 23, 2020 •

edited

Loading

Mazdaywik commented Jun 23, 2020

Cstyler commented Jun 25, 2020

Mazdaywik commented Jun 27, 2020

Использовать Mu в функциях высших порядков в LibraryEx #181

Использовать Mu в функциях высших порядков в LibraryEx #181

Comments

Mazdaywik commented Nov 21, 2018 • edited Loading

Мотивация

Препятствия и его обход

Mazdaywik commented Nov 21, 2018

Mazdaywik commented May 18, 2020

Влияние на производительность

Анализ замеров

Снижение производительности <s.Fn …> → <Mu s.Fn …>

Эффект от оптимизации при использовании Mu

Связь с #260 (оптимизация интринсиков)

Mazdaywik commented May 18, 2020

Cstyler commented Jun 9, 2020

Mazdaywik commented Jun 11, 2020 • edited Loading

Cstyler commented Jun 11, 2020 • edited Loading

Mazdaywik commented Jun 12, 2020

Cstyler commented Jun 12, 2020 • edited Loading

Mazdaywik commented Jun 17, 2020

Cstyler commented Jun 17, 2020

This comment has been minimized.

Mazdaywik commented Jun 23, 2020

Mazdaywik commented Jun 23, 2020

Cstyler commented Jun 23, 2020 • edited Loading

Mazdaywik commented Jun 23, 2020

Cstyler commented Jun 25, 2020

Mazdaywik commented Jun 27, 2020

Mazdaywik commented Nov 21, 2018 •

edited

Loading

Снижение производительности `<s.Fn …>` → `<Mu s.Fn …>`

Эффект от оптимизации при использовании `Mu`

Mazdaywik commented Jun 11, 2020 •

edited

Loading

Cstyler commented Jun 11, 2020 •

edited

Loading

Cstyler commented Jun 12, 2020 •

edited

Loading

Cstyler commented Jun 23, 2020 •

edited

Loading