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

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