Reduce or eliminate quadratic behavior in cancellation system? #58
Description
Currently, checking for cancellation is O(n), where n is the depth of the task's cancel stack. We do this check frequently, including every time a task yields and in yield_if_cancelled. This isn't so bad because generally cancel stacks are not terribly deep, but it is worrisome. (Note that the stack is always at least as deep as the supervision tree, so while a good practice is to only have one explicit timeout at the top of your code, that doesn't mean cancellation stacks are only 1 deep.)
This isn't really urgent until we start seeing cancellation-related operations showing up in profiles, but I suspect that eventually it might be worth reworking this code to improve the asymptotics. It's a bit tricky given the richness of our semantics (in particular shielding), but we can certainly do better than we are right now.
A simple change would be to have a per-task cache that says where the task is cancelled, and recompute it (a) any time one of the cancel scopes is cancelled, (b) any time one of the cancel states shielding state is mutated, (c) any time the cancel stack is popped. (I guess we can slightly optimize further by observing that shield = True cannot create a cancellation where there wasn't one before, and vice-versa for shield = False, and popping can never create a cancellation. But I suspect it's very rare for shields to be used for multiple tasks, or to be set/unset very often, so it doesn't much matter how fast that operation is -- the big win, if any, will be from reducing the overhead on yield. And popping is always restricted to just one task.)