Re: HZ, preferably as small as possible

[Daniel Phillips]

On Thursday 18 July 2002 14:57, Richard B. Johnson wrote:
> On Wed, 17 Jul 2002, Linus Torvalds wrote:
> > On Wed, 17 Jul 2002, Richard B. Johnson wrote:
> > >
> > > It is hardly novel and I can't imagine how Bresenham or whomever
> > > could make such a claim to the obvious. Even the DOS writer(s) used
> > > this technique to get one-second time intervals from the 18.206
> > > ticks/per second.
> > 
> > Ehh.. Look at _existing_ linux code to do exactly the same.
> > 
> > See update_wall_time_one_tick() and second_overflow() (which does a lot
> > more besides, but it does largely boil down to this "average fractions
> > using basic integer math" thing.
>
> Maybe you see something in the code I don't. In fact, the hardware
> apprears to have been programmed to interrupt at the HZ rate
> using the constant, CLOCK_TICK_RATE, defined in ../asm/timex.h.
> Maybe the hardware can't be programmed to interrupt at HZ so the
> real ticks are adjusted by 'average fractions' code, but it is
> very unclear if this is being done.
> 
> Here is a 20 year-old source snippit of some synthetic division
> code used to correct the DOS time by substituting part of INT 08.

Yes, that's the same algorithm all right, and 'synthetic division'
is a much better name for it than the one I used.  IMHO, we should be
doing this even when there happens to be an integral relationship 
between timer interrupt rate and HZ.  It eliminates a bunch of
posturing we'd otherwise be stuck with to explain/work around
restrictions in the choice of intervals.  With a little bit of head
scratching it's also possible to add the bookkeeping necessary to
handle varying physical interrupt rates, while still maintaining
the *exact* correct HZ tick count.

Stripping some cruft from your historical example:

 	SUB	WORD PTR [ACCUMULATOR],NUMERATOR
 	JNC	NO_TICK
 	MOV	AX,DIVISOR
 	ADD	WORD PTR [ACCUMULATOR],AX	; Synth div
 	CALL	TICK
NO_TICK:

Pretty hard to beat that for efficiency.

-- 
Daniel