Re: [committed] libstdc++: Improve performance of chrono::utc_clock::now()

[Jonathan Wakely <jwakely@redhat.com>]

[-- Attachment #1: Type: text/plain, Size: 8342 bytes --]

On Thu, 17 Nov 2022 at 09:57, Daniel Krügler <daniel.kruegler@gmail.com>
wrote:

> Am Do., 17. Nov. 2022 um 10:48 Uhr schrieb Jonathan Wakely <
> jwakely@redhat.com>:
> >
> >
> >
> > On Thu, 17 Nov 2022 at 09:47, Jonathan Wakely <jwakely@redhat.com>
> wrote:
> >>
> >>
> >>
> >> On Thu, 17 Nov 2022 at 09:25, Daniel Krügler <daniel.kruegler@gmail.com>
> wrote:
> >>>
> >>> Am Do., 17. Nov. 2022 um 10:07 Uhr schrieb Jonathan Wakely
> >>> <jwakely.gcc@gmail.com>:
> >>> >
> >>> >
> >>> >
> >>> > On Thu, 17 Nov 2022, 06:30 Daniel Krügler via Libstdc++, <
> libstdc++@gcc.gnu.org> wrote:
> >>> >>
> >>> >> Am Mi., 16. Nov. 2022 um 22:00 Uhr schrieb Jonathan Wakely via
> >>> >> Libstdc++ <libstdc++@gcc.gnu.org>:
> >>> >> >
> >>> >> > Tested x86_64-linux. Pushed to trunk.
> >>> >> >
> >>> >> > -- >8 --
> >>> >> >
> >>> >> > We can use an array instead of a std::vector, and we can avoid the
> >>> >> > binary search for the common case of a time point after the most
> recent
> >>> >> > leap second. On one system where I tested this, utc_clock::now()
> now
> >>> >> > takes about 16ns instead of 31ns.
> >>> >> >
> >>> >> > libstdc++-v3/ChangeLog:
> >>> >> >
> >>> >> >         * include/std/chrono (get_leap_second_info): Optimize.
> >>> >> > ---
> >>> >> >  libstdc++-v3/include/std/chrono | 31
> ++++++++++++++++++++++++-------
> >>> >> >  1 file changed, 24 insertions(+), 7 deletions(-)
> >>> >> >
> >>> >> > diff --git a/libstdc++-v3/include/std/chrono
> b/libstdc++-v3/include/std/chrono
> >>> >> > index 90b73f8198e..2468023f6c5 100644
> >>> >> > --- a/libstdc++-v3/include/std/chrono
> >>> >> > +++ b/libstdc++-v3/include/std/chrono
> >>> >> > @@ -2747,9 +2747,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> >>> >> >        {
> >>> >> >         if constexpr (is_same_v<_Duration, seconds>)
> >>> >> >           {
> >>> >> > -           // TODO move this function into the library and get
> leaps from tzdb.
> >>> >> > -           vector<seconds::rep> __leaps
> >>> >> > -           {
> >>> >> > +           const seconds::rep __leaps[] {
> >>> >> >                 78796800, // 1 Jul 1972
> >>> >> >                 94694400, // 1 Jan 1973
> >>> >> >                126230400, // 1 Jan 1974
> >>> >> > @@ -2778,12 +2776,31 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> >>> >> >               1435708800, // 1 Jul 2015
> >>> >> >               1483228800, // 1 Jan 2017
> >>> >> >             };
> >>> >> > +           // The list above is known to be valid until
> 2023-06-28 00:00:00 UTC
> >>> >> > +           const seconds::rep __expires = 1687910400;
> >>> >> > +           const seconds::rep __s =
> __ut.time_since_epoch().count();
> >>> >> >
> >>> >> > -           auto __s = __ut.time_since_epoch().count();
> >>> >> > -           auto __pos = std::upper_bound(__leaps.begin(),
> __leaps.end(), __s);
> >>> >> > +           const seconds::rep* __first = std::begin(__leaps);
> >>> >> > +           const seconds::rep* __last = std::end(__leaps);
> >>> >> > +
> >>> >> > +           if (__s > __expires)
> >>> >> > +             {
> >>> >> > +               // TODO: use updated leap_seconds from tzdb
> >>> >> > +#if 0
> >>> >> > +               auto __db = get_tzdb_list().begin();
> >>> >> > +               __first = __db->leap_seconds.data();
> >>> >> > +               __last = __first + __db->leap_seconds.size();
> >>> >> > +#endif
> >>> >> > +             }
> >>> >> > +
> >>> >> > +           // Don't bother searching the list if we're after the
> last one.
> >>> >> > +           if (__s > __last[-1])
> >>> >> > +             return { false, seconds(__last - __first) };
> >>> >> > +
> >>> >> > +           auto __pos = std::upper_bound(__first, __last, __s);
> >>> >> >             return {
> >>> >> > -             __pos != __leaps.begin() && __pos[-1] == __s,
> >>> >> > -             seconds{__pos - __leaps.begin()}
> >>> >> > +             __pos != begin(__leaps) && __pos[-1] == __s,
> >>> >>
> >>> >> The inconsistency between usage of std::begin versus begin here
> seems
> >>> >> odd and I'm wondering why instead of "begin(__leaps)" the above
> >>> >> introduced "__first" variable is not used instead.
> >>> >
> >>> >
> >>> > Because this code is going to be changed again soon, this is a
> partial merge from a local branch with the TODO fixed. Yes, it's
> inconsistent, but it works correctly and it's not my priority right now :-)
> >>>
> >>> What about the suggestion to use the already existing "__first"
> >>> variable instead of the begin call?
> >>
> >>
> >> It's an array, the begin call is free.
> >
> > Do you really want me to stop working on the missing time zone support
> to test and commit that change?
>
> I do not. I was reviewing and hoping to make a useful comment.
>
>
It is useful and I do appreciate the review, but like I said, the code is
going to change soon anyway, so I don't see any point making tiny stylistic
changes now (there's no problem with ADL here, as the array contains
int64_t values, and calling begin on an array is cheap).

This is what I have in my local branch:

    template<typename _Duration>
      leap_second_info
      get_leap_second_info(const utc_time<_Duration>& __ut)
      {
        if (__ut < utc_time<_Duration>{}) [[unlikely]]
          return {};

        if constexpr (is_same_v<_Duration, seconds>)
          {
            const seconds::rep __leaps[] {
                78796800, // 1 Jul 1972
                94694400, // 1 Jan 1973
               126230400, // 1 Jan 1974
               157766400, // 1 Jan 1975
               189302400, // 1 Jan 1976
               220924800, // 1 Jan 1977
               252460800, // 1 Jan 1978
               283996800, // 1 Jan 1979
               315532800, // 1 Jan 1980
               362793600, // 1 Jul 1981
               394329600, // 1 Jul 1982
               425865600, // 1 Jul 1983
               489024000, // 1 Jul 1985
               567993600, // 1 Jan 1988
               631152000, // 1 Jan 1990
               662688000, // 1 Jan 1991
               709948800, // 1 Jul 1992
               741484800, // 1 Jul 1993
               773020800, // 1 Jul 1994
               820454400, // 1 Jan 1996
               867715200, // 1 Jul 1997
               915148800, // 1 Jan 1999
              1136073600, // 1 Jan 2006
              1230768000, // 1 Jan 2009
              1341100800, // 1 Jul 2012
              1435708800, // 1 Jul 2015
              1483228800, // 1 Jan 2017
            };
            // The list above is known to be valid until 2023-06-28
00:00:00 UTC
            const seconds::rep __expires = 1687910400;
            const seconds::rep __s = __ut.time_since_epoch().count();

            if (__s < __expires)
              {
                const seconds::rep* __first = std::begin(__leaps);
                const seconds::rep* __last = std::end(__leaps);

                // Don't bother searching the list if we're after the last
one.
                if (__s > __last[-1])
                  return { false, seconds(__last - __first) };

                auto __pos = std::upper_bound(__first, __last, __s);
                return {
                  __pos != __first && __pos[-1] == __s,
                  seconds{__pos - __first}
                };
              }
            else
              {
                // use updated leap_seconds from tzdb
                auto __db = get_tzdb_list().begin();
                auto __first = __db->leap_seconds.begin();
                auto __last = __db->leap_seconds.end();
                sys_seconds __ss(__ut.time_since_epoch());
                auto __pos = std::upper_bound(__first, __last, __ss);
                return {
                  __pos != __first && __pos[-1] == __ss,
                  seconds{__pos - __first}
                };
              }
          }
        else
          {
            auto __s = chrono::time_point_cast<seconds>(__ut);
            return chrono::get_leap_second_info(__s);
          }
      }

But that can't be pushed to trunk now because get_tzdb_list() isn't defined
on trunk yet.

If you have any comments about *this* version, I'll be happy to hear them
:-)