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