Попробовал портировать с nim на daScriptинтерпретаторbrainfuck кода. Брейфак предельно простой язык, и базовая реализация интерпретатора занимает полчаса, но на нём можно потренироваться в ускорении кода и продемонстрировать возможности daScript в оптимизации.
Самая первая, максимально наивная, построчно скопированная реализация:
let totalDt = double(get_time_usec(totalTime)) /1000000.0lf
to_log(LOG_INFO, "total {totalDt} sec\n")
Если попытаться протестировать его на генераторе множества Мандельброта, можно заметить серьёзные проблемы со скоростью, вычисления занимают около 5 часов. Стоит попробовать его разогнать!
Отключение проверок границ и указателей
Код на brainfuck - это простая числодробилка, ускорить которую можно, отключив все дополнительные проверки обращений к памяти.
Как отключать проверки, мне рассказал Борис Баткин (так как интерпретатор nim делал один основных контрибьютеров языка, то его подсказки не отменяют честности сравнения — авторы находятся в одной “весовой категории” знания своего языка).
В первую очередь, можно заменить функцию charcter_at, которая проверяет,что индекс меньше длины строки, на character_uat, которая не делает этой проверки.
Также отключается проверка ссылок на null макросом [unsafe_deref].
Наконец, обращение к массиву можно выполнять не через разыменование ссылки, а через обращение по указателю:
let totalDt = double(get_time_usec(totalTime)) /1000000.0lf
to_log(LOG_INFO, "total {totalDt} sec\n")
Такая версия интерпретатора всё ещё тормозная, но уже позволяет дождаться завершения выполнения кода:
e:\src\daScript\bin\Release>daScript.exe brainfuck_00.das AAAAAAAAAAAAAAAABBBBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDEGFFEEEEDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB AAAAAAAAAAAAAAABBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDEEEFGIIGFFEEEDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBBBBB AAAAAAAAAAAAABBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEFFFI KHGGGHGEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBB AAAAAAAAAAAABBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEFFGHIMTKLZOGFEEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBB AAAAAAAAAAABBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEEFGGHHIKPPKIHGFFEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBBBB AAAAAAAAAABBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGHIJKS X KHHGFEEEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBB AAAAAAAAABBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGQPUVOTY ZQL[MHFEEEEEEEDDDDDDDCCCCCCCCCCCBBBBBBBBBBBBBB AAAAAAAABBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEFFFFFGGHJLZ UKHGFFEEEEEEEEDDDDDCCCCCCCCCCCCBBBBBBBBBBBB AAAAAAABBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEFFFFFFGGGGHIKP KHHGGFFFFEEEEEEDDDDDCCCCCCCCCCCBBBBBBBBBBB AAAAAAABBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEEFGGHIIHHHHHIIIJKMR VMKJIHHHGFFFFFFGSGEDDDDCCCCCCCCCCCCBBBBBBBBB AAAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDEEEEEEFFGHK MKJIJO N R X YUSR PLV LHHHGGHIOJGFEDDDCCCCCCCCCCCCBBBBBBBB AAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDEEEEEEEEEFFFFGH O TN S NKJKR LLQMNHEEDDDCCCCCCCCCCCCBBBBBBB AAAAABBCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDEEEEEEEEEEEEFFFFFGHHIN Q UMWGEEEDDDCCCCCCCCCCCCBBBBBB AAAABBCCCCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEFFFFFFGHIJKLOT [JGFFEEEDDCCCCCCCCCCCCCBBBBB AAAABCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEEFFFFFFGGHYV RQU QMJHGGFEEEDDDCCCCCCCCCCCCCBBBB AAABCCCCCCCCCCCCCCCCCDDDDDDDEEFJIHFFFFFFFFFFFFFFGGGGGGHIJN JHHGFEEDDDDCCCCCCCCCCCCCBBB AAABCCCCCCCCCCCDDDDDDDDDDEEEEFFHLKHHGGGGHHMJHGGGGGGHHHIKRR UQ L HFEDDDDCCCCCCCCCCCCCCBB AABCCCCCCCCDDDDDDDDDDDEEEEEEFFFHKQMRKNJIJLVS JJKIIIIIIJLR YNHFEDDDDDCCCCCCCCCCCCCBB AABCCCCCDDDDDDDDDDDDEEEEEEEFFGGHIJKOU O O PR LLJJJKL OIHFFEDDDDDCCCCCCCCCCCCCCB AACCCDDDDDDDDDDDDDEEEEEEEEEFGGGHIJMR RMLMN NTFEEDDDDDDCCCCCCCCCCCCCB AACCDDDDDDDDDDDDEEEEEEEEEFGGGHHKONSZ QPR NJGFEEDDDDDDCCCCCCCCCCCCCC ABCDDDDDDDDDDDEEEEEFFFFFGIPJIIJKMQ VX HFFEEDDDDDDCCCCCCCCCCCCCC ACDDDDDDDDDDEFFFFFFFGGGGHIKZOOPPS HGFEEEDDDDDDCCCCCCCCCCCCCC ADEEEEFFFGHIGGGGGGHHHHIJJLNY TJHGFFEEEDDDDDDDCCCCCCCCCCCCC A PLJHGGFFEEEDDDDDDDCCCCCCCCCCCCC ADEEEEFFFGHIGGGGGGHHHHIJJLNY TJHGFFEEEDDDDDDDCCCCCCCCCCCCC ACDDDDDDDDDDEFFFFFFFGGGGHIKZOOPPS HGFEEEDDDDDDCCCCCCCCCCCCCC ABCDDDDDDDDDDDEEEEEFFFFFGIPJIIJKMQ VX HFFEEDDDDDDCCCCCCCCCCCCCC AACCDDDDDDDDDDDDEEEEEEEEEFGGGHHKONSZ QPR NJGFEEDDDDDDCCCCCCCCCCCCCC AACCCDDDDDDDDDDDDDEEEEEEEEEFGGGHIJMR RMLMN NTFEEDDDDDDCCCCCCCCCCCCCB AABCCCCCDDDDDDDDDDDDEEEEEEEFFGGHIJKOU O O PR LLJJJKL OIHFFEDDDDDCCCCCCCCCCCCCCB AABCCCCCCCCDDDDDDDDDDDEEEEEEFFFHKQMRKNJIJLVS JJKIIIIIIJLR YNHFEDDDDDCCCCCCCCCCCCCBB AAABCCCCCCCCCCCDDDDDDDDDDEEEEFFHLKHHGGGGHHMJHGGGGGGHHHIKRR UQ L HFEDDDDCCCCCCCCCCCCCCBB AAABCCCCCCCCCCCCCCCCCDDDDDDDEEFJIHFFFFFFFFFFFFFFGGGGGGHIJN JHHGFEEDDDDCCCCCCCCCCCCCBBB AAAABCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEEFFFFFFGGHYV RQU QMJHGGFEEEDDDCCCCCCCCCCCCCBBBB AAAABBCCCCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEFFFFFFGHIJKLOT [JGFFEEEDDCCCCCCCCCCCCCBBBBB AAAAABBCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDEEEEEEEEEEEEFFFFFGHHIN Q UMWGEEEDDDCCCCCCCCCCCCBBBBBB AAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDEEEEEEEEEFFFFGH O TN S NKJKR LLQMNHEEDDDCCCCCCCCCCCCBBBBBBB AAAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDEEEEEEFFGHK MKJIJO N R X YUSR PLV LHHHGGHIOJGFEDDDCCCCCCCCCCCCBBBBBBBB AAAAAAABBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEEFGGHIIHHHHHIIIJKMR VMKJIHHHGFFFFFFGSGEDDDDCCCCCCCCCCCCBBBBBBBBB AAAAAAABBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEFFFFFFGGGGHIKP KHHGGFFFFEEEEEEDDDDDCCCCCCCCCCCBBBBBBBBBBB AAAAAAAABBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEFFFFFGGHJLZ UKHGFFEEEEEEEEDDDDDCCCCCCCCCCCCBBBBBBBBBBBB AAAAAAAAABBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGQPUVOTY ZQL[MHFEEEEEEEDDDDDDDCCCCCCCCCCCBBBBBBBBBBBBBB AAAAAAAAAABBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGHIJKS X KHHGFEEEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBB AAAAAAAAAAABBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEEFGGHHIKPPKIHGFFEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBBBB AAAAAAAAAAAABBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEFFGHIMTKLZOGFEEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBB AAAAAAAAAAAAABBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEFFFI KHGGGHGEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBB AAAAAAAAAAAAAAABBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDEEEFGIIGFFEEEDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBBBBB [I] total 564.99929999999994834 sec
564 секунды — в 30 раз быстрее первой версии, но всё ещё сильно медленнее интерпретатора на nim, который в релизной версии выполняется за 40 секунд.
Ahead-of-Time
daScript умеет транспилироваться в C++ код, для сравнения с nim попробуем скомпилировать интерпретатор, без внесения каких-либо изменений в код.
daScript.exe -aot brainfuck.das brainfuck.das.cpp
Полученный C++-файл проще всего подсунуть в пример tutorial02aot, который настроен на использование AoT варианта кода. Скомпилированный файл можно запустить:
e:\src\daScript\bin\Release>tutorial02aot.exe
[I] total 34.27342399999999856 sec
34 секунды — уже быстрее, чем nim, который сам по себе достаточно быстрый!
Just-in-Time
Можно попробовать двигаться дальше, подключив экспериментальный модуль dasLLVM. Чтобы собрать его, необходимо:
собрать проект llvm, или скачать собранный (например, от qt) и положить на уровень выше корневой директории проекта daScript, напрммер:
C:/dascript C:/libclang
сгенерировать решение и пересобрать dascript:
generate_msvc_2019.bat
Теперь можно воспользоваться аннотацией [jit], чтобы код функциии интерпретатора без AoT-компиляции перед первым выполнением компилировался с помощью llvm-c.
e:\src\daScript_my\bin\Release>daScript.exe brainfuck_2_jit.das [I] total 22.66654300000000077 sec
22.6 секунды, еще лучше! Генерация daScript-кода в llvm-ассемблер быстрее, чем в C++ — генератор передаёт больше полезной для оптимизации о кода, а также, возможно, задействуется сила оптимизаций LLVM.
Метапрограммирование
Можно двигаться дальше. Вместо того, чтобы писать функцию, которая интерпретирует любой код на brainfuck, можно написать макрос, который сгенерирует код конкретной функции в compile-time, и измерить время выполнения этой функции.
Можно использовать AstReaderMacro — тип макроса, который обрабатывает отдельные символы. Синтаксис вызова такого макроса:
% READER_MACRO_NAME ~ character_sequence %% //character_sequence будет передана на вход макросу
Шаблоны таких макросов можно посмотреть в модулях json_boost и regex_boost
module brainfuck_macro sharedpublic
defgenerateFunction(uniqueName, code)
let seqStr = string(code)
var blkArr : array<array<ExpressionPtr>>; defer_delete(blkArr)
var blk : array<ExpressionPtr>; defer_delete(blk)
blkArr |> emplace(blk)
blkArr[0] |> emplace_new <| qmacro_expr( ${ var tape: array<uint8>; })
let func = @@bf`exec_0xd_0xc //указатель на функцию
Для каждой функции генерируется уникальное имя, чтобы можно было создать несколько отдельных интерпретатов, и своя “лента” памяти. В дальнейшем, каждый отдельный символ brainfuck компилируется в одну или несколько ast-нод daScript, который затем могут быть просимулированы.
Если говорить о терминологии, то brainfuck можно рассматривать как предметно-ориентированный язык (DSL). Переменные состояния tape и tapePos вместе составляют семантическую модель этого языка, которая настраивается с помощью DSL, а затем транслируется в синтаксическое дерево на daScript (в терминах Мартина Фаулера из книги “Предметно-ориентированные языки программирования”).
Время выполнения такой скомпилированной функции в режиме интерпретации:
e:\src\daScript_my\bin\Release>daScript.exe brainfuck.das [I] total 29.28014399999999995 sec
Это немного медленнее скомпилированной JiT-версии, но уже быстрее AoT версии интерпретатора.
Macro + JiT
Дальше будет интереснее. Наша скомпилированная версия функции представляет собой по сути развёрнутую трассированную версию исполнения кода (и занимающую больше памяти). Попробуем применить к ней макрос [jit]:
e:\src\daScript_my\bin\Release>daScript.exe brainfuck.das [I] total 0.85775599999999996 sec
0.85 секунды! (плюс около секунды на само время компиляции функции). llvm jit умеет сворачивать идущие подряд повторяющиеся операторы инкремента и декремента, за счёт чего получилось ускорение в 30 раз (и соотвествующее уменьшение размера функции).
Для сравнения — compile-time версия на nim работает ~3 секунды и тратит ~20 секунд на компиляцию (nim работает медленно в compile-time режиме).
На каждом из шагов происходят серьёзные трансформации кода, которые могут включать оптимизации. Можно рассмотреть оптимизации в обратном порядке:
llvm — бекэнд генерации кода оптимизирует байт-код, на этом этапе заметен эффект от сворачивания идущих подряд операций
dascript simulate — при симуляции ast-дерева выбираются оптимизированные частные версии нод, мелкие ноды могут “сплавляться” в более крупные, применяются кастомные макросы, трансформирующие дерево по различным правилам
bf macro — на данном уровне производится трансляция команд brainfuck в ноды dascript, пока без оптимизаций
Оптимизации на стадиях трансформаций llvm были сделаны библиотекой из “комплекта” языка, на стадиях преобразования daScript — как встроенными в язык оптимизациями, так и добавленными для своего кода вручную. Можно теперь попробовать добавить пару оптимизаций на “стороне DSL”, т.е. в макрос трансформации brainfuck->daScript.
На данном этапе первую тупую и наивную реализацию уже получилось разогнать где-то в 20000 раз, и это отличный повод разогнать ещё немного :)
Можно выбрать несколько простых паттернов brainfuck кода и попробовать распознавать их и генерить более оптимальный код для этих частных случаев:
цепочка повторяющихся операций. Например, “+++++” можно интерпретировать не как 5 отдельных инкрементов, а как одну операцию увеличения на 5. Эту свёртку делает llvm для версии Macro+JiT, но если сделать её в своём макросе, то она также ускорит и обычный режим интерпретации
паттерн [-] можно интерпретировать как очистку ячейки памяти одной операцией
[->+<] - чуть более сложный паттерн, который часто встречается в примерах на brainfuck, “сложение двух ячеек с очисткой исходной”, может быть интерпретирован как 2 команды вместо цикла
можно продолжать обнаруживать и добавлять всё более сложные паттерны
(Приём с отслеживанием паттернов подходит, естественно, не только для brainfuck-кода, но и для любых DSL)
“Продвинутая” версия макроса, отслеживающая перечисленные паттерны
e:\src\daScript_my\bin\Release>daScript.exe brainfuck.das [I] total 0.70142899999999999 sec
Еще на 17% быстрее Из замеров явно стоило бы еще вынести print
Немного выводов
Основа оптимизации — написание грамотного кода на основном языке.
Техники JiT-компиляции (особенно в сочетании с кодогенерацией или замерами hot участков) могут давать крутые результаты, в том числе превосходящие статическую компиляцию
Организация цепочки преобразований кода в одной среде НАМНОГО удобнее, чем в разных (какой-нибудь вариант “кодоген на python” + макросы/шаблоны + код на C++” - мрак с отладкой). Особенно для более длинных цепочек.
Нормальные макросы = нормальная отладка и скорость компиляции DSL.