Skip to contentSkip to conversation

time: Improve performance of time64_to_tm(). Add tests.

PATCH Applied Cassio Neri 2 participants 2 messages Jun 22, 2021 – Jun 24, 2021 Timekeeping, clocksource core, NTP, alarmtimer

lore
Share & tools
lore
#0 lore raw

PATCH v4 1/1 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 approximately 3x 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 for it which checks every day in a 160,000 years interval centered at 1970-01-01 against the expected result.

[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 time_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/chcoee8o9

* 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 centered at 1970-01-01:

    https://quick-bench.com/q/bPV45fKpIgB7Q6QXZ7I1a-Y9AGw

(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/6rq7jvcfz

* History:

v4 Address Thomas Gleixner's comments: changelog text, reverse variable
declarations, fix tabulation and changed expression of is_leap_year.
v3 Address Joe Perches' comments: rename variable, change some types and
use upper_32_bits and lower_32_bits.
v2 Address Joe Perches's comments: more descriptive variable names, use
ULL markers and other smaller changes.
v1 Original implementation.

* Many thanks to reviewers.

---
 kernel/time/Kconfig     |   9 +++
 kernel/time/Makefile    |   1 +
 kernel/time/time_test.c |  98 ++++++++++++++++++++++++++++++
 kernel/time/timeconv.c  | 128 ++++++++++++++++++++++------------------
 4 files changed, 178 insertions(+), 58 deletions(-)
 create mode 100644 kernel/time/time_test.c
kernel/time/Kconfig +9 -0
index 83e158d016ba..3610b1bef142 100644
@@ -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
index 1fb1c1ef6a19..b733d09a6e4d 100644
@@ -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 +70 -58

153 lines not on this page · raw message

base-commit: 245a057fee18be08d6ac12357463579d06bea077

Signature · 1 line
2.32.0
merge bot Applied
#1 lore raw

[tip: timers/core] time: Improve performance of time64_to_tm()

The following commit has been merged into the timers/core branch of tip:

The following commit has been merged into the timers/core branch of tip:

Commit-ID:     276010551664f73b6f1616dde471d6f0d63a73ba
Gitweb:        https://git.kernel.org/tip/276010551664f73b6f1616dde471d6f0d63a73ba
Author:        Cassio Neri <[email protected]>
AuthorDate:    Tue, 22 Jun 2021 22:36:16 +01:00
Committer:     Thomas Gleixner <[email protected]>
CommitterDate: Thu, 24 Jun 2021 11:51:59 +02:00

time: Improve performance of time64_to_tm()

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 approximately 3x 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 for it which checks every day in a 160,000 years interval centered at 1970-01-01 against the expected result.

[1] Neri, Schneider, "Euclidean Affine Functions and Applications to Calendar Algorithms". https://arxiv.org/abs/2102.06959

---
 kernel/time/Kconfig     |   9 +++-
 kernel/time/Makefile    |   1 +-
 kernel/time/time_test.c |  98 ++++++++++++++++++++++++++++++-
 kernel/time/timeconv.c  | 128 +++++++++++++++++++++------------------
 4 files changed, 178 insertions(+), 58 deletions(-)
 create mode 100644 kernel/time/time_test.c
kernel/time/Kconfig +9 -0
index 83e158d..3610b1b 100644
@@ -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
index 1ed85b2..7e875e6 100644
@@ -22,3 +22,4 @@ obj-$(CONFIG_DEBUG_FS)				+= timekeeping_debug.o
 obj-$(CONFIG_TEST_UDELAY)			+= test_udelay.o
 obj-$(CONFIG_TIME_NS)				+= namespace.o
 obj-$(CONFIG_TEST_CLOCKSOURCE_WATCHDOG)		+= clocksource-wdtest.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 +70 -58

153 lines not on this page · raw message