[Twisted-Python] Performance issue in reactor.callLater

[Stefan Behnel]

Stefan Behnel schrieb:
> I guess I do see a problem if the value of a call somewhere 
> in the heap is changed. That brakes the heap invariant and may conflict 
> with further changes to the heap. Let me think about it.

Ok, I thought about it. And I believe the best way to do this is to write a specialized heap version. I copied the heapq implementation and adapted it so that it keeps track of the position in the heap for each DelayedCall. That makes it possible to remove a call without linear overhead and in log(N) time.

So, comparing the complexity of the heap version with the original version:

callLater:
	ORIG:	O(log(N)) for binary search + O(N) for array insertion (python lists are arrays as far as I know)
	HEAP:	O(1) as it is only appended to a list. Insertion is done in runUntilCurrent (as late as possible)

cancel:
	ORIG:	O(N) for linear array deletion
	HEAP:	O(log(N)) if it was already inserted, O(1) if it was only stored for later insertion (see post by Bob)

reset:
	ORIG:	O(N) for linear array deletion + O(log(N)) for binary search + O(N) for array insertion
	HEAP:	O(log(N)) for removal + O(log(N)) for insertion if it was already inserted
		O(1) if it was only stored

delay:
	see reset - could actually be implemented twice as fast in the heap (only _siftup), but I didn't do that - it's fast enough anyway

runUntilCurrent:
	heap implementation is about log(N) times slower, which is still much faster than the original implementaion if you add it up with callLater. There is always one call to callLater and at most (!) one iteration in runUntilCurrent for each DelayedCall.


So, summing it up, it kicks ass.


Other things to mention:

getDelayCalls has a slight change in semantics: It only returns the delayed calls that were already inserted into the heap, so if you run callLater and getDelayCalls in the same iteration of the main loop, you will not find your delayed call in the returned tuple. This is due to the change Bob proposed.


Now, are there any test cases in Twisted for the ReactorTime part? I'd like to see them run over my implementation to check if it works as expected in all cases.

You should also consider running pychecker over the old version, there were some unused variables and that kind of stuff.

Hoping for approval,
Stefan

-------------- next part --------------
A non-text attachment was scrubbed...
Name: base.py.diff
Type: text/x-patch
Size: 8016 bytes
Desc: not available
Url : http://twistedmatrix.com/pipermail/twisted-python/attachments/20040907/d2473bac/attachment.bin