[Python-Dev] collections.sortedtree

[Marko Rauhamaa]

Antoine Pitrou <solipsis at pitrou.net>:

> Marko Rauhamaa <marko at pacujo.net> wrote:
>> In my experience, networking entities typically start a timer at each
>> interaction and cancel the pending one. So you have numerous timers
>> that virtually never expire. You might have 100 interactions per
>> second, each canceling and restarting a 10-minute timer.
>
> Each individual heapq operation (push or pop) will be O(log n). That's
> not different from a balanced search tree (although of course the
> constant multiplier may vary).

Yes, but if I have 1000 connections with one active timer each. The size
of my sorted tree is 1000 timer objects. There are typically no expiries
to react to.

If the canceled timer lingers in the heapq till its expiry (in 10
minutes), the size is 100 * 10 * 60 = 60,000. The CPU has to wake up
constantly to clear the expired timers.

In practice, none of that might matter.


Marko