Skip to contentSkip to conversation

kernel/time: Improve performance of time64_to_tm. Add tests.

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

v3 of 4 Superseded Latest is v4 →

lore
Share & tools
lore
#0 lore raw

PATCH v3 1/1 kernel/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 ~3.2 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, I reckon the code is unlikely to need much maintenance, if any at all.

Added file kernel/time/time_test.c containing a KUnit test case that checks every day in a 160,000 years interval centered at 1970-01-01 against the expected result. A new config TIME_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 kernel/time/time_test.c (see above). It's possible to run it on 32 and 64 bits.

    https://godbolt.org/z/1rn1aqfqY

* Benchmarks: It measures the time taken by each implementation to process 65,536 numbers (time64_t). These numbers are pseudo-random under the uniform distribution on the interval corresponding to dates spanning 800 years centered at 1970-01-01:

https://quick-bench.com/q/COPMeRk9e00Sua85KFrKKL9YoSc

(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/e87rhha5b

* History

v3 Address reviewer comments: rename variable, change some types and use

     upper_32_bits and lower_32_bits.

v2 Address reviewer comments.
v1 Original implementation.

---
 kernel/time/Kconfig     |   9 +++
 kernel/time/Makefile    |   1 +
 kernel/time/time_test.c |  98 +++++++++++++++++++++++++++++
 kernel/time/timeconv.c  | 132 ++++++++++++++++++++++------------------
 4 files changed, 182 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 +74 -58

157 lines not on this page · raw message

base-commit: 245a057fee18be08d6ac12357463579d06bea077

Signature · 1 line
2.31.0
#1 lore raw

Cassio,

On Wed, Jun 02 2021 at 20:00, Cassio Neri wrote:

A few nitpicks vs. the subject line. The proper prefix is 'time:' and please write time64_to_tm().

Quoted 7 lines

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 ~3.2 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, I reckon the code is

s/I reckon//

Quoted 6 lines

unlikely to need much maintenance, if any at all.

Added file kernel/time/time_test.c containing a KUnit test case that checks every day in a 160,000 years interval centered at 1970-01-01 against the expected result. A new config TIME_KUNIT_TEST symbol was introduced to give the option to run this test suite.

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.

Changelogs should be written in imperative mood. The details about the filename and the config symbol are not interesting for the change log.

Quoted 5 lines

* Test evidence: This runs the same test implemented in kernel/time/time_test.c (see above). It's possible to run it on 32 and 64 bits.

    https://godbolt.org/z/1rn1aqfqY

Just that this uses XMM registers which the kernel does not. :)

Quoted 2 lines

+/*
+ * Tradicional implementation of is_leap.

Traditional

Also the comment is odd. ... implementation of "is_leap" above a function named "is_leap" !?!

You probably want to say:

Traditional implementation of leap year evaluation.

or something like that.

kernel/time/timeconv.c static const unsigned short __mon_yday[2][13] = { · line 55

Quoted 11 lines

void time64_to_tm(time64_t totalsecs, int offset, struct tm *result) {

kernel/time/timeconv.c +6 -2
-	long days, rem, y;
+	long days, rem;
 	int remainder;
-	const unsigned short *ip;
+
+	u64 u64tmp, udays, century, year;
+	u32 u32tmp, day_of_century, year_of_century, day_of_year, month,
+		day;
+	bool is_Jan_or_Feb, is_leap;

Can you please reorder that so it results in a reverse fir tree:

	u64 u64tmp, udays, century, year;
	u32 u32tmp, day_of_century, year_of_century, day_of_year, month, day;
	bool is_Jan_or_Feb, is_leap;
	long days, rem;

int remainder;

kernel/time/timeconv.c void time64_to_tm(time64_t totalsecs, int offset, struct tm *result) · line 108

Quoted 2 lines
kernel/time/timeconv.c +2 -0
+
+	udays           = ((u64) days) + 2305843009213814918ULL;

The tabulation uses spaces instead of tabs here and in various places below.

kernel/time/timeconv.c void time64_to_tm(time64_t totalsecs, int offset, struct tm *result) · line 121

Quoted 13 lines
kernel/time/timeconv.c +13 -0
+
+	u64tmp          = 4 * udays + 3;
+	century         = div64_u64_rem(u64tmp, 146097, &u64tmp);
+	day_of_century  = (u32) (u64tmp / 4);
+
+	u32tmp          = 4 * day_of_century + 3;
+	u64tmp          = 2939745ULL * u32tmp;
+	year_of_century = upper_32_bits(u64tmp);
+	day_of_year     = lower_32_bits(u64tmp) / 2939745 / 4;
+
+	year            = 100 * century + year_of_century;
+	is_leap         = year_of_century != 0 ?
+		year_of_century % 4 == 0 : century % 4 == 0;

This really is hard to read.

	is_leap		= year_of_century != 0 ?
			  year_of_century % 4 == 0 : century % 4 == 0;

or just:

	is_leap         = year_of_century ? !(year_of_century % 4) : !(century % 4);

That's longer than 80 characters, but that's not a really hard rule.

kernel/time/timeconv.c void time64_to_tm(time64_t totalsecs, int offset, struct tm *result) · line 129

Quoted 7 lines
kernel/time/timeconv.c +7 -0
+	u32tmp          = 2141 * day_of_year + 132377;
+	month           = u32tmp >> 16;
+	day             = ((u16) u32tmp) / 2141;
+
+	/* Recall that January 01 is the 306-th day of the year in the
+	 * computational (not Gregorian) calendar.
+	 */

/*
* Please format multiline comments according to regular
* kernel codingstyle.
*/

kernel/time/timeconv.c void time64_to_tm(time64_t totalsecs, int offset, struct tm *result) · line 137

Quoted 8 lines
kernel/time/timeconv.c +8 -0
+	is_Jan_or_Feb   = day_of_year >= 306;
+
+	/* Converts to the Gregorian calendar and adjusts to Unix time. */
+	year            = year + is_Jan_or_Feb - 6313183731940000ULL;
+	month           = is_Jan_or_Feb ? month - 12 : month;
+	day             = day + 1;
+	day_of_year     = is_Jan_or_Feb ?
+		day_of_year - 306 : day_of_year + 31 + 28 + is_leap;

See above.

Other than these nitpicks. Nice work!

Thanks,

tglx