bug report: [ #447945 ] time.time() is not non-decreasing

[Bengt Richter]

On Sat, 04 Aug 2001 15:53:42 -0700, zooko at zooko.com wrote:

>
>I have committed a cleaned up version of the IncreasingTimer which does less
>floating point arithmetic and which contains comments showing exactly what 
>I don't know about floating point.
>
>http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/~checkout~/mojonation/evil/common/timeutil.py?content-type=text/plain
>
>The relevant excerpt of the source is appended.
>
>Regards,
>
>Zooko
>
>
>class IncreasingTimer:
>    def __init__(self):
>        self.lasttime = time.time() # This stores the most recent answer that we returned from `time()'.
>        self.delta = 0 # We add this to the result from the underlying `time.time()'.
>
>        # How big of an increment do we need to add in order to make the new float greater than the old float?
>        trye = 1.0
>        while (self.lasttime + trye) > self.lasttime:
>            olde = trye
>            trye = trye / 2.0
>        self._TIME_EPSILON = olde
>
>    def time(self):
>        t = time.time() + self.delta
>        lasttime = self.lasttime
>
>        if t <= lasttime:
>            self.delta = self.delta + (lasttime - t) + self._TIME_EPSILON
>            t = lasttime + self._TIME_EPSILON
>
>        # XXX if you were sure that you could generate a bigger float in one pass, you could change
>        # this `while' to an `if' and optimize out a test.
>        while t <= lasttime:
>            # We can get into here only if self._TIME_EPSILON is too small to make the time float "tick over" to a new higher value.
>            # So we (permanently) double self._TIME_EPSILON.
>            # XXX is doubling epsilon the best way to quickly get a minimally bigger float?
>            self._TIME_EPSILON = self._TIME_EPSILON * 2.0
>            # Delta, having smaller magnitude than t, can be incremented by more than t was incremented.  (Up to the old epsilon more.)  That's OK.
>            self.delta = self.delta + self._TIME_EPSILON
>            t = t + self._TIME_EPSILON
>
>        self.lasttime = t
>        return t
>
I'm not sure why you would add a delta if the raw time.time() advances from the previously
returned time, so I didn't, in the following. If it doesn't work, let me know, and we'll fix it ;-)

BTW, if you're giving these times to a scheduler, you might want check on the precision of *its* sense
of time. Chances are good that the lsb on floating point is going to get lost in conversion to
an integer scheduler tick of some kind, so two times from IncreasingTimer might look simultaneous
and get put in a queue in an order you don't like, or get executed by two CPUs at the same time,
or if the dispatcher get control after some delay and finds two tasks past due (even though by
different amounts) and therefore dispatches both for several CPUs. A single CPU slicing back and
forth between a couple of slow threads could even wind up with unpredictable orders of both start and
finish for a couple of threads.

Even if you have a Python loop dispatching tasks from a queue based on floating point time from
an IncreasingTimer instance, you could have the problem if you have multiple worker threads, and
several tasks are overdue at once. Just a thought. Don't know if it applies.


import math, time

class IncreasingTimer:
    def __init__(self):
        self.lasttime = time.time() # Stores the most recent time returned to caller (after this)

    def time(self):
        t = time.time()
        if t <= self.lasttime:
            t = self.lasttime + math.ldexp(1, math.frexp(self.lasttime)[1]-53) #assumes ieee754 double
        self.lasttime = t
        return t