Date: Tue, 23 Sep 1997 04:22:12 +1000 From: Bruce Evans <bde@zeta.org.au> To: gibbs@plutotech.com, nate@mt.sri.com Cc: bde@zeta.org.au, 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: <199709221822.EAA25174@godzilla.zeta.org.au>
next in thread | raw e-mail | index | archive | help
>> >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. >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. >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. >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. >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. >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 >I would like to see some #'s that show us the # & amount of time it >takes in section on a 'normal' system, using both approaches. If >someone has some good ideas how to do that, I'm willing to learn >something and go do it. Profiling should show completely accurate numbers. High-resolution profiling (config -pp and kgmon -B ... gprof4 ...) should show fairly accurate times. Bruce
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199709221822.EAA25174>