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 <solip...@pitrou.net> wrote: > On Wed, 26 Mar 2014 23:57:27 +0200 > Marko Rauhamaa <ma...@pacujo.net> wrote: > > Antoine Pitrou <solip...@pitrou.net>: > > > > > Marko Rauhamaa <ma...@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@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)
_______________________________________________ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
