Optimiser question

[Robert Latest]

You don't say what the program does, so it's hard to guess what
might be cycle-sinks, but if it does any string-hacking, remember
that `strlen` and `strcat` (as examples) are not constant-time

Depending on the implementation they may be. Nothing stops a compiler from
generating additional code that keeps track of string lengths.

robert

 

[Robert Latest]

The tidy up was provoked by an article in the
IET Electronics magazine where ++i is esier to optimise than i++ due
to the need to store i and then increment it. (think I got that
correct).

That's an old myth. If the result of the "++i" or "i++" isn't needed,
any compiler will recognize this and generate identical code. If you do need
the side-effect of post-increment, the above "disadvantage" of i++ vs ++i
vanishes anyway. Think about it: "n[i++]=0" and "n=0;++i" are exactly
equivalent. As long as the C standard doesn't say: "pre-increment is faster
than post-increment" we can't universally answer your question.

As I dont know really how optimsers work I thought Id ask
the question.

As far as the C language itself is concerned, nobody knows what an optimizer
is. Your problem is an algorithm/implementation problem, not a language
problem.

robert

 

[Chris Dollin]

Depending on the implementation they may be. Nothing stops a compiler from
generating additional code that keeps track of string lengths.

Nothing except that if the char*s being tested might be widely accessible
and there are any functions called between tests the compiler can't assume
that the result is unchanged.

I agree that compilers /can/, in principle, do this. What's not so clear
is (a) whether any of them do and (b) how widely applicable the optimisation
is.

/Assuming/ that `strlen` (say) is a constant-time operation is ... sub-optimal.
(I'm not saying you're making that assumption.)

 

[Chris Dollin]

Philip Potter wrote:

No, they are not equivalent. They differ in the value to preserve
for the complete expression.

Which is why Philip specifically said that `i++;` and `++i;` were
equivalent; they're statements that contain /complete/ expressions.

 

[Stephen Sprunk]

Nothing except that if the char*s being tested might be widely
accessible and there are any functions called between tests the
compiler can't assume that the result is unchanged.

.... unless the compiler has interprocedual (aka whole-program) optimization,
where it _can_ determine if the string won't be changed. Of course, if the
compiler is capable of that, it should also be smart enough to remove the
second (and later) calls to strlen() via CSE without having to track the
length explicitly.

I agree that compilers /can/, in principle, do this. What's not so
clear is (a) whether any of them do and (b) how widely applicable
the optimisation is.

A few do, or at least attempt to. I'm not sure this specific example is all
that helpful, but IPO and WPO can provide significant gains.

/Assuming/ that `strlen` (say) is a constant-time operation is ... sub-
optimal. (I'm not saying you're making that assumption.)

C90/99 don't say it's constant-time, so it's a flawed assumption from the
get-go. Of course, the ISO standard offers very little in the way of
performance guarantees or even guidance, so the lack of a statement isn't
all that meaningful.

S

 

[CBFalconer]

Which is why Philip specifically said that `i++;` and `++i;` were
equivalent; they're statements that contain /complete/ expressions.

They have the equivalent effects on i, but return different
values. That affects the if statement action.

 

[Willem]

CBFalconer wrote:
) Chris Dollin wrote:
)> Which is why Philip specifically said that `i++;` and `++i;` were
)> equivalent; they're statements that contain /complete/ expressions.
)
) They have the equivalent effects on i, but return different
) values. That affects the if statement action.

Statements don't return values. Expressions do.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

 

[Philip Potter]

No, they are not equivalent. They differ in the value to preserve
for the complete expression. If that value is discarded, then it
doesn't matter, and the optimizer will usually reduce the
statements to the same code. Since the prefix ++ (or --) operator
yields the same value as the final operand value, it may be more
efficient when the expression value is used.

Although Chris Dollin has said why I feel my original statement was
correct, you've shown that it has the capacity to confuse. What I meant
to say was that, in a standalone statement, i++ is the same as ++i.
CBFalconer is right that if i++ or ++i appear as part of a larger
expression in which the return value is used, they are *not*
equivalent[1] - but then they're not complete statements.

Philip

[1] Actually, they can be equivalent even when their return value is used:
i = i++;
is equivalent to
i = ++i;
....because both have undefined behaviour

 

[lawrence.jones]

Statements don't return values. Expressions do.

What about the "return" statement? ;-)

-Larry Jones

Nobody knows how to pamper like a Mom. -- Calvin

 

[Willem]

(e-mail address removed) wrote:
)>
)> Statements don't return values. Expressions do.
)
) What about the "return" statement? ;-)

The return statement never even returns (to the function). ;-)
It causes an exit (out of the function).


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

 

[Nick Keighley]

[1] Actually, they can be equivalent even when their return value is used:
i = i++;
is equivalent to
i = ++i;
...because both have undefined behaviour - Hide quoted text -

buts that's on par with comparing NaNs.
Both statements may exhibit UB, bit it may be *different*
UB.

 

[Philip Potter]

[1] Actually, they can be equivalent even when their return value is used:
i = i++;
is equivalent to
i = ++i;
...because both have undefined behaviour - Hide quoted text -

buts that's on par with comparing NaNs.
Both statements may exhibit UB, bit it may be *different*
UB.

I thought of this (even the comparison with NaN) after posting. You are
quite correct. The equivalence argument loses all credibility when one
considers that a particular implementation is free to define each
expression to mean different things.

 

[Kevin D. Quitt]

We are using a variant of gcc
(3.4.1 I think) on Nios II platform, if that makes a difference.

All the difference in the world. I just finished a product using the Nios
II. One of my problems was that several of my code snippets were *too
fast* and interfered in the operation of DMA. (>> It *says* OT in the
subject! <<)

Feel free to carry this on in email, though, as micro-optimization really
doesn't belong here.

The fastest loop you can do what you're doing (with no further information)
is:

pEnd = pDest + count;

while ( pDest < pEnd )
*pDest++ = nPattern;

With more information, this loop can be sped up, possibly by almost four
times. As I said, feel free to contact me by email.