proposal: time: optimize algorithms by restricting valid year range

[normandesjr]

TL;DR:

The proposal is to improve the performance of Go's time package using the recent algorithms developed by Neri and Schneider [1]. Their algorithms are faster than alternatives and they have been adopted by libstdc++ (the GNU implementation of the C++ Standard Library) [2], the Linux Kernel [3], .NET [4] and Firefox [5]. My benchmarks confirm performance improvements in Go as well. (See below.)

To achieve better performance we should change the supported range of dates: instead of supporting years taking any int value, they should be restricted to a much smaller range which still spans tens of thousands of years.

Check the benchmark results that I obtained after implementing Neri-Schneider algorithms in Go source code.

Implementation:

Cassio Neri and I have implemented in Go source code the 32-bits versions of Neri-Schneider algorithms. They support dates from -1,468,000/Mar/01 to 1,471,745/Feb/28. Unfortunately, the current documentation of

`func Date(year int, month Month, day, hour, min, sec, nsec int, loc *Location) Time`

doesn't explicitly state the range of supported dates but, since the argument year has type int, one might expect that any year from math.MinInt to math.MaxInt is allowed. This is further confirmed by the test TestZoneBounds which uses math.MinInt32 as a minimum year. Only this test fails when I replace the current implementations with Neri-Schneider algorithms.

The main goal of this issue is to argue that the range supported by Neri-Schneider algorithms is more than enough for all practical applications (*). We also believe that the specification of the time package should explicitly state the range of supported dates. Moreover, this range should be smaller than the one supported by Neri-Schneider algorithms just in case faster but more restrictive algorithms are found in the future. Consider, for instance, the range specified by other popular programming languages:

C++ [6]:
from 1970/Jan/01 - 12,687,428 days to 1970/Jan/01 + 11,248,737 days, that is,
from -32,767/Jan/01 to 32,767/Dec/31.

C# [7]: from 0001/January/01 to 9999/Dec/31.

Ecma Script (a.k.a. JavaScript) [8]:
from 1970/Jan/01 - 100,000,000 days to 1970/Jan/01 + 100,000,000 days, that is,
from -271,821/Apr/20 to 275,760/Sep/13

We believe that any of those ranges are more than enough for the large majority of users and, concretely, suggest to set Go to use the same range as C++. (As mentioned above, the 32-bits implementations support a much larger range.) If you agree that it is fine, then I could submit the PR showing how it was implemented.

Follow the time's package benchmark. As you can see other functions got the benefits as well.

(*) It's worth mentioning that the Gregorian calendar is still not perfectly aligned to Earth's motions and a small error is accumulating. In a few thousands of years the error should be quite noticeable. Furthermore, Earth's rotation is slowing down which amplifies the problem [9]. The point here is that it's virtually impossible for the Gregorian calendar to remain in use in the next few thousands of years, let alone in billions of years.

References:

[1] Neri, C, Schneider, L. Euclidean affine functions and their application to calendar algorithms. Softw Pract Exper. 2023; 53(4): 937–970. doi:10.1002/spe.3172
https://onlinelibrary.wiley.com/doi/full/10.1002/spe.3172

See also Cassio Neri's presentation on calendar algorithms at C++Now 2023.
https://www.youtube.com/watch?v=0s9F4QWAl-E

[2] https://gcc.gnu.org/git/?p=gcc.git;a=blob;f=libstdc%2B%2B-v3/include/std/chrono;h=10e868e5a036924177cf952a81f4bce10c497106;hb=HEAD#l1673

[3] https://github.com/torvalds/linux/blob/master/kernel/time/timeconv.c#L78 and https://github.com/torvalds/linux/blob/master/drivers/rtc/lib.c#L68

[4] https://github.com/dotnet/runtime/blob/main/src/libraries/System.Private.CoreLib/src/System/DateTime.cs#L1377

[5] https://searchfox.org/mozilla-central/source/js/src/jsdate.cpp#217

[6] https://eel.is/c++draft/time.cal.ymd#members-20

[7] https://learn.microsoft.com/en-us/dotnet/api/system.datetime.minvalue?view=net-7.0#remarks and https://learn.microsoft.com/en-us/dotnet/api/system.datetime.maxvalue?view=net-7.0#remarks

[8] https://262.ecma-international.org/14.0/#sec-time-values-and-time-range

[9] Duncan S. Marking Time: The Epic Quest to Invent the Perfect Calendar. 1st ed. John Wiley & Sons; 2000.

[mauri870]

kindly CC @rsc (per https://dev.golang.org/owners)

[AlexanderYastrebov]

We also believe that the specification of the time package should explicitly state the range of supported dates.

It should be possible to split codepath into slow and fast versions depending on the year value without defining any new constraints on the year value, shouldn't it?

[normandesjr]

We also believe that the specification of the time package should explicitly state the range of supported dates.

It should be possible to split codepath into slow and fast versions depending on the year value without defining any new constraints on the yer value, shouldn't it?

Thanks @AlexanderYastrebov . It's possible, but I'm not sure if it's suitable. I've changed some functions, like absDate, daysSinceEpoch and Date, and we would add some complexity (and another branch) for a range of date that is unusal and that other languages already don't support. IMHO we should even add some asserts and panic if the year is outside the "new" specification. Make sense?