Многопоточный поиск пути

Прежде чем что-то параллелить, попробуй просто запилить нормальный алгоритм поиска пути, хотя бы простейший вариант A*. Твоя «простая рекурсивная функция» называется поиском в глубину, и это далеко не самый лучший способ это делать.

Интересует есть ли более быстрые/простые способы запускать от 1 до N потоков, чтобы они не делали лишную работу и не мешались друг другу

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

Отслеживать, что вся очередь обработана можно счётчиком. Каждый обработанный элемент - +1.

Естественно очередь должна быть многопоточной, а счётчик и лучший результат под мьютексом. Атомарным счётчик делать, насколько я понимаю нельзя, т.к. инкремент это две операции с доступом - чтение и запись.

Если нужно делать много поисков одновременно, то делаешь, например, очередь очередей.

Обычный обход, например, дерева, таков: берём очередь, добавляем туда начальную вершину, запускаем на ней пул потоков, поток берёт вершину из очереди и начинает её обходить, на развилках идёт по одной ветке, другие добавляет в очередь. Возьми его и модифицируй для своего случая.

Если у тебя бывают циклы, значит дополнительно нужно проверять чтобы потоки не ходили по одним и тем же путям. Тут будет трейдофф «потоки делают одно и ту же работу» vs. «оверхед на синхронизацию», есть широкое поле для экспериментов. Скажем, раз в N вершин потокам нужно будет полностью синхронизировать глобальное состояние (т.е. смержить данные о проходимости и посещённых вершинах, прекратив те потоки которые находятся внутри посещённой территории). Эффективность этого можно улучшить статистически, заставляя потоки предпочитать разные направления обхода чтобы меньше сталкиваться.

Другой подход - разделить пространство на сетку с более крупными ячейками, для каждой ячейки своя очередь и свой поток. Здесь может страдать параллельность (если лабиринт мало ветвится то будет работать мало потоков), зато не нужно согласовывать глобальное состояние и оверхед на синхронизацию минимальный (по мьютексу на ячейку это весьма fine-grained → минимум контеншона). Опять же, могут помочь эвристики - внутри ячейки нужно предпочитать направления ведущие к неизведанным стенам, чтобы скорее найти путь до них и запустить поток соседней ячейки.

А так гугли параллельный обход графа, я это на коленке придумал, а наверняка есть более монументальные труды.

нормальный алгоритм поиска пути

Не описан критерий «нормальности». Может быть это поиск кратчайшего пути, или сложность поиска (по времени, по памяти и др ресурсов), или чего нибудь другого. Если поиск кратчайшего пути, то его можно распараллелить по слоям. А вот поиск в глубину практически невозможно (А* как частный случай).

Может быть я не достаточно точно донес мысль, но A* и Дейкстра мне не подходят.
Вершин графа еще нету, они будут сгенерированы в зависимости от начального состояния. Т.е. цель не пройтись по графу от А до Б, а сгенерировать граф целиком и узнать как далеко он распространяется. Чем лучше начальные условия, тем больше будет граф.

Спасибо за мысль, заинтересовало. Диву даюсь, что сам не допер. Плюс можно регулировать количество обработчиков, что неплохо. Насчет счетчика - CAS'ы вроде есть для этого и std::atomic подходит для этого.

Если брать алгоритмы дин программирования, то поиск пути сводится к заполнению двумерной таблицы, ты можешь легко распараллелить его. Либо представить как умножение матриц, для этого тоже есть параллельные алгоритм

Но вообще если у тебя случай почти непрерывного пространства, то там есть свои алгоритмы типа rrt деревьев, возможно есть параллельные

Вообще может все не так, и тебе нужен обычный dfs однопоточный, но вершины заранее препроцессить во много потоков?

Это давно всё реализовано. Посмотри как работают современные рендереры. Luxrender, например, или ещё какой.

Там обрабатываются пути прохода фотонов и в камеру от источника света и из камеры в источник света и т.п.

Ищи в нете - волновой алгоритм. Хотя вообще это графы.

Создаёшь на старте пул потоков

Допустим. И сколько потоков?

Если нужно делать много поисков одновременно, то делаешь, например, очередь очередей.

Это не эффективно.

Вобщем для задачи нужно использовать волновой алгоритм по теории графов.

Далее создаём количество потоков не большее чем количество аппаратных вычислительных потоков на компьютере (или там гетерогенной системе вычисления).

Каждый проход вычисляет следующий шаг +1 для каждой вычислительной единице.

Муравьиный алгоритм предлагали уже?

Допустим. И сколько потоков?

По кол-ву ядер. Лучше дать возможность задавать настройками пользователю.

Это не эффективно.

Чем неэффективно?

Чем неэффективно?

Если по количеству ядер - всё ок.

В начале небыло обозначено просто.

Спасибо, не знал про rrt, для моей ситуации вроде подходит и распараллелить не трудно.

Всем большое спасибо, остановился на такой схеме:

• Есть очередь состояний, которые нужно просчитать, можно ли из него пройти дальше по любому направлению.
• Если пройти можно, для каждого следующего состояния кидается задача в очередь
• Пул потоков по кол-ву ядер(хотя тут можно регулировать) будет разбирать очередь(по порядку или случайным образом как в rrt) и тем самым порождать новые задачи.
  Когда задачи иссякнут - мы закончили
• Дублирование работы не будет, все тяжелые расчеты будут производиться 1 раз, а дальше будет проверка, обсчитано данное состояние или нет.

На выходе получится как раз граф, по коротому уже можно искать пути как душе угодно.
Не совсем ясно, что делать когда очередь разрастется и займет всю оперативку. Пока что единственно разумный вариант это подключить базу данных, к примеру sqlite\mysql\postgres и хранить очередь там, как и результаты обработки, но это заметно скажется на производительности я думаю.

Кто нибудь в курсе, есть ли смысл в postgres\mysql или sqlite потянет вполне такое?
Я с ним не работал до этого, только mysql\postgres знаю, но мне они кажутся слишком монструозными для этой задачи. Или есть альтернативы вместо базы данных?

A* и Дейкстра мне не подходят.
Вершин графа еще нету, они будут сгенерированы
в зависимости от начального состояния.

Плохая отмазка. Виртуальность вершин графа не мешает алгоритму A*

Сколько элементов (поворотов) в схеме (или что там) предполагается? если несколько миллионов то в пару гигов всё влезет нормально (если не сильно мудрить с хранением структуры данных). Если миллиарды - то тут нужно будет посмотреть.... или памяти вкинуть нормально. Несколько десятков/сотен гигов.

К тому же в линуксе нужно будет расширить предел размера выделяемого под программу если реально нужно будет обработать десятки/сотни миллионов узлов. Он обычно урезан в начале меньше чем в половину памяти общей. Не знаю от чего это зависит при установке системы.

Как по мне RRT слишком ресурсозатратный и не очень точный.

Хотя визуализация выглядит захватывающе.

хз, завтра думаю его опробовать вместо линейного.
12 элементов всего, но обычно 6-7, в зависимости от начального состояния там от пары тысяч элементов до пары сотен миллионов.
Мне 16 гигов бывает не хватет, из них обычно 14-15 свободно, втыкать больше некуда.
Пока что пощупал sqlite, не вытягивает он. Почти половина времени процессора уходит на sqlite, плюс он фигово реагирует на попытки использовать его в несколько потоков, ускорения считай нету вообще, что 1, что 5, что 10 потоков.
Буду пробовать другие варианты, потестирую постгрес, марию. Если кто нибудь выдаст 50 тысяч записей в секунду, я буду рад неимоверно.

LMDB попробуй. Не забудь только базы с флагом MDB_NOSYNC открывать, иначе LMDB будет фиксировать транзакции на диск. А это медленно.

до пары сотен миллионов

из них обычно 14-15 свободно

Должно хватать с головой.

Спасибо, вообще не знал про LMBD. Попробую, выглядит многообещающе.

Ну мне надо ее запускать не только там, где 16 гигов.Еще ноут есть, где 4 гигабайта за радость.

В любом случае БД будет узким местом по скорости. Нужно продумать хранение данных в памяти оптимально. Например по 4/8 байт на элемент (хотя зная конкретно задачу, можно оптимизировать очень жёстко) и влезет в 4 гига вполне вместе с операционкой.

LMDB попробуй

Как-то это не совсем по поиску оптимального/кратчайшего пути.

На самом деле пока ничего оптимальнее чем поиск кратчайшего пути по ветвям графа ничего не придумано.

Тут задача построить граф правильно и вкинуть некоторые оптимизации в зависимости от задачи.

Вот вот, главное корректно и оптимально построить граф, а LMDB тут будет как база данных для генерируемых вершин графа, это уже часть реализации.

Может быть и так. Но я не уверен.

Хотя я отталкиваюсь от своих технологий обхода пространства и преград, которые пока ещё не опубликовал.

Могу чуть позже выложить визуализацию обхода пространства по волновому алгоритму в графах. Чуток конечно более специализированному.

Вот например посмотри этот упоротый ужас:

https://www.youtube.com/watch?v=YKiQTJpPFkA

Там всего-то 20 точек обхода оптимизированным волновым алгоритмом. Они начудили тысячи ветвей.

Визуализация шикарная, но бестолковая во всех смыслах кроме антуража и представительности для не понимающих.

Вот тоже чудо-юдо... https://www.youtube.com/watch?v=Ob3BIJkQJEw

Тот же бессмысленный алгоритм, который делает тысячи переборов вместо десятков как можно было бы обычным оптимизированным волновым в 20-30 точек.

Ты упарываешься в визуальные спецэффекты на экране или в скорость работы и занимаемую память?

Мне пофигу на визуальные эффекты, скорость важнее.

Попробовал, в итоге остановился на MDB_NOSYNC | MDB_MAPASYNC | MDB_WRITEMAP
Быстрее sqlite в разы, мне от нее по сути нужен только mdb_put с MDB_NOOVERWRITE и без оного.
У меня такая картинка, при 3 и более потоков работают в основном 2 потока, остальные ждут в mdb_txn_begin.
Эту ситуацию можно улучшить?

Не сталкивался. Возможно, у тебя много записей и они вынужденно сериализуются? Попробуй перестроить работу так, чтобы нити копили данные и сохраняли их пачкой.

На всякий случай уточню, ты ведь транзакции, в которых только чтение происходит, с MDB_RDONLY создаёшь?

Если у тебя до 100 миллионов узлов (их можно вполне скомпоновать по 4 байта наверняка) и 4 гига памяти, не стоит притягивать БД.

Для каждой сгенерируемой вершины у меня получается 64 байта данных. Предельно можно ужаться до 36 наверное, но очень не хочется.
Для сотен миллионов вариантов уже нужно 6 гигов, что не всякий комп потянет
Использование баз может снять с меня заботу об уникальности просчитанных вершин, не надо писать свой контейнер под это дело.
Хотя в целом ты прав, при малых количествах можно обойтись без базы, как таковой, и всё держать в памяти, хотя в конце все равно выгружать придется

Та даже по 8 байт можно. Туда можно напихать вообще много чего.

1 гиг вместе с прогой и дополнительных промежуточных данных.

Научи, а? у меня есть 14 чисел, которые плавают от 0 до 65000, и 2 числа от 0 до пары миллиардов. Как это впихнуть в 8 байт?

думаю если ты более конкретно опишешь задачу там можно будет много чего порезать.

даже если взять 16 байт - то это меньше 2х гигов для 100 миллионов узлов.

в 16 байт можно впихнуть всё что ты описал + останется куча пустого места.

Все написано до тебя

У меня нет таких транзакций, только 1 метод на запись( с перезаписью значения и без)
Каждую новую вершину надо проверить на уникальность, иначе количество расчетов растет лавинообразно. А для этого приходится писать в базу. Можно конечно попробовать проверять, есть ли значение в базе через mdb_get, но сильно сомневаюсь, что это как то поменяет ситуацию, т.к. в случае отсутствия записи ее надо тут же создать.
Тем самым получить read-only transaction не видится возможным
С другой стороны, скорость и так выросла, мб этого хватит, и дальше пыхтеть смысла нету

иначе количество расчетов растет лавинообразно.

Ты куда-то не туда полез.

В волновом алгоритме нет лавины. В этом он и крут. Может ты его не понял просто (алгоритм). Можем с тобой адаптировать под твою задачу. Там проще чем ты себе воображаешь. Он не занимает места почти и очень быстрый.

Ага, пошел почитал литературу, нашел ошибку у себя. Пойду исправлять.
Но опять же, храня карту графа в памяти, имеем у каждой вершины 12 координат, по 2-4 байта на вершину + до 4 байт для значения вершины . Как ты предлагаешь сжать это все в 16 байт, я без понятия.

Как ты предлагаешь сжать это все в 16 байт, я без понятия.

Я задачу не знаю.

И даже если ты впихнёшь в 20 байт всё равно оно около двух гигов получится.