Trees

[Paul Rubin]

Marko Rauhamaa <marko at pacujo.net> writes:
> As I said, I use ordered mappings to implement timers... The downside
> of heapq is that canceled timers often flood the heapq structure...,
> GvR mentioned a periodic "garbage collection" as a potentially
> effective solution. 

You could look up the "timer wheel" approach used by the Linux kernel
and by Erlang.  It's less general than an ordered map, but probably
faster in practice.

  https://lkml.org/lkml/2005/10/19/46 

Has some info.  I think the kernel uses a different method now though.

Fwiw, I believe that the Haskell i/o manager uses an ordered map, and it
gets monstrous performance:

http://haskell.cs.yale.edu/wp-content/uploads/2013/08/hask035-voellmy.pdf

Some comments:
http://ezyang.tumblr.com/post/62152700458/haskell-mio-a-high-performance-multicore-io