On Wed, Mar 26, 2014 at 6: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. > Heaps provide easy access to the first item, but you can't find the last element without scanning the whole thing. With a heap, I think the best approach to the timer-cancellation problem is to periodically rebuild the heap from the non-cancelled items (Tornado keeps a count of cancellations and rebuilds the heap when the number of cancelled timeouts is half of the total. If cancellations are infrequent then they're just left in the heap until their time comes due). -Ben > > 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/ben%40bendarnell.com >
_______________________________________________ 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
