Алгоритм поиска пути (например Дейкстры) на WebAssembly?

Question

[Magneto903]

Мне хочется решить 2 задачи:
Найти расстояние от конкретной точки (пусть точка A) до всех остальных точек в графе
Восстановить наилучший (с наименьшей длиной) от точки A до любой точки в графе

На мой взгляд тут подходит алгоритм Дейкстры. Однако мне нужно решать эти задачи на фронтенде и в веб приложении. JavaScript слишком медленный для этой задачи. Я слышал, что webassembly работает очень быстро, часто почти с такой же скоростью, как код (например на C/C++) с которого компилировали в wasm, что явно быстрее JavaScript.

Я самостоятельно написал программу для решения этих 2 задач на С (с учетом того факта, что это должно будет скомплироваться в wasm) (однако это не в явном виде Дейкстра, а скорее модификация алгоритма поиска в ширину для взвешенных графов, ну или можно сказать, что это Дейкстра с очередью, где вершина может туда попадать не один раз)
Прикрепляю на всякий случай этот код
К сожалению, если его скомпилировать в wasm он работает довольно медленно, и даже медленнее, чем нативный JS. (Для 160+ вершин и 350+рёбер скорость больше 1ms) Возможно, с C кодом что-то не так. (Собирал в wasm через этот сервис)

Но меня интересует вопрос, возможно ли быстрее реализацию написать на wasm? (Если есть готовые реализации, буду очень признателен, если расскажете про них) На какую скорость я могу рассчитывать?

Comments

[Армянское Радио]

По следам вашего прошлого вопроса - я бы выкинул к чертям этот сервис, поставил бы компилятор локально, настроил и работал бы с ним. По поводу скоростей - подтверждаю, код, откомпилированный wasm (с нормальной настройкой, а не тыком в сайтик) работает также быстро, как собранный на C++.

[Magneto903]

Фокс Йовович, какой конкретно Вы бы посоветовали поставить компилятор? Emscripten? И что такое нормальные настройки?)

[Армянское Радио]

Magneto903, да, я им пользуюсь. "Нормальные настройки", это как минимум -O3, при условии, что код на C++ написан без ляпов вроде нарушения алиасинга.

[Magneto903]

Фокс Йовович, у меня C, а не C++. Этот сервис насколько я понял на сервере запускает emscripten. И да, в настройках там стоит флаг O3, там его можно указать. Но видимо или код плохой, или на сервисе какая-то фигня происходит

[Magneto903]

Фокс Йовович, и кстати, а я правильно понимаю, что я не могу просто взять какой-нибудь C++ код, например такой и собрать в wasm? Я где-то видел, что сложные структуры нельзя собрать, такие как вектора, пары и т.п...

[Армянское Радио]

Magneto903, можете взять и собрать C++. Если что, под WASM собирается и работает Qt, а там этих векторов, пар и прочего добра очень много.

[Magneto903]

Фокс Йовович, т.е. вот это я могу спокойно собрать? Если так, то это очень круто! А мне нужно будет в js выделять память специально как-то для этих сложных структур?

[Армянское Радио]

Magneto903, вам придется конвертировать каким-то образом структуры C++ в js

[Василий Банников]

Немного оффтопа, но я бы ещё попробовал взять https://crates.io/crates/pathfinding и попробовать скомпилировать в wasm. У раста очень приятная wasm-инфраструктура.