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

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

Peter Nilsson
Guest
Posts: n/a

 02-28-2012
Barry Schwarz <(E-Mail Removed)> wrote:
> Ping Cheu <(E-Mail Removed)> 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

Joe Pfeiffer
Guest
Posts: n/a

 02-28-2012
Ping Cheu <(E-Mail Removed)> 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.

BartC
Guest
Posts: n/a

 02-28-2012
"Ping Cheu" <(E-Mail Removed)> wrote in message
news:jigsb4\$rdc\$(E-Mail Removed)...
> 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

Stephen Sprunk
Guest
Posts: n/a

 02-28-2012
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

Stephen Sprunk
Guest
Posts: n/a

 02-28-2012
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

Joe keane
Guest
Posts: n/a

 02-28-2012
In article <jigsb4\$rdc\$(E-Mail Removed)>,
Ping Cheu <(E-Mail Removed)> wrote:
>Can anyone tell me?

I prefer the count-down method.

ct = len;
zp = bas;

while (--ct >= 0)
{
...(*zp)
zp++;
}

Think about it. You need a finite-state machine that outputs "0" ten
times then "1" one time. How much state do you need? About four bits,
certainly not two registers.

For complicated code, register allocation is always an issue (doubly so
for old x86).

If your compiler disdecides that loop control should be in registers,
and kicks out some other value that is really more important, it may be
an issue.

qarnos
Guest
Posts: n/a

 02-29-2012
On Feb 28, 1:16*pm, Peter Nilsson <(E-Mail Removed)> 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.

Phil Carmody
Guest
Posts: n/a

 03-02-2012
http://www.velocityreviews.com/forums/(E-Mail Removed) (Joe keane) writes:
> In article <jigsb4\$rdc\$(E-Mail Removed)>,
> Ping Cheu <(E-Mail Removed)> wrote:
> >Can anyone tell me?

>
> I prefer the count-down method.
>
> ct = len;
> zp = bas;
>
> while (--ct >= 0)

So you don't like unsigned types for counters then?

Phil
--
> I'd argue that there is much evidence for the existence of a God.

Pics or it didn't happen.
-- Tom (/. uid 822)

Joe keane
Guest
Posts: n/a

 03-05-2012
In article <(E-Mail Removed)>,
Phil Carmody <(E-Mail Removed)> wrote:
>So you don't like unsigned types for counters then?

It's typical C to use 'int' unless something else is needed.

It's probably an error if the counter comes in negative [or negative if
it were signed if it's unsigned], but maybe running zero times is fine.

beg = 8;
end = 6;
for (j = beg; j < end; j++)
...

Michael Angelo Ravera
Guest
Posts: n/a

 03-07-2012
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);
}

 Thread Tools

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post Buzz Lightyear C++ 10 08-12-2009 01:27 PM raan C++ 2 08-16-2007 07:13 PM david ullua C Programming 13 03-01-2006 11:02 PM The Jesus of Suburbia NZ Computing 2 02-11-2006 06:53 PM zaemin C Programming 5 06-04-2005 07:15 PM

Advertisments