time.perf_counter(): compute Greatest Common Denonimator (GCD) to reduce risk of integer overflow

[vstinner]

The time.perf_counter() function is implemented by calling QueryPerformanceCounter() and QueryPerformanceFrequency(). It computes QueryPerformanceCounter() * SEC_TO_SEC / QueryPerformanceFrequency() using int64_t integers. The problem is that SEC_TO_SEC is big: 10^9.

QueryPerformanceFrequency() usually returns 10 MHz on Windows 10 and newer. The fraction SEC_TO_NS / frequency = 1_000_000_000 / 10_000_000 can be simplified to 100 / 1.

I propose using a fraction internally to convert QueryPerformanceCounter() value to a number of seconds, and simplify the fraction using the Greatest Common Denominator (GCD).

There are multiple functions using a fraction:

• _PyTime_GetClockWithInfo() for clock() -- time.process_time() in Python
• _PyTime_GetProcessTimeWithInfo() for times() -- time.process_time() in Python
• py_get_monotonic_clock() for mach_absolute_time() on macOS -- time.monotonic() in Python
• py_get_win_perf_counter() for QueryPerformanceCounter() on Windows -- time.perf_counter() in Python

Linked PRs

• gh-112567: Add _PyTimeFraction C API #112568
• gh-112567: Add _Py_GetTicksPerSecond() function #112587

[serhiy-storchaka]

QueryPerformanceCounter() * SEC_TO_SEC / QueryPerformanceFrequency() can be calculated as

QueryPerformanceCounter() * (SEC_TO_SEC / QueryPerformanceFrequency()) +
QueryPerformanceCounter() * (SEC_TO_SEC % QueryPerformanceFrequency()) / QueryPerformanceFrequency()

or

SEC_TO_SEC * (QueryPerformanceCounter() / QueryPerformanceFrequency()) +
SEC_TO_SEC * (QueryPerformanceCounter() % QueryPerformanceFrequency()) / QueryPerformanceFrequency()

or

QueryPerformanceCounter() * (SEC_TO_SEC / QueryPerformanceFrequency()) +
(SEC_TO_SEC % QueryPerformanceFrequency()) * (QueryPerformanceCounter() / QueryPerformanceFrequency()) +
(SEC_TO_SEC % QueryPerformanceFrequency()) * (QueryPerformanceCounter() % QueryPerformanceFrequency()) / QueryPerformanceFrequency()

or

SEC_TO_SEC * (QueryPerformanceCounter() / QueryPerformanceFrequency()) +
(QueryPerformanceCounter() % QueryPerformanceFrequency()) * (SEC_TO_SEC / QueryPerformanceFrequency()) +
(QueryPerformanceCounter() % QueryPerformanceFrequency()) * (SEC_TO_SEC % QueryPerformanceFrequency()) / QueryPerformanceFrequency()

[vstinner]

QueryPerformanceCounter() * SEC_TO_SEC / QueryPerformanceFrequency() can be calculated as (...)

_PyTimeFraction_Mul(ticks, frac) is not a naive ticks * frac.numer / frac.denom operation, but already uses modulo to reduce the risk of integer overflow. I wrote an article on that :-) https://vstinner.github.io/python37-perf-counter-nanoseconds.html

But still, we can reduce the risk of integer overflow even further since in most cases, the numerator can be made way smaller in most cases. With QueryPerformanceFrequency(), the numerator is reduced from 10^9 to 100, since the common frequency is 10 MHz.

Since the frequency is only read once, IMO it's worth it to quickly compute a GCD.

[serhiy-storchaka]

And what if it is not reduced on some weird configuration?

[vstinner]

And what if it is not reduced on some weird configuration?

I only propose to make the current situation on known configuration better. If some platforms require very large numerator and denominator, later, we can consider to switch to int128_t for intermediate results in _PyTimeFraction_Mul(). For now, I don't think that it's needed.

By the way, _PyTime_Mul() clamps the result to [_PyTime_MIN; _PyTime_MAX] range on overflow.

[vstinner]

I merged my changes. @serhiy-storchaka: If you see room for improvement to reduce even more the risk of integer overflow in _PyTimeFraction_Mul(), go ahead ;-)