time: Improve performance of time64_to_tm()
authorCassio Neri <cassio.neri@gmail.com>
Tue, 22 Jun 2021 21:36:16 +0000 (22:36 +0100)
committerThomas Gleixner <tglx@linutronix.de>
Thu, 24 Jun 2021 09:51:59 +0000 (11:51 +0200)
commit276010551664f73b6f1616dde471d6f0d63a73ba
tree36bdb68afbbc7088b00c1ea0c9c55e8693b16960
parent4e82d2e20f3b11f253bc5c6e92f05ed3694a1ae3
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

Signed-off-by: Cassio Neri <cassio.neri@gmail.com>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
Link: https://lore.kernel.org/r/20210622213616.313046-1-cassio.neri@gmail.com
kernel/time/Kconfig
kernel/time/Makefile
kernel/time/time_test.c [new file with mode: 0644]
kernel/time/timeconv.c