Balanced trees

[Marko Rauhamaa]

Ian Kelly <ian.g.kelly at gmail.com>:

> Peeking at the code, it appears to use a heapq-based priority queue.
> Why would a balanced binary tree be better?

AFAIK, a heap queue doesn't allow for the deletion of a random element
forcing you to leave the canceled timers in the queue to be deleted
later.

In a very typical scenario, networking entities start timers very
frequently (depending on the load, maybe at 100..1000 Hz) but cancel
virtually every one of them, leading to some wakeup churn and extra
memory load. I don't know if the churn is better or worse than the tree
balancing overhead.

Imagine a web server that received HTTP connections. You might want to
specify a 10-minute idle timeout for the connections. In the heapq timer
implementation, your connection objects are kept in memory for 10
minutes even if they are closed gracefully because the canceled timer
maintains a reference to the object.

Of course, it may be that the heapq implementation sets the callback to
None leaving only the minimal timer object lingering and waiting to come
out of the digestive tract.


Marko