gmane.comp.lang.tcl.core

Kevin Kenny | 5 Jul 18:56

Re: after ids

Donal K. Fellows wrote:
> OK, how do you work out how long until the next event fires without an
> absolute time source? For added bonus points, do so with arbitrary
> real-time delays between processing points and without extra threads.

Donal,

Many people here are unquestionably arguing from ignorance, but
I do suspect after some conversations with Alexandre Ferrieux
that they are onto something with wanting a distinction between
absolute and relative times.

Absolute time, as far as Tcl is concerned, is UTC with smoothing
(http://www.cl.cam.ac.uk/~mgk25/uts.txt). It advances monotonically
and (more or less) continuously, ticking at an uneven rate to
accommodate TAI-UTC differences and NTP corrections.  It *can*
be nonmonotonic or discontinuous in unusual circumstances, owing
to an act of God (a network outage causing too large an NTP jump
to recover by advancing or retarding clock frequency), an act
of the operator (adjusting system time by the wristwatch-and-
-eyeball method), or an Act of Congress (Daylight Saving Time,
on operating systems that use civil time as the reference).

Its reference on Unix-like systems is gettimeofday(); on Windows
systems its ultimate reference is the system clock returned
by GetSystemTimeAsFileTime, with additional precision provided
by interpolation using the performace counter.

Relative time is not something that Tcl currently recognises,
but perhaps should.  It is strictly monotonic and uniform;

(Continue reading)

headers

Donal K. Fellows | 5 Jul 19:58

Re: after ids

Kevin Kenny wrote:
> Many people here are unquestionably arguing from ignorance, but I do
> suspect after some conversations with Alexandre Ferrieux that they
> are onto something with wanting a distinction between absolute and
> relative times.

While I could always see how to do it with single sets of timers, I
could never work out how to do it reliably with multiple event
sequences on different scales (e.g. a 13ms interval and a 1s interval)
where the event processing takes an appreciable time w.r.t. the
shorter intervals. Which happens for sure when using, say, Tk; redraws
are quite expensive. With each pending timer event assigned an
absolute time at which it becomes eligible for execution, it's pretty
simple to handle. But without it...

> I - and apparently you, Donal - had long believed that no portable
> way existed to get such a clock, but I am coming to suspect that the
> world is catching up with our needs.  On Windows, the information is
> available with the GetTickCount function, which has existed since the
> beginning (Windows attempts to calibrate its rate to NTP corrections,
> but guarantees its monotonicity except for the 49.7-day rollover,
> which we could deal with easily).  Unix-like systems are a tougher
> nut to crack, but with the Posix standards being implemented more and
> more widely, I suspect that the times() function is a reasonable
> reference on Unix-like systems.

Alas, no. On Darwin[*], times() is documented as returning the number
of clock ticks since the Unix epoch, and so is inherently coupled to
absolute time. It's also deprecated in favour of gettimeofday() (and
getrusage(), but that's by the by).

(Continue reading)

headers

Kevin Kenny | 6 Jul 01:29

Re: after ids

Donal K. Fellows wrote:
> Alas, no. On Darwin[*], times() is documented as returning the number
> of clock ticks since the Unix epoch, and so is inherently coupled to
> absolute time. It's also deprecated in favour of gettimeofday() (and
> getrusage(), but that's by the by).
> 
> Without a monotonic reference, the problem's just about impossible
> without doing something elaborate with a RTOS.

Does Darwin support clock_gettime(CLOCK_MONOTONIC, &timespec)?
That's the current OpenGroup thinking, and I do believe that I'd
have the configurator try for that first.  (Nope! Looked it
up - MacOSX does not support clock_gettime at all. What *were*
they thinking?)

In any case, on systems where there is no monotonic reference
available (I suspect the other BSD's share the problem with Darwin),
we can fall back on using gettimeofday() as the reference for
relative timers.  Darwin is less likely than Windows and Linux to
be deployed in an environnment with no possibility of a working
NTP infrastructure. (How many Apples do you see running factories
or labs?)  And it also doesn't have the "guaranteed twice a year"
failure that Windows appears to be prone to.  Alex's suggestion
makes things better on Windows and Linux, and does no harm on
HPUX and Solaris. The big hurdle is still autoconf - to recognize
the method to be used, from among

     clock_gettime(CLOCK_MONOTONIC, ...)
         Solaris, BSD's, newer Linuxes.  Solaris needs -lrt or -lposix4
     times()

(Continue reading)

headers

Daniel A. Steffen | 6 Jul 03:46

Re: after ids

On 05/07/2008, at 19:58, Donal K. Fellows wrote:

> On Darwin[*], times() is documented as returning the number
> of clock ticks since the Unix epoch, and so is inherently coupled to
> absolute time.

the Darwin implementation of times() comes from FreeBSD and is  
completely trivial, the return value is just gettimeofday() in ticks  
(c.f. Darwin source file Libc/gen/times-fbsd.c reproduced below).  
Might be worthwhile checking if current *BSDs still use this technique  
as well...

However, Darwin does have a platform-specific function to get a  
monotonic time reference: mach_absolute_time(), which we are using in  
Tcl already for high-resolution clicks, c.f. TclpGetWideClicks() and  
TclpWideClicksToNanoseconds() in tclUnixTime.c.

mach_absolute_time() is based on the CPU TSC (adjusted for CPU nap/ 
sleep) and is guaranteed to be monotonically increasing, see e.g. the  
following Darwin kernel sources for details:
     xnu/osfmk/i386/rtclock.c
     xnu/osfmk/i386/machine_routines_asm.s
     xnu/osfmk/i386/ommpage/commpage_mach_absolute_time.s
     xnu/osfmk/i386/commpage/commpage.c (commpage_set_nanotime)

All the implementations of relative timers in the OS (nanosleep(),  
pthread_cond_timedwait_relative_np() etc) are based on this reference.

Finding a function that returns an monotonic time reference on a

(Continue reading)

headers

Alexandre Ferrieux | 7 Jul 16:08

Re: after ids

On 7/6/08, Daniel A. Steffen <das@...> wrote:
>
> All the implementations of relative timers in the OS (nanosleep(),
> pthread_cond_timedwait_relative_np() etc) are based on this reference.

So, the shell loop 'while :;do sleep 1;echo foo;done' should have
visible quirks when someone sets the date, right ?

Is the timeout in select() also based on this absolute clock ?

> Finding a function that returns an monotonic time reference on a
> system does not solve the problem of implementing relative timers in
> Tcl however, you also need a way for the notifier to wait for a
> relative time interval, e.g. the current threaded unix notifier
> waiting is based on pthread_cond_timedwait(), which uses absolute time
> (c.f. Tcl_ConditionWait()).

That may be another reason to reform the threaded notifier, if you
allow me that digression 

> Darwin has pthread_cond_timedwait_relative_np() for exactly this
> purpose, I don't know if other systems have something equivalent.

Don't know either but please notice that going to select() everywhere
would solve the problem uniformly. The non-threaded unix notifer has
no problem with relative timers, it's just that currently the value is
recomputed based on absolute time when it needs be.

> (converting next absolute timer fire to a relative
> time interval may result in waiting for too long if there are changes

(Continue reading)

headers

Daniel A. Steffen | 7 Jul 19:38

Re: after ids

Hi Alexandre,

On 07/07/2008, at 16:08, Alexandre Ferrieux wrote:

> On 7/6/08, Daniel A. Steffen <das@...> wrote:
>>
>> All the implementations of relative timers in the OS (nanosleep(),
>> pthread_cond_timedwait_relative_np() etc) are based on this  
>> reference.
>
> So, the shell loop 'while :;do sleep 1;echo foo;done' should have
> visible quirks when someone sets the date, right ?

no, why? that's a relative timeout, /bin/sleep relies on nanosleep()  
and is not affected by calendar time changes (i.e. settimeofday() or  
adjtime())

the 'absolute' in mach_absolute_time() may be confusing matters,  
that's the monotonic time reference for relative time intervals (i.e.  
differences of m_a_t() values), whereas absolute timers are calendar  
time based.

However, on Darwin at least it turns out that even the APIs that take  
an absolute time to wait (like pthread_cond_timedwait()) in fact just  
wait for the relative interval to the value of gettimeofday() at the  
start of the call (i.e. if calendar time is adjusted/changed during  
the waiting, the kernel does not update the timeouts AFAICT).

> Is the timeout in select() also based on this absolute clock ?

(Continue reading)

headers

Alexandre Ferrieux | 7 Jul 21:16

Re: after ids

On 7/7/08, Daniel A. Steffen <das@...> wrote:
> Hi Alexandre,
>
> On 07/07/2008, at 16:08, Alexandre Ferrieux wrote:
>
> > On 7/6/08, Daniel A. Steffen <das@...> wrote:
> >
> > >
> > > All the implementations of relative timers in the OS (nanosleep(),
> > > pthread_cond_timedwait_relative_np() etc) are based on
> this reference.
> > >
> >
> > So, the shell loop 'while :;do sleep 1;echo foo;done' should have
> > visible quirks when someone sets the date, right ?
> >
>
> no, why? that's a relative timeout, /bin/sleep relies on nanosleep() and is
> not affected by calendar time changes (i.e. settimeofday() or adjtime())
> the 'absolute' in mach_absolute_time() may be confusing matters, that's the
> monotonic time reference for relative time intervals (i.e. differences of
> m_a_t() values), whereas absolute timers are calendar time based.

You're right, I was confused :-}

> However, on Darwin at least it turns out that even the APIs that take an
> absolute time to wait (like pthread_cond_timedwait()) in fact just wait for
> the relative interval to the value of gettimeofday() at the start of the
> call (i.e. if calendar time is adjusted/changed during the waiting, the
> kernel does not update the timeouts AFAICT).

(Continue reading)

headers

Daniel A. Steffen | 7 Jul 22:23

Re: after ids

On 07/07/2008, at 21:16, Alexandre Ferrieux wrote:

> Now what about the following hack: have a coarse-grained periodic
> task (say every 5 sec or so), based on a relative timer (!), that
> checks for dicontinuities in gettod() (among others, it would kick in
> everytime the machine is woken up from hibernation). Wouldn't that be
> an appropriate replacement for your systemwide event ? The idea being
> that when gettod is changed, precision under a few seconds is no
> longer a concern anyway...

agreed, feasible (if possibly somewhat expensive) fallback for systems  
where there is no gettod base change notification.

> Regarding your other question: what to do with a mix of relative and
> absolute timers ? Simple: have two queues of timer tokens, one with
> targets expressed in ticks (for the relative timers), the other with
> targets in gettod (for the absolute ones, just like today's [after]).

sure, that wasn't the question 
I was asking (before I figured out that pt_c_tw is internally also  
relying on a relative timeout) how the notifier should wait for both  
relative as well as absolute timeouts with a single API call, in the  
face of gettod base changes; the answer appears to be to use a  
relative timeout and listen to gettod base change notification (or  
fallback to your periodic gettod check timer above)...

Cheers,

Daniel

(Continue reading)

headers

Kevin Kenny | 7 Jul 16:44

Re: after ids

> Finding a function that returns an monotonic time reference on a 
> system does not solve the problem of implementing relative timers in
>  Tcl however, you also need a way for the notifier to wait for a 
> relative time interval, e.g. the current threaded unix notifier 
> waiting is based on pthread_cond_timedwait(), which uses absolute
> time (c.f. Tcl_ConditionWait()).

Is it really true that pthread_cond_timedwait uses an absolute time?
That would imply that every pthreads process that's waiting for a
timer will freeze if the system clock ever jumps backwards. Do
other things freeze on Darwin in that case?

It's not, strictly speaking, necessary to have functions that wait
for both absolute and relative times. It's good enough
if a wait can be interrupted when the system clock is reset.
WM broadcasts a WM_SETTINGSCHANGED in that case.

--

-- 
73 de ke9tv/2, Kevin

-------------------------------------------------------------------------
Sponsored by: SourceForge.net Community Choice Awards: VOTE NOW!
Studies have shown that voting for your favorite open source project,
along with a healthy diet, reduces your potential for chronic lameness
and boredom. Vote Now at http://www.sourceforge.net/community/cca08

headers

Daniel A. Steffen | 7 Jul 19:45

Re: after ids

On 07/07/2008, at 16:44, Kevin Kenny wrote:

>> Finding a function that returns an monotonic time reference on a  
>> system does not solve the problem of implementing relative timers in
>> Tcl however, you also need a way for the notifier to wait for a  
>> relative time interval, e.g. the current threaded unix notifier  
>> waiting is based on pthread_cond_timedwait(), which uses absolute
>> time (c.f. Tcl_ConditionWait()).
>
> Is it really true that pthread_cond_timedwait uses an absolute time?
> That would imply that every pthreads process that's waiting for a
> timer will freeze if the system clock ever jumps backwards. Do
> other things freeze on Darwin in that case?

no, as I have just discovered, while pthread_cond_timedwait takes an  
absolute time, it does in fact just wait for the relative interval to  
the value of gettimeofday() at the start of the call (i.e. if calendar  
time is adjusted/changed during  the waiting, the kernel does not  
update the timeouts AFAICT).

> It's not, strictly speaking, necessary to have functions that wait
> for both absolute and relative times. It's good enough
> if a wait can be interrupted when the system clock is reset.

agreed, Darwin sends a host notification when calendar time is changed  
via  settimeofday() (but not for adjustments due to adjtime()), it  
might take a separate thread to integrate listening to that  
notification into the tcl notifier though, I'd have to look into it.

(Continue reading)