Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #84186

Re: Constexpr evaluation of heavy stuff

Show key headers only | View raw

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...

Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Constexpr evaluation of heavy stuff Andrey Tarasevich <andreytarasevich@hotmail.com> - 2022-05-18 16:17 -0700
  Re: Constexpr evaluation of heavy stuff "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2022-05-19 09:19 +0200
    Re: Constexpr evaluation of heavy stuff David Brown <david.brown@hesbynett.no> - 2022-05-19 11:59 +0200
      Re: Constexpr evaluation of heavy stuff "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2022-05-19 12:37 +0200
        Re: Constexpr evaluation of heavy stuff David Brown <david.brown@hesbynett.no> - 2022-05-19 14:49 +0200
          Re: Constexpr evaluation of heavy stuff Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-05-19 06:19 -0700
            Re: Constexpr evaluation of heavy stuff Paavo Helde <eesnimi@osa.pri.ee> - 2022-05-19 20:32 +0300
              Re: Constexpr evaluation of heavy stuff Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-05-20 01:12 -0700
                Re: Constexpr evaluation of heavy stuff Juha Nieminen <nospam@thanks.invalid> - 2022-05-20 08:37 +0000
                Re: Constexpr evaluation of heavy stuff Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-05-20 02:21 -0700
                Re: Constexpr evaluation of heavy stuff Ben <ben.usenet@bsb.me.uk> - 2022-05-20 11:25 +0100
                Re: Constexpr evaluation of heavy stuff David Brown <david.brown@hesbynett.no> - 2022-05-20 12:47 +0200
                Re: Constexpr evaluation of heavy stuff Ben <ben.usenet@bsb.me.uk> - 2022-05-20 12:13 +0100
                Re: Constexpr evaluation of heavy stuff David Brown <david.brown@hesbynett.no> - 2022-05-20 14:27 +0200
                Re: Constexpr evaluation of heavy stuff Öö Tiib <ootiib@hot.ee> - 2022-05-20 06:33 -0700
                Re: Constexpr evaluation of heavy stuff Paavo Helde <eesnimi@osa.pri.ee> - 2022-05-20 17:15 +0300
                Re: Constexpr evaluation of heavy stuff Christian Gollwitzer <auriocus@gmx.de> - 2022-05-20 18:57 +0200
                Re: Constexpr evaluation of heavy stuff Paavo Helde <eesnimi@osa.pri.ee> - 2022-05-20 22:31 +0300
                Re: Constexpr evaluation of heavy stuff Manfred <noname@add.invalid> - 2022-05-21 21:56 +0200
                Re: Constexpr evaluation of heavy stuff Öö Tiib <ootiib@hot.ee> - 2022-05-21 23:24 -0700
                Re: Constexpr evaluation of heavy stuff Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-05-22 04:56 -0700
                Re: Constexpr evaluation of heavy stuff Öö Tiib <ootiib@hot.ee> - 2022-05-22 06:15 -0700
                Re: Constexpr evaluation of heavy stuff Manfred <noname@add.invalid> - 2022-05-22 21:46 +0200
                Re: Constexpr evaluation of heavy stuff "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2022-05-22 23:23 +0200
                Re: Constexpr evaluation of heavy stuff Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-05-22 16:26 -0700
                Re: Constexpr evaluation of heavy stuff Manfred <noname@add.invalid> - 2022-05-23 17:24 +0200
                Re: Constexpr evaluation of heavy stuff Richard Damon <Richard@Damon-Family.org> - 2022-05-23 19:41 -0400
                Re: Constexpr evaluation of heavy stuff scott@slp53.sl.home (Scott Lurndal) - 2022-05-24 16:15 +0000
                Re: Constexpr evaluation of heavy stuff Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-05-24 05:37 -0700
                Re: Constexpr evaluation of heavy stuff Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2022-05-20 04:19 -0700
                Re: Constexpr evaluation of heavy stuff Ben <ben.usenet@bsb.me.uk> - 2022-05-20 12:32 +0100
                Re: Constexpr evaluation of heavy stuff Juha Nieminen <nospam@thanks.invalid> - 2022-05-20 10:40 +0000
                Re: Constexpr evaluation of heavy stuff David Brown <david.brown@hesbynett.no> - 2022-05-20 12:31 +0200
                Re: Constexpr evaluation of heavy stuff Juha Nieminen <nospam@thanks.invalid> - 2022-05-20 10:43 +0000
                Re: Constexpr evaluation of heavy stuff David Brown <david.brown@hesbynett.no> - 2022-05-20 14:52 +0200
          Re: Constexpr evaluation of heavy stuff "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2022-05-19 15:34 +0200
    Re: Constexpr evaluation of heavy stuff "Alf P. Steinbach" <alf.p.steinbach@gmail.com> - 2022-05-19 17:03 +0200
  Re: Constexpr evaluation of heavy stuff Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-05-19 08:53 -0700
    Re: Constexpr evaluation of heavy stuff Marcel Mueller <news.5.maazl@spamgourmet.org> - 2022-05-19 18:33 +0200

csiph-web