time: Improve performance of time64_to_tm(). Add tests.
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
@@ -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
@@ -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
[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
@@ -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
@@ -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