Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #84080

Re: Trees

From Paul Rubin <no.email@nospam.invalid>
Newsgroups comp.lang.python
Subject Re: Trees
Date 2015-01-20 10:14 -0800
Organization A noiseless patient Spider
Message-ID <877fwhb9pk.fsf@jester.gateway.sonic.net> (permalink)
References <CAG=hEY1L-39EmuWpdEh_n-BNfs=qG9nL=MrMT0ar72yGBrkoUA@mail.gmail.com> <mailman.17884.1421734095.18130.python-list@python.org> <87ppa9944t.fsf@elektro.pacujo.net>

Show all headers | View raw

Marko Rauhamaa <marko@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

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Re: Trees Terry Reedy <tjreedy@udel.edu> - 2015-01-20 01:08 -0500
  Re: Trees Marko Rauhamaa <marko@pacujo.net> - 2015-01-20 11:45 +0200
    Re: Trees Paul Rubin <no.email@nospam.invalid> - 2015-01-20 10:14 -0800
      Re: Trees Marko Rauhamaa <marko@pacujo.net> - 2015-01-20 22:26 +0200
    Re: Trees Stephen Hansen <me+python@ixokai.io> - 2015-01-20 23:56 -0800
      Re: Trees Marko Rauhamaa <marko@pacujo.net> - 2015-01-21 10:35 +0200
      Re: Trees Rustom Mody <rustompmody@gmail.com> - 2015-01-21 04:09 -0800
        Re: Trees Chris Angelico <rosuav@gmail.com> - 2015-01-21 23:35 +1100
          Re: Trees Rustom Mody <rustompmody@gmail.com> - 2015-01-21 07:24 -0800
        Re: Trees Tim Chase <python.list@tim.thechases.com> - 2015-01-21 06:55 -0600
        Re: Trees Chris Angelico <rosuav@gmail.com> - 2015-01-22 00:01 +1100
        Re: Trees Tim Chase <python.list@tim.thechases.com> - 2015-01-21 08:26 -0600
        Re: Trees Chris Angelico <rosuav@gmail.com> - 2015-01-22 01:31 +1100
        Re: Trees Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-01-22 01:47 +1100
          Re: Trees Ian Kelly <ian.g.kelly@gmail.com> - 2015-01-21 09:15 -0700
          Re: Trees Ian Kelly <ian.g.kelly@gmail.com> - 2015-01-21 10:27 -0700
  Re: Trees Rustom Mody <rustompmody@gmail.com> - 2015-01-20 05:33 -0800
    Re: Trees Rustom Mody <rustompmody@gmail.com> - 2015-01-20 05:51 -0800
    Re: Trees Marko Rauhamaa <marko@pacujo.net> - 2015-01-20 16:15 +0200
      Re: Trees Rustom Mody <rustompmody@gmail.com> - 2015-01-20 06:35 -0800
    Re: Trees Ian Kelly <ian.g.kelly@gmail.com> - 2015-01-20 10:19 -0700
      Re: Trees Rustom Mody <rustompmody@gmail.com> - 2015-01-20 10:15 -0800
        Re: Trees Rustom Mody <rustompmody@gmail.com> - 2015-01-20 10:35 -0800
    Re: Trees Mario <marfig@gmail.com> - 2015-01-20 22:47 +0100
      Re: Trees Rustom Mody <rustompmody@gmail.com> - 2015-01-20 17:23 -0800
        Re: Trees Paul Rubin <no.email@nospam.invalid> - 2015-01-20 17:49 -0800
          Re: Trees Rustom Mody <rustompmody@gmail.com> - 2015-01-20 18:03 -0800
            Re: Trees Paul Rubin <no.email@nospam.invalid> - 2015-01-21 14:27 -0800
              Re: Trees Rustom Mody <rustompmody@gmail.com> - 2015-01-21 21:17 -0800
        Re: Trees Ian Kelly <ian.g.kelly@gmail.com> - 2015-01-21 15:54 -0700
          Re: Trees Rustom Mody <rustompmody@gmail.com> - 2015-01-21 21:20 -0800
            Re: Trees Ian Kelly <ian.g.kelly@gmail.com> - 2015-01-22 00:01 -0700
            Re: Trees Ian Kelly <ian.g.kelly@gmail.com> - 2015-01-21 23:56 -0700
          Re: Trees Paul Rubin <no.email@nospam.invalid> - 2015-01-21 23:16 -0800
            Re: Trees Rustom Mody <rustompmody@gmail.com> - 2015-01-22 08:54 -0800
      Re: Trees Terry Reedy <tjreedy@udel.edu> - 2015-01-20 21:19 -0500
        Re: Trees Mario Figueiredo <marfig@gmail.com> - 2015-01-21 14:05 +0000

csiph-web