Date: Mon, 22 Sep 1997 23:39:30 -0700 From: John-Mark Gurney <gurney_j@efn.org> To: Nate Williams <nate@mt.sri.com> Cc: "Justin T. Gibbs" <gibbs@plutotech.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 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. Message-ID: <19970922233930.12159@hydrogen.nike.efn.org> In-Reply-To: <199709221839.MAA01809@rocky.mt.sri.com>; from Nate Williams on Mon, Sep 22, 1997 at 12:39:44PM -0600 References: <199709220505.XAA29116@rocky.mt.sri.com> <199709220548.XAA08824@pluto.plutotech.com> <199709221839.MAA01809@rocky.mt.sri.com>
next in thread | previous in thread | raw e-mail | index | archive | help
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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?19970922233930.12159>