kernel/time: Improve performance of time64_to_tm. Add tests.
PATCH v2 1/1 kernel/time: Improve performance of time64_to_tm. Add tests.
From: Cassio Neri <[email protected]>
The current implementation of time64_to_tm contains unnecessary loops, branches and look-up tables. The new one uses an arithmetic-based algorithm appeared in [1] and is ~3.2 times faster (YMMV).
The drawback is that the new code isn't intuitive and contains many 'magic numbers' (not unusual for this type of algorithm). However, [1] justifies all those numbers and, given this function's history, I reckon the code is unlikely to need much maintenance, if any at all.
Added file kernel/time/time_test.c containing a KUnit test case that checks every day in a 160,000 years interval centered at 1970-01-01 against the expected result. A new config TIME_KUNIT_TEST symbol was introduced to give the option to run this test suite.
[1] Neri, Schneider, "Euclidean Affine Functions and Applications to Calendar Algorithms". https://arxiv.org/abs/2102.06959
---
* Disclaimer: I'm an author of [1] and, surely, I have an interest in seeing my algorithm made into the kernel. If not by this patch, I'm willing to work closely with maintainers, if they wish, in order to write an appropriate implementation.
* Test evidence: This runs the same test implemented in kernel/time/time_test.c (see above). It's possible to run it on 32 and 64 bits.
https://godbolt.org/z/1rn1aqfqY
* Benchmarks: It measures the time taken by each implementation to process 65,536 numbers (time64_t). These numbers are pseudo-random under the uniform distribution on the interval corresponding to dates spanning 800 years centered at 1970-01-01:
https://quick-bench.com/q/COPMeRk9e00Sua85KFrKKL9YoSc
(Apologies that the benchmark is in C++ but results in C should be close.)
* Disasembly: Shows, in particular, reduction in code size:
https://godbolt.org/z/e87rhha5b
* History
v2 Address reviewer comments.
v1 Original implementation.
--- kernel/time/Kconfig | 9 +++ kernel/time/Makefile | 1 + kernel/time/time_test.c | 98 ++++++++++++++++++++++++++++++ kernel/time/timeconv.c | 130 ++++++++++++++++++++++------------------ 4 files changed, 180 insertions(+), 58 deletions(-) create mode 100644 kernel/time/time_test.c
kernel/time/Kconfig +9 -0
@@ -64,6 +64,15 @@ config LEGACY_TIMER_TICK lack support for the generic clockevent framework. New platforms should use generic clockevents instead. +config TIME_KUNIT_TEST + tristate "KUnit test for kernel/time functions" if !KUNIT_ALL_TESTS + depends on KUNIT + default KUNIT_ALL_TESTS + help + Enable this option to test RTC library functions. + + If unsure, say N. + if GENERIC_CLOCKEVENTS menu "Timers subsystem"
kernel/time/Makefile +1 -0
@@ -21,3 +21,4 @@ obj-$(CONFIG_HAVE_GENERIC_VDSO) += vsyscall.o obj-$(CONFIG_DEBUG_FS) += timekeeping_debug.o obj-$(CONFIG_TEST_UDELAY) += test_udelay.o obj-$(CONFIG_TIME_NS) += namespace.o +obj-$(CONFIG_TIME_KUNIT_TEST) += time_test.o
kernel/time/time_test.c new file +98 -0
98 lines not on this page · raw message
kernel/time/timeconv.c +72 -58
156 lines not on this page · raw message
base-commit: 245a057fee18be08d6ac12357463579d06bea077
Signature · 1 line
2.31.0
Quoted 3 lines · Cassio Neri
The current implementation of
time64_to_tmcontains unnecessary loops, branches and look-up tables. The new one uses an arithmetic-based algorithm appeared in [1] and is ~3.2 times faster (YMMV).
trivia:
kernel/time/timeconv.c
Quoted 1 line
kernel/time/timeconv.c +0
-0
[]
kernel/time/timeconv.c static const unsigned short __mon_yday[2][13] = { · line 53
Quoted 10 lines
void
time64_to_tm(time64_t totalsecs, int offset, struct tm *result){kernel/time/timeconv.c +1
-1-long days, rem, y; +long days, rem;int remainder;
kernel/time/timeconv.c +4
-1-const unsigned short *ip; + +u64 u64tmp, udays, century, year; +u32 u32tmp, day_of_century, year_of_century, day_of_year, month, + day, janOrFeb, is_leap;
janOrFeb is an odd name choice and it and is_leap could be bool which _might_ improve performance in some memory access cases.
kernel/time/timeconv.c void time64_to_tm(time64_t totalsecs, int offset, struct tm *result) · line 114
Quoted 1 line
kernel/time/timeconv.c +1
-0+ year_of_century = (u32) (u64tmp >>32 );
Perhaps
year_of_century = upper_32_bits(u64tmp);
kernel/time/timeconv.c void time64_to_tm(time64_t totalsecs, int offset, struct tm *result) · line 115
Quoted 1 line
kernel/time/timeconv.c +1
-0+ day_of_year = ((u32 ) u64tmp) /2939745 /4 ;
and
day_of_year = lower_32_bits(u64tmp) / 2939745 / 4;
Quoted 8 lines
kernel/time/timeconv.c +8
-0+ is_leap = year_of_century !=0 ? + year_of_century %4 ==0 : century %4 ==0 ; + + u32tmp =2141 * day_of_year +132377 ; + month = u32tmp >>16 ; + day = ((u16 ) u32tmp) /2141 ; + +/* Recall that January 01 is the 306-th day of the year in the
kernel/time/timeconv.c void time64_to_tm(time64_t totalsecs, int offset, struct tm *result) · line 135
Quoted 10 lines
kernel/time/timeconv.c +10
-0+* computational (not Gregorian) calendar. +*/ + janOrFeb = day_of_year >=306 ; + +/* Converts to the Gregorian calendar and adjusts to Unix time. */ + year = year + janOrFeb -6313183731940000ULL ; + month = janOrFeb ? month -12 : month; + day = day +1 ; + day_of_year = janOrFeb ? + day_of_year -306 : day_of_year +31 +28 + is_leap;
I believe the extended naming improves readability, thanks.