rtc: Improve performance of rtc_time64_to_tm(). Add tests.
PATCH v5 1/1 rtc: Improve performance of rtc_time64_to_tm(). Add tests.
From: Cassio Neri <[email protected]>
The current implementation of rtc_time64_to_tm() contains unnecessary loops, branches and look-up tables. The new one uses an arithmetic-based algorithm appeared in [1] and is approximately 4.3 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, the code is unlikely to need much maintenance, if any at all.
Add a KUnit test case that checks every day in a 160,000 years interval starting on 1970-01-01 against the expected result. Add a new config RTC_LIB_KUNIT_TEST symbol 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].
* Test evidence: Same test implemented by lib_test.c, compiler switches are close to kernel's and it's possible to run this test on 32 and 64 bits:
https://godbolt.org/z/azoPon87s
* Benchmarks: Measures the time taken by each implementation to process 65,536 pseudo-random numbers (time64_t) drawn under the uniform distribution on the interval corresponding to dates spanning 800 years starting at 1970-01-01.
https://quick-bench.com/q/4sEYBU2y3iZiQE-2qKK1BQCsj-Y
(Apologies that the benchmark is in C++ but results in C should be close. Results need to be taken with a pinch of salt since compiler switches are not the same as the kernel's.)
* Disasembly: Compiler switches are close to kernel's and shows, in particular, reduction in code size:
https://godbolt.org/z/bsE6ebq3v
* History:
v5 Address comments by reviewers of a similar patch sent to the TIMEKEEPING
subsystem. (FWIW: The patch was accepted. https://tinyurl.com/2emaebs3)
v4 Improve clarity and removed call to is_leap(year) since it's possible to
figure it out from century and year of century.
v3 Squash previous patches/commits into a single one.
v2 Fix link issue on 32 bit platforms reported by the test robot. v1 Original patch.
* Thanks to Thomas Gleixner and Joe Perches.
--- drivers/rtc/Kconfig | 10 ++++ drivers/rtc/Makefile | 1 + drivers/rtc/lib.c | 107 ++++++++++++++++++++++++++++++----------- drivers/rtc/lib_test.c | 79 ++++++++++++++++++++++++++++++ 4 files changed, 170 insertions(+), 27 deletions(-) create mode 100644 drivers/rtc/lib_test.c
drivers/rtc/Kconfig +10 -0
@@ -10,6 +10,16 @@ config RTC_MC146818_LIB bool select RTC_LIB +config RTC_LIB_KUNIT_TEST + tristate "KUnit test for RTC lib functions" if !KUNIT_ALL_TESTS + depends on KUNIT + default KUNIT_ALL_TESTS + select RTC_LIB + help + Enable this option to test RTC library functions. + + If unsure, say N. + menuconfig RTC_CLASS bool "Real Time Clock" default n
drivers/rtc/Makefile +1 -0
@@ -178,3 +178,4 @@ obj-$(CONFIG_RTC_DRV_WM8350) += rtc-wm8350.o obj-$(CONFIG_RTC_DRV_X1205) += rtc-x1205.o obj-$(CONFIG_RTC_DRV_XGENE) += rtc-xgene.o obj-$(CONFIG_RTC_DRV_ZYNQMP) += rtc-zynqmp.o +obj-$(CONFIG_RTC_LIB_KUNIT_TEST) += lib_test.o
drivers/rtc/lib.c +80 -27
136 lines not on this page · raw message
drivers/rtc/lib_test.c new file +79 -0
79 lines not on this page · raw message
base-commit: bcae59d0d45b866d5b9525ea8ece6d671e6767c8
Signature · 1 line
2.32.0
Quoted 10 lines · Cassio Neri
The current implementation of
rtc_time64_to_tm()contains unnecessary loops, branches and look-up tables. The new one uses an arithmetic-based algorithm appeared in [1] and is approximately 4.3 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, the code is unlikely to need much maintenance, if any at all.
[...]
Applied, thanks!
[1/1] rtc: Improve performance of rtc_time64_to_tm(). Add tests.
commit: 1d1bb12a8b1805ddeef9793ebeb920179fb0fa38
Best regards,
Signature · 1 line
Alexandre Belloni <[email protected]>