[PATCH v3 0/1] offtime: optimized calculation of year from unix

Mon Sep 1 10:01:21 GMT 2025

Updatting this patch to account for feedback and incorporate new refinements.

CHANGES:

* Now calculates the year starting at the first 400-year leap year cycle
  that is below the minimum year allowed in tm->tm_year (-2147483999).  This
  allows assuming that all year calculations will be positive (i.e. adding
  years rather than subtracting).  This enabled streamlining and improved
  performance.
* Checks if MIN is defined and, if not, defines it rather than defining an
  entirely new MACRO
* Added additional comments to explain the MACROs and other unintuitive code
  (e.g. why start at year -2147483999)
* Fix spelling and styling issues
* Update the patch subject line so it refers to the correct file (:whoops:!)

REGRESSION TESTS:

* Passes all make check tests other than elf/tst-shstk-legacy-1g,
  which seems to be a kernel/hardware issue.
  (ref: https://sourceware.org/bugzilla/show_bug.cgi?id=31877)

UPDATED PERFORMANCE BENCHMARKS:

* All times are the median time of five runs
* All tests run the entire __offset function, not just the year calculation
 ** minor changes were made to the __offset function to allow execution in
    relative isolation from the rest of the glibc library
* All test runs were given a random number number from an array
  of random numbers generated before each test
 ** Array size was 100, 10000, or 1000000, as noted in the table
 ** Random number was either "rand()" or "(rand() - rand()) * rand()"
  *** Updated "(rand() - rand()) * rand()" benchmark to correctly produce
      64-bit inputs that do not go outside struct tm's max/min values
* Tests were compiled with either -O0 or -O3 optimization flag, as noted
* "Current" is execution time, in seconds, for current algorithm
* "Proposed" is execution time, in seconds, for (new) proposed algorithm

 -- Tests on 9800X3D, 32GB RAM, Linux Mint 22.1, 150M loops per test --

Array Size	Value	Optimize	Current(s)	Proposed(s)	Relative Time
100	        rand()	    0		3.673038	2.259116	61.5%
100	        rand()  	3		1.954789	1.350536	69.1%
100	        (r-r)*r 	0		7.123674	2.270692	31.9%
100	        (r-r)*r	    3		3.961592	1.374237	34.7%
10000	    rand()	    0		3.896807	2.588002	66.4%
10000   	rand()	    3		2.112533	1.372340	65.0%
10000   	(r-r)*r	    0		8.391101	3.171792	37.8%
10000   	(r-r)*r	    3		4.948121	1.749075	35.3%
1000000	    rand()	    0		4.749969	3.463198	72.9%
1000000	    rand()	    3		3.151351	3.055907	97.0%
1000000	    (r-r)*r	    0		8.995366	4.123248	45.8%
1000000	    (r-r)*r	    3		5.595650	3.585664	64.1%

Special Case Tests:
 - "neg" = "rand() * -1" // Tests negative values specifically
 - "massive" - removed because corrected (r-r)*r test spends significant time
   time testing massive numbers, making this special case unecessary
 - "big (2600s)" = "20000000000 + rand()" // 20000000000 = 10/11/2603
 - "big (2100s)" = "5000000000 + rand()" // 5000000000 = 6/11/2128
 - "1970" = "rand() % (365 * SECS_PER_DAY)"
  -- Chosen to show current algorithm's advantage in the year 1970, where it is
     able to bypass the year calculation completely

Array Size	Value	Optimize	Current(s)	Proposed(s)	Relative Time
1000000	    neg	        3		3.122325	3.074963	98.5%
1000000	    massive	    *redundant with corrected (r-r)*r benchmarks*
1000000	    big (2600s)	3		3.830318	3.025371	79.0%
1000000	    big (2100s)	3		3.227695	3.023615	93.7%
1000000	    1970	    3		1.968458	2.891870	146.9%

 -- Tests on i3-2120T, 8GB RAM, WSL2 on Windows 10, 50M loops per test --

NOTE: Reported times only had 1/64 sec precision. Tests are still accurate,
      just very low precision.

Array Size	Value	Optimize	Current(s)	Proposed(s)	Relative Time
100	        rand()	    0		5.5625  	4.625	    83%
100	        rand()	    3		2.5625	    1.8125	    71%
100	        (r-r)*r	    0		10.765625	4.640625	43%
100	        (r-r)*r	    3		4.84375	    1.796875	37%
10000	    rand()	    0		6.4375	    5.390625	84%
10000   	rand()	    3		3.125	    2.546875	82%
10000   	(r-r)*r	    0		11.953125	5.71875	    48%
10000   	(r-r)*r	    3		5.640625	2.8125	    50%
1000000	    rand()	    0		6.46875	    5.421875	84%
1000000	    rand()	    3		3.15625	    2.5625	    81%
1000000	    (r-r)*r	    0		12.0        5.765625	48%
1000000	    (r-r)*r	    3		5.671875	2.859375	50%

Array Size	Value	Optimize	Current(s)	Proposed(s)	Relative Time
1000000	    neg	        3		3.15625	    2.625	    83%
1000000	    massive	    *redundant with corrected (r-r)*r benchmarks*
1000000	    big (2600s)	3		3.796875	2.625	    69%
1000000	    big (2100s)	3		3.296875	2.59375	    79%
1000000	    1970	    3		1.90625	    2.4375	    128%

 -- Tests on 9800X3D, 32GB RAM, WSL2 in Windows 10, 150M loops per test --

Array Size	Value	Optimize	Current(s)	Proposed(s)	Relative Time
100	        rand()	    3		1.991614	1.366046	68.6%
10000	    rand()	    3		2.103214	1.537606	73.1%
1000000	    rand()	    3		3.128251	3.088647	98.7%

RESPONSE TO OTHER COMMENTS:

* In response to:
> Also, why not use sys/param.h's MIN instead of reinventing the wheel?

My thought on this was to avoid producing additional dependency chains where it's not necessary.  I've changed it to check if MIN is already defined, and to define it if it's not.  This solution avoids dependencies without defining a new unnecessary MACRO.

* In response to:
> +  y += MIN_YEAR_GROUP_NUM(days / DIVISOR_100, 3) * 100;
> +  days -= MIN_YEAR_GROUP_NUM(days / DIVISOR_100, 3) * DIVISOR_100;
>
> This looks like it calculates the wrong number if days / DIVISOR_100 == -4. Similarly for the other use of MIN_YEAR_GROUP_NUM.

AND

> Why not start at 1 instead of at 1601?

Short Version:
Correcting for "days / DIVISOR_100 == -4" produces inaccurate results.  1601 was mostly arbitrary, and, as noted above, I've now found a good non-arbitrary reason to make it something else.

Long Version:
These seemingly innocent comments started me down a deep rabbit hole.  When creating v1 of this patch submission, I originally tried to account for situations where (days / DIVISOR_100) == -4, but doing so would produce inaccurate results. I didn't fully understand why, but my tests (including a test that compares several hundred million random inputs to the results of the current __offtime function) all consistently indicated that "correcting" these cases was actually incorrect.  However, the comments above made me consider two things: 1) I should probably actually figure out why, and 2) since it seemed that there was a performance benefit with my algorithm when processing negative inputs, maybe I should set the starting year to something exceptionally high so all inputs would effectively be negative (note: I've since settled on the opposite of that).

I wasn't able to find any promising leads for #1, so I started with #2.  It turned out that setting the starting year to anything more than 1970 (even 2001), created significant issues.  This didn't make sense at first because setting the starting year to 1601 and inputting large negative numbers (i.e. years before 1601) worked fine, but when the starting year was after 1970, suddenly negative numbers could be a problem.  I tried manually adjusting the results in different ways to see if I could fix it at all, with the intent to develop a more general solution later.  It became clear very quickly that "subtracting years" involved different adjustments than "adding years".  I also eventually realized that some modifications needed to be made on leap years while other did not.  Most of these modifications could be done after all of the leap year blocks (i.e. 400 year, 100 year, 4 year, and 1 year division) were processed, but some could not.  If an error that only happens during a leap year makes 31 Dec look like 1 Jan, there was no way to know if a 1 Jan result needed to be adjusted or not.  Unfortunately, it was also impossible to make the checks while processing the leap year blocks because there was no way to know if the result was going to be a leap year before the year was calculated.

I was eventually able to resolve the above issues by having the 400 year calculation always subtract an extra 400 years.  I realized that was effectively making it so that all further calculations were guaranteed to be "positive" (i.e. adding years instead of subtracting them).  I then realized that, in v1 and v2 of this patch, allowing (days / DIVISOR_100) to equal -4 was necessary because it effectively did the same thing.  Accurately calculating the year with subtraction couldn't be done due to the need to know ahead of time if the year was going to result in a leap year. The fix was to overshoot the result so the rest could be done with addition.  After realizing that was the case, I changed the starting year to be just below the minimum possible value for a struct tm (as defined in the C standard, with tm->tm_year being represented by a regular signed int).  As a result, I could remove checks for cases where the days could be negative.  That was no longer a possibility.  I confirmed that removing the checks did not cause any inaccuracies with the previously mentioned random tests (that compare my algorithms result to the result of the current algorithm), some custom tests to check inputs that had caused problems during development and debugging, and with passing results from make check.

Developer Certificate of Origin
Version 1.1

Everyone is permitted to copy and distribute verbatim copies of this
license document, but changing it is not allowed.

Developer's Certificate of Origin 1.1

By making a contribution to this project, I certify that:

(a) The contribution was created in whole or in part by me and I
    have the right to submit it under the open source license
    indicated in the file; or

(b) The contribution is based upon previous work that, to the best
    of my knowledge, is covered under an appropriate open source
    license and I have the right under that license to submit that
    work with modifications, whether created in whole or in part
    by me, under the same open source license (unless I am
    permitted to submit under a different license), as indicated
    in the file; or

(c) The contribution was provided directly to me by some other
    person who certified (a), (b) or (c) and I have not modified
    it.

(d) I understand and agree that this project and the contribution
    are public and that a record of the contribution (including all
    personal information I submit with it, including my sign-off) is
    maintained indefinitely and may be redistributed consistent with
    this project or the open source license(s) involved.

Signed-off-by: Gary Gende <gary@garygende.com>

Gary Gende (1):
  offtime: optimized calculation of year from unix timestamp

 time/offtime.c | 48 ++++++++++++++++++++++++++++++++++--------------
 1 file changed, 34 insertions(+), 14 deletions(-)

-- 
2.43.0