[PATCH] libstdc++: Optimize chrono year::is_leap
Jonathan Wakely
jwakely@redhat.com
Fri Jul 31 10:46:14 GMT 2026
On Thu, 30 Jul 2026 at 17:51, Cassio Neri <cassio.neri@gmail.com> 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, <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
>> >> >
>> >>
>>
More information about the Libstdc++
mailing list