Avoid double precision floats in time.monotonic() computation to further increase flash space

[dhalbert]

time.monotonic() was dividing a 64-bit uint by 1000.0f. This caused the compiled code to _aeabi_u2lf(), which converts long long to float. In the process ul2f calls double-precision routines. I thought I had gotten rid of these by #325, but not completely.

I changed the arithmetic to break the 64-bit int into two pieces: multiply the top part by 2.0^32f and add it to the bottom part, then divide by 1000.0f. This avoids ul2f and there are no more double routines left in the image except the tiny _aeabi_d2f()`.

This gains back 3044 bytes!!

[ladyada]

nice!

[jerryneedell]

Dan, I'm probably misunderstanding what this is doing, but 2^32 = 4294967296 which requires more precision than can be expressed in a float, correct? So when it is multiplied by the upper portion of the time, isn't information lost? Does this essentially make the time.monotonic value only valid for the lower 32bits of the counter?

[jerryneedell]

Perhaps I am overthinking this, but the case I am concerned about if when two captures of time.monotonic differ in the lower portion of the upper 32bit word. Will differences of these time tags be valid?
In your proposed code, this value (time64 >> 32) * 4294967296.0f is not precisely determined because the 32 bit float representation of 4294967296.0f is not unique.

[dhalbert]

(I was going to mention this last night, but was too tired.) There is a precision problem with time.monotonic() but it was already there. It returns a float. A regular IEEE float is one bit of sign, 8 bits of exponent (power of 2), and 24 virtual bits of precision mantissa ( the top bit is always 1, unless, the exponent is all zeros, so only 23 bits are needed to store 24 bits of precision).

In CPy/MPy, the lower two bits are truncated, and are used for flag bits to differentiate pointers, ints and floats. So its floats are stored in 30 bits: one sign bit, 8 bits of exponent, and 22 preicison bits (21 physically).

time.monotonic() (before and after this change) converts an unsigned 64-bit millisecond tick counter to a float value in seconds. The float will accurately represent the number of msecs up to 2^22. At that point it will start losing accuracy, and will start incrementing only every second tick. At 2^23 it will be every fourth tick, etc. You can try this in the REPL:

>>> (2.0**22-1) - (2.0**22-2) 
1.0
>>> (2.0**22-0) - (2.0**22-1) 
1.0
>>> (2.0**22+1) - (2.0**22+0)    # no longer exact
0.0
>>> (2.0**22+2) - (2.0**22+1)  
2.0
>>> (2.0**22+3) - (2.0**22+2) 
0.0
>>> (2.0**22+4) - (2.0**22+3) 
2.0
>>>  #etc.

Note that 2^22 (4194304) msecs is only about 1.165 hours.

@jerryneedell 2^32 aka 4294967296.0f actually is represented exactly, because it's a power of two. The mantissa is exact. Gcc does the right thing, viz.:

#include <stdint.h>
#include <stdio.h>

int main() {
    union {
        uint32_t u;
        float f;
    } num;
    num.f = 4294967296.0f;
    
    printf("%f %x\n", num.f, num.u);
    return 0;
}

prints

4294967296.000000 4f800000

The 4f800000 is the exact representation of 2^32.

@tannewt asked in the pull request (#343) if I could distribute the division among the two halves. The precision is still lost due to single-precision floating point. So I don't believe it will make a difference:

>>> (2.0**22+1)/1000 - (2.0**22+0)/1000 
0.0
>>> (2.0**22+2)/1000 - (2.0**22+1)/1000 
0.00195313
>>> (2.0**22+3)/1000 - (2.0**22+2)/1000 
0.0
>>> (2.0**22+4)/1000 - (2.0**22+3)/1000 
0.00195313
>>> 

time.monotonic() is defined to never go backwards, but it's not guaranteed that it will increment uniformly. Here's the original PEP about it: https://www.python.org/dev/peps/pep-0418/#time-monotonic

[jerryneedell]

Dan,
Just to clarify my comment -
4294967296.000000 is exactly represented 0x4f800000
but it is not unique
4294967295.000000 also = 0x4f800000
and even
4294967200.000000 = 0x4f800000

I was concerned that it would add some discontinuity to time.monotonic.

[jerryneedell]

Okay - You have convinced me that since you really want the value to exactly 4294967296.000000 - you are OK and there will be no issues until the multiplicand gets very large and you get truncation but that is unavoidable. Thanks for the clarifications and all the work to save memory. Clever stuff!

[tannewt]

This sounds perfectly fine to me! If we start changing the millisecond fraction every other tick after an hour that seems plenty accurate to me.

…

On Tue, Oct 17, 2017 at 6:49 AM jerryneedell ***@***.***> wrote: Okay - You have convinced me that since your really want the value to exactly 4294967296.000000 - you are OK and there will be no issues until the multiplicand gets very large and you get truncation but that is unavoidable. Thanks for the clarifications and all the work to save memory. Clever stuff! — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#342 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AADNqU4OWCsfm-huTt5Z5rrfuaSq69G5ks5stLBWgaJpZM4P7irV> .

[dhalbert]

Implemented in PR #343.