[Python-Dev] collections.sortedtree

[Antoine Pitrou]

On Wed, 26 Mar 2014 23:57:27 +0200
Marko Rauhamaa <marko at pacujo.net> wrote:
> 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.

Ideally, I think you should be able to replace the cancelled item with
the last item in the heap and then fix the heap in logarithmic time,
but the heapq API doesn't seem to provide a way to do this.

Regards

Antoine.