Date: Tue, 23 Sep 1997 05:38:53 +1000 From: Bruce Evans <bde@zeta.org.au> To: bde@zeta.org.au, nate@mt.sri.com Cc: current@freebsd.org, gibbs@plutotech.com 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: <199709221938.FAA27469@godzilla.zeta.org.au>
next in thread | raw e-mail | index | archive | help
>> 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.) A delta list is a time-ordered list cleverly scaled to be relative to the current time. Hashing doesn't mix well with sorting. I don't know how to insert in an ordered list faster than O(log n). Deletion could be done in O(1) without using cookies by building hash table on insertion. >> >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.) I'm assuming that the size of the table (n) is proportional to the number of insertions per second. >> 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. The time taken to traverse the wheel queue is insignificant compared with the tick interval. >> >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? No (many timeouts expire naturally), but that doesn't affect the time spent calling timeout() or untimeout() by more than a factor of 2. (not enough to matter) * 2 = (not enough to matter). >> 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? Average small loss, but large win on some systems. >> >2) registering timeouts >> >3) de-registering timeouts > >How often are the above called (in comparison to clock ticks)? It depends. :-) Bruce
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199709221938.FAA27469>