Date: Mon, 22 Sep 1997 20:31:32 +0000 (GMT) From: Terry Lambert <tlambert@primenet.com> To: nate@mt.sri.com (Nate Williams) Cc: gibbs@plutotech.com, 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: <199709222031.NAA21421@usr06.primenet.com> In-Reply-To: <199709221905.NAA02100@rocky.mt.sri.com> from "Nate Williams" at Sep 22, 97 01:05:28 pm
next in thread | previous in thread | raw e-mail | index | archive | help
> > >A more deterministic implementation would associate an absolute tick > > >value (rather than a count) with each entry, and insert entries in > > >sorted order. > > > > More deterministic for who? This trades O(1) insertion for O(hash chain > > length) insertion so that softclock will become O(timeouts for the current > > tick). As timeout often is called from an interrupt context > > it is not so clear where it is better to pay the price of non-determinism. > > Softclock has the luxury of lowering it's spl at deterministic intervals > > (see the implementation) while a caller from an interrupt context doesn't. > > the current implementation always blocks interrupts for a deterministic > > amount of time. What you propose doesn't. > > From reading the papers, the performance would be neglidgable (sp?) > since they assume the hash chain length is <= 1. That's one of the > performance gains they assume. > > > Even so, it is probably better to store an absolute tick value regardless > > so that you don't have to perform the subtraction. > > A substraction is *dirt cheap* to do. Finding the element on the list > is much more expensive than the subtraction. This is why I suggested ordered insertion. For n elements, an ordered linear insertion of a perfectly random timeout is O(n/2). In reality, I would suggest maintaining a near-skiplist for some small number of entries. Since timers export off the head, in order, dividing the entries into, say, 8 ordered and equally spaced insertion vectors should work. Given the head-forward, these vectors could easily march forward through the list, as necessary to maintain spacing. This is O(log2(n)+(n/8)) in the average case. I think insertion can take a relatively "long time", in any case; it is the speed of expiration which is important. You can keep the doubly linked list so that removal is still O(1), and event processing is always O(number of events that expire), or ~= O(1). Better to take the hit when you have slack. If you use an absolute tick rather than a delta, then it doesn't matter how long the delay between "I want to insert" and "actual insertion", so long a the number of ticks it takes is less than the total number of ticks between the current time and the expiration time. Better to take the fuzz where you can afford fuzz, I say. Terry Lambert terry@lambert.org --- Any opinions in this posting are my own and not those of my present or previous employers.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199709222031.NAA21421>