Здравствуйте. У меня есть задача создания некого предметно-ориентированного фреймворка для инкрементальных

вычислений (условно, это можно отнести к классу задач типа salsa).

Есть набор условно чистых функций, которые вычисляют некоторые значения. В качестве входов функций могут служить выходы других таких же функций. Зависимости между функциями образуют DAG (циклические зависимости считаются ошибкой). Граф зависимостей определяется в процессе выполнения функции, то есть динамически. Если функция обращается к значению выхода другой функции, эта функция становится зависимой от той.

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

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

Я бы хотел, чтобы процесс вычислений был контролируемым. Чтобы его можно было приостанавливать. Более того, чтобы был приоретизирован пользовательский ввод (чтобы вычисления шли в фоне, когда пользовательского ввода нет).

Ещё отмечу, что речь идёт о вычислениях на одной машине, а не на класетер. Всеми данными владеет один процесс. И пользовательский ввод всегда контролируем (то есть ввод приходит явным образом).

Я совершенно теряюсь в том, как подойти к такой задаче. В частности:

1. Как эффективно организовать доступ к данным такого DAG графа, учитывая, что граф сам по себе единая точка синхронизации?

2. Имеет ли смысл заморачиваться с Rust futures, или для подобной задачи лучше собрать что-то на коленке? Отдельно отмечу, что мне хотелось бы получить решение, не зависящее от рантайма.

3. Может быть какие-нибудь общие рекомендации?

Думаю для начала есть смысл сделать однопоточный вариант, что бы было видно, что именно можно распараллелить и что будет управлять работой потоков (ставить им задачи).

1. Берешь петграф, NodeId кладешь в хэшмап рядом по нужному тебе ключу, профит 2. Ты не получишь решение без рантайма, вопрос только возьмешь ты существующий или напишешь какой-то свой с нуля. 3. вероятно узлы графа должны не сами что-то вычислять. а только скидываь задачи в очередь на выполнение. а там рантайм может их в сколько угодно потоков резолвить и репортить назад. В таком случае не придется делаь какого-то умного квантования времени - самые приоритетные задачки на текущий момент будут выполняться. если они все по длительности примерно одинаковые, то этого будет достаточно. открытые вопросы: а) что делать с низкоприоритетными узлами которые никогда не вычисляются? Поднимать приоритет со временем? Вопрос б) что делать с приоритетной задачей которая зависит от другой приоритетной задачи? они складываются/умножаются? в) какйо приоритет задачи. от которой зависят. Х других приоритетных задач7

> 1. Берешь петграф, NodeId кладешь в хэшмап рядом по нужному тебе ключу, профит Собственно, это наверное для меня сейчас основной вопрос. Складывать просто в хешмап — получим единую точку синхронизации всего процесса параллельных вычислений. Если вычисления каждой отдельной ноды будут короткие, и чаще будут писать в хешмапу, чем читать, это приведёт будет бутылочным горлышком.

Ты не должен хотеть часто перестраивать графк

зачем тебе писать в хэшмапу что-то

Потому что граф определяется динамически в процессе вычислений. И его топология может меняться в процессе перевычислений. Она не обязательно будет меняться часто, впрочем.

Оптимизация динамических графов вычислений? Хм. Похоже тянет на научную работу

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

вообще это единственно верный путь - делаем на коленке, измеряем перфоманс, делаем умную версию, понимаем что она работает медленее, берем наколеночное решение