Предлагается основываться на алгоритме MNR (в этой статье хорошо описан), который изменяет топологический порядок не на всем графе, а только на необходимом участке. Возможно, стоит посмотреть в сторону других алгоритмов.
Зачем это нужно?
На текущий момент инструмент Dl-Check (https://github.com/Devexperts/dlcheck) использует его для поиска циклов в графе блокировок (см. pre-print статьи, прикрепил к письму). Для корректной синхронизации используется ReadWriteLock следующим образом: при чтении значения топологического порядка используется ReadLock, а при его изменении – WriteLock. Таким образом, при изменении топологического порядка происходит практически stop the world, а меняется он не быстро судя по собранной статистике. Предлагается оптимизировать эту часть.
Идея
1. Давайте научимся захватывать WriteLock не на весь граф целиком, а только на тот «отрезочек» (affected region в статье), который собираемся изменять. Таким образом, появляется свой менеджер блокировок. Хотелось бы, чтобы этот менеджер блокировок работал lock-free при ограничении «один писатель на affected region».
2. Давайте научимся читать значение топологического порядка (нужно для проверки, что добавление ребра не нарушает текущий топ. порядок) lock-free. На текущий момент, если происходит изменение значения топ. порядка, то чтение ждет его окончания. Это долго.
Итого, все должны уметь читать значение топологического порядка lock-free, а его изменения должны производиться параллельно с ограничением «только один поток может изменять этот affected region».