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

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

Re: constexpr is really very smart!

Show key headers only | View raw

Michael S <already5chosen@yahoo.com> writes:

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

That's an interesting idea.  Can you also run a measurement where
the code is run inside loops?  I think it would be instructive
to compare the results under the two approaches.

(The server I use seems not to have the necessary support to
measure very fast code segments that are run only once.)

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

I think an argument could be made that repeatedly running the code
in a loop gives a more relevant result.  Any short code segment that
is run only a handful of times will never have a significant impact
on overall program performance.  It's better to optimize under the
assumption that the code will be "hot":  if it is hot then the
optimization will be worthwhile, and if it isn't hot then the loss
will be way down in the noise and not worth worrying about.

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

Thread

constexpr is really very smart! Student Project <student@invalid.invalid> - 2024-12-15 20:20 +0000
  Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-16 11:28 +0200
    Re: constexpr is really very smart! David Brown <david.brown@hesbynett.no> - 2024-12-16 11:18 +0100
      Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-16 13:23 +0200
        Re: constexpr is really very smart! David Brown <david.brown@hesbynett.no> - 2024-12-16 13:43 +0100
          Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-17 11:08 +0200
            Re: constexpr is really very smart! David Brown <david.brown@hesbynett.no> - 2024-12-17 11:10 +0100
        Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-18 03:26 -0800
          Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-18 14:39 +0200
            Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-18 07:42 -0800
    Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-17 12:54 -0800
      Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-18 01:33 +0200
        Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-18 13:51 +0200
          Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-19 00:40 -0800
            Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-20 02:17 +0200
              Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-20 14:59 -0800
                Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-22 00:07 +0200
                Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-22 10:25 -0800
                Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-23 17:47 +0200
                Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-24 05:21 -0800
                Bignum multiplication in Python vs GMP (was: constexpr is really very smart!) Michael S <already5chosen@yahoo.com> - 2024-12-25 11:05 +0200
                Re: Bignum multiplication in Python vs GMP (was: constexpr is really very smart!) Michael S <already5chosen@yahoo.com> - 2024-12-25 13:33 +0200
                Re: Bignum multiplication in Python vs GMP (was: constexpr is really very smart!) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-26 18:54 -0800
                Re: Bignum multiplication in Python vs GMP (was: constexpr is really very smart!) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-26 18:42 -0800
          Re: constexpr is really very smart! Student Project <student@invalid.invalid> - 2024-12-19 19:14 +0000
        Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-18 09:45 -0800
          Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-18 22:00 +0200
            Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-19 00:57 -0800
              Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-19 23:45 +0200
                Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-20 14:31 -0800
                Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-22 00:14 +0200
                Re: constexpr is really very smart! James Kuyper <jameskuyper@alumni.caltech.edu> - 2024-12-21 17:55 -0500
                Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-22 02:22 +0200
                Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-22 10:33 -0800
                Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-23 00:05 +0200
                Re: constexpr is really very smart! Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-12-22 17:17 -0800
  Re: constexpr is really very smart! Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-12-17 12:20 -0800
    Re: constexpr is really very smart! Student Project <student@invalid.invalid> - 2024-12-18 04:45 +0000
      Re: constexpr is really very smart! Michael S <already5chosen@yahoo.com> - 2024-12-18 14:17 +0200

csiph-web