[PATCH] libstdc++: Optimize chrono year::is_leap
Cassio Neri
cassio.neri@gmail.com
Thu Jul 30 16:50:49 GMT 2026
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, <jwakely@redhat.com> 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 <munizfco@gmail.com> 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 <
> jwakely@redhat.com> 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 <munizfco@gmail.com>
> >> > ---
> >> > 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
> >> >
> >>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20260730/0417a5a3/attachment.htm>
More information about the Libstdc++
mailing list