Path: csiph.com!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.lang.c++
Subject: Re: Constexpr evaluation of heavy stuff
Date: Thu, 19 May 2022 08:53:06 -0700
Organization: A noiseless patient Spider
Lines: 99
Message-ID: <86tu9l1pul.fsf@linuxsc.com>
References: <t63uqq$hnm$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Info: reader02.eternal-september.org; posting-host="2a3388073214779a12c7a9c38773b260"; logging-data="19239"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX196cZSTikRQhmFNPITljy1I5UsCOckaMWg="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:uLfW0HNc+In/oxs7GNyQYFYErsM= sha1:ZbQW7XQDRHPOAcMKWPrSh6vZt+g=
Xref: csiph.com comp.lang.c++:84186

Andrey Tarasevich <andreytarasevich@hotmail.com> writes:

> Hello
>
> Just for the sake of experiment I tried this
>
>   #include <array>
>
>   template <std::size_t N> constexpr auto collect_primes()
>   {
>     std::array<unsigned, N> primes = { 2, 3 };
>     std::size_t n_primes = 2;
>
>     for (unsigned i = 0; n_primes < N; ++i)
>     {
>       unsigned value = 6u * (i / 2u + 1u) + i % 2u * 2u - 1;
>
>       std::size_t i_prime = 0;
>       for (; i_prime < n_primes; ++i_prime)
>         if (value % primes[i_prime] == 0)
>           break;
>
>       if (i_prime == n_primes)
>         primes[n_primes++] = value;
>     }
>
>     return primes;
>   }
>
>   int main()
>   {
>     constexpr auto primes = collect_primes<78498>();
>     ...
>   }
>
> Given the above code GCC will [attempt to] build the table of primes
> at compile time.  Command line options like
>
>   -fconstexpr-ops-limit=10000000000
>
> are needed to prevent it from aborting this overly heavy compile-time
> evaluation prematurely.  And this compile-time evaluation takes hours
> and hours and hours and... well... honestly, I haven't been able to
> see it to completion.
>
> If I get rid of the `constexpr`, i.e. switch to regular run-time
> evaluation, the above table will be built in about 15 seconds on the
> same machine.
>
> Reducing the table size to 10000 results in 8 minute `constexpr`
> evaluation vs. 0.25 second run-time table generation.
>
> Granted, it is naive to expect the same efficiency from compile-time
> constexpr` evaluation as we expect from `-O3` run-time code.  They
> can't just paste the `constexpr` code into a temp file, compile it
> with `-O3` and run it to obtain the result (can they?).  The compiler
> will apparently have to "pseudo-run" the code inside an "abstract
> virtual C++ machine" of sorts... But the actual difference in
> performance is still rather startling.  What could be the primary
> reason behind `constexpr` evaluation being so much slower?  Is it just
> a quality of implementation issue?  Or is there a bunch of fundamental
> reasons it will always be slow?  I see that GCC consumes huge amounts
> of memory wile compiling this code... Is it trying to fully unwrap the
> cycle/logic, which could be the reason for massive memory consumption
> and subsequent slowdown once swapping begins?

I don't have answers for your questions, but I did play around
with this a little bit, enough to offer some ideas for what they
might be worth.  Disclaimer: my version of gcc is almost
certainly less advanced than yours, so that may have affected my
observations.

One:  I think -O0 is a better basis than -O3 for comparing a
constexpr version to a non-constexpr version.  Probably gcc
evaluates constexpr expressions using a very straightforward
interpretation than an optimized interpretation.

Two:  In evaluating constexpr code, std::array is much more
expensive than just a plain array (eg, unsigned primes[N];).
I measured the time ratio between them at about 6.7.

Three:  Apparently the amount of memory required for std::array
is also significantly more than a plain array.  I didn't try to
measure this but there were other indications in the respective
compilation behaviors.

Four:  Changing the source so a plain array could be used instead
of a std::array, and also a somewhat different method of testing
for primality, I saw a time ratio (between a compile-time version
and run-time only version) of about 125-150 to 1.  That is on a
much smaller interval than the original above because trying to
run the full interval made the compiler go belly up.

Five:  Related to the last point, I suspect there is a knee in
the curve for compile-time evaluation, perhaps because the array
of primes is a local variable, which implies that a very large
stack frame may be needed for the full interval.

Just some ideas for possible directions to explore...