[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Message-ID: <20250826201343.GN1827@brightrain.aerifal.cx>
Date: Tue, 26 Aug 2025 16:13:43 -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 04:08:53PM -0400, Rich Felker wrote:
> 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.
Attached sloppy test passes.
Rich
View attachment "months.c" of type "text/plain" (536 bytes)
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.
