Вот и настал этот час!
Тема доклада: практико-ориентированное введение в конечные автоматы, часть первая.
В конце вас ожидают самопальная open source утилита и увлекательные бенчмарки.

Видео:
https://youtu.be/1qiGurL0eYA
https://dzen.ru/video/watch/66fdd5505c5e4f1cf4d3ebfa

git репозиторий:
https://github.com/cheusov/convs_prog_fsm_intro

Презентация:
https://pkgs4unix.org/~cheusov/pub/convs_prog/fsm_intro/fsm_intro_part1.pdf

Огромная благодарность Игорю Чубину <igor@chub.in>
(chubin на github.com) за помощь в подготовке и Николаю за жесточайшую критику :-)

Всем привет. У меня новый доклад на тему "как написать эффективный интерпретатор".
Опять получился на час 🥵Если нет времени смотреть или вы знакомы с темой разработки интерпретаторов,
можете просмотреть презентацию. В принципе этого достаточно.

Утилита для изучения, игр и развлечений доступна на github.

Кратко об оптимизациях:
- отказ от явной проверки индексов массивов при обращении к стеку данных за счет mmap+mprotect
- direct threaded code with tail call optimization
- передача instruction pointer и data stack pointer через регистры (на x86_64 это rdi и rsi)

Кратко о результатах:
- в 9 раз медленее gcc -O2 (Compiler)
- в 2 раза медленеее luajit (JIT)
- на 10% быстрее pypy (JIT)
- в ~7 раз быстрее Lua-5.3 (Interpreter)
- отрыв от mawk, nawk, gawk, s-lang, python, perl гораздо бОльший (Interpreters)

Видео:
https://youtu.be/41KKVbmSBkY
https://dzen.ru/video/watch/671cea163dee994f8072937b

git репозиторий:
https://github.com/cheusov/convs_prog_efficient_interpreter

Презентация:
https://pkgs4unix.org/~cheusov/pub/convs_prog/efficient_interpreter/efficient_interpreter.pdf

Мы все знаем, что в процессоре есть кеши разных уровней. Те, кто пишет на низком кровне, знают, как они устроены, что такое cache line, ну и какие есть варианты реализаций у разных процессоров и производителей. Кто-то умеет пользоваться dtrace или perf и насчитывать количество так называемых cache misses. Все вроде бы ясно и понятно, но мне вдруг захотелось "потрогать руками" эти самые cache misses и "увидеть своими глазами" последствия промахов мимо кеша, а не просто наблюдать чиселки в dtrace/perf. В результате появилась игрушечная утилитка, которая позволяет это сделать.

https://github.com/cheusov/cache_line_test

Двухкратным ее запуском можно посмотреть результат промахов мимо кеша,
например, первого уровня. Результат запуска программы -- время работы
простого алгоритма суммирования чисел в буфере. Сумма в обоих
запусках должна быть одинаковой.

Для тех, кто совсем не в курсе:

The cache line is the smallest unit of RAM the CPU can load to perform operations. On the Intel CPU, this is 64 bytes, or 8 pointers in a 64-bit operating system. If at least one of the cores is writing, then cache coherency causes the cache line to be synchronized between the cores as each write forces a synchronization between the cores.

То есть, если вы зачитали байтик по какому-то адресу, на самом деле зачитается (и ляжет в кеш первого уровня (L1d)) блок памяти размером
в кеш-линейку (чаще всего это 64 байта). Далее, если вы читаете байт, лежащий в этой же кеш-линейке, то доступ к нему будет очень быстрым,
поскольку он уже в L1d. Если же вы "промахнулись", зачитается уже другая кеш-линейка, а это совсем не бесплатно ;-).

Пример #1:

На моем десктопе размер кеш-линейки -- 64 байта. Размер кеша первого уровня -- 256KiB.

0 cache_line_test$ env CACHE_LINE=64 mkcmake
...
0 cache_line_test$ for i in `seq 5`; do ./cache_line_test 256144 500000 0; done
time: 1379 millisecs (sum: 585934592)
time: 1378 millisecs (sum: 585934592)
time: 1375 millisecs (sum: 585934592)
time: 1377 millisecs (sum: 585934592)
time: 1390 millisecs (sum: 585934592)
0 cache_line_test$ for i in `seq 5`; do ./cache_line_test 256144 500000 32; done
time: 2527 millisecs (sum: 585934592)
time: 2573 millisecs (sum: 585934592)
time: 2561 millisecs (sum: 585934592)
time: 2769 millisecs (sum: 585934592)
time: 2785 millisecs (sum: 585934592)
0 cache_line_test$

Двухкратное замедление при промахах мимо кеша.

Пример #2:

Мой древний одноплатник Beagle Bone White с ARM Cortex-A8 CPU (ARMv7) на борту. Кеш-линейка -- 64 байта. Кеш первого уровня -- 32KiB.

0 cache_line_test$ for i in `seq 5`; do ./cache_line_test 32768 500000 0; done
time: 1814 millisecs, sum: 1198981120
time: 1797 millisecs, sum: 1198981120
time: 1799 millisecs, sum: 1198981120
time: 1796 millisecs, sum: 1198981120
time: 1796 millisecs, sum: 1198981120
0 cache_line_test$ for i in `seq 5`; do ./cache_line_test 32768 500000 32; done 
time: 7245 millisecs, sum: 1198981120
time: 7243 millisecs, sum: 1198981120
time: 7234 millisecs, sum: 1198981120
time: 7235 millisecs, sum: 1198981120
time: 7235 millisecs, sum: 1198981120
0 cache_line_test$

4-х кратное замедление!

Больше примеров и подробности о том, как все устроено -- в README.pod
в корне проекта. Играйтесь на здоровье! :-)

Вывод:

При реализации алгоритмов неплохо бы учитывать существование
кеш-линеек. Если вы что-то храните в некой структуре, сделайте так, чтобы по максимуму данных умещалось в кеш-линейку и выравняйте ее адрес на размер кеш-линейки. Возможно, это сильно улучшит производительность вашего алгоритма. Конечно, этот фокус недоступен пишущим на высокоурровневых языках программирования, таких как Python,
JS, Java, Kotlin, Lua....

С точки зрения производительности шаблон проектирования PImpl, часто
использующийся программистами на С++ -- антипаттерн :-)

Литература:

https://en.algorithmica.org/hpc/cpu-cache/