[Python-Dev] collections.sortedtree
Guido van Rossum
guido at python.org
Wed Mar 26 23:16:03 CET 2014
Yeah, so the pyftp fix is to keep track of how many timers were cancelled,
and if the number exceeds a threshold it just recreates the heap, something
like
heap = [x for x in heap if not x.cancelled]
heapify(heap)
On Wed, Mar 26, 2014 at 3:02 PM, Antoine Pitrou <solipsis at pitrou.net> wrote:
> 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.
> _______________________________________________
> Python-Dev mailing list
> Python-Dev at python.org
> https://mail.python.org/mailman/listinfo/python-dev
> Unsubscribe:
> https://mail.python.org/mailman/options/python-dev/guido%40python.org
>
--
--Guido van Rossum (python.org/~guido)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-dev/attachments/20140326/e64c8392/attachment.html>
More information about the Python-Dev
mailing list