[Python-Dev] collections.sortedtree (original) (raw)

Marko Rauhamaa marko at pacujo.net
Wed Mar 26 22:57:27 CET 2014

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

More information about the Python-Dev mailing list