From owner-freebsd-current Mon Sep 22 13:53:51 1997 Return-Path: Received: (from root@localhost) by hub.freebsd.org (8.8.7/8.8.7) id NAA18980 for current-outgoing; Mon, 22 Sep 1997 13:53:51 -0700 (PDT) Received: from ns.mt.sri.com (SRI-56K-FR.mt.net [206.127.65.42]) by hub.freebsd.org (8.8.7/8.8.7) with ESMTP id NAA18975 for ; Mon, 22 Sep 1997 13:53:46 -0700 (PDT) Received: from rocky.mt.sri.com (rocky.mt.sri.com [206.127.76.100]) by ns.mt.sri.com (8.8.7/8.8.7) with ESMTP id OAA15225; Mon, 22 Sep 1997 14:53:40 -0600 (MDT) Received: (from nate@localhost) by rocky.mt.sri.com (8.7.5/8.7.3) id OAA02847; Mon, 22 Sep 1997 14:53:38 -0600 (MDT) Date: Mon, 22 Sep 1997 14:53:38 -0600 (MDT) Message-Id: <199709222053.OAA02847@rocky.mt.sri.com> From: Nate Williams MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit To: "Justin T. Gibbs" Cc: Terry Lambert , nate@mt.sri.com, current@freebsd.org Subject: Re: cvs commit: src/sys/conf files src/sys/dev/vx if_vx.c if_vxreg.h src/sys/i386/apm apm.c src/sys/i386/conf GENERIC files.i386 In-Reply-To: <199709222029.OAA00790@pluto.plutotech.com> References: <199709221926.MAA16814@usr06.primenet.com> <199709222029.OAA00790@pluto.plutotech.com> X-Mailer: VM 6.29 under 19.15 XEmacs Lucid Sender: owner-freebsd-current@freebsd.org X-Loop: FreeBSD.org Precedence: bulk > >O(hash chain length) insertion and O(1) event identification beats > >O(1) insertion and O(total number of timeouts) event identification, > >which is what you get from an unordered list. > > Sure, assuming that's what you have, but the new scheme is > O(hash chain length) event identification in softclock + O(1) > insertion/removal. Not quite. It's really "O(hash chain length) event identification + O(n) callout overhead processing + O(1) insertion/removal" in the new scheme. > >> Even so, it is probably better to store an absolute tick value regardless > >> so that you don't have to perform the subtraction. > > > >Yes, at a minimum. Also, if the list is sorted, you do not have to > >traverse it in it's entirety. > > You do during a call to timeout(). True. There's really no way around higher costs at timeout() with the old scheme (although it would be trivial to optimize untimeout() with hashtables). Any other solution I can come up with ends up looking alot like the new scheme. :) Nate