[PATCH] libstdc++: Optimize chrono year::is_leap
Jonathan Wakely
jwakely@redhat.com
Thu Jul 30 16:25:53 GMT 2026
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