[PATCH 0/1] offset: optimized calculation of year from unix timestamp
gary@garygende.com
gary@garygende.com
Thu Aug 7 09:13:41 GMT 2025
offset: optimized calculation of year from unix timestamp
Summary:
Proposed update to the algorithm to calculate the year in __offset
function
in time/offset.c. This algorithm is completely of my own creation and
was
inspired by an attempt to optimize a similar challenge in a class.
The proposed algorithm performs better in almost all tested cases. I've
done my best to follow the guide for submitting a patch, but please let
me
know if anything else is needed.
Performance and regression test results are below.
PERFORMANCE TESTS:
Performance tests were run as follows:
- All tests run in WSL on Windows 10, except when noted
- All times are the median time of five runs
- All tests run the entire __offset function, NOT just the year calc
-- minor changes were made to the __offset function to allow execution
in
relative isolation from the rest of the glibc library
- All tests were run in a loop either 150M or 50M times (noted below)
- 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;
smaller
arrays favor the proposed algorithm (branches are more
predictable?)
-- Random number was either "rand()" or "(rand() - rand()) * rand()",
noted
as "(r-r)*r" in the table; special case random values are described
below
- 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 proposed algorithm
-- Tests on 9800X3D, 32GB RAM, 150M loops per test --
Array Size Value Optimize Current(s) Proposed(s) Relative
Time
100 rand() 0 2.883820 2.080411 72.1%
100 rand() 3 1.769464 1.231158 69.6%
100 (r-r)*r 0 2.943186 2.061422 70.0%
100 (r-r)*r 3 1.744450 1.206275 69.1%
10000 rand() 0 3.235184 2.981079 92.1%
10000 rand() 3 2.007818 1.942647 96.8%
10000 (r-r)*r 0 3.780366 3.322390 87.9%
10000 (r-r)*r 3 2.443487 2.064534 84.5%
1000000 rand() 0 3.943282 3.787320 96.0%
1000000 rand() 3 2.901754 3.118926 107.5%
1000000 (r-r)*r 0 4.589405 4.147633 90.4%
1000000 (r-r)*r 3 3.356032 3.362730 100.2%
Special Case Tests
- "neg" = "rand() * -1" // Tests negative values specifically
- "massive" = "9000000000000000001 + rand()" // Test near size limit
- "big (2600s)" = "20000000000 + rand()" // 20000000000 = 10/11/2603
-- Chosen to show when proposed algorithm's advantage at larger
numbers
is creating significant separation
- "big (2100s)" = "5000000000 + rand()" // 5000000000 = 6/11/2128
-- Chosen because it is roughly the "break even" point on the 9800X3D
tests;
on other tested CPUs, proposed algorithm is always faster (expect
1970)
- "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 (does not occur in
1971)
Array Size Value Optimize Current(s) Proposed(s) Relative
Time
1000000 neg 3 2.959450 2.645889 89.4%
1000000 massive 3 5.577484 2.990748 53.6%
1000000 big (2600s) 3 3.586870 2.996320 83.5%
1000000 big (2100s) 3 3.012133 3.007142 99.8%
1000000 1970 3 1.612619 2.440661 151.3%
-- Tests on i3-2120T, 8GB RAM, 50M loops per test --
NOTE: Reported times only had 1/64 sec precision. Tests are still
accurate,
just very low precision. Overall result on this CPU is clear
regardless.
Array Size Value Optimize Current(s) Proposed(s) Relative
Time
100 rand() 0 5.21875 4.3125 83%
100 rand() 3 2.25 1.671875 74%
100 (r-r)*r 0 5.28125 4.265625 81%
100 (r-r)*r 3 2.25 1.609375 72%
10000 rand() 0 5.953125 5.359375 90%
10000 rand() 3 2.8125 2.640625 94%
10000 (r-r)*r 0 6.34375 5.515625 87%
10000 (r-r)*r 3 3.109375 2.65625 85%
1000000 rand() 0 5.96875 5.25 88%
1000000 rand() 3 2.828125 2.390625 85%
1000000 (r-r)*r 0 6.34375 5.546875 87%
1000000 (r-r)*r 3 3.140625 2.71875 87%
Special Case Tests
Array Size Value Optimize Current(s) Proposed(s) Relative
Time
1000000 neg 3 2.875 2.390625 83%
1000000 massive 3 6.140625 2.546875 41%
1000000 big (2600s) 3 3.421875 2.546875 74%
1000000 big (2100s) 3 2.921875 2.546875 87%
1000000 1970 3 1.671875 2.21875 133%
-- Tests on LCD Steam Deck APU, 150M loops per test --
NOTE: These tests were run on SteamOS
Array Size Value Optimize Current(s) Proposed(s) Relative
Time
100 (r-r)*r 3 3.959199 2.822849 71.3%
10000 (r-r)*r 3 6.097982 5.910726 96.9%
1000000 (r-r)*r 3 6.076666 5.836087 96.0%
REGRESSION TESTS:
The following tests failed with BOTH the current algorithm and the
proposed
algorithm. It's unclear why they failed, but it seems likely to be
related
to running in Windows Subsystem for Linux.
FAIL: elf/check-abi-libc
FAIL: elf/tst-audit28
FAIL: elf/tst-noload
FAIL: elf/tst-thrlock
FAIL: io/ftwtest
FAIL: io/ftwtest-time64
FAIL: math/test-misc
FAIL: misc/tst-syslog
FAIL: nptl/tst-mutex10
FAIL: nptl/tst-stack4
FAIL: nptl/tst-umask1
FAIL: nss/tst-nss-files-hosts-long
FAIL: posix/globtest
FAIL: posix/tst-chmod
FAIL: posix/tst-execl2
FAIL: posix/tst-execle2
FAIL: posix/tst-execlp2
FAIL: posix/tst-execv2
FAIL: posix/tst-execve2
FAIL: posix/tst-execvp2
FAIL: posix/tst-execvpe2
FAIL: stdio-common/tst-freopen64-7
FAIL: stdio-common/tst-freopen7
FAIL: stdio-common/tst-setvbuf2
FAIL: stdlib/tst-system
The following test failed on the current algorithm and passed on the new
algorithm. I see no reason why that would be the case, but that was the
result I received.
Current: FAIL: stdio-common/tst-fseek
Proposed: PASS: stdio-common/tst-fseek
Developer Certificate of Origin
Version 1.1
Copyright (C) 2004, 2006 The Linux Foundation and its contributors.
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):
offset: optimized calculation of year from unix timestamp
time/offtime.c | 40 +++++++++++++++++++++++++++-------------
1 file changed, 27 insertions(+), 13 deletions(-)
--
2.43.0
More information about the Libc-alpha
mailing list