[Twisted-Python] Performance issue in reactor.callLater

[James Y Knight]

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 
the list.

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.

James