rtc: Improve performance of rtc_time64_to_tm. Add tests.
PATCH v4 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 ~4.3 times faster.
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 drivers/rtc/lib_test.c containing a KUnit test case that checks every day in a 160,000 years interval starting on 1970-01-01 against the expected result. A new config RTC_LIB_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 drivers/rtc/lib_test.c (see above). It's possible to run it on 32 and 64 bits.
https://godbolt.org/z/Tn6KjGTzc
* Benchmarks: It measures the time taken by each implementation to process 65,536 numbers. These numbers are pseudo-random under the uniform distribution on the interval corresponding to dates spanning 800 years starting at 1970-01-01.
https://quick-bench.com/q/whT24JkC6TBSDdvfmir2v4b52R4
(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/d145E4Eea
* History:
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.
--- drivers/rtc/Kconfig | 10 ++++ drivers/rtc/Makefile | 1 + drivers/rtc/lib.c | 104 ++++++++++++++++++++++++++++++----------- drivers/rtc/lib_test.c | 78 +++++++++++++++++++++++++++++++ 4 files changed, 167 insertions(+), 26 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 +78 -26
133 lines not on this page · raw message
drivers/rtc/lib_test.c new file +78 -0
78 lines not on this page · raw message
base-commit: bcae59d0d45b866d5b9525ea8ece6d671e6767c8
Signature · 1 line
2.31.0