Date: Mon, 22 Sep 1997 12:38:31 -0600 (MDT) From: Nate Williams <nate@mt.sri.com> To: Bruce Evans <bde@zeta.org.au> Cc: gibbs@plutotech.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 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.c ... Message-ID: <199709221838.MAA01799@rocky.mt.sri.com> In-Reply-To: <199709221822.EAA25174@godzilla.zeta.org.au> References: <199709221822.EAA25174@godzilla.zeta.org.au>
next in thread | previous in thread | raw e-mail | index | archive | help
Bruce Evans writes: > >> >only 2 bits. This is 96 times denser than the current callout table. > >> > >> And runs in roughly O(n) time every time the interval timer expires. > > But it doesn't. Since the point of the new method is to avoid O(n) > behaviour, of course I presented a method that was O(1) in the usual > case. > > >Except that processing a tick now runs O(n), where n is the # of > >elements in the callout wheel (which gets pretty big when you have 630 > >callouts in your example above, since the initial size of the callout > > Not great. My method uses a split queue to usually avoid having to > look at the half expired timeouts. The old method used a delta list > for similar reasons. I'm surprised that there is no trace of delta > lists in the new method. I am as well. It *seems* to me that this is probably the biggest bottleneck in the softclock() handling, and wouldn't add that much overhead to the timeout registration code (since once you've got the correct hash entry, you could simply copy the head's value, or calculate the new value, neither of which would take that long.) > >wheel is set), so I still don't see a big win. I'm not saying that it's > >any worse/better than the existing scheme, in fact I don't see a win. > > However, it's only O(n). The old method was O(n^2) for each insertion > and deletion, which makes it O(n^2) altogether. Huh? How was O(n^2)? I see it as O(n) for insertion, and O(n) for deletion, which is still O(n). (I'm looking at the 4.3/4.4 books, and don't have the code handy.) > >Stating that it takes O(n) times to add/remove a callout and calling it > >a win when it takes O(n) time to process a tick isn't a win in my book. > > The point is that the tick interval is fixed. But, the time it takes to do softclock is not, and you can sometimes take too long in the softclock interrupt handler. > >PHK answered by saying that on his laptop, it seemed to be a wash, so > >that's encouraging, but it seems to have the ability to make the system > >slower. (I'd like to see how PHK compared the two approaches.) > > timeout() probably doesn't get called enough to matter. Umm, I would think there's a one-one match for timeout/untimeout, wouldn't there? > >additions w/out the call wheel). I just want to understand *why* it's > >making things better for the average user, since the average user > >doesn't have > 10 drives running tags. Penalizing the 'extreme' user > >doesn't seem to be a big win in my book. > > I expect it will make things slightly worse for the average user, but > the difference will be too small to measure. So do you think the new solution is a 'win' overall? > >In summary, all of the operations are called 'often'. > > > >1) clock ticks > > No, they only occur every 10 ms, which is approximately eternity for a > fast CPU :-). > > >2) registering timeouts > >3) de-registering timeouts How often are the above called (in comparison to clock ticks)? Nate
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199709221838.MAA01799>