Mazdaywik
commented
2 years ago Задача не актуальная…
Задача не актуальная, т.к. сопоставление с образцом не является узким местом. Для примера возьмём применение компилятора Рефала-05 к исходникам MSCP-A:
*Compiling mscp-a.ref:
*Compiling accessMSCP.ref:
*Compiling AnalyzeFunDef.ref:
*Compiling basics.ref:
*Compiling c-prefal-decompiled.ref:
*Compiling DiofEqs.ref:
*Compiling Drive.ref:
*Compiling Generalize.ref:
*Compiling prefal-decompiled.ref:
*Compiling residual.ref:
*Compiling Stack.ref:
*Compiling Unfold_SCP.ref:
*Compiling WordEqsCases.ref:
*Compiling WordEquations.ref:
+Linking D:\Mazdaywik\Documents\Refal-05\lib/Library.c
+Linking D:\Mazdaywik\Documents\Refal-05\lib/refal05rts.c
*** Compilation successed ***
Total program time: 8.641 seconds (100.0 %).
(Total refal time): 7.044 seconds (81.5 %).
Linear result time: 2.695 seconds (31.2 %).
Linear pattern time: 1.659 seconds (19.2 %).
Builtin time: 1.597 seconds (18.5 %).
t- and e-var copy time: 1.349 seconds (15.6 %).
Open e-loop time (clear): 0.891 seconds (10.3 %).
Repeated e-var match time (inside e-loops): 0.450 seconds (5.2 %).
Step count 15699483
Memory used 1987669 nodes, 1987669 * 16 = 31802704 bytesПостроение результатных выражений (31,2 %) требует в полтора больше времени, чем сопоставление с образцом (19,2 %).
Если мы просуммируем все компоненты стадии анализа (19,2 + 10,3 + 5,2 = 34,7 %) и стадии синтеза (31,2 + 15,6 = 46,7 %), то всё равно выйдет, что стадия синтеза выполняется в 1,35 раз дольше, чем стадия анализа. Оптимизация сопоставления с образцом может ускорить только два из трёх компонентов стадии анализа, т.к. сопоставление с повторными переменными останется неизменным.
Тестирование выполнялось на коммитах https://github.com/Mazdaywik/Refal-05/commit/c5891a3b820a7379c2ceb963777745947ca481d1 Рефала-05 и https://github.com/Mazdaywik/refal-5-framework/commit/1c1888c972786f1047419f3cadc81fda405d2d43 фреймворка. Во фреймворке несколько последних коммитов посвящены борьбе с избыточными копированиями переменных.
Конечно, результат не очень репрезентативен, т.к. тестировалось всего одно приложение на всего одном наборе входных данных. Но нагляден.
Интересно разобраться, почему стадия синтеза такая медленная. Нужно выполнить профилирование. Анализ производительности выполнялся на Linux, вернее на WSL версии 2, т.к. там есть соответствующие инструменты (gprof на Windows даёт неточный результат).
Рефал-05 был собран gcc с флагами -DR05_CLOCK_SKIP=20 -O1 -pg (включает код профилирования для gprof), был склонирован репозиторий MSCP-A, адаптирован для Рефала-05 (удалены лишние функции) и собраны в нём все исходники:
mazdaywik@Mazdaywik-NB10:~/MSCP-A05$ ../Refal-05/bin/refal05c *.ref
*Compiling AnalyzeFunDef.ref:
*Compiling DiofEqs.ref:
*Compiling Drive.ref:
*Compiling Generalize.ref:
*Compiling Stack.ref:
*Compiling Unfold_SCP.ref:
*Compiling WordEqsCases.ref:
*Compiling WordEquations.ref:
*Compiling accessMSCP.ref:
*Compiling basics.ref:
*Compiling residual.ref:
*** Compilation successed ***
Total program time: 26.098 seconds (100.0 %).
(Total refal time): 19.633 seconds (75.2 %).
Linear result time: 7.500 seconds (28.7 %).
Linear pattern time: 7.017 seconds (26.9 %).
Builtin time: 6.465 seconds (24.8 %).
Open e-loop time (clear): 2.559 seconds (9.8 %).
Repeated e-var match time (inside e-loops): 1.677 seconds (6.4 %).
t- and e-var copy time: 0.740 seconds (2.8 %).
Repeated t-var match time (inside e-loops): 0.140 seconds (0.5 %).
Step count 13381086
Memory used 1987669 nodes, 1987669 * 32 = 63605408 bytes(Это запуск Рефала-05, собранного с -pg, специальная сборка работает медленнее обычной.)
Полученный профиль выглядит так:
Flat profile:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls us/call us/call name
18.56 0.80 0.80 122974329 0.01 0.01 r05_alloc_node
14.15 1.41 0.61 839352 0.73 1.21 copy_nonempty_evar
10.44 1.86 0.45 334882 1.34 1.35 output_func
6.50 2.14 0.28 139759020 0.00 0.00 ensure_memory
5.68 2.39 0.25 42443937 0.01 0.01 list_splice
3.25 2.53 0.14 21891348 0.01 0.01 r05_brackets_left
3.13 2.66 0.14 147716732 0.00 0.00 r05_empty_seq
…Существенное время в работе программы занимают r05_alloc_node и copy_nonempty_evar (замер последней — 0,61 секунда (третья колонка) в целом согласуется с t- and e-var copy time: 0.740 seconds (2.8 %).). Заметную долю времени требует также output_func (вызывается из Putout, компилятор действительно генерирует длинные тексты на Си), ensure_memory и list_splice. Т.е., в топ-5 четыре функции относятся к операциям синтеза.
С чего бы это? r05_alloc_node действительно вызывается очень много раз (122 974 329). Но ensure_memory и r05_empty_seq вызываются даже чаще (соответственно, 139 759 020 и 147 716 732), но требуют меньше времени. Давайте посмотрим на r05_alloc_node и подумаем, что же в ней может выполняться так медленно?
Всего лишь взятие звена из списка и его частичная инициализация (вызов ensure_memory не считаем, т.к. он в профиле подсчитан отдельно). Неужели эти три присваивания такие медленные?
Ответ нам даст другой диагностический инструмент — Cachegrind, инструмент Valgrind’а. Отладчик Valgrind интерпретирует машинный код инструкция за инструкцией, выполняя при этом дополнительную диагностику. Чаще всего используется инструмент Memcheck, проверяющий правильность обращения к памяти (позволяет выявлять работу с неправильными указателями, выход за границы объектов в динамической памяти, утечки памяти и т.д.). Инструмент Cachegrind моделирует кэш процессора и для каждого обращения к памяти определяет, был ли промах кэша. Конечно, модель, скорее всего, отличается от реального кэша, но результат, скорее всего, адекватен.
Cachegrind отображает статистику в 10 колонок: первые три колонки на кэш инструкций, вторые три — на операции чтения, третьи три — на операции записи, последняя — имя функции или строчка кода. В каждой группе из трёх колонок первая — число инструкций/записей/чтений, вторая — промах кэша L1, третья — промах кэша L2.
Полный профиль: profile-cachegrind.txt.
Начало профиля выглядит так:
--------------------------------------------------------------------------------
Ir I1mr ILmr Dr D1mr DLmr Dw D1mw DLmw file:function
--------------------------------------------------------------------------------
2,068,034,248 2 2 147,716,732 0 0 0 0 0 /home/mazdaywik/Refal-05/src/../lib/refal05rts.c:r05_empty_seq
1,548,224,347 3 3 376,872,051 2,026,113 744,485 376,872,051 4,776 12 /home/mazdaywik/Refal-05/src/../lib/refal05rts.c:list_splice
1,229,743,290 2 2 491,897,316 37,845,926 7,009,149 491,897,316 10,056,602 1,931,757 /home/mazdaywik/Refal-05/src/../lib/refal05rts.c:r05_alloc_node
931,135,184 4 4 297,310,110 7,054,425 191,442 197,676,447 11,176 21 /home/mazdaywik/Refal-05/src/../lib/refal05rts.c:r05_brackets_left
855,569,869 1 1 122,224,267 0 0 244,448,534 1,165,303 392,675 /home/mazdaywik/Refal-05/src/../lib/refal05rts.c:weld
633,811,612 4 4 145,134,156 782,198 123,861 127,152,110 25,325 34 /home/mazdaywik/Refal-05/src/../lib/refal05rts.c:r05_tvar_left
628,874,731 2 2 256,204,531 3,634,465 332,348 56,176,385 0 0 /home/mazdaywik/Refal-05/src/../lib/refal05rts.c:move_left
603,184,565 2 2 119,049,585 27,000 60 43,651,515 6,542 2 /home/mazdaywik/Refal-05/src/../lib/refal05rts.c:fast_clock
600,911,136 175 94 190,532,500 41,371,420 4,565,250 103,106,540 1,729 60 /home/mazdaywik/Refal-05/src/../lib/refal05rts.c:copy_nonempty_evar
573,060,629 1,910 9 279,549,716 1,751 9 6,002,602 987,881 987,869 /home/mazdaywik/Refal-05/src/../lib/refal05rts.c:ensure_memory
378,648,842 1,039 80 86,605,877 280,598 38,447 75,675,069 3,469 11 /home/mazdaywik/Refal-05/src/../lib/refal05rts.c:r05_svar_leftВидно, что функции r05_alloc_node и copy_nonempty_evar имеют значительную долю промахов кэша. Рассмотрим профиль первой функции:
368,922,987 1 1 0 0 0 122,974,329 0 0 struct r05_node *r05_alloc_node(enum r05_datatag tag) {
. . . . . . . . . struct r05_node *node;
. . . . . . . . .
122,974,329 1 1 0 0 0 122,974,329 2,762 10 ensure_memory();
122,974,329 0 0 122,974,329 0 0 0 0 0 node = s_free_ptr;
245,948,658 0 0 122,974,329 37,845,926 7,009,149 122,974,329 0 0 s_free_ptr = s_free_ptr->next;
122,974,329 0 0 0 0 0 122,974,329 10,053,840 1,931,747 node->tag = tag;
. . . . . . . . . return node;
245,948,658 0 0 245,948,658 0 0 0 0 0 }Число 245 млн в первой колонке у строки s_free_ptr = s_free_ptr->next; обусловлено тем, что в ней выполняются две инструкции — инструкция чтения поля next и инструкция записи в глобальную переменную. Из инструкций чтения в этой строке примерно треть промахиваются мимо кэша L1 и каждая двадцатая — мимо кэша L2.
При выполнении строчки node->tag = tag; в двенадцатой части случаев строка кэша, содержащая узел списка, помечена доступной для чтения. Для нас это роли не играет.
. . . . . . . . . static void copy_nonempty_evar(
. . . . . . . . . struct r05_node *evar_b_sample, struct r05_node *evar_e_sample
5,036,112 22 13 0 0 0 3,357,408 1,071 8 ) {
839,352 0 0 839,352 34,427 3,397 0 0 0 struct r05_node *limit = evar_e_sample->next;
1,678,704 0 0 0 0 0 839,352 658 52 clock_t start_copy_time = clock();
. . . . . . . . .
1,678,704 0 0 0 0 0 0 0 0 struct r05_node *bracket_stack = 0;
. . . . . . . . .
95,921,192 0 0 0 0 0 0 0 0 while (evar_b_sample != limit) {
94,242,488 76 41 47,121,244 33,338,144 3,754,456 47,121,244 0 0 struct r05_node *copy = r05_alloc_node(evar_b_sample->tag);
. . . . . . . . .
141,363,732 0 0 47,121,244 0 0 0 0 0 if (is_open_bracket(copy)) {
3,827,940 0 0 0 0 0 3,827,940 0 0 copy->info.link = bracket_stack;
7,655,880 0 0 0 0 0 0 0 0 bracket_stack = copy;
86,586,608 77 40 0 0 0 0 0 0 } else if (is_close_bracket(copy)) {
. . . . . . . . . struct r05_node *open_cobracket = bracket_stack;
. . . . . . . . .
7,655,880 0 0 0 0 0 0 0 0 assert(bracket_stack != 0);
7,655,880 0 0 3,827,940 42,538 0 0 0 0 bracket_stack = bracket_stack->info.link;
. . . . . . . . . r05_link_brackets(open_cobracket, copy);
. . . . . . . . . } else {
78,930,728 0 0 39,465,364 0 0 39,465,364 0 0 copy->info = evar_b_sample->info;
. . . . . . . . . }
. . . . . . . . .
47,121,244 0 0 47,121,244 7,903,153 807,268 0 0 0 evar_b_sample = evar_b_sample->next;
. . . . . . . . . }
. . . . . . . . .
1,678,704 0 0 0 0 0 0 0 0 assert(bracket_stack == 0);
. . . . . . . . .
1,678,704 0 0 0 0 0 839,352 0 0 add_copy_tevar_time(clock() - start_copy_time);
5,036,112 0 0 4,196,760 25,261 78 0 0 0 }Здесь для нас существенны промахи кэша в строчках struct r05_node *copy = r05_alloc_node(evar_b_sample->tag); и evar_b_sample = evar_b_sample->next; — при создании копии оригинал выражения часто оказывается вне кэша и его приходится подгружать. Почему после чтения evar_b_sample->tag весь узел не закэшировался и последующее чтение evar_b_sample->next также даёт промахи кэша, мне не очевидно.
Заметное время работы имеет и функция list_splice, посмотрим и на неё тоже:
. . . . . . . . . static struct r05_node *list_splice(
. . . . . . . . . struct r05_node *res, struct r05_node *begin, struct r05_node *end
339,551,496 0 0 0 0 0 212,219,685 0 0 ) {
339,551,496 1 1 0 0 0 42,443,937 4,776 12 if ((res != begin) && ! r05_empty_seq(begin, end)) {
. . . . . . . . . struct r05_node *prev_res = res->prev;
40,736,143 0 0 40,736,143 1,213,659 462,350 0 0 0 struct r05_node *prev_begin = begin->prev;
40,736,143 0 0 40,736,143 742,905 282,074 0 0 0 struct r05_node *next_end = end->next;
. . . . . . . . .
122,208,429 0 0 40,736,143 69,549 61 40,736,143 0 0 weld(prev_res, begin);
122,208,429 0 0 0 0 0 40,736,143 0 0 weld(end, res);
122,208,429 0 0 0 0 0 40,736,143 0 0 weld(prev_begin, next_end);
. . . . . . . . . } else {
. . . . . . . . . /* Цель достигнута сама по себе */
84,887,874 1 1 0 0 0 0 0 0 return res;
. . . . . . . . . }
. . . . . . . . .
81,472,286 1 1 0 0 0 0 0 0 return begin;
254,663,622 0 0 254,663,622 0 0 0 0 0 }Странно, что строчка struct r05_node *prev_res = res->prev; профиля не имеет, а строчка weld(prev_res, begin); имеет некоторое количество промахов. Возможно, это последствия оптимизации в режиме -O1, так что строчку с weld следует трактовать как:
122,208,429 0 0 40,736,143 69,549 61 40,736,143 0 0 weld(res->prev, begin);Здесь тоже интересно, что обращения к полям ->next и ->prev приводят к заметному количеству промахов кэша.
Промежуточный вывод состоит в том, что сопоставление с образцом не является узким местом, узким местом является преобразование списка поля зрения в списковой реализации. Возможным путём оптимизации Рефала-05 может быть отказ от генерации всего текста программы в памяти, вместо этого нужно выписывать строчки в файл сразу, по мере их порождения. Это уменьшит потребление памяти компилятором и ускорит операции синтеза выражений.
…но соблазнительная
Переписывание сопоставления с образцом оценочно должно заметно сократить объём рантайма без существенного изменения объёма кодогенератора. Также, не исключено, что кодогенерация в чём-то упростится.
STrusov
Вынесено из комментария https://github.com/Mazdaywik/Refal-05/issues/33#issuecomment-1256872395.
Актуальная реализация сопоставления с образцом сложная, костыльная и неэффективная. Она унаследована от Простого Рефала, а как правильно компилировать сопоставления с образцом, я тогда не знал.
Костыли в ней, например, в необходимости запоминать диапазоны при сопоставлениях с открытыми переменными.
Предлагается сделать сопоставления с образцом в духе диссертации Романенко — каждый распознанный элемент кладётся на стек, диапазоны открытые — это просто края уже распознанных элементов. Система команд Романенко предлагает стек времени выполнения и два «регистра» границ — следствие того, что команды интерпретируются и ради уменьшения объёма байткода (у команд меньше аргументов). Очевидно, что положение сопоставленных элементов на стеке известно во время компиляции, так что вместо стека будет простой массив ячеек и команды будут ссылаться на ячейки явным образом.
Такое представление системы команд очевидным образом допускает выделение общих префиксов — оптимизацию совместного сопоставления с образцом в её простейшем варианте. Возможно, её реализую, если это не займёт много кода.
Сопоставление с образцом в духе диссертации Романенко будет гораздо проще задокументировать — фактически нужно пересказать своими словами соответствующий раздел учебника Турчина.
Тоже самое предполагается в дальнейшем сделать и в Рефале-5λ — https://github.com/bmstu-iu9/refal-5-lambda/issues/204.
Этапы