Skip to contentSkip to conversation

rtc: Improve performance of rtc_time64_to_tm. Add tests.

PATCH Superseded Cassio Neri 1 participant 1 message Jun 2, 2021 Real time clock (RTC)

v4 of 5 Superseded Latest is v5 →

lore
Share & tools
lore
#0 lore raw

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
index 914497abeef9..af65f5007f78 100644
@@ -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
index 2dd0dd956b0e..763d3628c603 100644
@@ -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