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

Groups > comp.lang.c > #17996 > unrolled thread

Which operation is more expensive?(a <= b and a != 0)

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

Contents

  Which operation is more expensive?(a <= b and a != 0) Ping Cheu <nospam@nospam.com> - 2012-02-27 21:24 +0000
    Re: Which operation is more expensive?(a <= b and a != 0) James Kuyper <jameskuyper@verizon.net> - 2012-02-27 16:47 -0500
      Re: Which operation is more expensive?(a <= b and a != 0) Michael Angelo Ravera <maravera@prodigy.net> - 2012-03-07 04:23 -0800
    Re: Which operation is more expensive?(a <= b and a != 0) Keith Thompson <kst-u@mib.org> - 2012-02-27 13:54 -0800
      Re: Which operation is more expensive?(a <= b and a != 0) falk@rahul.net (Edward A. Falk) - 2012-02-27 23:47 +0000
    Re: Which operation is more expensive?(a <= b and a != 0) Shao Miller <sha0.miller@gmail.com> - 2012-02-27 16:57 -0500
      Re: Which operation is more expensive?(a <= b and a != 0) Stephen Sprunk <stephen@sprunk.org> - 2012-02-28 13:43 -0600
    Re: Which operation is more expensive?(a <= b and a != 0) Richard Damon <news.x.richarddamon@xoxy.net> - 2012-02-27 16:58 -0500
    Re: Which operation is more expensive?(a <= b and a != 0) Malcolm McLean <malcolm.mclean5@btinternet.com> - 2012-02-27 13:55 -0800
      Re: Which operation is more expensive?(a <= b and a != 0) Kenneth Brody <kenbrody@spamcop.net> - 2012-03-03 15:58 -0500
    Re: Which operation is more expensive?(a <= b and a != 0) Keith Thompson <kst-u@mib.org> - 2012-02-27 14:17 -0800
    Re: Which operation is more expensive?(a <= b and a != 0) Barry Schwarz <schwarz45@yahoo.com> - 2012-02-27 14:52 -0800
      Re: Which operation is more expensive?(a <= b and a != 0) Peter Nilsson <airia@acay.com.au> - 2012-02-27 18:16 -0800
        Re: Which operation is more expensive?(a <= b and a != 0) qarnos <darrencubitt@gmail.com> - 2012-02-29 12:20 -0800
        Re: Which operation is more expensive?(a <= b and a != 0) Barry Schwarz <schwarzb@dqel.com> - 2012-03-13 22:07 -0700
    Re: Which operation is more expensive?(a <= b and a != 0) Kaz Kylheku <kaz@kylheku.com> - 2012-02-28 00:56 +0000
    Re: Which operation is more expensive?(a <= b and a != 0) Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2012-02-27 19:18 -0700
      Re: Which operation is more expensive?(a <= b and a != 0) China Blue Sea <chine.bleu@yahoo.com> - 2012-02-27 18:30 -0800
    Re: Which operation is more expensive?(a <= b and a != 0) "BartC" <bc@freeuk.com> - 2012-02-28 13:22 +0000
    Re: Which operation is more expensive?(a <= b and a != 0) Stephen Sprunk <stephen@sprunk.org> - 2012-02-28 13:38 -0600
    Re: Which operation is more expensive?(a <= b and a != 0) jgk@panix.com (Joe keane) - 2012-02-28 22:35 +0000
      Re: Which operation is more expensive?(a <= b and a != 0) Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2012-03-03 01:36 +0200
        Re: Which operation is more expensive?(a <= b and a != 0) jgk@panix.com (Joe keane) - 2012-03-05 20:03 +0000
          Re: Which operation is more expensive?(a <= b and a != 0) Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2012-03-12 01:08 +0200
            Re: Which operation is more expensive?(a <= b and a != 0) Harald van Dijk <haraldvdijk@gmail.com> - 2012-03-12 00:05 -0700
              Re: Which operation is more expensive?(a <= b and a != 0) James Kuyper <jameskuyper@verizon.net> - 2012-03-12 08:59 -0400
                Re: Which operation is more expensive?(a <= b and a != 0) gwowen <gwowen@gmail.com> - 2012-03-12 06:24 -0700
                  Re: Which operation is more expensive?(a <= b and a != 0) James Kuyper <jameskuyper@verizon.net> - 2012-03-12 10:13 -0400
                    Re: Which operation is more expensive?(a <= b and a != 0) Keith Thompson <kst-u@mib.org> - 2012-03-12 10:44 -0700
                    Re: Which operation is more expensive?(a <= b and a != 0) Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2012-03-13 17:12 +0200
            Re: Which operation is more expensive?(a <= b and a != 0) Keith Thompson <kst-u@mib.org> - 2012-03-12 11:20 -0700

Page 1 of 2  [1] 2  Next page →

#17996 — Which operation is more expensive?(a <= b and a != 0)

From a web-site that teaches optimization for c,

I saw bellow optimization rule.

    int fact1_func (int n)
    {
        int i, fact = 1;
        for (i = 1; i <= n; i++)
          fact *= i;
        return(fact);
    }

    int fact2_func(int n)
    {
        int i, fact = 1;
        for (i = n; i != 0; i--)
           fact *= i;
        return(fact);
    }

The author say 'fact2_func' is faster than 'fact1_func'.

That means 'i <= n' operation is more expensive than 'i != 0'.

So far, I thought all condition statements have same cost.

So I want to know the cost of condition states from the fast one to slow 
one.

Can anyone tell me? 

[toc] | [next] | [standalone]

#17997

On 02/27/2012 04:24 PM, Ping Cheu wrote:
> From a web-site that teaches optimization for c,
> 
> I saw bellow optimization rule.
> 
>     int fact1_func (int n)
>     {
>         int i, fact = 1;
>         for (i = 1; i <= n; i++)
>           fact *= i;
>         return(fact);
>     }
> 
>     int fact2_func(int n)
>     {
>         int i, fact = 1;
>         for (i = n; i != 0; i--)
>            fact *= i;
>         return(fact);
>     }
> 
> The author say 'fact2_func' is faster than 'fact1_func'.
> 
> That means 'i <= n' operation is more expensive than 'i != 0'.
> 
> So far, I thought all condition statements have same cost.
> 
> So I want to know the cost of condition states from the fast one to slow 
> one.
> 
> Can anyone tell me? 

Yes, someone can tell you. And the answers will be different on
different machines, and for different compilers on the same machine, and
for different optimization levels for the same compiler on the same
machine. The timings will be different depending upon the nature of the
surrounding code, which will affect how effective the compiler's
optimization will be. Finally, and most importantly, if there are two
different but logically equivalent ways of writing your code, the best
modern compilers will, at high optimization levels, re-write the slower
one so that it is implemented that same way as the faster one. As a
result, if you perform a test, you may find that the two loops execute
equally fast.

In a language like C, which is meant to be widely portable and which
gives you very poor control over the generated machine code, it's a
waste of time to acquire that kind of knowledge. It makes more sense to
worry about such things when you're writing assembly code, where you
have more precise control over what the generated machine code will look
like, and a corresponding responsibility to acquire precisely that kind
of information for the particular machine you're writing the assembly
code for. You don't expect such code to be portable, so you don't have
to worry about the fact that the answers will be different on different
machines.

In C, it makes more sense to worry about higher-level issues - make sure
your algorithm doesn't waste time doing the same thing twice (or worse,
the same thing N times, for N very large). Make sure it only does what
needs to be done, and doesn't waste time and source code doing things
that don't need to be done. Make sure your algorithm is correct, and
most important of all, write your code so that it is clearly a correct
implementation of the algorithm. Let the compiler worry about making it
fast.

If and only if you find your program has a actual speed problem, run a
profiler to find out where it is wasting the most time - it's almost
never the same place that you thought it was, and it's almost never
involves issues like the loop condition you're worrying about here. Keep
in mind that the changes you make to speed it up for the current
platform could make it run slower on some other platform - so you should
always be very reluctant to make such changes.

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

#18283

On Monday, February 27, 2012 1:47:13 PM UTC-8, James Kuyper wrote:
> On 02/27/2012 04:24 PM, Ping Cheu wrote:
> > From a web-site that teaches optimization for c,
> > 
> > I saw bellow optimization rule.
> > 
> >     int fact1_func (int n)
> >     {
> >         int i, fact = 1;
> >         for (i = 1; i <= n; i++)
> >           fact *= i;
> >         return(fact);
> >     }
> > 
> >     int fact2_func(int n)
> >     {
> >         int i, fact = 1;
> >         for (i = n; i != 0; i--)
> >            fact *= i;
> >         return(fact);
> >     }
> > 
> > The author say 'fact2_func' is faster than 'fact1_func'.
> > 
> > That means 'i <= n' operation is more expensive than 'i != 0'.
> > 
> > So far, I thought all condition statements have same cost.
> > 
> > So I want to know the cost of condition states from the fast one to slow 
> > one.
> > 
> > Can anyone tell me? 
> 
> Yes, someone can tell you. And the answers will be different on
> different machines, and for different compilers on the same machine, and
> for different optimization levels for the same compiler on the same
> machine. The timings will be different depending upon the nature of the
> surrounding code, which will affect how effective the compiler's
> optimization will be. Finally, and most importantly, if there are two
> different but logically equivalent ways of writing your code, the best
> modern compilers will, at high optimization levels, re-write the slower
> one so that it is implemented that same way as the faster one. As a
> result, if you perform a test, you may find that the two loops execute
> equally fast.
> 
> In a language like C, which is meant to be widely portable and which
> gives you very poor control over the generated machine code, it's a
> waste of time to acquire that kind of knowledge. It makes more sense to
> worry about such things when you're writing assembly code, where you
> have more precise control over what the generated machine code will look
> like, and a corresponding responsibility to acquire precisely that kind
> of information for the particular machine you're writing the assembly
> code for. You don't expect such code to be portable, so you don't have
> to worry about the fact that the answers will be different on different
> machines.
> 
> In C, it makes more sense to worry about higher-level issues - make sure
> your algorithm doesn't waste time doing the same thing twice (or worse,
> the same thing N times, for N very large). Make sure it only does what
> needs to be done, and doesn't waste time and source code doing things
> that don't need to be done. Make sure your algorithm is correct, and
> most important of all, write your code so that it is clearly a correct
> implementation of the algorithm. Let the compiler worry about making it
> fast.
> 
> If and only if you find your program has a actual speed problem, run a
> profiler to find out where it is wasting the most time - it's almost
> never the same place that you thought it was, and it's almost never
> involves issues like the loop condition you're worrying about here. Keep
> in mind that the changes you make to speed it up for the current
> platform could make it run slower on some other platform - so you should
> always be very reluctant to make such changes.

... what he said, but you can write the factorial function better than either of these. 

1) You have no protection of overflow in either of the above examples. 
2) The result isn't correct or useful for negative inputs
3) If you wanted it to be really fast, you'd use a const table (with the table in code space)
4) Write it like this and save a whole iteration (skipping a multiply by what you know will be one and the end of the calculation):
    int fact2_func(int n)
    {
        int i, fact = 1;
         for (i = n; i > 1; i--)
            fact *= i;
         return(fact);
    }

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

#17998

Ping Cheu <nospam@nospam.com> writes:
> From a web-site that teaches optimization for c,
>
> I saw bellow optimization rule.
>
[snip]
>
> The author say 'fact2_func' is faster than 'fact1_func'.
>
> That means 'i <= n' operation is more expensive than 'i != 0'.
>
> So far, I thought all condition statements have same cost.
>
> So I want to know the cost of condition states from the fast one to slow 
> one.
>
> Can anyone tell me? 

No.

The C language standard says absolutely nothing about the relative
performance of different operations.

It may be the case that "i <= n" will be more expensive than "i !=0"
on some particular system.  On another system, they might take
the same time, or "i != 0" might even be more expensive.

If I had to guess, I'd say that "i != 0" is likely to be slightly
faster, or at least no slower, since it only has to load one variable
rather than two before doing the comparison.

On the other hand, a decent optimizing compiler might generate equally
good code for both.

But *I don't have to guess*.  I can measure it -- which is what you
should do if the performance matters.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
    Will write code for food.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

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

#18008

In article <ln8vjo7xiy.fsf@nuthaus.mib.org>,
Keith Thompson  <kst-u@mib.org> wrote:
>
>On the other hand, a decent optimizing compiler might generate equally
>good code for both.
>
>But *I don't have to guess*.  I can measure it -- which is what you
>should do if the performance matters.

Best answer.  But bear in mind that the result will depend on the cpu
architecture and compiler used.

I can say that for gcc 4.4.3 on x86, with optimization level 4, the
"i <= n" variant generated one more instruction in the inner loop than the
"i != 0" variant.

Now with caching and other hardware optimizations, it might not make a
difference, but you'd have to run timing tests to be sure.

-- 
	-Ed Falk, falk@despams.r.us.com
	http://thespamdiaries.blogspot.com/

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

#17999

On 2/27/2012 16:24, Ping Cheu wrote:
>  From a web-site that teaches optimization for c,
>

Please share the source.  With no follow-up to your last thread, the 
probability of this happening seems low.

> I saw bellow optimization rule.
>
>      int fact1_func (int n)
>      {
>          int i, fact = 1;
>          for (i = 1; i<= n; i++)
>            fact *= i;
>          return(fact);
>      }
>
>      int fact2_func(int n)
>      {
>          int i, fact = 1;
>          for (i = n; i != 0; i--)
>             fact *= i;
>          return(fact);
>      }
>
> The author say 'fact2_func' is faster than 'fact1_func'.
>
> That means 'i<= n' operation is more expensive than 'i != 0'.
>
> So far, I thought all condition statements have same cost.
>
> So I want to know the cost of condition states from the fast one to slow
> one.
>
> Can anyone tell me?

Please don't take a claim out of context and suppose it applies 
universally.  Please share the context.

C doesn't define "the speed" of evaluation of anything that I'm aware 
of, so my answer would be "no, 'fact2_func' is not defined to always be 
faster than 'fact1_func'."

However, if you consider that 'i <= n' involves _two_ reads and 'i != 0' 
involves _one_ read, then unless you can read both at the same time or 
deduce an optimization, 2 reads > 1 read.

Enjoy.

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

#18040

On 27-Feb-12 15:57, Shao Miller wrote:
> However, if you consider that 'i <= n' involves _two_ reads and 'i != 0'
> involves _one_ read, then unless you can read both at the same time or
> deduce an optimization, 2 reads > 1 read.

True, but in most cases a modern CPU will be able to hoist both loads
far above the comparison, if both aren't _already_ in registers, so that
effect _should_ be irrelevant.

S

-- 
Stephen Sprunk         "God does not play dice."  --Albert Einstein
CCIE #3723         "God is an inveterate gambler, and He throws the
K5SSS        dice at every possible opportunity." --Stephen Hawking

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

#18000

On 2/27/12 4:24 PM, Ping Cheu wrote:
> From a web-site that teaches optimization for c,
> 
> I saw bellow optimization rule.
> 
>     int fact1_func (int n)
>     {
>         int i, fact = 1;
>         for (i = 1; i <= n; i++)
>           fact *= i;
>         return(fact);
>     }
> 
>     int fact2_func(int n)
>     {
>         int i, fact = 1;
>         for (i = n; i != 0; i--)
>            fact *= i;
>         return(fact);
>     }
> 
> The author say 'fact2_func' is faster than 'fact1_func'.
> 
> That means 'i <= n' operation is more expensive than 'i != 0'.
> 
> So far, I thought all condition statements have same cost.
> 
> So I want to know the cost of condition states from the fast one to slow 
> one.
> 
> Can anyone tell me? 

The difference is that the second compares to a constant 0, which MAY be
faster than comparing to a variable n.

Many processors can quickly test the value of a register to see if it is
negative or positive (sign bit test) or zero or non-zero without running
an explicit comparison operation.

Note that the second version will behave differently in the case of n<0,
likely taking a significantly longer time than the first, finally
returning a value that is probably 0 (after numerous instances of
undefined behavior of overflow), while the first will rapidly return 1.

If you change the second to use i > 0, they will both return rapidly,
but you have possibly lost some of the advantage, as this relationship
is less often a built in automatic, but may still be slightly faster due
to the constant 0 instead of the variable n being used.

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

#18001

On Feb 27, 9:24 pm, Ping Cheu <nos...@nospam.com> wrote:
>
> Can anyone tell me?
>
If we say if(x != 0) then the processor can load x into a register,
and do a comparison for zero. If we say if(x < n) then the processor
needs to load x and n into registers, then do a subtraction, then look
for carry. So the first test is simpler. Whether it is actually faster
or not depends on whether the circuitry that would have done the more
complex calculation is otherwise employed, or is sitting idle. Often
on modern processors xand n will usually both be in registers anyway,
and an inequality compare completes in exactly as many clock cycles as
a test against zero.

--
Basic Algorithms - a second book of C
http://www.malcolmmclean.site11.com/www

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

#18162

On 2/27/2012 4:55 PM, Malcolm McLean wrote:
> On Feb 27, 9:24 pm, Ping Cheu<nos...@nospam.com>  wrote:
>>
>> Can anyone tell me?
>>
> If we say if(x != 0) then the processor can load x into a register,
> and do a comparison for zero. If we say if(x<  n) then the processor
> needs to load x and n into registers, then do a subtraction, then look
> for carry.

"Needs to"?  There is no "needs to".  Suppose the CPU has memory-to-memory 
comparison operations?  Or, quite possibly, both x and n are already in 
registers.  And certainly "needs to ... do a subtraction" is quite a bit of 
a stretch, given that it's more likely "compare register A to register B".

> So the first test is simpler. Whether it is actually faster
> or not depends on whether the circuitry that would have done the more
> complex calculation is otherwise employed, or is sitting idle. Often
> on modern processors xand n will usually both be in registers anyway,
> and an inequality compare completes in exactly as many clock cycles as
> a test against zero.

I think James Kuyper said it best in his reply.

The short answer is "it depends", and "if it really matters to you, you need 
to test it on your implementation to find out which one is 'better' in your 
particular case".

-- 
Kenneth Brody

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

#18002

Ping Cheu <nospam@nospam.com> writes:
> From a web-site that teaches optimization for c,
>
> I saw bellow optimization rule.
>
>     int fact1_func (int n)
>     {
>         int i, fact = 1;
>         for (i = 1; i <= n; i++)
>           fact *= i;
>         return(fact);
>     }
>
>     int fact2_func(int n)
>     {
>         int i, fact = 1;
>         for (i = n; i != 0; i--)
>            fact *= i;
>         return(fact);
>     }
>
> The author say 'fact2_func' is faster than 'fact1_func'.
[...]

One other thing: if int is 32 bits, both functions will overflow
for any argument value greater than 12.  If int is 64 bits (or if
you modify the functions to return a 64-bit result), it overflows
for arguments greater than 20.

If you're not calling these functions many many times (thousands or
millions), their performance isn't going to matter.  And if you are,
the fix is to cache the results so you don't have to recompute the
same results; a table lookup would be a good approach.

Don't waste your time optimizing code whose performance doesn't matter.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
    Will write code for food.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

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

#18004

On Feb 27, 3:24 pm, Ping Cheu <nos...@nospam.com> wrote:
> From a web-site that teaches optimization for c,
>
> I saw bellow optimization rule.
>
>     int fact1_func (int n)
>     {
>         int i, fact = 1;
>         for (i = 1; i <= n; i++)
>           fact *= i;
>         return(fact);
>     }
>
>     int fact2_func(int n)
>     {
>         int i, fact = 1;
>         for (i = n; i != 0; i--)
>            fact *= i;
>         return(fact);
>     }
>
> The author say 'fact2_func' is faster than 'fact1_func'.
>
> That means 'i <= n' operation is more expensive than 'i != 0'.
>
> So far, I thought all condition statements have same cost.
>
> So I want to know the cost of condition states from the fast one to slow
> one.
>
> Can anyone tell me?

On at least one system, there are machine intsructions that will set
processor flags for an arithmetic operation that indicate whether the
result is positive, negative, or zero.  On that machine, the i--
method will not require a comparison.  The i++ method will always
require a comparison to n.

The same system has instructions that can test a value against zero
faster than a test against an arbitrary constant.

In the general case, tha author is merely displaying is lack of
experience and imagination.

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

#18014

Barry Schwarz <schwar...@yahoo.com> wrote:
> Ping Cheu <nos...@nospam.com> wrote:
> > I saw bellow optimization rule.
> >         for (i = 1; i <= n; i++)
...
> >         for (i = n; i != 0; i--)
...
> In the general case, tha author is merely displaying is
> lack of experience and imagination.

I suppose BWK was demonstrating the same lack of experience and
imagination when he wrote Exercise 2.9 in K&R2, implying...

  for (b = 0; x; x &= x - 1)
    b++;

...was always faster than...

  for (b = 0; x != 0; x >>= 1)
    if (x & 01)
      b++;

These sorts of tricks are still relevant, just considerably
less significant.

--
Peter

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

#18072

On Feb 28, 1:16 pm, Peter Nilsson <ai...@acay.com.au> wrote:
>
> I suppose BWK was demonstrating the same lack of experience and
> imagination when he wrote Exercise 2.9 in K&R2, implying...
>
>   for (b = 0; x; x &= x - 1)
>     b++;
>
> ...was always faster than...
>
>   for (b = 0; x != 0; x >>= 1)
>     if (x & 01)
>       b++;
>

These are completely different algorithms for computing the same
result. In this case, the "fast" version will, for most inputs,
perform fewer fundamental operations than the "slow version". In fact,
in the *worst case scenario* it will perform exactly the same number
of operations as the "slow" version. This is a good example of how to
optimise *an algorithm*.

In the OP, the number of operations is identical (for n >= 0, at
least) - the only difference is a semantic one over how the loop
condition is evaluated. It is an attempt to influence the machine code
generated by the compiler. It may well work, but to say it is
unconditionally "faster" is misleading at best.

It is grossly unfair to try to draw an equivalence between the two.

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

#18745

On Mon, 27 Feb 2012 18:16:59 -0800 (PST), Peter Nilsson
<airia@acay.com.au> wrote:

>Barry Schwarz <schwar...@yahoo.com> wrote:
>> Ping Cheu <nos...@nospam.com> wrote:
>> > I saw bellow optimization rule.
>> >         for (i = 1; i <= n; i++)
>...
>> >         for (i = n; i != 0; i--)
>...
>> In the general case, tha author is merely displaying is
>> lack of experience and imagination.
>
>I suppose BWK was demonstrating the same lack of experience and
>imagination when he wrote Exercise 2.9 in K&R2, implying...
>
>  for (b = 0; x; x &= x - 1)
>    b++;
>
>...was always faster than...
>
>  for (b = 0; x != 0; x >>= 1)
>    if (x & 01)
>      b++;
>
>These sorts of tricks are still relevant, just considerably
>less significant.

Since BWK started the discussion with the caveat "In a two's
complement system ...", he specifically avoided making a general
assertion.  Furthermore, he only claimed it was useful for writing a
faster bit counting function, not that it had some property of
universal superiority.

It wouldn't surprise me if the trick had other applications also.  It
also wouldn't surprise me if there were other non-obvious tricks which
could be proven to increase efficiency.

But neither of those points has anything to do with my comment that
the author of the original assertion that started this thread was
making global pronouncements without any supporting basis.

-- 
Remove del for email

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

#18013

On 2012-02-27, Ping Cheu <nospam@nospam.com> wrote:
> From a web-site that teaches optimization for c,
>
> I saw bellow optimization rule.
>
>     int fact1_func (int n)
>     {
>         int i, fact = 1;
>         for (i = 1; i <= n; i++)
>           fact *= i;
>         return(fact);
>     }

Your function will invoke multiplication overflow (undefined behavior) for
values of n which are not that large.

>     int fact2_func(int n)
>     {
>         int i, fact = 1;
>         for (i = n; i != 0; i--)
>            fact *= i;
>         return(fact);
>     }
>
> The author say 'fact2_func' is faster than 'fact1_func'.

Worrying about this is pointless because the factorial function grows so fast
relative to the constrained range of int, that you cannot have a significantly
large domain value of n.

This also means it is practical to do it with a table lookup:

  int fact3_func(int n)
  {
    /* This table is going to be quite small: */
    static int fact_table[] = { 1, 1, 2, 24, 120, ...}

    if (n >= 0 && n < sizeof fact_table / sizeof *fact_table)
      return fact_table[n];

    /* trouble: what to do? */
    return -1;
  }

Before you worry about how the direction of the loop affects machine
cycles, consider the limiting circumstances and the algorithm.

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

#18015

Ping Cheu <nospam@nospam.com> writes:

> From a web-site that teaches optimization for c,
>
> I saw bellow optimization rule.
>
>     int fact1_func (int n)
>     {
>         int i, fact = 1;
>         for (i = 1; i <= n; i++)
>           fact *= i;
>         return(fact);
>     }
>
>     int fact2_func(int n)
>     {
>         int i, fact = 1;
>         for (i = n; i != 0; i--)
>            fact *= i;
>         return(fact);
>     }
>
> The author say 'fact2_func' is faster than 'fact1_func'.
>
> That means 'i <= n' operation is more expensive than 'i != 0'.
>
> So far, I thought all condition statements have same cost.
>
> So I want to know the cost of condition states from the fast one to slow 
> one.
>
> Can anyone tell me? 

For compilers and architectures for which this is true, the reason is
that the condition codes are set as a side effect of the decrement, so
you don't need to actually perform the comparison in the decrement
version.

It isn't true for all architectures because (1) not all architectures
let you get away with skipping the comparison, and (2) many
implementations will manage to combine the increment, compare, and
branch in u-ops that get executed out of order and don't end up taking
any extra time.

It isn't true for all compilers because (assuming it's true for the
architecture in the first place!) the compiler may figure out it can run
the loop backwards all by itself.

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

#18016

> > That means 'i <= n' operation is more expensive than 'i != 0'.
> >
> > So far, I thought all condition statements have same cost.
> >
> > So I want to know the cost of condition states from the fast one to slow 
> > one.
> >
> > Can anyone tell me? 
> 
> For compilers and architectures for which this is true, the reason is
> that the condition codes are set as a side effect of the decrement, so
> you don't need to actually perform the comparison in the decrement
> version.

Merely posting this will consume more compute resource on millions of machine 
around the world than will be saved by the 'efficient' solution.

The best solution is the one you can back to 14 months later and think, yeah, 
that's what I was doing way back when.

-- 
My name Indigo Montoya.      |    R'lyeh 38o57'6.5''S 102o51'16''E.
You flamed my father.        |       I'm whoever you want me to be.
Prepare to be spanked.       |  Annoying Usenet one post at a time.
Stop posting that!           |    At least I can stay in character.

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

#18031

"Ping Cheu" <nospam@nospam.com> wrote in message
news:jigsb4$rdc$1@speranza.aioe.org...
> From a web-site that teaches optimization for c,
>
> I saw bellow optimization rule.
>
>    int fact1_func (int n)
>    {
>        int i, fact = 1;
>        for (i = 1; i <= n; i++)
>          fact *= i;
>        return(fact);
>    }

On one test, your fact2_func took about 1/3 less time to execute than
fact1_func.

However fact1_func can be optimised a little: starting at i=2 for example.

> That means 'i <= n' operation is more expensive than 'i != 0'.

> So far, I thought all condition statements have same cost.

'i<=n' involves two variables. 'i!=0' involves one variable and a constant,
which being zero might not be needed at all; it's equivalent to just 'i',
which is one variable and no constants.

In general the cost depends on how many variable and constant terms there
are, with constants being a little more efficient than variables. But in
practice it depends on so many other factors (the types involved for
example), that it's difficult to say.

And you don't really know what the compiler might do; it's possible that any
calls to one of these functions with a constant argument will be optimised
out completely so the issue doesn't even come up.

-- 
Bartc 

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

#18039

On 27-Feb-12 15:24, Ping Cheu wrote:
> From a web-site that teaches optimization for c,
> 
> I saw bellow optimization rule.
> ...
> The author say 'fact2_func' is faster than 'fact1_func'.
> 
> That means 'i <= n' operation is more expensive than 'i != 0'.

The Standard does not guarantee the performance of _any_ operation; at
best, such "optimizations" are only valid for a particular
implementation.  They may (and often do) vary by platform, compiler,
optimization levels, and command-line options.  Unless the web site in
question specifies the exact implementation he is using, such advice is
worthless, as the exact opposite may be true of the implementation _you_
are using.

> So far, I thought all condition statements have same cost.

That is unlikely to be exactly true, but the difference is likely
immeasurable on most implementations.  At worst, any difference should
be completely insignificant to the performance of your program as a whole.

> Can anyone tell me? 

The only way you can find out is to test _your implementation_ yourself.
 However, the answer isn't likely to matter.

Concentrate on writing clear and correct code, and let the compiler
worry about making it fast.  If _actual measurement_ shows your program
isn't fast enough, such tricks are unlikely to help; spend your time
finding a better algorithm, not optimizing a poor algorithm.

S

-- 
Stephen Sprunk         "God does not play dice."  --Albert Einstein
CCIE #3723         "God is an inveterate gambler, and He throws the
K5SSS        dice at every possible opportunity." --Stephen Hawking

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

Page 1 of 2  [1] 2  Next page →

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

csiph-web