Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Michael S <already5chosen@yahoo.com>
Newsgroups: comp.lang.c++
Subject: Re: constexpr is really very smart!
Date: Wed, 18 Dec 2024 22:00:06 +0200
Organization: A noiseless patient Spider
Lines: 89
Message-ID: <20241218220006.00003f8e@yahoo.com>
References: <vjndub$2glcu$1@paganini.bofh.team>
	<20241216112808.00003f74@yahoo.com>
	<86jzbyghdw.fsf@linuxsc.com>
	<20241218013342.0000518a@yahoo.com>
	<867c7whol9.fsf@linuxsc.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Injection-Date: Wed, 18 Dec 2024 21:00:08 +0100 (CET)
Injection-Info: dont-email.me; posting-host="b9b47f030a8936d1360dde1a260912d6";
	logging-data="2572644"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18BtGi7cH/MzX4cXJlPONZy24KWRBoeRmk="
Cancel-Lock: sha1:6qVnYScvRRWexSp1JZCKknXXO4c=
X-Newsreader: Claws Mail 4.1.1 (GTK 3.24.34; x86_64-w64-mingw32)
Bytes: 3519

On Wed, 18 Dec 2024 09:45:38 -0800
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

> Michael S <already5chosen@yahoo.com> writes:
> 
> > On Tue, 17 Dec 2024 12:54:19 -0800
> > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> >  
> >> Michael S <already5chosen@yahoo.com> writes:
> >>  
> [...]
> >>> #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;
> >>> }  
> >>
> >> Here is my second fastest fibonacci calculation code (for
> >> relatively small inputs):
> >>
> >>     typedef long unsigned long ULL;
> >>
> >>     ULL
> >>     fibonacci( unsigned n ){
> >>         ULL  b = n&1,  a = b^1;
> >>
> >>         if(  n & 2  )  a += b,  b += a;
> >>         if(  n & 4  )  a += b,  b += a,  a += b,  b += a;
> >>         if(  n & 8  ){
> >>             ULL na = 13*a+21*b, nb = 21*a+34*b;
> >>             a = na,  b = nb;
> >>         }
> >>
> >>         n >>= 4;
> >>         while(  n--  ){
> >>             ULL  na = 610*a + 987*b,  nb = 987*a + 1597*b;
> >>             a = na,  b = nb;
> >>         }
> >>
> >>         return  b;
> >>     }  
> >
> > From BigO perspective this code looks like it's still O(n) so no
> > better than simple loop.  
> 
> It is O(n) but it has a smaller constant.
> 
> > According to my measurement gear, in range 0 to 92 there are few
> > points where it is faster than simple loop, but in majority of
> > cases it is slower.  
> 
> I'm at a loss to understand how this could happen.  In my own
> measurements, the code shown above runs faster than a simple loop in
> all cases above n > 12, more than twice as fast when n > 17, more
> than three times as fast when n > 42, and going up from there.  What
> might account for these radically different results?


May be, number of repetitions?
I run the test only once. That gives relative advantage to smaller
code which is less sensitive to cold ICache and to cold branch
predictors.
Also, because I am running it only once, my test is not so good in
seeing differences between various "good" algorithms.
But I feel that running test once is more realistic.