precise_time_ns can overflow on Windows

[rusty-nail2]

The last line of precise_time_ns uses a 64 bit multiplication that will overflow frequently.

Using floats would be the easy way out, but it would reduce precision to 53 bits.

[Gankra]

As a datapoint, this is literally what microsoft itself recommends doing.

LARGE_INTEGER StartingTime, EndingTime, ElapsedMicroseconds;
LARGE_INTEGER Frequency;

QueryPerformanceFrequency(&Frequency); 
QueryPerformanceCounter(&StartingTime);

// Activity to be timed

QueryPerformanceCounter(&EndingTime);
ElapsedMicroseconds.QuadPart = EndingTime.QuadPart - StartingTime.QuadPart;


//
// We now have the elapsed number of ticks, along with the
// number of ticks-per-second. We use these values
// to convert to the number of elapsed microseconds.
// To guard against loss-of-precision, we convert
// to microseconds *before* dividing by ticks-per-second.
//

ElapsedMicroseconds.QuadPart *= 1000000;
ElapsedMicroseconds.QuadPart /= Frequency.QuadPart;

Where LARGE_INTEGER is a u64.

But we're multiplying by an extra 1000.

[rusty-nail2]

In fairness to Microsoft, they're operating on a time difference computed mod 2^64, so as long as the interval length is reasonable (less than a few thousand hours for a typical tick rate) it can't overflow.

But precise_time_ns computes an absolute time rather than a difference, so overflows are guaranteed to happen at some point. The 1000x factor only makes it more noticeable.

[Gankra]

Since we're dealing with absolute time (and therefore something large), it's probably not unreasonable to divide first, or maybe even partially multiply by 1000000000. Something like:

ticks * 1000 / ticks_per_s * 1000000

maybe? What are "typical" and "extreme" tick rates and absolute ticks like? An incredibly robust implementation could presumably branch on the size of ticks to determine the optimal split of the 1000000000.

[nodakai]

The x86_64 architecture has the 64 bit MUL instruction whose result is effectively a 128 bit integer which never overflows. Likewise, the DIV instruction takes an effectively 128 bit integer as the dividened.

• http://is.gd/UQQAqu

asm!("mulq $2; divq $3" : "={rax}"(d) : "{rax}"(a), "{rdi}"(b), "{rsi}"(c) : "%rdx" );

i386 offers (u32, u32) -> u64 MUL and (u64, u32) -> (u32, u32) DIV/MOD, so we should be able to implement 64 bit MUL and DIV without overflow.

Windows RT runs on ARMv7 (=~ Cortex-A). It has (u32, u32) -> u64 UMULL but lacks DIV and we have to call a division routine. Perhaps we can forget about it for now...

[vadimcn]

We could use techniques similar to division by a constant via multiplication and shifts.
Of course, in this case, we also have the 1000000000 multiplier, which together with the "magic constant" is going to overflow even a 128 bit register, but multiplication can be done "in parts".

[vadimcn]

Don't OSX and iOS have a similar problem here and here?
What is the typical value of info.numer? This seems to suggest that is can be large, just like on Windows.

[vadimcn]

@pcwalton ^