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

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

What practice can get speed improvement in C++?

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

Contents

  What practice can get speed improvement in C++? fl <rxjwg98@gmail.com> - 2015-07-14 16:53 -0700
    Re: What practice can get speed improvement in C++? Barry Schwarz <schwarzb@dqel.com> - 2015-07-14 17:23 -0700
      Re: What practice can get speed improvement in C++? bartekltg <bartekltg@gmail.com> - 2015-07-15 15:10 +0200
        Re: What practice can get speed improvement in C++? JiiPee <no@notvalid.com> - 2015-07-16 05:00 +0100
          Re: What practice can get speed improvement in C++? Öö Tiib <ootiib@hot.ee> - 2015-07-16 01:04 -0700
            Re: What practice can get speed improvement in C++? JiiPee <no@notvalid.com> - 2015-07-16 16:48 +0100
              Re: What practice can get speed improvement in C++? JiiPee <no@notvalid.com> - 2015-07-16 16:52 +0100
          Re: What practice can get speed improvement in C++? bartekltg <bartekltg@gmail.com> - 2015-07-16 13:23 +0200
            Re: What practice can get speed improvement in C++? Öö Tiib <ootiib@hot.ee> - 2015-07-16 06:54 -0700
              Re: What practice can get speed improvement in C++? bartekltg <bartekltg@gmail.com> - 2015-07-16 17:30 +0200
                Re: What practice can get speed improvement in C++? Öö Tiib <ootiib@hot.ee> - 2015-07-16 11:16 -0700
                  Re: What practice can get speed improvement in C++? bartekltg <bartekltg@gmail.com> - 2015-07-17 17:06 +0200
            Re: What practice can get speed improvement in C++? JiiPee <no@notvalid.com> - 2015-08-04 16:14 +0100
    Re: What practice can get speed improvement in C++? Victor Bazarov <v.bazarov@comcast.invalid> - 2015-07-14 20:29 -0400
      Re: What practice can get speed improvement in C++? woodbrian77@gmail.com - 2015-07-14 19:50 -0700
    Re: What practice can get speed improvement in C++? "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2015-07-15 05:07 +0200
    Re: What practice can get speed improvement in C++? Lőrinczy Zsigmond <nospam@for.me> - 2015-07-15 06:38 +0200
    Re: What practice can get speed improvement in C++? Paavo Helde <myfirstname@osa.pri.ee> - 2015-07-15 00:22 -0500
      Re: What practice can get speed improvement in C++? fl <rxjwg98@gmail.com> - 2015-07-16 04:34 -0700
        Re: What practice can get speed improvement in C++? Martijn van Buul <pino@dohd.org> - 2015-07-21 09:28 +0000
    Re: What practice can get speed improvement in C++? Juha Nieminen <nospam@thanks.invalid> - 2015-08-03 08:16 +0000
      Re: What practice can get speed improvement in C++? woodbrian77@gmail.com - 2015-08-03 13:48 -0700
        Re: What practice can get speed improvement in C++? Juha Nieminen <nospam@thanks.invalid> - 2015-08-04 08:21 +0000
          Re: What practice can get speed improvement in C++? Öö Tiib <ootiib@hot.ee> - 2015-08-04 08:07 -0700
          Re: What practice can get speed improvement in C++? woodbrian77@gmail.com - 2015-08-04 10:15 -0700
            Re: What practice can get speed improvement in C++? Bo Persson <bop@gmb.dk> - 2015-08-04 20:09 +0200
              Re: What practice can get speed improvement in C++? woodbrian77@gmail.com - 2015-08-04 12:38 -0700
                Re: What practice can get speed improvement in C++? Bo Persson <bop@gmb.dk> - 2015-08-05 17:03 +0200
                  Re: What practice can get speed improvement in C++? woodbrian77@gmail.com - 2015-08-05 23:32 -0700
              Re: What practice can get speed improvement in C++? Öö Tiib <ootiib@hot.ee> - 2015-08-05 03:55 -0700
            Re: What practice can get speed improvement in C++? Christopher Pisz <nospam@notanaddress.com> - 2015-08-04 14:09 -0500
              Re: What practice can get speed improvement in C++? woodbrian77@gmail.com - 2015-08-04 12:18 -0700
                Re: What practice can get speed improvement in C++? Christopher Pisz <nospam@notanaddress.com> - 2015-08-04 14:50 -0500
                Re: What practice can get speed improvement in C++? Öö Tiib <ootiib@hot.ee> - 2015-08-05 04:11 -0700
            Re: What practice can get speed improvement in C++? Juha Nieminen <nospam@thanks.invalid> - 2015-08-05 08:12 +0000
              Re: What practice can get speed improvement in C++? Martin Shobe <martin.shobe@yahoo.com> - 2015-08-05 08:53 -0500
              Re: What practice can get speed improvement in C++? woodbrian77@gmail.com - 2015-08-05 22:24 -0700
                Re: What practice can get speed improvement in C++? Ian Collins <ian-news@hotmail.com> - 2015-08-06 17:42 +1200
                  Re: What practice can get speed improvement in C++? woodbrian77@gmail.com - 2015-08-05 22:53 -0700
                    Re: What practice can get speed improvement in C++? Öö Tiib <ootiib@hot.ee> - 2015-08-06 00:20 -0700
                    Re: What practice can get speed improvement in C++? Christopher Pisz <nospam@notanaddress.com> - 2015-08-06 10:10 -0500
                  Re: What practice can get speed improvement in C++? Bo Persson <bop@gmb.dk> - 2015-08-06 17:29 +0200
                    Re: What practice can get speed improvement in C++? woodbrian77@gmail.com - 2015-08-06 09:38 -0700
                Re: What practice can get speed improvement in C++? Juha Nieminen <nospam@thanks.invalid> - 2015-08-10 08:25 +0000
    Re: What practice can get speed improvement in C++? pip010 <pip010@gmail.com> - 2015-08-03 04:22 -0700

Page 1 of 3  [1] 2 3  Next page →

#37076 — What practice can get speed improvement in C++?

Hi,

I am given the following question:



Experience in C/C++ code optimization for speed improvement.



I can only get the following answers:

1. Use reference to replace a direct parameter in function call;
2. Use register for some frequent variables;
3. Use assembly code to replace C code
4. Unroll a loop(?)


What is your opinion to the question?

Thanks,

[toc] | [next] | [standalone]

#37077

On Tue, 14 Jul 2015 16:53:30 -0700 (PDT), fl <rxjwg98@gmail.com>
wrote:

>Hi,
>
>I am given the following question:
>
>
>
>Experience in C/C++ code optimization for speed improvement.
>
>
>
>I can only get the following answers:
>
>1. Use reference to replace a direct parameter in function call;

Benefit is realized only when argument is a very large aggregate or
function is called very frequently.

>2. Use register for some frequent variables;

Compiler is free to ignore suggested storage class.

>3. Use assembly code to replace C code

No longer C or C++ and a maintenance nightmare.

>4. Unroll a loop(?)

Is this practical if the iteration count is not constant.

>What is your opinion to the question?

The best way of improving speed is to select or design a speed
efficient algorithm.  For a trivial example, computing factorials will
be faster in a loop than using recursion.

-- 
Remove del for email

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

#37083

On 15.07.2015 02:23, Barry Schwarz wrote:
> On Tue, 14 Jul 2015 16:53:30 -0700 (PDT), fl <rxjwg98@gmail.com>
> wrote:
>
>> Hi,
>>
>> I am given the following question:
>>
>>
>>
>> Experience in C/C++ code optimization for speed improvement.
>>
>>
>>
>> I can only get the following answers:
>>
>> 1. Use reference to replace a direct parameter in function call;
>
> Benefit is realized only when argument is a very large aggregate or
> function is called very frequently.


T& and const T& is quite good habit. In most cases it will
be used with containers. And if we use it for small types
(for example because we write const T & in template, and then
use if with 'int') compiler regardless will copy value.

>> 2. Use register for some frequent variables;
>
> Compiler is free to ignore suggested storage class.

Even worse.
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4296.pdf
D.2 register keyword [depr.register]
1 The use of the register keyword as a storage-class-specifier (7.1.1) 
is deprecated.



>> 3. Use assembly code to replace C code
>
> No longer C or C++ and a maintenance nightmare.

>> 4. Unroll a loop(?)
>
> Is this practical if the iteration count is not constant.
>
>> What is your opinion to the question?
>
> The best way of improving speed is to select or design a speed
> efficient algorithm.  For a trivial example, computing factorials will
> be faster in a loop than using recursion.

IMHO it shoud be threated as the same algorithm, just different
execution. I think changing recursion to loops, aside from
oblivious cases like factorial, is premature optimalization.
And in simple cases it change nothing, compiler will change
it for us:

c++ code:
int factorial (int x){
     if (x>1)  return x*factorial(x-1);
     else return x;
}

asm generated by gcc

     .type    _Z9factoriali, @function
_Z9factoriali:
.LFB1879:
     .cfi_startproc
     cmpl    $1, %edi
     jle    .L50
     movl    $1, %edx
     .p2align 4,,10
     .p2align 3
.L49:
     leal    -1(%rdi), %eax
     imull    %edi, %edx
     cmpl    $1, %eax
     movl    %eax, %edi
     jne    .L49
.L48:
     imull    %edx, %eax
     ret
.L50:
     movl    %edi, %eax
     movl    $1, %edx
     jmp    .L48


Just a simple loop;-)

bartekltg

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

#37096

On 15/07/2015 14:10, bartekltg wrote:
> On 15.07.2015 02:23, Barry Schwarz wrote:
>
>
>
>>
>>> What is your opinion to the question?
>>
>> The best way of improving speed is to select or design a speed
>> efficient algorithm.  For a trivial example, computing factorials will
>> be faster in a loop than using recursion.
>
> IMHO it shoud be threated as the same algorithm, just different
> execution. I think changing recursion to loops, aside from
> oblivious cases like factorial, is premature optimalization.
> And in simple cases it change nothing, compiler will change
> it for us:
>
> c++ code:
> int factorial (int x){
>     if (x>1)  return x*factorial(x-1);
>     else return x;
> }

factorial maybe not the best example as I would do it using constexpr:
constexpr long long fac(int k)
{
     return (k == 0) ? 1 : k * fac(k - 1);
}
giving an instant answer (calculated compile time).

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

#37098

On Thursday, 16 July 2015 07:01:03 UTC+3, JiiPee  wrote:
> On 15/07/2015 14:10, bartekltg wrote:
> > On 15.07.2015 02:23, Barry Schwarz wrote:
> >
> >
> >
> >>
> >>> What is your opinion to the question?
> >>
> >> The best way of improving speed is to select or design a speed
> >> efficient algorithm.  For a trivial example, computing factorials will
> >> be faster in a loop than using recursion.
> >
> > IMHO it shoud be threated as the same algorithm, just different
> > execution. I think changing recursion to loops, aside from
> > oblivious cases like factorial, is premature optimalization.
> > And in simple cases it change nothing, compiler will change
> > it for us:
> >
> > c++ code:
> > int factorial (int x){
> >     if (x>1)  return x*factorial(x-1);
> >     else return x;
> > }
> 
> factorial maybe not the best example as I would do it using constexpr:
> constexpr long long fac(int k)
> {
>      return (k == 0) ? 1 : k * fac(k - 1);
> }
> giving an instant answer (calculated compile time).

Yes, factorial is always terrible example. Even see your own code.
No checks of limits? You prefer to document that 'k > 20' and
'k < 0' are undefined behavior? People usually prefer (possibly
compile time) diagnostics to such documentation.

Even IEEE double precision can't contain 23! accurately and will
overflow at 171! so usefulness of factorial is rather narrowly
limited.

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

#37112

On 16/07/2015 09:04, Öö Tiib wrote:
> On Thursday, 16 July 2015 07:01:03 UTC+3, JiiPee  wrote:
>> c++ code:
>> int factorial (int x){
>>      if (x>1)  return x*factorial(x-1);
>>      else return x;
>> }
>> factorial maybe not the best example as I would do it using constexpr:
>> constexpr long long fac(int k)
>> {
>>       return (k == 0) ? 1 : k * fac(k - 1);
>> }
>> giving an instant answer (calculated compile time).
> Yes, factorial is always terrible example. Even see your own code.
> No checks of limits? You prefer to document that 'k > 20' and
> 'k < 0' are undefined behavior? People usually prefer (possibly
> compile time) diagnostics to such documentation.
>
> Even IEEE double precision can't contain 23! accurately and will
> overflow at 171! so usefulness of factorial is rather narrowly
> limited.

I did not mean it to be perfectly done (just the idea), but you can 
easily change it to something like:

constexpr long long unsafeFac(int k)
{
      return (k == 0) ? 1 : k * fac(k - 1);
}

constexpr long long fac(int k)
{
      return (k < 0 || k > 15) ?|||throw|  |exception()|  : unsafeFac(k);
}

Now it complains *compile* time the error (which is definitely better than a runtime version) if k is too big or too small.




>

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

#37113

On 16/07/2015 16:48, JiiPee wrote:
> On 16/07/2015 09:04, Öö Tiib wrote:
>> On Thursday, 16 July 2015 07:01:03 UTC+3, JiiPee  wrote:
>>> c++ code:
>>> int factorial (int x){
>>>      if (x>1)  return x*factorial(x-1);
>>>      else return x;
>>> }
>>> factorial maybe not the best example as I would do it using constexpr:
>>> constexpr long long fac(int k)
>>> {
>>>       return (k == 0) ? 1 : k * fac(k - 1);
>>> }
>>> giving an instant answer (calculated compile time).
>> Yes, factorial is always terrible example. Even see your own code.
>> No checks of limits? You prefer to document that 'k > 20' and
>> 'k < 0' are undefined behavior? People usually prefer (possibly
>> compile time) diagnostics to such documentation.
>>
>> Even IEEE double precision can't contain 23! accurately and will
>> overflow at 171! so usefulness of factorial is rather narrowly
>> limited.
>
> I did not mean it to be perfectly done (just the idea), but you can 
> easily change it to something like:
>
> constexpr long long unsafeFac(int k)
> {
>      return (k == 0) ? 1 : k * fac(k - 1);
> }
>
> constexpr long long fac(int k)
> {
>      return (k < 0 || k > 15) ?|||throw|  |exception()|  : unsafeFac(k);
> }

ups, letters messed up, should be:
constexpr long long fac(int k)
{
      return (k < 0 || k > 15) ? throw exception() : unsafeFac(k);
}


>
> Now it complains *compile* time the error (which is definitely better 
> than a runtime version) if k is too big or too small.
>

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

#37105

On 16.07.2015 06:00, JiiPee wrote:
> On 15/07/2015 14:10, bartekltg wrote:
>> On 15.07.2015 02:23, Barry Schwarz wrote:
>>
>>
>>
>>>
>>>> What is your opinion to the question?
>>>
>>> The best way of improving speed is to select or design a speed
>>> efficient algorithm.  For a trivial example, computing factorials will
>>> be faster in a loop than using recursion.
>>
>> IMHO it shoud be threated as the same algorithm, just different
>> execution. I think changing recursion to loops, aside from
>> oblivious cases like factorial, is premature optimalization.
>> And in simple cases it change nothing, compiler will change
>> it for us:
>>
>> c++ code:
>> int factorial (int x){
>>     if (x>1)  return x*factorial(x-1);
>>     else return x;
>> }
>
> factorial maybe not the best example as I would do it using constexpr:
> constexpr long long fac(int k)
> {
>      return (k == 0) ? 1 : k * fac(k - 1);
> }
> giving an instant answer (calculated compile time).

Sure...

main(){
	big_int x;
	cin>>c;
	cout<<fac(x);
}

;-)

Also, instead int we have for example arthmetic modulo 1 178 973 853,
so x can be too bit to put every possible answer in a array.

bartekltg

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

#37109

On Thursday, 16 July 2015 14:23:56 UTC+3, bartekltg  wrote:
> On 16.07.2015 06:00, JiiPee wrote:
> > On 15/07/2015 14:10, bartekltg wrote:
> >> On 15.07.2015 02:23, Barry Schwarz wrote:
> >>
> >>
> >>
> >>>
> >>>> What is your opinion to the question?
> >>>
> >>> The best way of improving speed is to select or design a speed
> >>> efficient algorithm.  For a trivial example, computing factorials will
> >>> be faster in a loop than using recursion.
> >>
> >> IMHO it shoud be threated as the same algorithm, just different
> >> execution. I think changing recursion to loops, aside from
> >> oblivious cases like factorial, is premature optimalization.
> >> And in simple cases it change nothing, compiler will change
> >> it for us:
> >>
> >> c++ code:
> >> int factorial (int x){
> >>     if (x>1)  return x*factorial(x-1);
> >>     else return x;
> >> }
> >
> > factorial maybe not the best example as I would do it using constexpr:
> > constexpr long long fac(int k)
> > {
> >      return (k == 0) ? 1 : k * fac(k - 1);
> > }
> > giving an instant answer (calculated compile time).
> 
> Sure...
> 
> main(){
> 	big_int x;
> 	cin>>c;
> 	cout<<fac(x);
> }
> 
> ;-)

My psychic abilities fail me ... what is here 'big_int' and what is 'c' 
and is the 'fac' here called with uninitialized argument? 


> Also, instead int we have for example arthmetic modulo 1 178 973 853,
> so x can be too bit to put every possible answer in a array.

Who suggested to put answers to array? In both functions 
all checks are missing but neither puts anything to array.

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

#37111

On 16.07.2015 15:54, Öö Tiib wrote:
> On Thursday, 16 July 2015 14:23:56 UTC+3, bartekltg  wrote:
>> On 16.07.2015 06:00, JiiPee wrote:
>>> On 15/07/2015 14:10, bartekltg wrote:
>>>> On 15.07.2015 02:23, Barry Schwarz wrote:
>>>>
>>>>
>>>>
>>>>>
>>>>>> What is your opinion to the question?
>>>>>
>>>>> The best way of improving speed is to select or design a speed
>>>>> efficient algorithm.  For a trivial example, computing factorials will
>>>>> be faster in a loop than using recursion.
>>>>
>>>> IMHO it shoud be threated as the same algorithm, just different
>>>> execution. I think changing recursion to loops, aside from
>>>> oblivious cases like factorial, is premature optimalization.
>>>> And in simple cases it change nothing, compiler will change
>>>> it for us:
>>>>
>>>> c++ code:
>>>> int factorial (int x){
>>>>      if (x>1)  return x*factorial(x-1);
>>>>      else return x;
>>>> }
>>>
>>> factorial maybe not the best example as I would do it using constexpr:
>>> constexpr long long fac(int k)
>>> {
>>>       return (k == 0) ? 1 : k * fac(k - 1);
>>> }
>>> giving an instant answer (calculated compile time).
>>
>> Sure...
>>
>> main(){
>> 	big_int x;
>> 	cin>>c;
>> 	cout<<fac(x);
>> }
>>
>> ;-)
>
> My psychic abilities fail me ... what is here 'big_int' and what is 'c'

A type. It can be uint64_t, uint1024_t from boost or relay
big integer from GMP. What do you like and need. It doesn't matter.

 > and is the 'fac' here called with uninitialized argument?

Sorry, a typo, should be
	cin>>x;

The point is, constexpr will help us when... the argument is constant;-)
In the other case, it is just a function.


>
>> Also, instead int we have for example arthmetic modulo 1 178 973 853,
>> so x can be too bit to put every possible answer in a array.
>
> Who suggested to put answers to array?In both functions


I just skip two post:

I: constexpr cant help with nonconst.
somebody: you can put answers in a small array, small because
21! is outside range of uint64_t.
I: for factorial yes, but not always. Look at modified problem 
(factorial modulo).

 > all checks are missing but neither puts anything to array.

It doesn't matter, computing "factorial of integer munbers in modulo
arithmetic" is quite artificial problem. This is only a simple example.

The point is: a simple recursion will be optimized to loop. For more
complex case it is hard. For example you can write quicksort as a loop
(using small stack for division points), it isn't even that hard, but
still most implementations (including standard library) use recursion.
Can you write extended euclidean algorithm (simple algorithm from
school:) as loop? I think of course you can, but it won't be pretty
and wou would waste too much time.

Of course, if you see something like factorial, you shouldn't event
think and write it as a loop. But in other case, wasting time on
rewriting algorithm as a loop I consider premature optimalization.

Of course, there is always an exception. For GPU you probably start
from removing all recursions ;-)

bartekltg

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

#37118

On Thursday, 16 July 2015 18:30:30 UTC+3, bartekltg  wrote:
> On 16.07.2015 15:54, Öö Tiib wrote:
> > On Thursday, 16 July 2015 14:23:56 UTC+3, bartekltg  wrote:
> >> On 16.07.2015 06:00, JiiPee wrote:
> >>> On 15/07/2015 14:10, bartekltg wrote:
> >>>> On 15.07.2015 02:23, Barry Schwarz wrote:
> >>>>
> >>>>
> >>>>
> >>>>>
> >>>>>> What is your opinion to the question?
> >>>>>
> >>>>> The best way of improving speed is to select or design a speed
> >>>>> efficient algorithm.  For a trivial example, computing factorials will
> >>>>> be faster in a loop than using recursion.
> >>>>
> >>>> IMHO it shoud be threated as the same algorithm, just different
> >>>> execution. I think changing recursion to loops, aside from
> >>>> oblivious cases like factorial, is premature optimalization.
> >>>> And in simple cases it change nothing, compiler will change
> >>>> it for us:
> >>>>
> >>>> c++ code:
> >>>> int factorial (int x){
> >>>>      if (x>1)  return x*factorial(x-1);
> >>>>      else return x;
> >>>> }
> >>>
> >>> factorial maybe not the best example as I would do it using constexpr:
> >>> constexpr long long fac(int k)
> >>> {
> >>>       return (k == 0) ? 1 : k * fac(k - 1);
> >>> }
> >>> giving an instant answer (calculated compile time).
> >>
> >> Sure...
> >>
> >> main(){
> >> 	big_int x;
> >> 	cin>>c;
> >> 	cout<<fac(x);
> >> }
> >>
> >> ;-)
> >
> > My psychic abilities fail me ... what is here 'big_int' and what is 'c'
> 
> A type. It can be uint64_t, uint1024_t from boost or relay
> big integer from GMP. What do you like and need. It doesn't matter.

Factorial algorithms for arbitrary precision integer are different beast
entirely. Those can take some time.

>  > and is the 'fac' here called with uninitialized argument?
> 
> Sorry, a typo, should be
> 	cin>>x;
> 
> The point is, constexpr will help us when... the argument is constant;-)
> In the other case, it is just a function.

Yes, that is how 'constexpr' functions work.

> >> Also, instead int we have for example arthmetic modulo 1 178 973 853,
> >> so x can be too bit to put every possible answer in a array.
> >
> > Who suggested to put answers to array?In both functions
> 
> 
> I just skip two post:
> 
> I: constexpr cant help with nonconst.
> somebody: you can put answers in a small array, small because
> 21! is outside range of uint64_t.
> I: for factorial yes, but not always. Look at modified problem 
> (factorial modulo).

Ok, indeed there are no silver bullets.

>  > all checks are missing but neither puts anything to array.
> 
> It doesn't matter, computing "factorial of integer munbers in modulo
> arithmetic" is quite artificial problem. This is only a simple example.

Ok.

> The point is: a simple recursion will be optimized to loop. For more
> complex case it is hard. For example you can write quicksort as a loop
> (using small stack for division points), it isn't even that hard, but
> still most implementations (including standard library) use recursion.
> Can you write extended euclidean algorithm (simple algorithm from
> school:) as loop? 

It has been usually described as simple loop? Pseudo-code from wikipedia:

    function extended_gcd(a, b)
        s := 0;    old_s := 1
        t := 1;    old_t := 0
        r := b;    old_r := a
        while r ≠ 0
            quotient := old_r div r
            (old_r, r) := (r, old_r - quotient * r)
            (old_s, s) := (s, old_s - quotient * s)
            (old_t, t) := (t, old_t - quotient * t)
        output "Bézout coefficients:", (old_s, old_t)
        output "greatest common divisor:", old_r
        output "quotients by the gcd:", (t, s)


> I think of course you can, but it won't be pretty
> and wou would waste too much time.

Might be you mix something up here ... it is simple algorithm.

> Of course, if you see something like factorial, you shouldn't event
> think and write it as a loop. But in other case, wasting time on
> rewriting algorithm as a loop I consider premature optimalization.

Depends how large factorials and how often are really need. 
Calculating 10,000,000! naively will take minutes and there are
ways to optimize that:
http://www.cs.berkeley.edu/~fateman/papers/factorial.pdf
Sorry it is lisp, but the major number crunchers tend to love lisp.

> Of course, there is always an exception. For GPU you probably start
> from removing all recursions ;-)

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

#37132

On 16.07.2015 20:16, Öö Tiib wrote:
>> A type. It can be uint64_t, uint1024_t from boost or relay
>> big integer from GMP. What do you like and need. It doesn't matter.
>
> Factorial algorithms for arbitrary precision integer are different beast
> entirely. Those can take some time.

I have never saw one.



>> The point is: a simple recursion will be optimized to loop. For more
>> complex case it is hard. For example you can write quicksort as a loop
>> (using small stack for division points), it isn't even that hard, but
>> still most implementations (including standard library) use recursion.
>> Can you write extended euclidean algorithm (simple algorithm from
>> school:) as loop?
>
> It has been usually described as simple loop? Pseudo-code from wikipedia:
>
>      function extended_gcd(a, b)
>          s := 0;    old_s := 1
>          t := 1;    old_t := 0
>          r := b;    old_r := a
>          while r ≠ 0
>              quotient := old_r div r
>              (old_r, r) := (r, old_r - quotient * r)
>              (old_s, s) := (s, old_s - quotient * s)
>              (old_t, t) := (t, old_t - quotient * t)
>          output "Bézout coefficients:", (old_s, old_t)
>          output "greatest common divisor:", old_r
>          output "quotients by the gcd:", (t, s)

Heh, dementia;-] I was sure wiki have recursive version,
what other source could I have used to write that (as an
argument for usefulness of tuple) ;-)

tuple<int, int, int> egcd(int a,int b)
{ //return  {gcd, x, y}; a*x+b*y = gcd;

	if (b==0)
		return make_tuple(a,1,0);
	else
	{
		int g,x,y;
		tie(g,y,x) = egcd(b,a%b);
		return make_tuple(g,x, y - ((a / b)) * x);
	}
}

Getting the first version from the second isn't as hard a I thought,
but still not trivial.


>> I think of course you can, but it won't be pretty
>> and wou would waste too much time.
>
> Might be you mix something up here ... it is simple algorithm.

No, its my fault, I didn't check and in my small math 'forfun'
library I used recursion.

>
>> Of course, if you see something like factorial, you shouldn't event
>> think and write it as a loop. But in other case, wasting time on
>> rewriting algorithm as a loop I consider premature optimalization.
>
> Depends how large factorials and how often are really need.
> Calculating 10,000,000! naively will take minutes and there are
> ways to optimize that:
> http://www.cs.berkeley.edu/~fateman/papers/factorial.pdf

Interesting sport. I like it ;-)


> Sorry it is lisp, but the major number crunchers tend to love lisp.

)))))))))))))))

If you work with number theory you have to have enough
"RAM" in brain to track all brackets without effort :)

bartekltg

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

#37326

On 16/07/2015 12:23, bartekltg wrote:
> On 16.07.2015 06:00, JiiPee wrote:
>> On 15/07/2015 14:10, bartekltg wrote:
>>> On 15.07.2015 02:23, Barry Schwarz wrote:
>>>
>>>
>>>
>>>>
>>>>> What is your opinion to the question?
>>>>
>>>> The best way of improving speed is to select or design a speed
>>>> efficient algorithm.  For a trivial example, computing factorials will
>>>> be faster in a loop than using recursion.
>>>
>>> IMHO it shoud be threated as the same algorithm, just different
>>> execution. I think changing recursion to loops, aside from
>>> oblivious cases like factorial, is premature optimalization.
>>> And in simple cases it change nothing, compiler will change
>>> it for us:
>>>
>>> c++ code:
>>> int factorial (int x){
>>>     if (x>1)  return x*factorial(x-1);
>>>     else return x;
>>> }
>>
>> factorial maybe not the best example as I would do it using constexpr:
>> constexpr long long fac(int k)
>> {
>>      return (k == 0) ? 1 : k * fac(k - 1);
>> }
>> giving an instant answer (calculated compile time).
>
> Sure...
>
> main(){
>     big_int x;
>     cin>>c;
>     cout<<fac(x);
> }
>
> ;-)
>

#include <iostream>
#include <exception>

constexpr long long unsafeFac(int k)
{
     return (k == 0) ? 1 : k * unsafeFac(k - 1);
}

constexpr long long fac(int k)
{
     return (k < 0 || k > 15) ? throw std::exception() : unsafeFac(k);
}

int main()
{
     uint64_t x;
     std::cin >> x;
     try
     {
         std::cout << fac(x);
     }
     catch (std::exception& e)
     {
         std::cerr << "factorial must be [0-15] " << e.what() << '\n';
     }

     return 0;
}

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

#37078

On 7/14/2015 7:53 PM, fl wrote:
> I am given the following question:
>
>
>
> Experience in C/C++ code optimization for speed improvement.

That's not a question.  AFAIK, a question starts with an auxiliary verb 
or with a special word like "where" or "who" or "what" or "how", and 
ends with a question mark ("?").  Here you have a directive or an 
incomplete sentence.

> I can only get the following answers:
>
> 1. Use reference to replace a direct parameter in function call;
> 2. Use register for some frequent variables;
> 3. Use assembly code to replace C code
> 4. Unroll a loop(?)
>
>
> What is your opinion to the question?

My opinion is that the questioner doesn't know the subject.

0.  There is no such thing as C/C++.

As for the choices for optimizing the speed, 1 and 4 are viable.  Using 
'register' is but a hint to the compiler.  Choice 3 seems nothing to do 
with C++ (the topic of this newsgroup).

V
-- 
I do not respond to top-posted replies, please don't ask

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

#37079

On Tuesday, July 14, 2015 at 7:29:51 PM UTC-5, Victor Bazarov wrote:
> On 7/14/2015 7:53 PM, fl wrote:
> > I am given the following question:
> >
> >
> >
> > Experience in C/C++ code optimization for speed improvement.
> 
> That's not a question.  AFAIK, a question starts with an auxiliary verb 
> or with a special word like "where" or "who" or "what" or "how", and 
> ends with a question mark ("?").  Here you have a directive or an 
> incomplete sentence.
> 
> > I can only get the following answers:
> >
> > 1. Use reference to replace a direct parameter in function call;
> > 2. Use register for some frequent variables;
> > 3. Use assembly code to replace C code
> > 4. Unroll a loop(?)
> >
> >
> > What is your opinion to the question?
> 
> My opinion is that the questioner doesn't know the subject.
> 
> 0.  There is no such thing as C/C++.
> 
> As for the choices for optimizing the speed, 1 and 4 are viable.  Using 
> 'register' is but a hint to the compiler.  Choice 3 seems nothing to do 
> with C++ (the topic of this newsgroup).
> 

There's an asm keyword, but I don't think it gets used
much.

The OP may wish to consider some containers in Boost
that outperform those in the C++ standard.

Brian
Ebenezer Enterprises - So far G-d has helped us.
http://webEbenezer.net

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

#37080

On 15-Jul-15 1:53 AM, fl wrote:
>
> I am given the following question:
>
> Experience in C/C++ code optimization for speed improvement.

I read that as, "list your experience with speed optimization for C and 
C++ code".


> I can only get the following answers:
>
> 1. Use reference to replace a direct parameter in function call;
> 2. Use register for some frequent variables;
> 3. Use assembly code to replace C code
> 4. Unroll a loop(?)
>
> What is your opinion to the question?

First, it's about particular programming languages, so presumably if you 
have experience with MEASURING, which is the most important thing, then 
you are expected to relate something of how you did that differently for 
the two mentioned languages, than for some other possible languages. I 
think you would be expected to mention some common tools and approaches 
for this, such as profiler, Unix-land `time` command, instrumenting code 
with timers and logging, and just dead reckoning (which can tell you if 
other ways are necessary). Regarding timers it would be nice if you know 
about the very limited resolution of C library time in Windows, and 
knowing about higher resolution C++11 timers, and about Boost timers.

Second, after measuring comes algorithmic considerations. Replacing an 
O(n^2) algorithm with an O(n) algorithm is common. E.g. I think it would 
count in a positive way if you mentioned how you once optimized some 
repeated string concatenation, perhaps in Java. Knowing about support 
for this in C++11 would be extra point.

Third, simple mechanical optimizations like you mention above. But your 
point (2), "Use register for some frequent variables", would count 
NEGATIVELY if I were to evaluate the answer, unless this is about an 
application to become part of a compiler development team (for ordinary 
app code you should leave that to the compiler: forcing it you're likely 
to do worse). On the other hand, knowing that the "register" keyword was 
deprecated in C++11 would be positive.


Cheers & hth.,

- Alf

-- 
Using Thunderbird as Usenet client, Eternal September as NNTP server.

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

#37081

Forget it. 'Smart tricks' won't give you more than a few percent.
Plus kindly remember:
Premature optimization is the root of all evil

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

#37082

fl <rxjwg98@gmail.com> wrote in news:aaa4556e-8239-412c-be9d-7308a1a2cbb6
@googlegroups.com:

> Hi,
> 
> I am given the following question:
> 
> 
> 
> Experience in C/C++ code optimization for speed improvement.
> 

This is not a question. If this is a requirement for a new hire, then I 
would think this means the ability to run a profiler like 
valgrind+callgrind, ability to interpret results and ability to modify the 
code to get rid of bottlenecks found this way.

hth
Paavo

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

#37106

On Tuesday, July 14, 2015 at 10:22:54 PM UTC-7, Paavo Helde wrote:
> fl <rx*****8@gmail.com> wrote in news:aaa4556e-8239-412c-be9d-7308a1a2cbb6
> @googlegroups.com:
> 
> > Hi,
> > 
> > I am given the following question:
> > 
> > 
> > 
> > Experience in C/C++ code optimization for speed improvement.
> > 
> 
> This is not a question. If this is a requirement for a new hire, then I 
> would think this means the ability to run a profiler like 
> valgrind+callgrind, ability to interpret results and ability to modify the 
> code to get rid of bottlenecks found this way.
> 
> hth
> Paavo

Thanks for the replies. The question is from a new hire. The position is about
programming for embedded RTOS system, although the code may be for the test
 bench (less embedded in some sense). I code a lot at the lower level. It is 
the first time I know valgrind+callgrind. 

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

#37175

* fl:
> On Tuesday, July 14, 2015 at 10:22:54 PM UTC-7, Paavo Helde wrote:
>> fl <rx*****8@gmail.com> wrote in news:aaa4556e-8239-412c-be9d-7308a1a2cbb6
>> @googlegroups.com:
>> > 
>> > Experience in C/C++ code optimization for speed improvement.
>> > 
>> 
>> This is not a question. If this is a requirement for a new hire, then I 
>> would think this means the ability to run a profiler like 
>> valgrind+callgrind, ability to interpret results and ability to modify the 
>> code to get rid of bottlenecks found this way.
>
> Thanks for the replies. The question is from a new hire. The position is
> about programming for embedded RTOS system, although the code may be for the
> test bench (less embedded in some sense). I code a lot at the lower level. It
> is the first time I know valgrind+callgrind. 

Programming for an RTOS requires a different mindset every now and then, 
depending on the real-time restrictions and the platform. For example, 
the *maximum* runtime requirements of an algorithm is often more important
than the *average* requirement, because the first is a limiting factor on
response time. Available memory and processor resources often don't scale as
easily, and some C++ features (or parts of the standard library) just don't
combine well with a hard real-time behaviour. 

Often, the mere fact that you use an RTOS has implications beyond the 
obvious. On modern desktop and server operating systems, a stack overflow 
is almost unheard of, but on RTOS systems, stack space is usually *very*
limited, so you need to be aware of deeply recursive routines, or large objects
placed on the stack. Deadlocks are often more fatal; if your browser stalls for
a couple of seconds it is annoying; if the ECU of a car stalls it can lead to a
deadly accident. 

Granted, this is all about "how to write your algorithm" and "what pitfalls
to avoid" rather than "what tricks to use to get a perceived boost", and
personally, I don't think "speed improvement" covers anything of the required
skills to sucessfully handle real-time programming.

-- 
Martijn van Buul - pino@dohd.org 

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

Page 1 of 3  [1] 2 3  Next page →

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

csiph-web