[Openmcl-devel] time travel

[Gary Byers]

AFAIK, mach_absolute_time() is implemented in terms of the "rdtsc" (Read Time
Stamp Counter") instruction, which returns the value of a 64-bit on-chip
counter that increments once every machine cycle.

There are a few things that can make it difficult to use the value returned
by rdtsc for high-resolution timing.

1) the time-stamp counters are per-cpu, which generally means that unless the
OS takes steps to get and keep the TSCs of all CPU cores in sync, the value
returned by a rdtsc executed on CPU B may be less than a value returned on
CPU A.  As far as I know, OSX deals with this pretty well.

2) CPUs (especially those used in laptops and many consumer machines)
don't always run at the same clock rate these days; they'll often
switch into low-power states where the number of machine cycles per second
is less then the maximum.  On a Core2-Quad desktop machine running Linux

$ cat /sys/devices/system/cpu/cpu0/cpufreq/scaling_available_frequencies 
2394000 1596000

which says that a machine marketed as having a 2.4GHz CPU can also run at
a bit under 1.6GHz.

Things like mach_absolute_time() have to be able to account for the fact that
the CPU frequency is dynamic (and therefore the values returned by rdtsc have
to be scaled by different amounts depending on the CPU frequency.)  I'm sure
that mach_absolute_time() does deal with this, but I remember looking at the
code once and thinking that it was a lot more complicated than I would have
guessed.

3) [Even fuzzier.]  'rdtsc' instructions can be virtualized (meaning that things
like VMWare and Parallels can detect their use by at least some programs.)  I
don't know enough about the technology involved to know whether this means that
a 'hypervisor' (or whatever they call it) can affect the results returned by
rdtsc to host-OS programs.

Both the result of the rdtsc instruction and the 64-bit integer
returned by mach_absolute_time() are returned as a pair of 32-bit
integers (containing the low and high 32 bits of the result.)  I find
it awfully suspicious that the absolute value of difference between t2
and t1 in the cases where time travel occurred is as close as it is to
2^32 (as if some code in mach_absolute_time() neglected to add a carry
bit out of the low half into the high half.

CCL just takes those 2 32-bit halves of mach_absolute_time()'s result
and makes a lisp integer (almost always a bignum in the 32-bit lisp)
out of them. (There -is- a bug here, in that 64-bit return values from
foreign function calls aren't handled correctly in the x8632 CCL when
the argument and return-value processing occur out of line; in your
DOTIMES loop, that'd all happen in compiled code unless DEBUG or SAFETY
optimize settings are cranked up, and I don't think that there's a problem
when they aren't.

So yes, I can think of a few explanations.  I have no idea if any of them
is correct, or what the workaround would be.

FWIW, I can't get the DOTIMES loop below to fail unless I add a
"(DECLARE (OPTIMIZE (SAFETY 3)))"; when it fails in that case, it's
confused about the sign bit of the low 32 bits of the result (bit 31),
and you're seeing apparent confusion about the value of the low bit of
the high 32 bits (bit 32).


On Fri, 15 May 2009, Alexander Repenning wrote:

> In some animations I found irregularities which I traced back to some strange 
> behavior of mach_absolute_time
>
> This loop should produce no output. On PPCs it works but on my Intel-Mac 
> (with CCL 32) I get some output indicating that once in a while my computer 
> appears to travel back in time for about 4 seconds
>
> (dotimes (i 1000)
> (let ((t1 (#_mach_absolute_time)))
>   (sleep 0.01)
>   (let ((t2 (#_mach_absolute_time)))
>     (when (> t1 t2) (print (- t2 t1))))))
>
> -4284773073
> -4284777830
> -4284869530
>
> Can anybody reproduce this and is there any explanation, work around for this 
> kind of madness?
>
> Alex
>
>
> Prof. Alexander Repenning
>
> University of Colorado
> Computer Science Department
> Boulder, CO 80309-430
>
> vCard: http://www.cs.colorado.edu/~ralex/AlexanderRepenning.vcf
>
>