Skip site navigation (1)Skip section navigation (2)
Date:      Tue, 14 Nov 2006 16:11:20 +0100
From:      Andre Oppermann <andre@freebsd.org>
To:        Poul-Henning Kamp <phk@phk.freebsd.dk>,  arch@freebsd.org
Subject:   Re: a proposed callout API
Message-ID:  <4559DC98.8030103@freebsd.org>
In-Reply-To: <20061113230455.GP9291@funkthat.com>
References:  <7105.1163451221@critter.freebsd.dk> <20061113230455.GP9291@funkthat.com>

next in thread | previous in thread | raw e-mail | index | archive | help
John-Mark Gurney wrote:
> Poul-Henning Kamp wrote this message on Mon, Nov 13, 2006 at 20:53 +0000:
>> Imagine the number of lists is four, we then label them with Tnow+2s,
>> Tnow+8s, Tnow+32s and "the rest".
>>
>> Armed callouts go into the first list that is labeled with a higher
>> strike time.
>>
>> If a callout is rescheduled to later, it's timeout is updated, but
>> it is not moved in the list.
>>
>> If a callout is cancled, it is removed from the list.
>>
>> Twice per second, the first list is scanned, and any due callouts
>> called and any callouts later than the lists strike time is moved
>> into the right list.
>>
>> When "Tnow+2s" rolls around, the lists are rotated to the left:
>> the Tnow+8s becomes "Tnow+2s" etc.
>>
>> The idea behind this (untried) scheme for the long callouts, is to
>> distribute the callouts somewhat evenly in the lists, while maintaining
>> only the relevant entries in the first list, the point being that
>> most of them (TCP keepalive, CAM etc) will never happen, so spending
>> time sorting them more than necessary is pointless.  Obviously,
>> this algorithm needs to be tested in practice and tuned/changed/discared
>> depending on the results.
> 
> The other option is to use a fibonacci heap for these lists...  It
> brings features that we want to this problem..   check out:
> http://resnet.uoregon.edu/~gurney_j/jmpc/fib.html
> 
> Hmmm... even though my page says extract out of order is O(lgn), that
> is after an extract min does the rebalancing, and happens after many
> extracts have happened...  (you can OO extract the first one in O(1),
> but a future extract will require lgn work)...
> 
> Though w/ a large list the first extract min is pretty expensive (as
> it pays for all the O(1) inserts that haven't been extracted yet)...

It's important to know that any random memory accesses on modern
CPUs are really expensive because of cache misses.  That's why
Judy tries beat RB tries by an order of a magnitude these days.

-- 
Andre




Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?4559DC98.8030103>