[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20250826200851.GM1827@brightrain.aerifal.cx>
Date: Tue, 26 Aug 2025 16:08:53 -0400
From: Rich Felker <dalias@...c.org>
To: Alexey Moiseytsev <himeraster@...il.com>
Cc: musl@...ts.openwall.com
Subject: Re: [PATCH] __secs_to_tm: replace the linear search with a
closed-form integer formula
On Tue, Aug 26, 2025 at 02:42:00PM +0300, Alexey Moiseytsev wrote:
> Replace the sequential subtraction loop with a fixed-point month-index calculation to speed up month lookup.
> The month index is computed using a reciprocal 2^14/535 ≈ 30.62 (close to the mean month length); the small bias 333 is chosen to provide correct rounding.
> The day-of-month is recovered with (979*months + 16) >> 5, which yields the cumulative month starts [0, 31, 61, 92, 122, 153, 184, 214, 245, 275, 306, 337] (March-first).
> Microbenchmarks for the gmtime_r function show up to 1.5-2 times speed up depending on CPU model.
>
> Signed-off-by: Alexey Moiseytsev <himeraster@...il.com>
> ---
> src/time/__secs_to_tm.c | 5 ++---
> 1 file changed, 2 insertions(+), 3 deletions(-)
>
> diff --git a/src/time/__secs_to_tm.c b/src/time/__secs_to_tm.c
> index 093d9021..2a266dbf 100644
> --- a/src/time/__secs_to_tm.c
> +++ b/src/time/__secs_to_tm.c
> @@ -15,7 +15,6 @@ int __secs_to_tm(long long t, struct tm *tm)
> int qc_cycles, c_cycles, q_cycles;
> int months;
> int wday, yday, leap;
> - static const char days_in_month[] = {31,30,31,30,31,31,30,31,30,31,31,29};
>
> /* Reject time_t values whose year would overflow int */
> if (t < INT_MIN * 31622400LL || t > INT_MAX * 31622400LL)
> @@ -57,8 +56,8 @@ int __secs_to_tm(long long t, struct tm *tm)
>
> years = remyears + 4*q_cycles + 100*c_cycles + 400LL*qc_cycles;
>
> - for (months=0; days_in_month[months] <= remdays; months++)
> - remdays -= days_in_month[months];
> + months = (remdays * 535 + 333) >> 14;
> + remdays -= (979 * months + 16) >> 5;
>
> if (months >= 10) {
> months -= 12;
> --
> 2.34.1
Wow, this is a nice find. I'll run (and post here) a test to confirm
that the right result is given for each of the very small input value
set, just to be safe.
Rich
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
