kernel/time: Improve performance of time64_to_tm. Add tests.
PATCH v3 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
v3 Address reviewer comments: rename variable, change some types and use
upper_32_bits and lower_32_bits.
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 | 132 ++++++++++++++++++++++------------------ 4 files changed, 182 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 +74 -58
157 lines not on this page · raw message
base-commit: 245a057fee18be08d6ac12357463579d06bea077
Signature · 1 line
2.31.0
Cassio,
On Wed, Jun 02 2021 at 20:00, Cassio Neri wrote:
A few nitpicks vs. the subject line. The proper prefix is 'time:' and please write time64_to_tm().
Quoted 7 lines
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).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
s/I reckon//
Quoted 6 lines
unlikely to need much maintenance, if any at all.
Added file
kernel/time/time_test.ccontaining 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 configTIME_KUNIT_TESTsymbol was introduced to give the option to run this test suite.
Add a KUnit test for it which checks every day in a 160,000 years interval centered at 1970-01-01 against the expected result.
Changelogs should be written in imperative mood. The details about the filename and the config symbol are not interesting for the change log.
Quoted 5 lines
* 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
Just that this uses XMM registers which the kernel does not. :)
Quoted 2 lines
+/*
+ * Tradicional implementation ofis_leap.
Traditional
Also the comment is odd. ... implementation of "is_leap" above a function named "is_leap" !?!
You probably want to say:
Traditional implementation of leap year evaluation.
or something like that.
kernel/time/timeconv.c static const unsigned short __mon_yday[2][13] = { · line 55
Quoted 11 lines
void
time64_to_tm(time64_t totalsecs, int offset, struct tm *result){kernel/time/timeconv.c +6
-2-long days, rem, y; +long days, rem;int remainder; -const unsigned short *ip; + +u64 u64tmp, udays, century, year; +u32 u32tmp, day_of_century, year_of_century, day_of_year, month, + day; +bool is_Jan_or_Feb, is_leap;
Can you please reorder that so it results in a reverse fir tree:
u64 u64tmp, udays, century, year; u32 u32tmp, day_of_century, year_of_century, day_of_year, month, day; bool is_Jan_or_Feb, is_leap; long days, rem;
int remainder;
kernel/time/timeconv.c void time64_to_tm(time64_t totalsecs, int offset, struct tm *result) · line 108
Quoted 2 lines
kernel/time/timeconv.c +2
-0+ + udays = ((u64 ) days) +2305843009213814918ULL ;
The tabulation uses spaces instead of tabs here and in various places below.
kernel/time/timeconv.c void time64_to_tm(time64_t totalsecs, int offset, struct tm *result) · line 121
Quoted 13 lines
kernel/time/timeconv.c +13
-0+ + u64tmp =4 * udays +3 ; + century =div64_u64_rem (u64tmp,146097 , &u64tmp); + day_of_century = (u32) (u64tmp /4 ); + + u32tmp =4 * day_of_century +3 ; + u64tmp =2939745ULL * u32tmp; + year_of_century =upper_32_bits (u64tmp); + day_of_year =lower_32_bits (u64tmp) /2939745 /4 ; + + year =100 * century + year_of_century; + is_leap = year_of_century !=0 ? + year_of_century %4 ==0 : century %4 ==0 ;
This really is hard to read.
is_leap = year_of_century != 0 ? year_of_century % 4 == 0 : century % 4 == 0;
or just:
is_leap = year_of_century ? !(year_of_century % 4) : !(century % 4);
That's longer than 80 characters, but that's not a really hard rule.
kernel/time/timeconv.c void time64_to_tm(time64_t totalsecs, int offset, struct tm *result) · line 129
Quoted 7 lines
kernel/time/timeconv.c +7
-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 +* computational (not Gregorian) calendar. +*/
/*
* Please format multiline comments according to regular
* kernel codingstyle.
*/
kernel/time/timeconv.c void time64_to_tm(time64_t totalsecs, int offset, struct tm *result) · line 137
Quoted 8 lines
kernel/time/timeconv.c +8
-0+ is_Jan_or_Feb = day_of_year >=306 ; + +/* Converts to the Gregorian calendar and adjusts to Unix time. */ + year = year + is_Jan_or_Feb -6313183731940000ULL ; + month = is_Jan_or_Feb ? month -12 : month; + day = day +1 ; + day_of_year = is_Jan_or_Feb ? + day_of_year -306 : day_of_year +31 +28 + is_leap;
See above.
Other than these nitpicks. Nice work!
Thanks,
tglx