From owner-freebsd-current Mon Sep 22 23:39:46 1997 Return-Path: Received: (from root@localhost) by hub.freebsd.org (8.8.7/8.8.7) id XAA23357 for current-outgoing; Mon, 22 Sep 1997 23:39:46 -0700 (PDT) Received: from hydrogen.nike.efn.org (resnet.uoregon.edu [128.223.170.28]) by hub.freebsd.org (8.8.7/8.8.7) with ESMTP id XAA23350 for ; Mon, 22 Sep 1997 23:39:42 -0700 (PDT) Received: (from jmg@localhost) by hydrogen.nike.efn.org (8.8.7/8.8.7) id XAA28674; Mon, 22 Sep 1997 23:39:30 -0700 (PDT) Message-ID: <19970922233930.12159@hydrogen.nike.efn.org> Date: Mon, 22 Sep 1997 23:39:30 -0700 From: John-Mark Gurney To: Nate Williams Cc: "Justin T. Gibbs" , 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 src/sys/i386/eisa 3c5x9.c aha1742.c aic7770.c bt74x.c eisaconf.c eisaconf.h if_fea.c if_vx_eisa.c src/sys/i386/i386 autoconf. References: <199709220505.XAA29116@rocky.mt.sri.com> <199709220548.XAA08824@pluto.plutotech.com> <199709221839.MAA01809@rocky.mt.sri.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Mailer: Mutt 0.69 In-Reply-To: <199709221839.MAA01809@rocky.mt.sri.com>; from Nate Williams on Mon, Sep 22, 1997 at 12:39:44PM -0600 Reply-To: John-Mark Gurney Organization: Cu Networking X-Operating-System: FreeBSD 2.2.1-RELEASE 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/ Sender: owner-freebsd-current@FreeBSD.ORG X-Loop: FreeBSD.org Precedence: bulk Nate Williams scribbled this message on Sep 22: > > In performing the conversion of all the client code, it became quite > > obvious that the common case is to schedule a timeout that will be > > canceled before it expires and that the lifetime of a timeout is quite > > short. > > Is 'short' shorter than a single softclock()? If not, then we still > need to do more work than we used to do. And, if we have 2 ticks, > 'assuming all things we're equal' the new code could be the same speed > as the old code. > > (Obviously bogus explanation follows): > > Old code: > 1) timeout = O(x) ~= 10 seconds > 2) untimeout = O(x) ~= 10 seconds > 3) softclock = O(1) ~= 1 second > > So, assuming we call a timeout, get 2 softclock updates, and then call > untimeout we get: > > 10 + 1 + 1 + 10 = 22 seconds. > > New code: > 1) timeout = O(1) ~= 1 seconds > 2) untimeout = O(1) ~= 1 seconds > 3) softclock = O(n) ~= 10 second > > The same as above: > > 1 + 10 + 10 + 1 = 22 seconds. > > Again, this is so obviously bogus that I hate to even mention it, but it > explains what I'm trying to say. Depending on *how often* and *how > long* each of the operations takes, the new solution may not be a win. > > I'll stop for now, since this is as much a learning experience for me as > anything, and I don't want to wear out my welcome. :) :) now... I want to know why something more effecient isn't used.. something like a Fibonacci heap... this will provide amortized constant time for insert and minimum (find what is min)... then for actually deleting a key (performed once for each key when either expired or removed) it performs in O(lgn) time... from the sounds of it.. this will be a VERY big win... as then softclock will run at worst O(xlgn) when x elements expires... and O(1) when there isn't anything to expire... for more info, look up Fibonacci heaps in a Data structures book like, Introduction to Algorithms, by Cormen, Leiserson, and Rivest... ISBN 0-07-013143-0... I was surprised that something like this isn't already implemented genericly in the kernel... I was thinking about working on implementing this in the near future once I found out that such a thing doesn't exist already in FreeBSD... -- John-Mark Gurney Modem/FAX: +1 541 683 6954 Cu Networking Live in Peace, destroy Micro$oft, support free software, run FreeBSD