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

Groups > comp.lang.c++ > #121210 > unrolled thread

constexpr is really very smart!

Back to article view | Back to comp.lang.c++

Contents

  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

Page 2 of 2 — ← Prev page 1 [2]

#121298 — Bignum multiplication in Python vs GMP (was: constexpr is really very smart!)

On Tue, 24 Dec 2024 05:21:42 -0800
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

> Michael S <already5chosen@yahoo.com> writes:
> 
> > On Sun, 22 Dec 2024 10:25:59 -0800
> > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> >  
> >> Michael S <already5chosen@yahoo.com> writes:
> >>  
> >>> On Fri, 20 Dec 2024 14:59:07 -0800
> >>> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> >>>  
> >>>> I ran a python version to compute fibonacci( 10000000 ).  This
> >>>> code ran 30% faster than the previous version, which I would be
> >>>> is almost entirely due to the expression factoring with 'c'.
> >>>> Great!  
> >>>
> >>> This one does fib(10M) in 89 msec on my very old home PC.
> >>>
> >>> [code]  
> >>
> >> You are the speed king!  
> >
> > But approximately the same code in python is MUCH slower.
> > 2.9 sec on 11 y.o. PC that still serves me as a desktop at work.
> > 2.0 sec on 5.5 y.o. mall server.  
> 
> That matches my experience with doing this in python.
> 
> > I don't really understand why.
> > I expected that nearly all time is spend in multiplication of few
> > huge numbers, probably over 75% of time in last couple of steps (6
> > multiplications).  And I was under impression that internally Python
> > uses the same GMP library that I used in C. So I expected the same
> > speed, more or less.  May be, 1.5x slowdown because of less
> > efficient memory handling in Python. 35x difference is a big
> > surprise.  
> 
> Yes, I have no explanation either.  Your reasoning looks sound to
> me.
>

I did few more time measurements both with GMP and with Python. It
clearly showed that they use not just different implementations of
bignum multiplication, but different algorithms.
GMP multiplication for operands in range of above ~200,000 bits is
approximately O(N*log(N)) with number of bits, or just a little bit
slower than that. 
Python multiplication scale much worse, approximately as (N**1.55).

And indeed after binging more I had seen the following discussion on
reddit:
https://www.reddit.com/r/Python/comments/7h62ul/python_largeinteger_computation_speed_a_comparison/

A relevant quote:
"Python seems to use two algorithms for bignum multiplication: "the
O(N**2) school algorithm" and Karatsuba if both operands contain more
than 70 decimal digits. (Your example reaches 70 decimal digits already
after the 5th(?) squaring, and after the 22nd there are ~17million
decimal digits(?). The wast majority of the time is spent on the last
one or two multiplications i.e. Karatsuba.)

Meanwhile GMP implements seven multiplication algorithms: The same(?)
"school" and Karatsuba algorithms, plus various Toom and an FFT method
(Strassen), but I'm unclear on what the exact thresholds are that
select these. It seems these thresholds are in "limbs" ("the part of a
multi-precision number that fits in a single machine word") instead of
decimal digits, with e.g. FFT method being used after "somewhere
between 3000 and 10000 limbs", i.e. >~30k - 100k(?) decimal digits, so
it would probably be used for the relevant steps in your example."


It seem that that threshold for FFT method mentioned in the quote
applies to number of limbs (i.e. 64-bit groups of bits in our specific
case) in the product rather than in the operands. Also it is possible
that in the newer versions of GMP the threshold is a lower than it
was 7 years ago.

I wonder, why python uses its own thing instead of GMP.
Incompatible licenses or plain NIH ?

[toc] | [prev] | [next] | [standalone]

#121299 — Re: Bignum multiplication in Python vs GMP (was: constexpr is really very smart!)

On Wed, 25 Dec 2024 11:05:05 +0200
Michael S <already5chosen@yahoo.com> wrote:

> On Tue, 24 Dec 2024 05:21:42 -0800
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> 
> > Michael S <already5chosen@yahoo.com> writes:
> >   
> > > On Sun, 22 Dec 2024 10:25:59 -0800
> > > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> > >    
> > >> Michael S <already5chosen@yahoo.com> writes:
> > >>    
> > >>> On Fri, 20 Dec 2024 14:59:07 -0800
> > >>> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> > >>>    
> > >>>> I ran a python version to compute fibonacci( 10000000 ).  This
> > >>>> code ran 30% faster than the previous version, which I would be
> > >>>> is almost entirely due to the expression factoring with 'c'.
> > >>>> Great!    
> > >>>
> > >>> This one does fib(10M) in 89 msec on my very old home PC.
> > >>>
> > >>> [code]    
> > >>
> > >> You are the speed king!    
> > >
> > > But approximately the same code in python is MUCH slower.
> > > 2.9 sec on 11 y.o. PC that still serves me as a desktop at work.
> > > 2.0 sec on 5.5 y.o. mall server.    
> > 
> > That matches my experience with doing this in python.
> >   
> > > I don't really understand why.
> > > I expected that nearly all time is spend in multiplication of few
> > > huge numbers, probably over 75% of time in last couple of steps (6
> > > multiplications).  And I was under impression that internally
> > > Python uses the same GMP library that I used in C. So I expected
> > > the same speed, more or less.  May be, 1.5x slowdown because of
> > > less efficient memory handling in Python. 35x difference is a big
> > > surprise.    
> > 
> > Yes, I have no explanation either.  Your reasoning looks sound to
> > me.
> >  
> 
> I did few more time measurements both with GMP and with Python. It
> clearly showed that they use not just different implementations of
> bignum multiplication, but different algorithms.
> GMP multiplication for operands in range of above ~200,000 bits is
> approximately O(N*log(N)) with number of bits, or just a little bit
> slower than that. 
> Python multiplication scale much worse, approximately as (N**1.55).
> 
> And indeed after binging more I had seen the following discussion on
> reddit:
> https://www.reddit.com/r/Python/comments/7h62ul/python_largeinteger_computation_speed_a_comparison/
> 
> A relevant quote:
> "Python seems to use two algorithms for bignum multiplication: "the
> O(N**2) school algorithm" and Karatsuba if both operands contain more
> than 70 decimal digits. (Your example reaches 70 decimal digits
> already after the 5th(?) squaring, and after the 22nd there are
> ~17million decimal digits(?). The wast majority of the time is spent
> on the last one or two multiplications i.e. Karatsuba.)
> 
> Meanwhile GMP implements seven multiplication algorithms: The same(?)
> "school" and Karatsuba algorithms, plus various Toom and an FFT method
> (Strassen), but I'm unclear on what the exact thresholds are that
> select these. It seems these thresholds are in "limbs" ("the part of a
> multi-precision number that fits in a single machine word") instead of
> decimal digits, with e.g. FFT method being used after "somewhere
> between 3000 and 10000 limbs", i.e. >~30k - 100k(?) decimal digits, so
> it would probably be used for the relevant steps in your example."
> 
> 
> It seem that that threshold for FFT method mentioned in the quote
> applies to number of limbs (i.e. 64-bit groups of bits in our specific
> case) in the product rather than in the operands. Also it is possible
> that in the newer versions of GMP the threshold is a lower than it
> was 7 years ago.
> 
> I wonder, why python uses its own thing instead of GMP.
> Incompatible licenses or plain NIH ?
> 

Forgot to mention. 
As said in the same redit thread, one can use GMP from python. It's
pretty easy, just not the default. 

import gmpy2

def fib(n):
  if n < 1:
    return 0

  tmp = n
  msb = 1
  while tmp > 1:
    msb += msb
    tmp //= 2
  f0=gmpy2.mpz(0); f1=gmpy2.mpz(1);
  while msb > 1:
    ff0 = f0*f0 + f1*f1
    f1 = (f0+f0+f1)*f1
    f0 = ff0
    msb //= 2
    if msb & n:
      f0 = f1
      f1 += ff0
  return f1


For big values of n gmpy2-based variant calculates Fibbonaci numbers at
approximately the same speed as C variant. For smaller numbers - not
quite the same as C and for n < ~10,000 it is slower than default
python math.

[toc] | [prev] | [next] | [standalone]

#121303 — Re: Bignum multiplication in Python vs GMP (was: constexpr is really very smart!)

Michael S <already5chosen@yahoo.com> writes:

>> [GMP in python?]
>
> Forgot to mention.
> As said in the same redit thread, one can use GMP from python.  It's
> pretty easy, just not the default.
>
> [example]

Thank you, that is good to know.

> For big values of n gmpy2-based variant calculates Fibbonaci numbers at
> approximately the same speed as C variant.  For smaller numbers - not
> quite the same as C and for n < ~10,000 it is slower than default
> python math.

So now we need a hybrid method where "small" numbers use default
python algorithms and advance to GMP for larger numbers, with each
of those two already being hybrids?  A hybrid**2 algorithm?  I like
it. ;)

By the way, in the last week or so I sent you two emails.  Could I
ask you to send a short email in response (assuming they arrived,
which I expect they did)?

[toc] | [prev] | [next] | [standalone]

#121302 — Re: Bignum multiplication in Python vs GMP (was: constexpr is really very smart!)

Michael S <already5chosen@yahoo.com> writes:

> On Tue, 24 Dec 2024 05:21:42 -0800
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>>
>>> [python runs much slower than GMP]
>>
>> Yes, I have no explanation either.  Your reasoning looks sound to
>> me.
>
> I did few more time measurements both with GMP and with Python.  It
> clearly showed that they use not just different implementations of
> bignum multiplication, but different algorithms.
> GMP multiplication for operands in range of above ~200,000 bits is
> approximately O(N*log(N)) with number of bits, or just a little bit
> slower than that.
> Python multiplication scale much worse, approximately as (N**1.55).

That's consistent with using Karatsuba:  log2( 3 ) =~ 1.585.

> And indeed after binging more I had seen the following discussion on
> reddit: [link]
>
> A relevant quote:
> "Python seems to use two algorithms for bignum multiplication:  "the
> O(N**2) school algorithm" and Karatsuba if both operands contain more
> than 70 decimal digits.  (Your example reaches 70 decimal digits already
> after the 5th(?) squaring, and after the 22nd there are ~17million
> decimal digits(?).  The wast majority of the time is spent on the last
> one or two multiplications i.e. Karatsuba.)
>
> Meanwhile GMP implements seven multiplication algorithms:  The same(?)
> "school" and Karatsuba algorithms, plus various Toom and an FFT method
> (Strassen), but I'm unclear on what the exact thresholds are that
> select these.  It seems these thresholds are in "limbs" ("the part of a
> multi-precision number that fits in a single machine word") instead of
> decimal digits, with e.g. FFT method being used after "somewhere
> between 3000 and 10000 limbs", i.e. >~30k - 100k(?) decimal digits, so
> it would probably be used for the relevant steps in your example."

That ratio suggests the limbs are 32 bits (ie, roughly 10 digits each).

> It seem that that threshold for FFT method mentioned in the quote
> applies to number of limbs (i.e. 64-bit groups of bits in our specific
> case) in the product rather than in the operands.  Also it is possible
> that in the newer versions of GMP the threshold is a lower than it
> was 7 years ago.

I have no intuition regarding whether a threshold would be chosen
based on the sizes of the operands or the sizes of the product.  For
this particular problem it's only one iteration difference anyway.

> I wonder, why python uses its own thing instead of GMP.
> Incompatible licenses or plain NIH ?

Perhaps (1) python doesn't want to be bound by the rather severe
terms of a GNU license, or (2) historical inertia.

Let me add that I appreciate your excellent investigation results.
They reinforce my view that it was wise for me to cease the deep
dives into performance issues. :)

[toc] | [prev] | [next] | [standalone]

#121265

On 18/12/2024 11:51, Michael S wrote:
> Iterative:
> 
> static long long fib(long n)
> {
>    if (n <= 0)
>      return 0;
>    // find MS bit
>    unsigned long tmp = n;
>    unsigned long bit = 1;
>    while (tmp > 1) {
>      bit += bit;
>      tmp /= 2;
>    }
>    // for n > 0
>    // fib(n*2)   = (fib(n-1)+fib(n+1))*fib(n)
>    // fib(n*2+1) = fib(n)*fib(n)+fib(n+1)*fib(n+1)
>    long long a = 0, b = 1;
>    while (bit > 1) {
>      long long c = a + b; // fib(n+1)
>      bit /= 2;
>      if ((n & bit)==0) { // (n-1,n) => (n*2-1,n*2)
>        c += a;
>        a = a*a + b*b;
>        b = c*b;
>      } else {            // (n-1,n) => (n*2,n*2+1)
>        a = (a + c)*b;
>        b = b*b + c*c;
>      }
>    }
>    return b;
> }

Here is my test result of this iterative function:

> D:\CmdLine\C_Cpp\Chrono06>program
> Testing fibonacci function
> fib(92) = 7540113804746346429
> Time taken by fib: 0 microseconds
> 
> D:\CmdLine\C_Cpp\Chrono06>program
> Testing fibonacci function
> fib(92) = 7540113804746346429
> Time taken by fib: 0 microseconds
> 
> D:\CmdLine\C_Cpp\Chrono06>program
> Testing fibonacci function
> fib(92) = 7540113804746346429
> Time taken by fib: 0 microseconds
> 
> D:\CmdLine\C_Cpp\Chrono06>program
> Testing fibonacci function
> fib(92) = 7540113804746346429
> Time taken by fib: 0 microseconds

The full program to run in G++ is:

<+++++++++++++++++++++++++++++++++++++++++++++>

#include <iostream>
#include <chrono>

using namespace std;
using namespace std::chrono;

long long fib(long n)
{
     if (n <= 0)
         return 0;
     // find MS bit
     unsigned long tmp = n;
     unsigned long bit = 1;
     while (tmp > 1)
     {
         bit += bit;
         tmp /= 2;
     }
     // for n > 0
     // fib(n*2)   = (fib(n-1)+fib(n+1))*fib(n)
     // fib(n*2+1) = fib(n)*fib(n)+fib(n+1)*fib(n+1)
     long long a = 0, b = 1;
     while (bit > 1)
     {
         long long c = a + b; // fib(n+1)
         bit /= 2;
         if ((n & bit) == 0)
         { // (n-1,n) => (n*2-1,n*2)
             c += a;
             a = a * a + b * b;
             b = c * b;
         }
         else
         { // (n-1,n) => (n*2,n*2+1)
             a = (a + c) * b;
             b = b * b + c * c;
         }
     }
     return b;
}

int main(void)
{
     cout << "Testing fibonacci function\n";
     auto start = high_resolution_clock::now();
     constexpr int num = 92;
     long long result = fib (num);
     auto stop = high_resolution_clock::now();

     auto duration = duration_cast<microseconds>(stop - start);
     cout << "fib(" << num << ") = " << result << "\n";
     cout << "Time taken by fib: " << duration.count() << " microseconds\n";

}

<+++++++++++++++++++++++++++++++++++++++++++++>

[toc] | [prev] | [next] | [standalone]

#121254

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?

[toc] | [prev] | [next] | [standalone]

#121256

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.

[toc] | [prev] | [next] | [standalone]

#121264

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.

[toc] | [prev] | [next] | [standalone]

#121266

On Thu, 19 Dec 2024 00:57:20 -0800
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

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


I feel that running fib(n) with the same n in loop too unrealistic.
So I decided to run, at least, with different values of n.
Ended up spending about a hour just to build a test bench.

The answer is - in a loop of more than dozen iterations your code is
indeed faster. Esp. so for hundred or more iterations.

Here is my test bench.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <intrin.h>

long long fib(long n);
volatile long long dummy;

int main(int argz, char** argv)
{
  if (argz < 2) {
    printf("Go away!\n");
    return 1;
  }

  char* endp;
  long n = strtol(argv[1], &endp, 0);
  if (endp == argv[1]) {
    printf("%s is not a number. Go away!\n", argv[1]);
    return 1;
  }

  if (argz == 2) {
    unsigned long long t0 = _rdtsc();
    long long f = fib(n);
    unsigned long long t1 = _rdtsc();
    printf("fib(%ld)=%lld. %lld clock cycles.\n", n, f, t1 - t0);
    return 0;
  }

  // argz > 2
  if (argv[2][0]=='t') {
    long long f0 = 0, f1 = 1;
    for (long i = 0; i <= n; ++i) {
      long long res = fib(i);
      if (res != f0) {
        printf("Mistake at n = %ld. %lld instead of %lld\n"
         , i, res, f0);
        return 1;
      }
      long long f2 = f0 + f1;
      f0 = f1;
      f1 = f2;
    }
    printf("o.k.\n");
    return 0;
  }

  long m = strtol(argv[2], &endp, 0);
  if (endp == argv[2]) {
    printf("%s is not a number. Go away!\n", argv[2]);
    return 1;
  }

  if (n > m) {
    long tmp = n; n = m; m = tmp;
  }

  unsigned long dn = m - n + 1;
  if (dn > 1000000) {
    printf(
      "Range [%ld..%ld] is wider than 1M. Unsupported. I am sorry.\n"
      , n, m);
    return 1;
  }

  size_t n_iter = 10;
  if (argz > 3) { // get non-default number of iterations
    unsigned long long val = strtoull(argv[3], &endp, 0);
    if (endp == argv[3]) {
      printf("%s is not a number. Go away!\n", argv[3]);
      return 1;
    }
    if (val < 1 || val > 10000000) {
      printf(
      "number of iterations %s is out of range "
      "[1..10,000,000]. Go away!\n", argv[3]);
      return 1;
    }
    n_iter = val;
  }

  long* an = malloc(n_iter*sizeof(long));
  if (an) {
    // prepare array of random arguments
    srand(1);
    for (size_t i = 0; i < n_iter; ++i)
      an[i] = (long)((((uint64_t)(rand() & 0x7fff) * dn) >> 15) + n);

    dummy = 0;
    unsigned long long t0 = _rdtsc();
    for (size_t i = 0; i < n_iter; ++i)
      dummy += fib(an[i]);
    unsigned long long t1 = _rdtsc();
    dummy = 0;

    printf(
      "n in range [%ld..%ld]. %zu iterations."
      " %llu clocks. %llu clocks/iter\n"
      ,n, m, n_iter, t1-t0, (t1-t0)/n_iter);

    free(an);
  } else {
    perror("malloc()");
    return 1;
  }

  return 0;
}

[toc] | [prev] | [next] | [standalone]

#121281

Michael S <already5chosen@yahoo.com> writes:

> On Thu, 19 Dec 2024 00:57:20 -0800
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> 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:
[...]
>>>>> According to my measurement gear, in range 0 to 92 there are few
>>>>> points where [the code I posted] 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.
[...]
>
> I feel that running fib(n) with the same n in loop too unrealistic.
> So I decided to run, at least, with different values of n.

I agree, that is a better choice for a measurement test load.

> Ended up spending about a hour just to build a test bench.
>
> The answer is - in a loop of more than dozen iterations your code is
> indeed faster.  Esp. so for hundred or more iterations.

I'm happy to learn that my instincts were validated here.  And I
also learned something, about the effects of code warmup.  Very
interesting.

> Here is my test bench.  [...]

Thank you for that.  Sadly I am not able to run it because my
test environment is lacking _rdtsc(), and I haven't been able
to find out how to install it.

By the way, I send you an email earlier today.  Did that get to
you?

[toc] | [prev] | [next] | [standalone]

#121284

On Fri, 20 Dec 2024 14:31:54 -0800
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

> 
> Thank you for that.  Sadly I am not able to run it because my
> test environment is lacking _rdtsc(), and I haven't been able
> to find out how to install it.
> 

Any x86-64 Linux should have _rdtsc() as inline function (or built-in)
defined in x86intrin.h. No installation required.

> By the way, I send you an email earlier today.  Did that get to
> you?

Yes, I got it.

[toc] | [prev] | [next] | [standalone]

#121285

On 12/21/24 17:14, Michael S wrote:
> On Fri, 20 Dec 2024 14:31:54 -0800
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> Thank you for that. Sadly I am not able to run it because my
>> test environment is lacking _rdtsc(), and I haven't been able
>> to find out how to install it.
>>
>
> Any x86-64 Linux should have _rdtsc() as inline function (or built-in)
> defined in x86intrin.h. No installation required.

On my x86-64 Linux system, that header (indirectly) declares __rdtsc(),
but not _rdtsc.

[toc] | [prev] | [next] | [standalone]

#121286

On Sat, 21 Dec 2024 17:55:20 -0500
James Kuyper <jameskuyper@alumni.caltech.edu> wrote:

> On 12/21/24 17:14, Michael S wrote:
> > On Fri, 20 Dec 2024 14:31:54 -0800
> > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> >  
> >> Thank you for that. Sadly I am not able to run it because my
> >> test environment is lacking _rdtsc(), and I haven't been able
> >> to find out how to install it.
> >>  
> >
> > Any x86-64 Linux should have _rdtsc() as inline function (or
> > built-in) defined in x86intrin.h. No installation required.  
> 
> On my x86-64 Linux system, that header (indirectly) declares
> __rdtsc(), but not _rdtsc.
> 
> 

Thank you.
I'd guess I knew it once, but  because I don't run microbenchmark on
Linux all that often, had forgotten.

[toc] | [prev] | [next] | [standalone]

#121288

Michael S <already5chosen@yahoo.com> writes:

> On Fri, 20 Dec 2024 14:31:54 -0800
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> Thank you for that.  Sadly I am not able to run it because my
>> test environment is lacking _rdtsc(), and I haven't been able
>> to find out how to install it.
>
> Any x86-64 Linux should have _rdtsc() as inline function (or built-in)
> defined in x86intrin.h.  No installation required.

Okay.  As it turns out knowing that doesn't help me, but thank
you for the info.  I'm taking this as a sign from heaven that
I should be spending my energies somewhere other than measuring
performance.

[toc] | [prev] | [next] | [standalone]

#121290

On Sun, 22 Dec 2024 10:33:57 -0800
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:

> Michael S <already5chosen@yahoo.com> writes:
> 
> > On Fri, 20 Dec 2024 14:31:54 -0800
> > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> >  
> >> Thank you for that.  Sadly I am not able to run it because my
> >> test environment is lacking _rdtsc(), and I haven't been able
> >> to find out how to install it.  
> >
> > Any x86-64 Linux should have _rdtsc() as inline function (or
> > built-in) defined in x86intrin.h.  No installation required.  
> 
> Okay.  As it turns out knowing that doesn't help me, but thank
> you for the info.  I'm taking this as a sign from heaven that
> I should be spending my energies somewhere other than measuring
> performance.
> 

Did you see correction of James Kuyper? 
Under Linux it is called __rdtsc().

[toc] | [prev] | [next] | [standalone]

#121292

Michael S <already5chosen@yahoo.com> writes:

> On Sun, 22 Dec 2024 10:33:57 -0800
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> Michael S <already5chosen@yahoo.com> writes:
>>
>>> On Fri, 20 Dec 2024 14:31:54 -0800
>>> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>>>
>>>> Thank you for that.  Sadly I am not able to run it because my
>>>> test environment is lacking _rdtsc(), and I haven't been able
>>>> to find out how to install it.
>>>
>>> Any x86-64 Linux should have _rdtsc() as inline function (or
>>> built-in) defined in x86intrin.h.  No installation required.
>>
>> Okay.  As it turns out knowing that doesn't help me, but thank
>> you for the info.  I'm taking this as a sign from heaven that
>> I should be spending my energies somewhere other than measuring
>> performance.
>
> Did you see correction of James Kuyper?
> Under Linux it is called __rdtsc().

Yes I saw that.

[toc] | [prev] | [next] | [standalone]

#121236

Student Project <student@invalid.invalid> writes:
> 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.

Can you post the relevant code?

[...]

-- 
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
void Void(void) { Void(); } /* The recursive call of the void */

[toc] | [prev] | [next] | [standalone]

#121241

On 17/12/2024 20:20, Keith Thompson wrote:
> Student Project <student@invalid.invalid> writes:
>> 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.
> 
> Can you post the relevant code?
> 
> [...]
> 

Code in the boxed area below: (The purpose is to demonstrate constexpr NOT the recursive algorithm. The video is very clear about this). 


It is the same code as in the video. G++ gives you the best result after 
changing one line to:

/*constexpr*/ int result_c = fibonacci_c(num);

G++ result is (multiple runs) - All timings in milliseconds:
D:\CmdLine\C_Cpp\Chrono05>program
Fibonacci_c 9227465
Time taken: 9
Fibonacci 9227465
Time taken: 289

D:\CmdLine\C_Cpp\Chrono05>program
Fibonacci_c 9227465
Time taken: 4
Fibonacci 9227465
Time taken: 276

D:\CmdLine\C_Cpp\Chrono05>program
Fibonacci_c 9227465
Time taken: 8
Fibonacci 9227465
Time taken: 284

D:\CmdLine\C_Cpp\Chrono05>program
Fibonacci_c 9227465
Time taken: 5
Fibonacci 9227465
Time taken: 276

clang++ and Visual studio are the slowest. I don't know why.



<+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
#include <iostream>
#include <chrono>

int fibonacci(int n)
{
     if (n <= 1)
         return n;
     return fibonacci(n - 2) + fibonacci(n - 1);
}

constexpr int fibonacci_c(int n)
{
     if (n <= 1)
         return n;
     return fibonacci_c(n - 2) + fibonacci_c(n - 1);
}

int main(void)
{
     // using namespace std::literals::chrono_literals;
     auto start = std::chrono::high_resolution_clock::now();
     constexpr int num = 35;
     /*constexpr*/ int result_c = fibonacci_c(num);

     std::cout << "Fibonacci_c " << result_c << "\n";
     std::cout << "Time taken: " << 
std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::high_resolution_clock::now() 
- start).count() << "\n";

     start = std::chrono::high_resolution_clock::now();
     int result = fibonacci(num);
     std::cout << "Fibonacci " << result << "\n";
     std::cout << "Time taken: " << 
std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::high_resolution_clock::now() 
- start).count() << "\n";

}

<+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

[toc] | [prev] | [next] | [standalone]

#121249

On Wed, 18 Dec 2024 04:45:20 +0000
Student Project <student@invalid.invalid> wrote:

> 
> <+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
> #include <iostream>
> #include <chrono>
> 
> int fibonacci(int n)
> {
>      if (n <= 1)
>          return n;
>      return fibonacci(n - 2) + fibonacci(n - 1);
> }
> 
> constexpr int fibonacci_c(int n)
> {
>      if (n <= 1)
>          return n;
>      return fibonacci_c(n - 2) + fibonacci_c(n - 1);
> }
> 
> int main(void)
> {
>      // using namespace std::literals::chrono_literals;
>      auto start = std::chrono::high_resolution_clock::now();
>      constexpr int num = 35;
>      /*constexpr*/ int result_c = fibonacci_c(num);
> 
>      std::cout << "Fibonacci_c " << result_c << "\n";
>      std::cout << "Time taken: " << 
> std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::high_resolution_clock::now() 
> - start).count() << "\n";
> 
>      start = std::chrono::high_resolution_clock::now();
>      int result = fibonacci(num);
>      std::cout << "Fibonacci " << result << "\n";
>      std::cout << "Time taken: " << 
> std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::high_resolution_clock::now() 
> - start).count() << "\n";
> 
> }
> 
> <+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
> 

It is likely that at least part of the time you are measuring cout print
time instead of calculations time you are interested in.
Also, if you are using gcc on Windows then there is a significant chance
that implementation of high_resolution_clock is broken. steady_clock is
more reliable.

Try following:
 volatile dummy = 0;
 auto t00 = std::chrono::steady_clock::now();// first call can be slow
 dummy = 1;
 auto t0 = std::chrono::steady_clock::now();
 dummy = 2;
 auto result_c = fibonacci_c(num);
 dummy = 3;
 auto t1 = std::chrono::steady_clock::now();
 dummy = 4;
 auto result = fibonacci(num);
 dummy = 5;
 auto t2 = std::chrono::steady_clock::now();
 dummy = 3;

 etc...

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.lang.c++

csiph-web