Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.lang.c++
Subject: Re: constexpr is really very smart!
Date: Wed, 18 Dec 2024 03:26:15 -0800
Organization: A noiseless patient Spider
Lines: 119
Message-ID: <86frmlgrl4.fsf@linuxsc.com>
References: <vjndub$2glcu$1@paganini.bofh.team> <20241216112808.00003f74@yahoo.com> <vjouq6$12khu$2@dont-email.me> <20241216132315.00007859@yahoo.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Date: Wed, 18 Dec 2024 12:26:18 +0100 (CET)
Injection-Info: dont-email.me; posting-host="bbceff83978fead1ac4b0629d6983104";
	logging-data="2397817"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19A63KRdxo8Mc6qOxqgQuxQMRwCxurGSv4="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:WFE7OIMk55xp3Btw38VHh9hRolY=
	sha1:JxiqEtV9IKcrzIT3yXSOZCoccjY=
Bytes: 5668

Michael S <already5chosen@yahoo.com> writes:

> On Mon, 16 Dec 2024 11:18:46 +0100
> David Brown <david.brown@hesbynett.no> wrote:
>
>> On 16/12/2024 10:28, Michael S wrote:
>>
>>> On Sun, 15 Dec 2024 20:20:42 +0000
>>> Student Project <student@invalid.invalid> wrote:
>>>
>>>> The constexpr is really very smart because it can speed up
>>>> algorithms 1000 times according to Dave, Microsoft retired
>>>> engineer.  He has proved it by creating this video:
>>>>
>>>> <https://youtu.be/8-VZoXn8f9U?si=iy1UimoWcaLG31Xi>
>>>>
>>>> On my computer it took 270 microseconds to calculate fib(35) like
>>>> in his example.  It was almost instant at the blink of the eyes.
>>>>
>>>>> [...]
>>>>
>>>> Amazing.
>>>
>>> I didn't see the video (I never see that type of videos), but 270
>>> microseconds sound astonishingly slow for fib(35).
>>>
>>> #include <stdio.h>
>>> #include <stdlib.h>
>>> #include <intrin.h>
>>>
>>> static long long fib(long n)
>>> {
>>>    if (fib <= 0)
>>>      return 0;
>>>    long long f0 = 0, f1 = 1;
>>>    for (long i = 1; i < n; ++i) {
>>>      long long f2 = f0 + f1;
>>>      f0 = f1;
>>>      f1 = f2;
>>>    }
>>>    return f1;
>>> }
>>
>> There are a dozen different ways to calculate Fibonacci numbers,
>> ranging from very fast to very slow - but demonstrating different
>> things.  Even your program is going to be very slow compared to
>> just using
>> [garbled;  presumably ceil(pow((1+sqrt(5))/2, n)/sqrt(5))]

No, it won't.  The well-known formula for fibonacci numbers is
mathematically exact but numerically poor;  it gets wrong answers
even for outputs well under 64 bits.  It isn't all that fast either.

> My news reader is not sure about equation above.
> You probably meant ceil(pow((1+sqrt(5))/2, n)/sqrt(5))
> It works well with double precision math up to nu.  After that it
> would need high precision fp library, so probably [much] slower
> than simple loop above at least up to n' where we run out of range
> of int64 result.

Right.  The simple loop is faster.

>> My guess is that the OP is referring to some kind of naive
>> recursive Fibonacci implementation.
>
> Something like that ?
> static long long slow_fib(long n)
> {
>   if (n < 1)
>     return 0;
>   if (n == 1)
>     return 1;
>   return slow_fib(n-2)+slow_fib(n-1);
> }
>
> Yes, 270 usec could be considered fast relatively to that.
> slow_fib(35) takes 20 msec on my old PC.
>
>> If the function is declared "constexpr" and the values used are
>> compile-time constants, then maybe the use of "constexpr" leads
>> to more of it being pre-calculated at compile time.
>
> But then, how long would it take to compile?
> I'd guess for n5 it's not too bad, but what about n'?
> Slow algorithm is a slow algorithm.  Doing it in compile time can
> only exaggerate the slowness.

That isn't right.  A computation done at compile time isn't
obliged to use the same algorithm;  it is obliged only to get the
same results that the code would.  There is a simple way to take
advantage of a function like the one shown above, but constexpr,
to get a pre-compiled result much faster than simply plodding
through a simulation.  (Hint: it's a pure function whose output
depends only on its input, and only a small number of inputs are
needed for the overall result.)

>> The OP is right that "constexpr" can be very "smart" - but I'm
>> not sure this is the best calculation for demonstrating that.
>> However, I have not watched the video either, and maybe it's well
>> presented.
>
> If it is video and it is about programming then it can not be good.

I think the video is not bad.  Its primary purpose is to talk about
uses of constexpr that are not completely simple.  I've already
played around with such uses so the video didn't have much to say to
me, but for someone who hasn't done that there is a good chance it
will help them go up the learning curve.  At this stage of my
programming education I don't get much benefit from tutorial-type
content, but I think there are plenty of people who do.

If I may express a personal view, while I don't begrudge the
existence of tutorial material, I do find it irksome that there
is very little material that addresses a more advanced audience,
people who have a lot of background and experience but simply
lack knowledge in a particular area.  I'm tired of slogging
through mush that talks to its readers like they are all still
learning the basics.  Being ignorant is not the same as being
uneducated (and really not the same as being stupid.. ick).