Re: [PATCH] libstdc++: Optimize chrono year::is_leap

Is this good for trunk?

Em dom., 2 de ago. de 2026 às 10:03, Cassio Neri <[email protected]>
escreveu:

> Hi all,
>
> My findings pretty much confirm what Francisco reported.
>
> When GCC vectorises the benchmark loop, my algorithm (with L.
> Schneider and U. Drepper) ) is ~20% faster than Rueffner's (I have no
> idea why) but when GCC doesn't vectorise, then Hueffner's is more than
> ~2x faster than mine. (Results at the bottom.)
>
> I had a glance at the assembly of the whole benchmark code (not only
> the functions in isolation) to confirm the changes in codegen related
> to vectorisation.
>
> My intuition (no science involved) is that is_leap is very unlikely to
> be called in a loop as in the benchmark code, so that, in practice,
> GCC will rarely vectorise is_leap. I believe Francisco's change will
> improve performance in the most likely case. (I'm happy to see the
> current algorithm/code being replaced.)
>
> My measurements follow.
>
> 1) Jonathan's benchmark code compiled with -O3:
>
>
> ------------------------------------------------------------------------------------------
>   Benchmark                                Time             CPU
> Iterations UserCounters...
>
> ------------------------------------------------------------------------------------------
>   BM_all_years_neri                     9185 ns         9177 ns
> 75196 items_per_second=3.05124G/s
>   BM_all_years_hueffner                11060 ns        11021 ns
> 63871 items_per_second=2.54058G/s
>   BM_only_leap_years_neri               7155 ns         7143 ns
> 97960 items_per_second=2.96951G/s
>   BM_only_leap_years_hueffner           8466 ns         8457 ns
> 82658 items_per_second=2.50801G/s
>   BM_only_non_leap_years_neri           2269 ns         2266 ns
> 311720 items_per_second=2.99582G/s
>   BM_only_non_leap_years_hueffner       2637 ns         2634 ns
> 265893 items_per_second=2.57747G/s
>
> 2) With -O3 -fno-tree-vectorize:
>
>
> ------------------------------------------------------------------------------------------
>   Benchmark                                Time             CPU
> Iterations UserCounters...
>
> ------------------------------------------------------------------------------------------
>   BM_all_years_neri                    43187 ns        43145 ns
> 16299 items_per_second=648.975M/s
>   BM_all_years_hueffner                21190 ns        21165 ns
> 32295 items_per_second=1.32296G/s
>   BM_only_leap_years_neri              33077 ns        33042 ns
> 21524 items_per_second=641.902M/s
>   BM_only_leap_years_hueffner          15691 ns        15677 ns
> 44499 items_per_second=1.35296G/s
>   BM_only_non_leap_years_neri          10568 ns        10558 ns
> 65968 items_per_second=643.128M/s
>   BM_only_non_leap_years_hueffner       5133 ns         5127 ns
> 134345 items_per_second=1.32431G/s
>
> 3) Replacing the inner loop with the one below, also turns vectorisation
> off.
>
>   for (auto y : years)
>   {
>       auto b = is_leap(y);
>       benchmark::DoNotOptimize(b);
>   }
>
> With -O3 (adding -fno-tree-vectorize doesn't change much):
>
>
> ------------------------------------------------------------------------------------------
>   Benchmark                                Time             CPU
> Iterations UserCounters...
>
> ------------------------------------------------------------------------------------------
>   BM_all_years_neri                    46917 ns        46874 ns
> 14923 items_per_second=597.348M/s
>   BM_all_years_hueffner                17727 ns        17690 ns
> 38571 items_per_second=1.58282G/s
>   BM_only_leap_years_neri              35551 ns        35518 ns
> 19535 items_per_second=597.161M/s
>   BM_only_leap_years_hueffner          13404 ns        13375 ns
> 51384 items_per_second=1.58574G/s
>   BM_only_non_leap_years_neri          11479 ns        11455 ns
> 59135 items_per_second=592.774M/s
>   BM_only_non_leap_years_hueffner       4406 ns         4401 ns
> 159766 items_per_second=1.54284G/s
>
>
> On Fri, 31 Jul 2026 at 07:46, Jonathan Wakely <[email protected]> wrote:
> >
> > On Thu, 30 Jul 2026 at 17:51, Cassio Neri <[email protected]> wrote:
> > >
> > > Hi Jonathan and Francisco.
> > >
> > > I would also expect Hüffner's algorithm to be faster than mine.
> According to Ben Joffe's benchmark (*), it should be between 4% and 14%
> faster.
> >
> > Yes, the generated code looks like it should be faster.
> >
> > > I'll have a look during the weekend.
> >
> > That would be much appreciated, thanks!
> >
> > >
> > > (*) https://www.benjoffe.com/fast-leap-year
> > >
> > > FWIW: I wouldn't mind at all if my code is replaced :-)
> > >
> > > Cheers,
> > > Cassio
> > >
> > >
> > >
> > >
> > > On Thu, 30 Jul 2026, 13:26 Jonathan Wakely, <[email protected]>
> wrote:
> > >>
> > >> CC Cassio (see
> https://gcc.gnu.org/pipermail/libstdc++/2026-July/067388.html
> > >> for the start of the thread, also quoted below).
> > >>
> > >> On Thu, 30 Jul 2026 at 16:53, Francisco Muniz <[email protected]>
> wrote:
> > >> >
> > >> > Thanks, I had only checked scalar code generation initially.  In an
> isolated scalar test on x86_64, the new form is 7 instructions versus  10
> for the existing form, but I can reproduce that benchmark results depend on
> optimization context.  With GCC 17 -O3 generic, the loop favors the
> existing form, while with -fno-tree-vectorize or -march=native the new form
> is faster on my machine.
> > >> >
> > >> > Given that, I have to do more benchmarking before claiming this is
> a performance improvement, focus was mostly on number of instructions
> > >>
> > >>
> > >> I don't get consistent results, but for the benchmark code below
> > >> (using Google Benchmark) I see worse performance for is_leap_hueffner.
> > >>
> > >> #include <algorithm>
> > >> #include <chrono>
> > >> #include <functional>
> > >> #include <random>
> > >> #include <vector>
> > >> #include <span>
> > >> #include <benchmark/benchmark.h>
> > >>
> > >> namespace {
> > >>
> > >> bool is_leap_neri(short y)
> > >> {
> > >>     return (y & (y % 25 == 0 ? 15 : 3)) == 0;
> > >> }
> > >>
> > >> bool is_leap_hueffner(short y)
> > >> {
> > >>     const auto y32 = static_cast<unsigned int>(y) + 32800u;
> > >>     return ((y32 * 1073750999u) & 3221352463u) <= 126976u;
> > >> }
> > >>
> > >> constexpr int firstYear = -3999;
> > >> constexpr int lastYear  = 24000;
> > >> std::mt19937 rng(0x1234);
> > >>
> > >> std::vector<short> makeYears()
> > >> {
> > >>     std::vector<short> years;
> > >>     years.reserve(lastYear - firstYear + 1);
> > >>
> > >>     for (auto y = firstYear; y <= lastYear; ++y)
> > >>         years.push_back(y);
> > >>     std::shuffle(years.begin(), years.end(), rng);
> > >>
> > >>     return years;
> > >> }
> > >>
> > >> const std::vector<short> years = makeYears();
> > >> const std::vector<short> leap_years = [](auto v){
> > >>     std::erase_if(v, is_leap_neri);
> > >>     std::shuffle(v.begin(), v.end(), rng);
> > >>     return v;
> > >> }(years);
> > >> const std::vector<short> non_leap_years = [](auto v){
> > >>     std::erase_if(v, std::not_fn(is_leap_neri));
> > >>     std::shuffle(v.begin(), v.end(), rng);
> > >>     return v;
> > >> }(years);
> > >>
> > >> template<auto is_leap>
> > >> void run_benchmark(std::span<const short> years, benchmark::State&
> state)
> > >> {
> > >>     for (auto _ : state)
> > >>     {
> > >>         unsigned count = 0;
> > >>         for (auto y : years)
> > >>             count += is_leap(y);
> > >>         benchmark::DoNotOptimize(count);
> > >>     }
> > >>
> > >>     state.SetItemsProcessed(state.iterations() * years.size());
> > >> }
> > >>
> > >> } // namespace
> > >>
> > >> static void BM_all_years_neri(benchmark::State& state)
> > >> {
> > >>     run_benchmark<is_leap_neri>(years, state);
> > >> }
> > >>
> > >> BENCHMARK(BM_all_years_neri);
> > >>
> > >> static void BM_all_years_hueffner(benchmark::State& state)
> > >> {
> > >>     run_benchmark<is_leap_hueffner>(years, state);
> > >> }
> > >>
> > >> BENCHMARK(BM_all_years_hueffner);
> > >>
> > >> static void BM_only_leap_years_neri(benchmark::State& state)
> > >> {
> > >>     run_benchmark<is_leap_neri>(leap_years, state);
> > >> }
> > >>
> > >> BENCHMARK(BM_only_leap_years_neri);
> > >>
> > >> static void BM_only_leap_years_hueffner(benchmark::State& state)
> > >> {
> > >>     run_benchmark<is_leap_hueffner>(leap_years, state);
> > >> }
> > >>
> > >> BENCHMARK(BM_only_leap_years_hueffner);
> > >>
> > >> static void BM_only_non_leap_years_neri(benchmark::State& state)
> > >> {
> > >>     run_benchmark<is_leap_neri>(non_leap_years, state);
> > >> }
> > >>
> > >> BENCHMARK(BM_only_non_leap_years_neri);
> > >>
> > >> static void BM_only_non_leap_years_hueffner(benchmark::State& state)
> > >> {
> > >>     run_benchmark<is_leap_hueffner>(non_leap_years, state);
> > >> }
> > >>
> > >> BENCHMARK(BM_only_non_leap_years_hueffner);
> > >>
> > >> BENCHMARK_MAIN();
> > >>
> > >>
> ------------------------------------------------------------------------------------------
> > >> Benchmark                                Time             CPU
> > >> Iterations UserCounters...
> > >>
> ------------------------------------------------------------------------------------------
> > >> BM_all_years_neri                     7172 ns         7156 ns
> > >> 98499 items_per_second=3.913G/s
> > >> BM_all_years_hueffner                 9585 ns         9565 ns
> > >> 72842 items_per_second=2.92731G/s
> > >> BM_only_leap_years_neri               5424 ns         5408 ns
> > >> 131330 items_per_second=3.92231G/s
> > >> BM_only_leap_years_hueffner           7417 ns         7380 ns
> > >> 95061 items_per_second=2.87408G/s
> > >> BM_only_non_leap_years_neri           1746 ns         1742 ns
> > >> 394463 items_per_second=3.89825G/s
> > >> BM_only_non_leap_years_hueffner       2330 ns         2325 ns
> > >> 303924 items_per_second=2.92068G/s
> > >>
> > >>
> > >> But with variations on the benchmark code which shouldn't really
> > >> affect the performance, I see the new code being faster.
> > >>
> > >> >
> > >> >
> > >> > Em qui., 30 de jul. de 2026 às 12:11, Jonathan Wakely <
> [email protected]> escreveu:
> > >> >>
> > >> >> On Thu, 30 Jul 2026 at 01:58, Francisco Muniz wrote:
> > >> >> >
> > >> >> > Use Falk Hueffner's leap-year test for year::is_leap after
> shifting
> > >> >> > the valid std::chrono::year range by a multiple of 400. The shift
> > >> >> > preserves divisibility by 4, 100, and 400, and the unsigned
> conversion
> > >> >> > gives the intended modulo 2^32 arithmetic.
> > >> >> >
> > >> >> > Idea by Cassio Neri: add 32800, which is 82 * 400, to shift the
> signed
> > >> >> > year range into the supported non-negative range.
> > >> >>
> > >> >> This is interesting, but your new code is slower than Cassio's code
> > >> >> when I benchmark it. Have you done your own benchmarking?
> > >> >>
> > >> >> >
> > >> >> > Tested on x86_64-pc-linux-gnu:
> > >> >> >   make -j$(nproc) all-gcc
> > >> >> >   make -j$(nproc) all-target-libstdc++-v3
> > >> >> >   make check RUNTESTFLAGS='conformance.exp=std/time/year/1.cc'
> > >> >> >   make check RUNTESTFLAGS='conformance.exp=std/time/year/2.cc'
> > >> >> >
> > >> >> > libstdc++-v3/ChangeLog:
> > >> >> >
> > >> >> >         * include/std/chrono (year::is_leap): Use Hueffner
> leap-year
> > >> >> >         test after biasing the year by a multiple of 400.
> > >> >> >
> > >> >> > Signed-off-by: Francisco Muniz <[email protected]>
> > >> >> > ---
> > >> >> >  libstdc++-v3/include/std/chrono | 31
> ++++++++-----------------------
> > >> >> >  1 file changed, 8 insertions(+), 23 deletions(-)
> > >> >> >
> > >> >> > diff --git a/libstdc++-v3/include/std/chrono
> b/libstdc++-v3/include/std/chrono
> > >> >> > index 692fd6025e7..4483914c08b 100644
> > >> >> > --- a/libstdc++-v3/include/std/chrono
> > >> >> > +++ b/libstdc++-v3/include/std/chrono
> > >> >> > @@ -904,29 +904,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> > >> >> >        constexpr bool
> > >> >> >        is_leap() const noexcept
> > >> >> >        {
> > >> >> > -       // Testing divisibility by 100 first gives better
> performance [1], i.e.,
> > >> >> > -       //     return _M_y % 100 == 0 ? _M_y % 400 == 0 : _M_y %
> 16 == 0;
> > >> >> > -       // Furthermore, if _M_y % 100 == 0, then _M_y % 400 == 0
> is equivalent
> > >> >> > -       // to _M_y % 16 == 0, so we can simplify it to
> > >> >> > -       //     return _M_y % 100 == 0 ? _M_y % 16 == 0 : _M_y %
> 4 == 0.  // #1
> > >> >> > -       // Similarly, we can replace 100 with 25 (which is good
> since
> > >> >> > -       // _M_y % 25 == 0 requires one fewer instruction than
> _M_y % 100 == 0
> > >> >> > -       // [2]):
> > >> >> > -       //     return _M_y % 25 == 0 ? _M_y % 16 == 0 : _M_y % 4
> == 0.  // #2
> > >> >> > -       // Indeed, first assume _M_y % 4 != 0.  Then _M_y % 16
> != 0 and hence,
> > >> >> > -       // _M_y % 4 == 0 and _M_y % 16 == 0 are both false.
> Therefore, #2
> > >> >> > -       // returns false as it should (regardless of _M_y % 25.)
> Now assume
> > >> >> > -       // _M_y % 4 == 0.  In this case, _M_y % 25 == 0 if, and
> only if,
> > >> >> > -       // _M_y % 100 == 0, that is, #1 and #2 are equivalent.
> Finally, #2 is
> > >> >> > -       // equivalent to
> > >> >> > -       //     return (_M_y & (_M_y % 25 == 0 ? 15 : 3)) == 0.
> > >> >> > -
> > >> >> > -       // References:
> > >> >> > -       // [1] https://github.com/cassioneri/calendar
> > >> >> > -       // [2] https://godbolt.org/z/55G8rn77e
> > >> >> > -       // [3]
> https://gcc.gnu.org/pipermail/libstdc++/2021-June/052815.html
> > >> >> > -
> > >> >> > -       return (_M_y & (_M_y % 25 == 0 ? 15 : 3)) == 0;
> > >> >> > +       // Shift into the range supported by Falk Hueffner's
> leap-year test:
> > >> >> > +       //
> hueffner.de/falk/blog/a-leap-year-check-in-three-instructions.html
> > >> >> > +       // Adding a multiple of 400 preserves divisibility by 4,
> 100, and 400.
> > >> >> > +       // Idea by Cassio Neri: add 32800 (82 * 400).
> > >> >> > +       // The conversion to uint32_t gives the algorithm's
> intended modulo 2^32
> > >> >> > +       // arithmetic.
> > >> >> > +       const auto __y = static_cast<uint32_t>(_M_y) + 32800u;
> > >> >> > +       return ((__y * 1073750999u) & 3221352463u) <= 126976u;
> > >> >> >        }
> > >> >> >
> > >> >> >        explicit constexpr
> > >> >> > --
> > >> >> > 2.47.3
> > >> >> >
> > >> >>
> > >>
> >
>