Optimizations - Programmer vs. Compiler?

Saravana Kannan asks: "I have been coding in C for a while (10 yrs or so) and tend to use short code snippets. As a simple example, take 'if (!ptr)' instead of 'if (ptr==NULL)'. The reason someone might use the former code snippet is because they believe it would result in smaller machine code if the compiler does not do optimizations or is not smart enough to optimize the particular code snippet. IMHO the latter code snippet is clearer than the former, and I would use it in my code if I know for sure that the compiler will optimize it and produce machine code equivalent to the former code snippet. The previous example was easy. What about code that is more complex? Now that compilers have matured over years and have had many improvements, I ask the Slashdot crowd, what they believe the compiler can be trusted to optimize and what must be hand optimized?" "How would your answer differ (in terms of the level of trust on the compiler) if I'm talking about compilers for Desktops vs. Embedded systems? Compilers for which of the following platforms do you think is more optimized at present - Desktops (because is more commonly used) or Embedded systems (because of need for maximum optimization)? Would be better if you could stick to free (as in beer) and Open Source compilers. Give examples of code optimizations that you think the compiler can/can't be trusted to do."

Comments

Clear & Concise Code

[kwiqsilver]

It's better to write clear, legible code that saves a human minutes of reading, than complex code that might save a computer a few milliseconds of processing time per year, because human time costs more than machine time.
Also the clear code will result in fewer misinterpretations, which will mean fewer bugs (especially when the original author is not the one doing maintenance years later), further reducing costs in dollars, man hours, and frustration.

Beware of habits.

[SharpFang]

I got in the habit of writing "readable but inefficient" code, taking care that my constructs don't get too sophisticated for the optimizer but then depending on gcc -O3 thoroughly. And then it happened I had to program 8051 clone. Then I learned there are no optimizing compilers for '51, that I'm really tight on CPU cycles, and that I simply don't know HOW to write really efficient C code.
Ended up writing my programs in assembler...

Check out the LLVM demo page

[sabre]

LLVM is an aggressive compiler that is able to do many cool things. Best yet, it has a demo page here: http://llvm.org/demo, where you can try two different things and see how they compile.

One of the nice things about this is that the code is printed in a simple abstract assembly language that is easy to read and understand.

The compiler itself is very cool too btw, check it out. :)

-Chris

Re:Algorithms, Not Stupid Processor Tricks

[Flyboy Connor]

Quite agree, it's about the algorithm, not about the code.

One of the finest moments in my programming career was when my boss asked me to see if I could gain a speed improvement in a program that surveyed a huge datastore and generated volumes of text from it. This program had to run once a month, and deliver its result in the same month. The program that was originally written, unfortunately, took three months to run (it started out OK, but the data store had grown considerably). They had asked one of our "best programmers" to create a faster version of the program. He did that by reprogramming the entire thing in assembly (you may now understand why managers thought he was one of the best programmers). It took him six whole months to finish the new version. The resulting program completed the task in just about one month. However, my boss was afraid that when the datastore would grow a bit more, we would again be in trouble. That's when he asked me to look it over. I started by investigating the problem, which at first glance looked like a network traversing problem. I soon realised it could be solved by a nested matrix multiplication (which is, of course, a standard way to discover paths in a network). It was a matrix with about a million rows and columns, but since it contained only zeroes and ones (with a couple of thousands times more zeroes than ones), the multiplication was easy to implement in a fast way. Within half-a-day, I had built a prototype program in a high-level language which did the whole job in a few hours.

While I am still pleased with this result, I really think it came off so well not because I was so smart, but because the assembly programmer was not really worthy of the name. Still, I often use this as an illustration for students who are writing illegible code and argue that it is so very fast.

Re:Clear Code

[david duncan scott]

Yup, that's why your bank throws away all three zillion lines of COBOL every year -- because there's a greater risk in maintenance than in new code.

I wish I could put my hands on an article I read a couple years back on the code in the Space Shuttle. They go at that code base with an attitude that makes the average paranoid look happy-go-lucky. In fact, they approach software engineering kind of like other engineers do -- as if lives depended on it. It's old, it's slow, and it works. (Oh, wait, here it is.) That's how code is maintained.

Re:Write C for C programmers

[14erCleaner]

I disagree with you about the readability of (!ptr), but at least it is a very common idiom in C, and I can accept that.

But please, oh, please, don't write this:

if (!strcmp(x,y))

Intuitively, that looks exactly backwards from what it's testing (equality).

On the "optimize for the compiler" issue, I think what's been said already is right: don't do it unless it's in a critical spot, write code for readability (and big-picture efficiency) first, then worry about local optimizations only if there's a problem.

Re:Wrong, wrong, wrong

[PoopJuggler]

Any company who makes a C compiler where NULL != 0 will not get much business methinks

Re:Clear Code

[lymc]

Now, let me tell you the flip side of that story. I was working on the Viking Mars Lander program long ago (1976). The code for the lander programs was frozen a year before launch (which itself was a year before landing). Some dozen "books" of the assembly code were created and archived for use when the landers finally landed. All went well for about 6 months after landing. Updates were made and duly entered into the master asssembly listings. After six months of this, the listings were so xed out, and all the margin space used with notes, that errors started creeping in. Finally an uploaded patch wrote over part of the antenna pointing table, and the lander was lost, but for a fortuitious accident which allowed the table to be re-established (with much howling and gnashing of teeth). Sometimes new is better, even if it is painful.

Re:Clear Code

[drgonzo59]

Same goes for code that runs on the airplanes (like Boeing passenger aircraft). In fact the developers have to prove that each possible! branch that code could ever take won't lead to unpredictable behavior or crash. If you have 100 independent 'if' statements that is at least 2^100 possibilites. The code they write is very linear, they avoid branching at all cost.

There is a whole are of study involved in correctness checking, which is related to the SAT (Satisfiability) problem.

The operating system choice is also interesting. Linux doesn't even come close to what they need. Having device drivers in the kernel is just not a good idea. It needs to have a separation kernel, at least that is the goal. I presently think they use the INTEGRITY operating system by Green Hills, but I could be wrong.

Just optimize for the "big picture"

[Jugalator]

There's often no point in fiddling around with details, and you should instead focus on optimizing for "the big picture", e.g. whether you should really re-establish a database connection each time a user selects OK in a dialog box.

As for simple code optimizations, here's what a modern compiler (Microsoft Visual C++ .NET 2003 in this case) optimize code as: (yes, I've checked these myself as I've been writing this post)

for (int i = 0; i < 5; i++)
{
int j = 42;
if (j == 13)
{
printf("j is %d", j); j = 42;
}
}
return 0;

... optimized to ...

xor eax, eax
ret 0

In other words, it basically threw away all that code since the program wouldn't make use of any values that would be calculated there. And this:

for (int i = 0; i < 100; i++)
{
int j = 42;
i += j;
}
printf("i is %d", i);
return 0;

... optimized to ...

push 129
push OFFSET FLAT:??_C@_07JEGIODIB@i?5is?5?$CFd?$AA@
call _printf
add esp, 8
xor eax, eax
ret 0

Do you see what that means -- yep, the compiler understood that the resulting value would be 129 by analyzing the for loop and simply just push that value onto the stack as a parameter to printf. It basically optimizes to:

printf("i is %s", 129);
return 0

That's probably considered some simplistic analyzing too, by today's compilers. ;-)

Finally, a story that my signature works well with

[smcdow]

I've been using it for a while...