Educated guesses for efficiency?

[Frederick Gotham]

Commonly, people may ask a question along the lines of, "Which code
snippet is more efficient?".

If the code is anything other than assembler (e.g. C or C++), then
there's no precise answer because we don't know the instruction set of
the target system, or how the compiler will "map" each executable line of
C code to assembly instructions.

I consider myself to be fairly proficient in C, but I'll admit I know
very little about machine code, instructions set, and the like...

When writing fully-portable code, are there any guidelines as to how to
write your code in order to make an "educated guess" as to what would be
more efficient on *most* target platforms?

For instance, I heard that on the original machine for which C was
intended, that there was a single CPU instruction which could perform the
following:

*p++ = something; /* (p is a pointer variable) */

Therefore, at the time, it would have made sense to make use of "*p++" as
much as possible in the code.

So, my question is: Is there any sort of guide available on the web which
discusses constructs which should be used in fully-portable code because
they're likely to be quite efficient across the board?
--

Frederick Gotham

[jacob navia]

Frederick Gotham a écrit :

Commonly, people may ask a question along the lines of, "Which code
snippet is more efficient?".

If the code is anything other than assembler (e.g. C or C++), then
there's no precise answer because we don't know the instruction set of
the target system, or how the compiler will "map" each executable line of
C code to assembly instructions.

I consider myself to be fairly proficient in C, but I'll admit I know
very little about machine code, instructions set, and the like...

When writing fully-portable code, are there any guidelines as to how to
write your code in order to make an "educated guess" as to what would be
more efficient on *most* target platforms?

For instance, I heard that on the original machine for which C was
intended, that there was a single CPU instruction which could perform the
following:

*p++ = something; /* (p is a pointer variable) */

Therefore, at the time, it would have made sense to make use of "*p++" as
much as possible in the code.

So, my question is: Is there any sort of guide available on the web which
discusses constructs which should be used in fully-portable code because
they're likely to be quite efficient across the board?

There is no one code snippet more efficient than another, if they
are strictly equivalent. Today's optimizing compilers are quite good
at generating very tight and fast assembly code.

In modern workstations, most of the traditional "optimizati ons" like

"a*2 is more expensive than a << 1"

are no longer valid. Much more important than the instructions
themselves is the data layout.

Data layout is today where the efficiency can be improved. The memory is
running at more or less 400 MHZ, the processor is running at more than
2-3GHZ. By improving the locality of data accesses you can gain a lot
in efficiency by avoiding expensive main memory reads that can cost you
like 10 or more cheap instructions of one cycle.

Data layout is a hot research subject, and I would recommend you reading
the manuals of the CPU vendor about this.

For the AMD/Intel world, both have produced optimizations manuals that
are a very instructive read.

jacob

[Morris Dovey]

Frederick Gotham (in Xn************* **************@ 194.125.133.14)
said:

| So, my question is: Is there any sort of guide available on the web
| which discusses constructs which should be used in fully-portable
| code because they're likely to be quite efficient across the board?

If there is, I'd be inclined to not trust it. It's really the compiler
writers' job to turn any and all valid source code into efficient
intermediate and/or executable codes. This allows the programmer to
focus on producing _valid_ source code solutions.

--
Morris Dovey
DeSoto Solar
DeSoto, Iowa USA
http://www.iedu.com/DeSoto

[Tim Prince]

Frederick Gotham wrote:

For instance, I heard that on the original machine for which C was
intended, that there was a single CPU instruction which could perform the
following:

*p++ = something; /* (p is a pointer variable) */

Therefore, at the time, it would have made sense to make use of "*p++" as
much as possible in the code.

Modern compilers are very good at optimizing array operations, so you
shouldn't go out of your way to use pointers. If you do use pointers,
any good compiler should be able to turn

*p = something;
++p;
into as efficient code, when "something" doesn't involve conflicting
operations. So the old advice to make your source code as clear as
possible to humans who need to understand it is better than ever. The
most likely gain in the ++ operator is saving in typing and typos.

A certain architecture which has had it fanatics is better suited to

*++p = something;

and the difference in performance could be detected.

[Eric Sosman]

Frederick Gotham wrote:

Commonly, people may ask a question along the lines of, "Which code
snippet is more efficient?".

If the code is anything other than assembler (e.g. C or C++), then
there's no precise answer because we don't know the instruction set of
the target system, or how the compiler will "map" each executable line of
C code to assembly instructions.

I consider myself to be fairly proficient in C, but I'll admit I know
very little about machine code, instructions set, and the like...

When writing fully-portable code, are there any guidelines as to how to
write your code in order to make an "educated guess" as to what would be
more efficient on *most* target platforms?

For instance, I heard that on the original machine for which C was
intended, that there was a single CPU instruction which could perform the
following:

*p++ = something; /* (p is a pointer variable) */

Some guy named Ritchie writes, in reference to the development
of C's immediate ancestor B:

Thompson went a step further by inventing the ++ and --
operators, which increment or decrement; their prefix or
postfix position determines whether the alteration occurs
before or after noting the value of the operand. [...]
People often guess that they were created to use the
auto-increment and auto-decrement address modes provided
by the DEC PDP-11 on which C and Unix first became popular.
This is historically impossible, since there was no PDP-11
when B was developed.

As for the PDP-11's addressing modes, there were indeed some
instances where the compiler could translate *p++ or *--p to a
single instruction. But it certainly could not do so in all
circumstances! The hardware's increment or decrement was by
either one or two bytes (for byte- or word-using instructions),
so other operand sizes needed additional instructions to adjust
the pointer value.

As for the larger question, there's a rather bitter thread
raging at this very moment over the question of whether micro-
optimizations of this sort are necessary nowadays, or even whether
they're truly optimizations at all. The doubters seem to be in
the majority, but can't be said to be winning -- nobody "wins" in
silly debates like that one.

Concerning the even larger question, I'd recommend reading

http://www.codeproject.com/tips/optimizationenemy.asp

for some good sense about optimization. The principal message
is simple: "Measure, measure, measure!" The corollary is also
simple: Since you can't know anything useful about performance
until you've measured the running code, micro-optimizations in
the initial development are silly.

--
Eric Sosman
es*****@acm-dot-org.invalid

[Richard Heathfield]

Frederick Gotham said:

Commonly, people may ask a question along the lines of, "Which code
snippet is more efficient?".
The one that costs the maintainer the least time to fix.

<snip>
When writing fully-portable code, are there any guidelines as to how to
write your code in order to make an "educated guess" as to what would be
more efficient on *most* target platforms?
Sure.

1) Use good algorithms.
2) Write clear code.
3) All code should either do something good or stop something bad happening.
4) If, as you write a section of code, a smile comes over your face and you
think "hey, this is way cool", it probably needs re-writing.
For instance, I heard that on the original machine for which C was
intended, that there was a single CPU instruction which could perform the
following:

Who cares about a single instruction? If you're interested in efficiency, go
for macro-efficiencies. Maybe x = -x is a nanosecond quicker than x *= -1,
and maybe it isn't, but we know for sure that a binary search is vastly
quicker than a linear search in almost all circumstances.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

[jacob navia]

Richard Heathfield a écrit :

4) If, as you write a section of code, a smile comes over your face and you
think "hey, this is way cool", it probably needs re-writing.

I do not agree with this at all.

Sometimes I write a program I am proud of, or at least I like the way
I wrote it.

It is short, powerful, there is nothing too much, nothing missing.

Programming is fun.

Yes, you can see the world as a sea of tears.

Or you can see the world as a place where you can find joy and
satisfaction with what you have done.

jacob

[Michael Mair]

Richard Heathfield schrieb:

Frederick Gotham said:

When writing fully-portable code, are there any guidelines as to how to
write your code in order to make an "educated guess" as to what would be
more efficient on *most* target platforms?
Sure.

1) Use good algorithms.

Yes.
2) Write clear code.
Yes.
3) All code should either do something good or stop something bad happening.
Depends on your definition of good and bad.
4) If, as you write a section of code, a smile comes over your face and you
think "hey, this is way cool", it probably needs re-writing.

No and yes.

I usually smile when the roles identified during specification
and design really work as intended, everything comes down to
exactly the right level of granularity and clarity, and I just
get the feeling that it will be joy to revisit the code
throughout the years.
Or if I found a clever way to break complexity without
endangering clarity and conciseness.
And I find this "way cool".

On the other hand, nifty tricks essentially coming down to
micro-optimization can give this feeling, too -- for them, I
agree with you for most applications. However, the threshold
is very different for different projects, people, departments,
etc.
Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.

[Richard Heathfield]

Michael Mair said:

Richard Heathfield schrieb:

4) If, as you write a section of code, a smile comes over your face and
you think "hey, this is way cool", it probably needs re-writing.
No and yes.

I usually smile when the roles identified during specification
and design really work as intended, everything comes down to
exactly the right level of granularity and clarity, and I just
get the feeling that it will be joy to revisit the code
throughout the years.
Or if I found a clever way to break complexity without
endangering clarity and conciseness.
And I find this "way cool".

So do I, and that's why I included the weasel word "probably". I'm afraid
that you and I are in a minority.

On the other hand, nifty tricks essentially coming down to
micro-optimization can give this feeling, too -- for them, I
agree with you for most applications.
That's the kind of thing I was talking about, yes.

However, the threshold is very different for different projects, people,
departments, etc.

Sure. If your target machine has 256 octets of storage and you find a
micro-optimisation that reduces your object code size from 257 octets to
254, then you have every right to feel pleased.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

[Keith Thompson]

jacob navia <ja***@jacob.re mcomp.fr> writes:

Richard Heathfield a écrit :

4) If, as you write a section of code, a smile comes over your face
and you think "hey, this is way cool", it probably needs re-writing.

I do not agree with this at all.

Sometimes I write a program I am proud of, or at least I like the way
I wrote it.

It is short, powerful, there is nothing too much, nothing missing.

Programming is fun.

Yes, you can see the world as a sea of tears.

Or you can see the world as a place where you can find joy and
satisfaction with what you have done.

You and Richard are talking about two very different forms of "hey,
this is way cool". If the reaction comes from having written
well-constructed and *clear* code, then it really is way cool. If it
comes from having written code that so incredibly clever that nobody
else will ever understand it, file it away for possible submission to
the IOCCC, or delete it so it will never see the light of day.

On this point, I suspect the three of us are in complete agreement.

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.