Лабиринт

Ностальгирую тут немного...

Вспоминаю еще те времена, когда учился на старших курсах в СМИ, ныне СибГИУ. Студенты обычных специальностей, типа металлургов или металловедов вешались, обучаясь информатики. Уж не помню как тогда кафедра эта называлась, на которой мучили студентов, потом она долго была кафедрой прикладной информатики.
И обучали там студентов-металлургов, литейщиков и прочих в те далекие времена... программированию. В СССР, а потом и России компьютеризация только начиналось, компьютеров-то толком не было, не говоря уже о прикладных программах. Поэтому программировали все подряд.

Одна из задачек для студентов там была про поиск пути в лабиринте. Металловедам и строителям это было просто невыносимо скучно и непонятно, а нам, обучающимся именно программированию, было страсть как интересно.

Интернетов тогда в Сибири не было, да наверно и во всей России тоже, хорошей специализированной литературы  также не хватало, поэтому алгоритмы мы придумывали сами. Для этой задачки самый оригинальный вариант решения придумал Алексей Щелоков, с очень забавной биологической аналогией.
В реальности же это был старый добрый, сто лет как известный волновой алгоритм.

Я потом с ним много изгалялся. В контексте биологического описания реализовывал его с помощью ООП, хотя по сути волнового алгоритма никакой ООП там не требуется, гораздо эффективнее просто поиск в ширину на массиве.
Кстати, тогда же я и выяснил, что выделение динамической памяти под NT происходит гораздо, наверное, на два порядка, медленнее, чем на Windows 9x.
Поэтому когда выяснилось, что операции 4 КиБ блоками при копировании файла сильно загружает процессорное ядро, я предложил, что эта та самая "неэффективность" системных вызовов на платформе NT.
Но думаю, я был не прав. Все же с времен NT много воды утекло, думаю, сейчас большинство системных вызовов происходит гораздо быстрее. Так что наиболее вероятная причина, как заметил Иван Колесников, в издержках межпоточной синхронизации. Надо будет потестить, но пока руки не доходят.

В общем, ностальгируя накидал быстренько программку поиска пути в лабиринте на окрестностях фон Неймана. Сначала хотел решить задачу в квадрате размером 100 000, но потом понял, что для решения памяти не хватит, и остановился на 40 000.

Правда, надо было еще лабиринт каким-то образом сделать. Сделал случайным образом. Лабиринт получился не очень красивым, но зато достаточно сложным для решения волновым алгоритмом.
Мой рабочий FX-4350 на архитектуре PileDriver и жестких дисках загрузил лабиринт примерно за 40 секунд, а нашел кратчайший путь за 52.4 секунды.
А вот Ryzen 7 5800X на архитектуре Zen 3 и с SSD на PCI Gen 3 x4 сделал те же операции за 22.5 и 21.5 секунды.

По сравнению с началом 90-х годов прошлого века эта, конечно, потрясающая производительность. Тогда и 100х100 лабиринт не сильно быстро решался.
Удивило лишь то, что замена HDD на SSD не сильно ускорила процесс загрузки. Честно говоря, я ожидал большего.

Может быть, когда станет совсем скучно, попробую оптимизировать эту программку. Первое, что мне приходит в голову – это мой любимый ассемблер.
Второе, но более важное: модификация поиска в ширину, что бы в первую очередь просматривать горизонталь (строки), а лишь затем двигаться по вертикали. Можно рассчитывать на увеличение производительности за счет того, что обрабатываемая часть массива уже подгружена в кэш.