Предыдущая реализация поиска волновым алгоритмом в лабиринте была неплоха, но работала не так уж и быстро. Иван Колесников предположил, что дело в медленной работе памяти и попробовал реорганизовать хранения данных так, что бы рядом расположенные данные в двухмерном пространстве оказались относительно близко друг к другу и в одномерном пространстве. Для этого он использовал Z-порядок (по русски почему-то в вики статья называется кривая Мортона) для перехода от двухмерных координат к одномерным.
Подход показал очень хорошие результаты по производительности, обеспечивая почти двукратное превосходство для сложных случаев на интеловском процессоре.
Так же Иван протестировал программку на M1, который показал очень неплохую производительность, превышающую производительность топового мобильного процессора Intel 9-го поколения.
Итак, скорость работы волнового алгоритма сильно зависит от памяти, но вроде же для частичного решения этой проблемы и предназначен кэш? Которого в современных процессорах много, да еще и его, этого кэша, три уровня обычно.
Тут проблема в том, кэш для этой задачи очень "горячий". Фронт волны проходит в сложных случаях проходит по совершенно разным участкам лабиринта (читай, памяти, так как лабиринт в ней и хранится), что приводит к тому, что расчет одного участка волны приводит к неминуемому удалению из кэша другого участка волны, что сильно увеличивает промахи мимо кэша и драматически снижает производительность работы с памятью.
Реорганизация памяти в Z-порядке существенно снижает эту проблему, но можно попытаться решить проблему и по-другому, просто оптимизировав программу.
Первое, с чего я начала – с банальной регистровой оптимизации. Так как в 64-битном режиме в архитектуре x64 доступно 16 регистров, то результат оказался ощутимым – примерно 30% ускорения за счет того, что я избавился от сохранения служебной информации в памяти.
К сожалению, компилятор Delphi, видимо, не сильно умеет в такую оптимизацию. Зато он позволяет достаточно легко и удобно писать часть кода на ассемблере. Не так удобно, как в 32-битной версии, когда можно было вставлять ассемблерные кусочки в любую часть кода. В 64-битной можно лишь писать целиком ассемблерные функции. Но отладка осталось все также очень удобной.
30% хорошо, но можно ли лучше? Что еще требует обращения к памяти, кроме переменных? Конечно же, вызов процедур и функции, которые даже при регистровой передачи параметров сохраняют/извлекают в/из стек(а) адрес возврата.
Помню, я даже бывало рассказывал на лекциях о забавном случае, когда ответственного руководителя направления разработки процессоров IBM отправили в корпоративную "ссылку" за то, что в очередном процессоре (в те времена это были монстры для мейнфреймов) не оказалось команд для работы со стеком.
Видимо, очень давно производительность памяти была сравнима с производительностью процессоров, да и в общем-то она была не велика, поэтому выделение отдельных команд для управления стеком было оправданным.
Но что мы видим сейчас? Если не ошибаюсь, в RISC V адрес возврата сохраняется не в памяти, а в регистре! В случае, если глубина вложенности вызовов функций не велика, а память существенно медленнее, чем процессор (в современном мире это почти всегда так), то это может существенно поднять производительность программы.
При необходимости же всегда можно организовать работу стека программным образом, а отсутствие дополнительных команд отлично вписывается в концепцию RISC.
К сожалению, в архитектуре x64 возможности сохранять адрес возврата в регистрах нет, поэтому просто приходится "раскатывать" тело вызываемой функции в код основной процедуры. У меня это была относительно маленькая функция проверки возможности хода и, если он возможен, сохранения фронта волны и порядка обхода на следующей итерации.
После избавления от лишних вызовов удалось поднять производительность почти в два раза относительно исходной.
Еще оптимизировал дисковые операции за счет буферизированного ввода/вывода. Правда, тут по хорошему надо бы еще оптимизировать и преобразование исходных данных в удобный для решения массив, но не это моя основная цель.
Итак, результаты:
AMD FX-4350:
загрузка примерно 15-16 секунд, но так как на компьютере используется HDD, то сильно зависит от фрагметированности файла; в худшем случае было 26 секунд. В среднем загрузка ускорилась в два раза;
kvy в прямом направлении и обратном направлении: 19 сек;
A – 10 сек;
B – 26 сек.
Ryzen 7 5800X:
загрузка 6 сек;
kvy в прямом 9.4 сек, в обратом – 10.3 сек;
A – 5.9 сек;
B – 6.8 сек.
В общем, можно сказать, что оптимизация удалась. На данных, хранящихся в обычных массивах, FX-4350 обогнал более свежий, хоть и мобильный Intel, проиграв на Z-порядке. Впрочем, на процессоре с аналогичной производительность, думаю этого проигрыша бы не было.
Ну а на Ryzen 7 производительность оказалась даже выше, чем у такого монстра, как M1. Жаль, нельзя их сравнить в равных условиях, так как вполне вероятно, что более жесткая оптимизация под M1 позволила бы ему обогнать Ryzen. Все же 31 регистр общего назначение должен дать жару!
Только набирая текст, обратил внимание на несколько феноменальный результат Ryzen на файле B. Для всех прочих тестов вариант B был самым тяжелым для процессора и выполнялся медленнее всего. Удивительно, что для Ryzen он оказался проще, чем обычно более легкий вариант kvy.
Еще развлекаясь с лабиринтами, обнаружил, что большинство стандартных программ просмотра текстовых файлов и простые текстовые редакторы просто не в состоянии нормально работать с реально большими размерами. Видимо, не такая это уж и простая задачка.
