From owner-freebsd-arch@FreeBSD.ORG Mon Nov 13 23:07:20 2006 Return-Path: X-Original-To: arch@freebsd.org Delivered-To: freebsd-arch@FreeBSD.ORG Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id F034716A415 for ; Mon, 13 Nov 2006 23:07:20 +0000 (UTC) (envelope-from jmg@hydrogen.funkthat.com) Received: from hydrogen.funkthat.com (gate.funkthat.com [69.17.45.168]) by mx1.FreeBSD.org (Postfix) with ESMTP id 091BC43E35 for ; Mon, 13 Nov 2006 23:05:04 +0000 (GMT) (envelope-from jmg@hydrogen.funkthat.com) Received: from hydrogen.funkthat.com (rqq0vflwxhue1l8x@localhost.funkthat.com [127.0.0.1]) by hydrogen.funkthat.com (8.13.6/8.13.3) with ESMTP id kADN4uWo051917; Mon, 13 Nov 2006 15:04:56 -0800 (PST) (envelope-from jmg@hydrogen.funkthat.com) Received: (from jmg@localhost) by hydrogen.funkthat.com (8.13.6/8.13.3/Submit) id kADN4t8C051916; Mon, 13 Nov 2006 15:04:55 -0800 (PST) (envelope-from jmg) Date: Mon, 13 Nov 2006 15:04:55 -0800 From: John-Mark Gurney To: Poul-Henning Kamp Message-ID: <20061113230455.GP9291@funkthat.com> Mail-Followup-To: Poul-Henning Kamp , arch@freebsd.org References: <7105.1163451221@critter.freebsd.dk> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <7105.1163451221@critter.freebsd.dk> User-Agent: Mutt/1.4.2.1i X-Operating-System: FreeBSD 5.4-RELEASE-p6 i386 X-PGP-Fingerprint: B7 EC EF F8 AE ED A7 31 96 7A 22 B3 D8 56 36 F4 X-Files: The truth is out there X-URL: http://resnet.uoregon.edu/~gurney_j/ X-Resume: http://resnet.uoregon.edu/~gurney_j/resume.html Cc: arch@freebsd.org Subject: Re: a proposed callout API X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list Reply-To: John-Mark Gurney List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 13 Nov 2006 23:07:21 -0000 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)... -- John-Mark Gurney Voice: +1 415 225 5579 "All that I will do, has been done, All that I have, has not."