Re: [PATCH] libstdc++: Optimize chrono year::is_leap
Cassio Neri <[email protected]> Sun, 2 Aug 2026 10:02:53 -0300
| Newsgroups | gmane.comp.gcc.patches,gmane.comp.gcc.libstdc++.devel |
|---|---|
| Message-ID | <CAOfgUPhEGg6OPXJA3HoCk8n_uAbVtFytxtnGZTXh04Ezd-=UKA@mail.gmail.com> |
Hi all,
My findings pretty much confirm what Francisco reported.
When GCC vectorises the benchmark loop, my algorithm (with L.
Schneider and U. Drepper) ) is ~20% faster than Rueffner's (I have no
idea why) but when GCC doesn't vectorise, then Hueffner's is more than
~2x faster than mine. (Results at the bottom.)
I had a glance at the assembly of the whole benchmark code (not only
the functions in isolation) to confirm the changes in codegen related
to vectorisation.
My intuition (no science involved) is that is_leap is very unlikely to
be called in a loop as in the benchmark code, so that, in practice,
GCC will rarely vectorise is_leap. I believe Francisco's change will
improve performance in the most likely case. (I'm happy to see the
current algorithm/code being replaced.)
My measurements follow.
1) Jonathan's benchmark code compiled with -O3:
------------------------------------------------------------------------------------------
Benchmark Time CPU
Iterations UserCounters...
------------------------------------------------------------------------------------------
BM_all_years_neri 9185 ns 9177 ns
75196 items_per_second=3.05124G/s
BM_all_years_hueffner 11060 ns 11021 ns
63871 items_per_second=2.54058G/s
BM_only_leap_years_neri 7155 ns 7143 ns
97960 items_per_second=2.96951G/s
BM_only_leap_years_hueffner 8466 ns 8457 ns
82658 items_per_second=2.50801G/s
BM_only_non_leap_years_neri 2269 ns 2266 ns
311720 items_per_second=2.99582G/s
BM_only_non_leap_years_hueffner 2637 ns 2634 ns
265893 items_per_second=2.57747G/s
2) With -O3 -fno-tree-vectorize:
------------------------------------------------------------------------------------------
Benchmark Time CPU
Iterations UserCounters...
------------------------------------------------------------------------------------------
BM_all_years_neri 43187 ns 43145 ns
16299 items_per_second=648.975M/s
BM_all_years_hueffner 21190 ns 21165 ns
32295 items_per_second=1.32296G/s
BM_only_leap_years_neri 33077 ns 33042 ns
21524 items_per_second=641.902M/s
BM_only_leap_years_hueffner 15691 ns 15677 ns
44499 items_per_second=1.35296G/s
BM_only_non_leap_years_neri 10568 ns 10558 ns
65968 items_per_second=643.128M/s
BM_only_non_leap_years_hueffner 5133 ns 5127 ns
134345 items_per_second=1.32431G/s
3) Replacing the inner loop with the one below, also turns vectorisation off.
for (auto y : years)
{
auto b = is_leap(y);
benchmark::DoNotOptimize(b);
}
With -O3 (adding -fno-tree-vectorize doesn't change much):
------------------------------------------------------------------------------------------
Benchmark Time CPU
Iterations UserCounters...
------------------------------------------------------------------------------------------
BM_all_years_neri 46917 ns 46874 ns
14923 items_per_second=597.348M/s
BM_all_years_hueffner 17727 ns 17690 ns
38571 items_per_second=1.58282G/s
BM_only_leap_years_neri 35551 ns 35518 ns
19535 items_per_second=597.161M/s
BM_only_leap_years_hueffner 13404 ns 13375 ns
51384 items_per_second=1.58574G/s
BM_only_non_leap_years_neri 11479 ns 11455 ns
59135 items_per_second=592.774M/s
BM_only_non_leap_years_hueffner 4406 ns 4401 ns
159766 items_per_second=1.54284G/s
On Fri, 31 Jul 2026 at 07:46, Jonathan Wakely <[email protected]> wrote:
>
> 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
> >> >> >
> >> >>
> >>
>