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. I'll have a look during the weekend.
(*) 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 > >> > > >> > >
