Skip to contentSkip to conversation

rtc: Improve performance of rtc_time64_to_tm(). Add tests.

PATCH Applied Cassio Neri 2 participants 2 messages Jun 24, 2021 – Aug 9, 2021 Real time clock (RTC)

lore
Share & tools
lore
#0 lore raw

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
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 +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
maintainer Applied
#1 lore raw
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]>