Оптимизация check

[Senbjorn]

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

[Senbjorn]

P. S. cancel становится тяжелее, а check максимально легковесный. Кажется это большой плюс, так как скорее всего вызовов cancel ожидается меньше, чем вызовов check

[pomponchik]

Привет!

Спасибо за идеи по оптимизации. Как раз сейчас я занимаюсь именно ими, например в одном из последних пулл-реквестов заехало несколько различных идей.

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

Есть главная причина, почему я решил выбрать не его:

• Он не учитывает то, как работают самоотменяемые виды токенов, например ConditionToken. Для того, чтобы отследить выполнение произвольного условия, необходимо вызвать переданный пользователем библиотеки callable. В ситуации "разворота" опроса статуса это просто не будет работать.

Мы можем также рассмотреть гибридные реализации, например когда явная отмена child приводит к отмене parent, но все же parent также продолжает проверять все вложенные токены на случай, если среди них есть самоотменяемые. Этот вариант может выглядеть привлекательно, однако я вынужден был отказаться и от него по ряду причин:

• На хранение ссылок потребовалось бы больше памяти.
• Возможны разнообразные сложности с синхронизацией потоков.
• Этот подход порождает циклические ссылки, с которыми не очень хорошо умеет работать интерпретатор CPython.