Date: Mon, 22 Sep 1997 14:00:10 -0600 (MDT) From: Nate Williams <nate@mt.sri.com> To: Bruce Evans <bde@zeta.org.au> Cc: nate@mt.sri.com, 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: <199709222000.OAA02491@rocky.mt.sri.com> In-Reply-To: <199709221938.FAA27469@godzilla.zeta.org.au> References: <199709221938.FAA27469@godzilla.zeta.org.au>
next in thread | previous 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.
Again, I was confused. I re-read the paper, and the 'buckets' aren't
all for the same timeout value, but are for timeouts that are similar.
(Unlike your 'specific' solution, which used timeouts that were all
alike as I understand it.)
> >> >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.
But, the act of insertion/deletion is still O(n).
> >> 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.
Even at splhigh(), when you have to look at *every* entry and decrement
it's counter?
> >> >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 still don't understand. You are saying that we call untimeout() more
often than timeout is called. How can that be? That makes no sense,
since it appears to me that timeout() would be called more often than
untimeout(), especially when you consider that the only time you call
untimeout() is when the 'expected' data is aquired before the timer
expires.
Ie:
#define MAX_RETRIES 10
static int retries = 0;
try_work()
{
tell_something_to_get_data(got_data());
timeout(timed_out_getting_data());
return;
}
got_data()
{
untimeout(timed_out_getting_data());
do_work();
retries = 0;
}
timed_out_getting_data()
{
if (retries++ > MAX_RETRIES)
panic("Augh, couldn't get data");
try_work();
}
It seems to me that timeout is called slightly more often than
untimeout, although the difference is minimal since one would hope that
timeouts don't occur at all (or very often anyway) in the above code.
Nate
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199709222000.OAA02491>