Date: Mon, 22 Sep 1997 14:53:38 -0600 (MDT) From: Nate Williams <nate@mt.sri.com> To: "Justin T. Gibbs" <gibbs@plutotech.com> Cc: Terry Lambert <tlambert@primenet.com>, 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 Message-ID: <199709222053.OAA02847@rocky.mt.sri.com> In-Reply-To: <199709222029.OAA00790@pluto.plutotech.com> References: <199709221926.MAA16814@usr06.primenet.com> <199709222029.OAA00790@pluto.plutotech.com>
next in thread | previous in thread | raw e-mail | index | archive | help
> >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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199709222053.OAA02847>