Re: [PATCH v3] kernel/time: Improve performance of time64_to_tm. Add tests.

From: Thomas Gleixner
Date: Tue Jun 22 2021 - 12:03:41 EST


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().

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

> 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.

> * 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. :)

> +/*
> + * 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.


> void time64_to_tm(time64_t totalsecs, int offset, struct tm *result)
> {
> - 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;

> +
> + udays = ((u64) days) + 2305843009213814918ULL;

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

> +
> + 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.

> + 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.
*/

> + 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