[go] time: optimize time <-> date conversions

11 views

Skip to first unread message

Russ Cox (Gerrit)

unread,

Jul 31, 2024, 5:29:51 PM7/31/24

to Russ Cox, goph...@pubsubhelper.golang.org, golang-...@googlegroups.com, Go LUCI, Ian Lance Taylor, Alexander Yastrebov, golang-co...@googlegroups.com

Russ Cox submitted the change with unreviewed changes

Unreviewed changes

9 is the latest approved patch-set.
The change was submitted with unreviewed changes in the following files:

```
The name of the file: src/time/time.go
Insertions: 75, Deletions: 37.

@@ -463,7 +463,7 @@
 // Note that f* is usually the “easy” function to write: it's the
 // calendrical multiplication that inverts the more complex division.
 //
-// Neri and Schneider [1] prove that when f* takes the form
+// Neri and Schneider prove that when f* takes the form
 //
 //	f*(n) = (a n + b) / c
 //
@@ -538,14 +538,13 @@
 	// Days from March 1 through end of year
 	marchThruDecember = 31 + 30 + 31 + 30 + 31 + 31 + 30 + 31 + 30 + 31
 
-	// The number of years we shift internal time to get absolute time.
-	// Must be 0 mod 400, and dates before March 1, -absoluteYears will not
-	// compute correctly, but otherwise can be changed at will.
+	// absoluteYears is the number of years we subtract from internal time to get absolute time.
+	// This value must be 0 mod 400, and it defines the “absolute zero instant”
+	// mentioned in the “Computations on Times” comment above: March 1, -absoluteYears.
+	// Dates before the absolute epoch will not compute correctly,
+	// but otherwise the value can be changed as needed.
 	absoluteYears = 292277022400
 
-	// The number of days we shift internal time to get absolute time.
-	absoluteDays = absoluteYears/400*daysPer400Years + marchThruDecember
-
 	// The year of the zero Time.
 	// Assumed by the unixToInternal computation below.
 	internalYear = 1
@@ -563,18 +562,34 @@
 	wallToInternal int64 = (1884*365 + 1884/4 - 1884/100 + 1884/400) * secondsPerDay
 )
 
-type (
-	absSeconds uint64
-	absDays    uint64
-	absCentury uint64
-	absCyear   int
-	absYday    int
-	absMonth   int
-	absLeap    int
-	absJanFeb  int
-)
+// An absSeconds counts the number of seconds since the absolute zero instant.
+type absSeconds uint64
 
-// dateToAbsDays takes a standard year and returns the
+// An absDays counts the number of days since the absolute zero instant.
+type absDays uint64
+
+// An absCentury counts the number of centuries since the absolute zero instant.
+type absCentury uint64
+
+// An absCyear counts the number of years since the start of a century.
+type absCyear int
+
+// An absYday counts the number of days since the start of a year.
+// Note that absolute years start on March 1.
+type absYday int
+
+// An absMonth counts the number of months since the start of a year.
+// absMonth=0 denotes March.
+type absMonth int
+
+// An absLeap is a single bit (0 or 1) denoting whether a given year is a leap year.
+type absLeap int
+
+// An absJanFeb is a single bit (0 or 1) denoting whether a given day falls in January or February.
+// That is a special case because the absolute years start in March (unlike normal calendar years).
+type absJanFeb int
+
+// dateToAbsDays takes a standard year/month/day and returns the
 // number of days from the absolute epoch to that day.
 func dateToAbsDays(year int64, month Month, day int) absDays {
 	// See “Computations on Times” comment above.
@@ -586,17 +601,21 @@
 	amonth += 12 * janFeb
 	y := uint64(year) - uint64(janFeb) + absoluteYears
 
-	// For amonth is in the range [3,14],
+	// For amonth is in the range [3,14], we want:
 	//
 	//	ayday := (153*amonth - 457) / 5
 	//
-	// is equivalent to
+	// (See the “Computations on Times” comment above
+	// as well as Neri and Schneider, section 7.)
+	//
+	// That is equivalent to:
 	//
 	//	ayday := (979*amonth - 2919) >> 5
 	//
-	// and the latter uses a couple fewer instructions,
-	// so use that one, saving a few cycles.
-	// See Neri and Schneider, section 8.3.
+	// and the latter form uses a couple fewer instructions,
+	// so use it, saving a few cycles.
+	// See Neri and Schneider, section 8.3
+	// for more about this optimization.
 	//
 	// (Note that there is no saved division, because the compiler
 	// implements / 5 without division in all cases.)
@@ -616,7 +635,7 @@
 }
 
 // split splits days into century, cyear, ayday.
-func (days absDays) split() (century absCentury, cyear absCyear, yday absYday) {
+func (days absDays) split() (century absCentury, cyear absCyear, ayday absYday) {
 	// See “Computations on Times” comment above.
 	d := 4*uint64(days) + 3
 	century = absCentury(d / 146097)
@@ -631,26 +650,30 @@
 	// so do that instead.
 	cd := uint32(d%146097) | 3
 
-	// For cdays in the range [0,146097] (100 years),
+	// For cdays in the range [0,146097] (100 years), we want:
 	//
 	//	cyear := (4 cdays + 3) / 1461
 	//	yday := (4 cdays + 3) % 1461 / 4
 	//
-	// is equivalent to:
+	// (See the “Computations on Times” comment above
+	// as well as Neri and Schneider, section 7.)
+	//
+	// That is equivalent to:
 	//
 	//	cyear := (2939745 cdays) >> 32
 	//	yday := (2939745 cdays) & 0xFFFFFFFF / 2939745 / 4
 	//
 	// so do that instead, saving a few cycles.
-	// See Neri and Schneider, section 8.3.
+	// See Neri and Schneider, section 8.3
+	// for more about this optimization.
 	hi, lo := bits.Mul32(2939745, uint32(cd))
 	cyear = absCyear(hi)
-	yday = absYday(lo / 2939745 / 4)
+	ayday = absYday(lo / 2939745 / 4)
 	return
 }
 
-// split splits yday into absolute month and standard (1-based) day-in-month.
-func (yday absYday) split() (m absMonth, mday int) {
+// split splits ayday into absolute month and standard (1-based) day-in-month.
+func (ayday absYday) split() (m absMonth, mday int) {
 	// See “Computations on Times” comment above.
 	//
 	// For yday in the range [0,366],
@@ -665,15 +688,15 @@
 	//
 	// so do that instead, saving a few cycles.
 	// See Neri and Schneider, section 8.3.
-	d := 2141*uint32(yday) + 197913
-	return absMonth(d >> 16), 1 + int(d&0xFFFF/2141)
+	d := 2141*uint32(ayday) + 197913
+	return absMonth(d >> 16), 1 + int((d&0xFFFF)/2141)
 }
 
-// janFeb returns 1 if the March 1-based yday is in January or February, 0 otherwise.
-func (yday absYday) janFeb() absJanFeb {
+// janFeb returns 1 if the March 1-based ayday is in January or February, 0 otherwise.
+func (ayday absYday) janFeb() absJanFeb {
 	// See “Computations on Times” comment above.
 	jf := absJanFeb(0)
-	if yday >= marchThruDecember {
+	if ayday >= marchThruDecember {
 		jf = 1
 	}
 	return jf
@@ -725,7 +748,7 @@
 	return
 }
 
-// yearYday converts days into standard year, yday.
+// yearYday converts days into the standard year and 1-based yday.
 func (days absDays) yearYday() (year, yday int) {
 	century, cyear, ayday := days.split()
 	janFeb := ayday.janFeb()
@@ -894,7 +917,7 @@
 // Common durations. There is no definition for units of Day or larger
 // to avoid confusion across daylight savings time zone transitions.
 //
-// To count the number of units in a Duration, divide:
+// To count the number of units in a [Duration], divide:
 //
 //	second := time.Second
 //	fmt.Print(int64(second/time.Millisecond)) // prints 1000
@@ -1244,6 +1267,17 @@
 	if m >= March {
 		adj = -2
 	}
+
+	// With the -2 adjustment after February,
+	// we need to compute the running sum of:
+	//	0  31  30  31  30  31  30  31  31  30  31  30  31
+	// which is:
+	//	0  31  61  92 122 153 183 214 245 275 306 336 367
+	// This is almost exactly 367/12×(m-1) except for the
+	// occasonal off-by-one suggesting there may be an
+	// integer approximation of the form (a×m + b)/c.
+	// A brute force search over small a, b, c finds that
+	// (214×m - 211) / 7 computes the function perfectly.
 	return (214*int(m)-211)/7 + adj
 }
 
@@ -1254,6 +1288,10 @@
 		}
 		return 28
 	}
+	// With the special case of February eliminated, the pattern is
+	//	31 30 31 30 31 30 31 31 30 31 30 31
+	// Adding m&1 produces the basic alternation;
+	// adding (m>>3)&1 inverts the alternation starting in August.
 	return 30 + int((m+m>>3)&1)
 }
 
```
```
The name of the file: src/time/abs_test.go
Insertions: 10, Deletions: 0.

@@ -29,6 +29,7 @@
 	{"AbsDate", testAbsDate},
 	{"DateToAbsDays", testDateToAbsDays},
 	{"DaysIn", testDaysIn},
+	{"DaysBefore", testDaysBefore},
 }
 
 func testAbsDaysSplit(t testingT) {
@@ -171,3 +172,12 @@
 		}
 	}
 }
+
+func testDaysBefore(t testingT) {
+	for m, want := range []int{0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365} {
+		d := daysBefore(Month(m + 1))
+		if d != want {
+			t.Errorf("daysBefore(%d) = %d, want %d", m, d, want)
+		}
+	}
+}
```
```
The name of the file: src/time/time_test.go
Insertions: 8, Deletions: 8.

@@ -129,10 +129,10 @@
 		tm := Unix(sec, 0).UTC()
 		newsec := tm.Unix()
 		if newsec != sec {
-			t.Errorf("Unix(%d).Unix() = %d", sec, newsec)
+			t.Errorf("Unix(%d, 0).Unix() = %d", sec, newsec)
 		}
 		if !same(tm, golden) {
-			t.Errorf("Unix(%d):  // %#v", sec, tm)
+			t.Errorf("Unix(%d, 0):  // %#v", sec, tm)
 			t.Errorf("  want=%+v", *golden)
 			t.Errorf("  have=%v", tm.Format(RFC3339+" MST"))
 		}
@@ -146,10 +146,10 @@
 		tm := Unix(0, nsec).UTC()
 		newnsec := tm.Unix()*1e9 + int64(tm.Nanosecond())
 		if newnsec != nsec {
-			t.Errorf("NanosecondsToUTC(%d).Nanoseconds() = %d", nsec, newnsec)
+			t.Errorf("Unix(0, %d).Nanoseconds() = %d", nsec, newnsec)
 		}
 		if !same(tm, golden) {
-			t.Errorf("NanosecondsToUTC(%d):", nsec)
+			t.Errorf("Unix(0, %d):", nsec)
 			t.Errorf("  want=%+v", *golden)
 			t.Errorf("  have=%+v", tm.Format(RFC3339+" MST"))
 		}
@@ -163,10 +163,10 @@
 		tm := Unix(sec, 0)
 		newsec := tm.Unix()
 		if newsec != sec {
-			t.Errorf("SecondsToLocalTime(%d).Seconds() = %d", sec, newsec)
+			t.Errorf("Unix(%d, 0).Seconds() = %d", sec, newsec)
 		}
 		if !same(tm, golden) {
-			t.Errorf("SecondsToLocalTime(%d):", sec)
+			t.Errorf("Unix(%d, 0):", sec)
 			t.Errorf("  want=%+v", *golden)
 			t.Errorf("  have=%+v", tm.Format(RFC3339+" MST"))
 		}
@@ -180,10 +180,10 @@
 		tm := Unix(0, nsec)
 		newnsec := tm.Unix()*1e9 + int64(tm.Nanosecond())
 		if newnsec != nsec {
-			t.Errorf("NanosecondsToLocalTime(%d).Seconds() = %d", nsec, newnsec)
+			t.Errorf("Unix(0, %d).Seconds() = %d", nsec, newnsec)
 		}
 		if !same(tm, golden) {
-			t.Errorf("NanosecondsToLocalTime(%d):", nsec)
+			t.Errorf("Unix(0, %d):", nsec)
 			t.Errorf("  want=%+v", *golden)
 			t.Errorf("  have=%+v", tm.Format(RFC3339+" MST"))
 		}
```

Change information

Commit message:

time: optimize time <-> date conversions

Optimize the time -> date and date -> time conversions using the
methods outlined in:

    Cassio Neri and Lorenz Schneider,
    “Euclidean affine functions and their
    application to calendar algorithms,”
    SP&E 2023. https://doi.org/10.1002/spe.3172

I took the opportunity to introduce some types to make the code
significantly clearer and optimize a few other parts I noticed along
the way. The result is noticeably faster across the board.

Probably this doesn't matter much in real programs, but all the other
languages are picking this up, and it is less code than what we had
before.

Proposal #63844 suggested adopting this algorithm and simultaneously
restricting the range of valid years supported by the package from its
current ±292277022399 (plenty for anyone) to a mere ±32767.
This CL does NOT make any such restriction. The range of valid years
is almost exactly what it was before. (It is the same size but shifted
10 months earlier, which no one will ever care about.)

This CL removes any real need to consider the proposal, since it
would be a breaking change for truly insignificant benefit.

Thanks to Normandes Junior and Cassio Neri for CL 548155
and for discussion on #63844, which prompted me to write this CL.
This CL is all new code and does not include code from CL 548155
except as noted in the isLeap function implementation.

For #63844.

goos: linux
goarch: amd64
pkg: time
cpu: AMD Ryzen 9 7950X 16-Core Processor
                        │ timeold.txt  │             timenew.txt              │
                        │    sec/op    │   sec/op     vs base                 │
Format-32                  156.5n ± 1%   148.1n ± 1%   -5.37% (n=125)
FormatRFC3339-32           118.5n ± 1%   112.1n ± 1%   -5.40% (n=125)
FormatRFC3339Nano-32       119.2n ± 1%   113.0n ± 1%   -5.20% (n=125)
FormatNow-32               96.88n ± 2%   97.22n ± 1%        ~ (p=0.173 n=125)
MarshalJSON-32             79.77n ± 1%   75.82n ± 1%   -4.95% (n=125)
MarshalText-32             79.25n ± 1%   76.18n ± 1%   -3.87% (p=0.000 n=125)
Parse-32                   79.80n ± 1%   78.28n ± 1%   -1.90% (p=0.000 n=125)
ParseRFC3339UTC-32         29.10n ± 1%   28.90n ± 0%        ~ (p=0.094 n=125)
ParseRFC3339UTCBytes-32    30.72n ± 1%   30.88n ± 1%        ~ (p=0.894 n=125)
ParseRFC3339TZ-32          92.29n ± 0%   90.27n ± 1%   -2.19% (p=0.000 n=125)
ParseRFC3339TZBytes-32     133.4n ± 1%   132.0n ± 1%        ~ (p=0.004 n=125)
ParseDuration-32           41.11n ± 3%   44.08n ± 2%        ~ (p=0.088 n=125)
Hour-32                    2.834n ± 0%   2.829n ± 1%        ~ (p=0.891 n=125)
Second-32                  2.811n ± 1%   2.828n ± 1%        ~ (p=0.208 n=125)
Date-32                    9.228n ± 1%   5.788n ± 0%  -37.28% (n=125)
Year-32                    6.404n ± 1%   4.673n ± 1%  -27.03% (n=125)
YearDay-32                 6.399n ± 1%   5.802n ± 0%   -9.33% (n=125)
Month-32                   9.108n ± 1%   4.700n ± 1%  -48.40% (n=125)
Day-32                     9.106n ± 1%   4.686n ± 1%  -48.54% (n=125)
ISOWeek-32                10.060n ± 0%   7.998n ± 1%  -20.50% (n=125)
GoString-32                84.59n ± 1%   83.82n ± 1%        ~ (p=0.027 n=125)
DateFunc-32                6.993n ± 0%   6.144n ± 1%  -12.14% (n=125)
UnmarshalText-32           94.78n ± 2%   89.49n ± 1%   -5.58% (n=125)
geomean                    29.60n        26.13n       -11.70%

goos: darwin
goarch: arm64
pkg: time
cpu: Apple M3 Pro
                        │ timeold-m3.txt │            timenew-m3.txt            │
                        │     sec/op     │   sec/op     vs base                 │
Format-12                    152.6n ± 0%   147.4n ± 0%   -3.41% (n=125)
FormatRFC3339-12            101.50n ± 0%   92.02n ± 0%   -9.34% (n=125)
FormatRFC3339Nano-12        101.30n ± 0%   92.68n ± 0%   -8.51% (n=125)
FormatNow-12                 93.50n ± 0%   94.65n ± 0%   +1.23% (p=0.000 n=125)
MarshalJSON-12               50.06n ± 0%   48.25n ± 0%   -3.62% (n=125)
MarshalText-12               49.70n ± 0%   47.51n ± 0%   -4.41% (n=125)
Parse-12                     97.91n ± 0%   95.90n ± 0%   -2.05% (n=125)
ParseRFC3339UTC-12           36.45n ± 0%   35.78n ± 1%   -1.84% (n=125)
ParseRFC3339UTCBytes-12      38.11n ± 0%   37.42n ± 0%   -1.81% (n=125)
ParseRFC3339TZ-12           100.80n ± 1%   97.58n ± 0%   -3.19% (n=125)
ParseRFC3339TZBytes-12       111.8n ± 1%   107.4n ± 0%   -3.94% (n=125)
ParseDuration-12             52.70n ± 0%   52.84n ± 0%        ~ (p=0.028 n=125)
Hour-12                      2.657n ± 0%   2.655n ± 0%        ~ (p=0.018 n=125)
Second-12                    2.656n ± 0%   2.654n ± 0%        ~ (p=0.084 n=125)
Date-12                      8.201n ± 0%   5.055n ± 0%  -38.36% (n=125)
Year-12                      5.694n ± 0%   4.086n ± 0%  -28.24% (n=125)
YearDay-12                   5.693n ± 0%   4.828n ± 0%  -15.19% (n=125)
Month-12                     8.206n ± 0%   4.231n ± 0%  -48.44% (n=125)
Day-12                       8.199n ± 0%   4.551n ± 0%  -44.49% (n=125)
ISOWeek-12                   9.032n ± 0%   7.298n ± 0%  -19.20% (n=125)
GoString-12                  62.78n ± 0%   60.61n ± 0%   -3.46% (n=125)
DateFunc-12                  7.318n ± 0%   6.431n ± 0%  -12.12% (n=125)
UnmarshalText-12             99.66n ± 0%   95.64n ± 0%   -4.03% (n=125)