[Twisted-Python] Performance issue in reactor.callLater
James Y Knight
foom at fuhm.net
Thu Sep 9 15:59:21 EDT 2004
On Sep 9, 2004, at 5:39 AM, Stefan Behnel wrote:
> 1) If we remove the entry during the call to cancel(), it takes log(N)
> time and is only done once.
> 2) If we do /not/ remove the entry, cancel() takes constant time (set
> a flag), but runUntilCurrent has to deal with a larger stack on each
> iteration. So this may slow down things considerably if many delayed
> calls are cancelled and remain on the stack.
I'm thinking of something like:
- When you call cancel, set the cancelled flag, and increment a counter
of cancelled items.
- in runUntilCurrent, if the number of cancelled items in the list is
both > 50 and > 1/2 of the total items, filter them out and re-heapify
Now, the only thing left that needs the heap_pos is moving a
delayedcall to a sooner time. This is an unlikely event, and thus we
should not be overly concerned about its speed.
Now we can use the builtin heapq, which is written in C in Python 2.4.
Patch attached to bug.
More information about the Twisted-Python