Slashdot Log In
Optimizations - Programmer vs. Compiler?
Posted by
Cliff
on Fri Feb 25, 2005 03:46 PM
from the who-can-obfuscate-better dept.
from the who-can-obfuscate-better dept.
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."
This discussion has been archived.
No new comments can be posted.
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
Full
Abbreviated
Hidden
Loading... please wait.
Ask the compiler... (Score:5, Funny)
Compiler: Optimizing? Optimizing? Don't talk to me about optimizing. Here I am, brain the size of a planet, and they've got me optimizing inane snippets of code. Just when you think code couldn't possibly get any worse, it suddenly does. Oh look, a null pointer. I suppose you'll want to see the assembly now. Do you want me to go into an infinite loop or throw an exception right where I'm standing?
Programmer: Yeah, just show me the stack trace, won't you compiler?
Re:Ask the compiler... (Score:5, Funny)
Parent
Optimization rules... (Score:5, Funny)
Plus I got extra credit for implementing phong shading. I didn't even try to do phong shading.
Parent
Clear Code (Score:5, Insightful)
Re:Clear Code (Score:5, Insightful)
Parent
Re:Clear Code (Score:5, Interesting)
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. [fastcompany.com]) That's how code is maintained.
Parent
Must be nice (Score:5, Insightful)
one customer
420,000 lines
260 staff
no competition
no trade shows
no salespeople selling new features that have never been discussed
It's interesting to talk about their attention to detail, but to hold it up as a model for all software development neglects to consider that they are working under an entirely different set of constraints from most everyone else.
Parent
Re:Clear Code (Score:5, Interesting)
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.
Parent
Re:Clear Code - Boeing (Score:5, Funny)
HAL! Open the bathroom door!
I'm sorry Dave, you shouldn't have had that last burrito.
Parent
Re:Not always. (Score:5, Insightful)
I comment things that are non intuitive. I comment things that I *think* may be non intuitive. I comment things that I think someone else might have some difficulty understanding, because I happened to be deep into a code burn and consequently wrote something pretty tight, pretty sweet, but also pretty obfuscated. Finally, I comment things that I think *I* may not understand when I go back and look at the code again 3 months from now.
I don't comment every single line... I don't comment simple data structures, loops "/* this is a for loop using the integer variable I */" etc which would be stupid. I do however disassemble the complex portions of my code, describe how I'm dispatching events and best of all *why* I decided to do things a certain way instead of a different way.
I have, however, been handed 30k lines of code with zero documentation and not a single comment anywhere in it, with absolutely no clue at all how it worked and no access to the original programmer and been told "We need such and such fixed|updated|added by friday" and had to spend the entire week basically tracing every single line of code to figure out that the original programmer must have been smoking crack with NO indication of why he wrote things how he did and NO help when he decided to be exceedingly "clever"
in his code. That time was wasted.
Would it have killed him to simply put a comment block explaining his event dispatch model? Or to tell me what his functions and methods did and best of all why they did it?
There *is* a middle ground, believe it or not.
-- Gary F.
Parent
Re:Clear Code (Score:5, Insightful)
Parent
Re:Clear Code (Score:5, Insightful)
Another thing to remember is this: the compiler isn't stupid; don't pretend that it is. I had senior developers at an earlier job mad at me because I wasn't creating temporary variables for the limits of my loop indices (on unprofiled code, nonetheless!). It took actually digging up an article on the net to show that all modern compilers automatically dereference any const references (be they arrays, linked lists, const object functions, etc) before starting the loop.
Another example: function calls. I've heard some people be insistant that the way to speed up an inner loop is to remove the code from function calls so that you don't have function call overhead. No! Again, compilers will do this for you. As compilers were evolving, they added the "inline" keyword, which does this for you. Eventually, the compilers got smart enough that they started inlining code on their own when not specified and not inlining it when coders told it to be inline if it would be inefficient. Due to coder pressure, at least one compiler that I read about had an "inlinedamnit" (or something to that effect) keyword to force inlining when you're positive that you know better than the compiler
Once again, the compiler isn't stupid. If an optimization seems "obvious" to you, odds are pretty good that the compiler will take care of it. Go for the non-obvious optimizations. Can you remove a loop from a nested set of loops by changing how you're representing your data? Can you replace a hack that you made with standard library code (which tends to be optimized like crazy)? Etc. Don't start dereferencing variables, removing the code from function calls, or things like this. The compiler will do this for you.
If possible, work with the compiler to help it. Use "restrict". Use "const". Give it whatever clues you can.
Parent
Re:Clear Code (Score:5, Insightful)
Parent
Re:Clear Code (Score:5, Insightful)
Lets say you're traversing a 2D array of data (e.g., an image).
for(x=0; x < width; x++)
{
for(y=0; y < height; y++)
{
}
}
versus
for(y=0; y < height; y++)
{
for(x=0; x < width; x++)
{
}
}
The latter piece of code is just as clear as the first; however, will likely run about 50 times faster than the first, due to caching issues.
Will the compiler optimize the first piece of code to look like the second? Probably not (tell me if I'm wrong), as there may be a reason to process things in a particular order.
In addition, the latter piece of code may actually be less clear, as in some cases, it may not read well to do height before width in the for loop.
As a result, you'll still need to write code thinking about optimization.
Parent
Re:Clear Code (Score:5, Informative)
123
456
789
data[y][x];
This, in memory, is:
123456789
Similarly, the accsess order for the second loop is:
123456789
But for the first one, it is:
147258369
The first one hits memory sequentially, which is good for caching as each cache line stores a large chunk of sequential memory.
Considering hitiing the cache as oposed to hitting main memory is at least 100 times faster, you'll be lucky if the first loop is only 50 times slower.
This still presumes data stored in the specified order in memory (which is common for image formats, but not the only way things are done).
Parent
C and "flexibility" of expression operators (Score:5, Insightful)
! means "not" or "inverse of"; it is a boolean function. The variable ptr is a pointer; it is a reference to data, which means it isn't really data itself. !ptr shouldn't compute; a boolean operator should only work on boolean data. But C logical comparators are designed to work on everything. You are just supposed to know that 0 == NULL == false. This supposition is totally arbitrary and doesn't hold up in any language with strong typing.
This is what makes C difficult for beginners. Bad code compiles even though it has logical flaws, and ends up failing in mysterious ways.
The second case makes more sense. Equality is an operator that should work on all types of data. NULL is necessary if you are going to abstract data through the use of pointers or objects. Doing away with NULL would be equivalent to eliminating true and false and using 1 and 0 instead. Or eliminating strings and using sequences of ASCII codes. These substitutions are technically correct but in reality they make code unreadable.
Parent
You should always... (Score:5, Funny)
Re:You should always... (Score:5, Funny)
Parent
Re:You should always... (Score:5, Funny)
Parent
Re:You should always... (Score:5, Funny)
Parent
Re:You should always... (Score:5, Informative)
There's nothing wrong with short variable names.
Thus quoth Linus in the Linux Coding Style guide.
Parent
Re:You should always... (Score:5, Informative)
some random integer loop counter, it should probably be called "i".
Calling it "loop_counter" is non-productive, if there is no chance of it
being mis-understood.
That last clause is an important one that often gets neglected. In fact, you should never, ever, call a variable loop_counter. That's as bad as pure reverse hungarian - it tells you how its used, not what it means.
I suggest that, for all non-trivial cases (and I'd prefer to see people err verbosely than compactly), you should use descriptive names. Not loop_counter, but maybe something like curRow? It doesn't have to be long, but at least then as the loop grows over time someone can understand a piece of code more easily than having to scroll back up to check that you are indeed in the "i" loop. Its even more critical when someone comes along and adds a nested (or containing) loop. Or whatever.
Same with "tmp". If its truly temporary, such as:
int tmp = getFooCount();
doSomething(tmp);
then it should be removed and rewritten as:
doSomething(getFooCount());
If its not that temporary, give it a real name. If you insist that it is temporary then you may have a scoping issue - having variables useful but only in part of your function could indicate that your function is doing too much work. If you insist its truly temporary, scope it down:
someRandomCode();
{
int foo = getFoo();
doSomething(foo);
doSomethingElse(foo);
}
moreCode();
At least now you've guaranteed that it is temporary. Better yet, just name it usefully.
Parent
Re:You should always... (Score:5, Insightful)
With the greatest respect to Linus, but writing a kernel does not make you the authority on programming. It does make you the authority on what particular style you allow in your CVS tree, but that's it.
I certainly agree that loop_counter is a bad name, though. But rather than use i, I prefer to at least make a note of what sort of objects I'm looping through.
For instance:
Code can never be 100% self documenting, but that's no reason not to settle for 0%. Whether you use CamelCase or words_broken_with_underscores is a matter of style, and you should stick with the style of the code base you're working on.
Anyone who can't or won't work with multiple languages or adopt the necessary style for an existing project is a poor programmer. When you create project, you create the rules. When you work on someone else's project, you follow the rules.
Parent
i, j, k, ... (Score:5, Informative)
I think that most people forget that the reason that i, j, k, etc. are used for loop counters is that unless otherwise declared, I..N default to INTEGER in FORTRAN. This convention just carried over as programmers migrated from FORTRAN to other languages and has been passed down through the ages.
Parent
Time to post the famous Knuth quote... (Score:5, Informative)
That's a Tony Hoare quote, not Donalded Knuth (Score:5, Informative)
Parent
Algorithms, Not Stupid Processor Tricks (Score:5, Insightful)
The sad truth is that, as far as optimization goes, this isn't where attention is most needed.
Before we start worrying about things like saving two cycles here and there, we need to start teaching people how to select the proper algorithm for the task at hand.
There are too many programmers who spend hours turning their code into unreadable mush for the sake of squeezing a few milliseconds out of a loop that runs on the order of O(n!) or O(2^n).
For 99% of the coders out there, all that needs to be known about code optimization is: pick the right algorithms! Couple this with readable code, and you'll have a program that runs several thousand times faster than it'll ever need to and is easy to maintain--and that's probably all you'll ever need.
Re:Algorithms, Not Stupid Processor Tricks (Score:4, Insightful)
Parent
Re:Algorithms, Not Stupid Processor Tricks (Score:5, Interesting)
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.
Parent
The algorithm that must not be named! (Score:5, Funny)
The most frustrating thing is that, if you must use the algorithm that must not be named, the bidirectional form of the algorithm is much faster (in practice) than the unidirectional form yet really no more complex to code than the latter if you have any potential as a software developer.
Parent
Re:Algorithms, Not Stupid Processor Tricks (Score:5, Informative)
And while we're at it - n^2 vs 2^n *is* a big deal when working on 1ghz+ systems... If we have 1000 objects, an operation that takes 10 cycles and an n^2 algorithm, then we get a runtime of 0.01 seconds (10 x 1000 x 1000 cycles ), if we have a 2^n algorithm then we get a runtime in the hours, and no amount of optimizing the code in the loop (even down to one instruction) is going to get us anywhere near the n^2 algorithm.
Parent
Clear & Concise Code (Score:5, Interesting)
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.
From the "Patenting Fire" department (Score:4, Funny)
Prepare to be sued.
Tradeoffs (Score:5, Insightful)
Hard to measure, but what is the tradeoff between increased speed and increased readability (which is a prerequisite for correctness and maintainability)? And if you can estimate that tradeoff, which is more important to the goals of your application?
As a side note, it is far more important to make sure you are using efficient algorithms and data structures than to make minor local optimizations. I've seen programmers use bizarre local optimization tricks in a module that ran in exponential time rather than log time.
Most people should not bother (Score:5, Insightful)
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?
Programmers cost lots more per hour than computer time. Let the compiler optimize and let the programmers concentrated on developing solid maintainable code.
If you make code too clever in an effort to try to pre-optimize, you end up with code that other people have difficulty understanding. This is leads to lower quality code as it evolves if the people that follow you are not as savvy.
Not only that, but the vast majority of code written today is UI-centric or I/O bound. If you want real optimization, design a harddrive/controller combo that gets you 1 GBps off the physical platter (and at a price that consumers can afford).
Beware of habits. (Score:5, Interesting)
Ended up writing my programs in assembler...
Huh (Score:5, Informative)
As a simple example, take 'if (!ptr)' instead of 'if (ptr==NULL)'.
Both forms resolve to the same opcode. Even under my 6502 compiler.
CMP register,val
JNE
Enjoy,
Re:Huh (Score:5, Insightful)
However, any compiler worth anything should find that and optimize it very easily in the case where you're comparing to a constant that evaluates to zero.
Parent
$.02 (Score:5, Insightful)
2) Profile your code
3) Optimize the bottlenecks
That said, (!ptr) should be just as maintanable as (ptr == NULL) simply because it is a frequently used 'dialect'. As long as these 'shortcuts' are used throughout the entire codebase they should be familiar enough that they don't get in the way of maintainability.
micro optimization (Score:5, Insightful)
Compilers are pretty good at that, and you should let them do their job.
Programmers should optimize at a higher level: by their choice of algorithms, organizing the program so that memory access is cache-friendly, making sure various objects don't get destroyed and re-created unnecessarily, that sort of thing.
Those who forget Tony Hoare... (Score:5, Insightful)
"Premature optimization is the root of all evil"
If there's only one rule in computer programming a person ever learns, "Hoare's dictum" is the one I would choose.
Almost all modern languages have extensive libraries available to handle common programming tasks and can handle the vast majority of optimizations you speak of automatically. This means that 99.99% of the time you shouldn't be thinking about optimizations at all. Unless you're John Carmack or you're writing a new compiler from scratch (and perhaps you are) or involved in a handful of other activities you're making a big big mistake if your spending any time worrying about these things. There are far more important things to worry about, such as writing code that can be understood by others, can easily be units tested, etc.
A few years ago I used to write C/C++/asm code extensively and used to be obsessed with performance and optimization. Then, one day, I had an epiphany and started writing code that is about 10 times slower than my old code (different in computer language and style) and infinitely easier to understand and expand. The only time I optimize now is at the very very end of development when I have solid profiler results from the final product that show noticable delays for the end user and this only happens rarely.
Of course, this is just my own personal experience and others may see things differently.
Write C for C programmers (Score:5, Insightful)
With regard to your example, I can't imagine any modern compiler wouldn't treat the two as equivalent.
However, in your example, I actually prefer "if (!ptr)" to "if (ptr == NULL)", for two reasons. First the latter is more error-prone, because you can accidentally end up with "if (ptr = NULL)". One common solution to avoid that problem is to write "if (NULL == ptr)", but that just doesn't read well to me. Another is to turn on warnings, and let your compiler point out code like that -- but that assumes a decent compiler.
The second, and more important, reason is that to anyone who's been writing C for a while, the compact representation is actually clearer because it's an instantly-recognizable idiom. To me, parsing the "ptr == NULL" format requires a few microseconds of thought to figure out what you're doing. "!ptr" requires none. There are a number of common idioms in C that are strange-looking at first, but soon become just another part of your programming vocabulary. IMO, if you're writing code in a given language, you should write it in the style that is most comfortable to other programmers in that language. I think proper use of idiomatic expressions *enhances* maintainability. Don't try to write Pascal in C, or Java in C++, or COBOL in, well, anything, but that's a separate issue :-)
Oh, and my answer to your more general question about whether or not you should try to write code that is easy for the compiler... no. Don't do that. Write code that is clear and readable to programmers and let the compiler do what it does. If profiling shows that a particular piece of code is too slow, then figure out how to optimize it, whether by tailoring the code, dropping down to assembler, or whatever. But not before.
code should be written for people to read (Score:5, Insightful)
- Structure and Interpretation of Computer Programs [tinyurl.com]
Not a question that can be asked generally (Score:5, Informative)
In general, however, systems are now fast enought that when in doubt, write the clearest code possible. I mean for most apps, speed is not critical, however for all apps stability and lack of bugs is important and obscure code leads to problems.
Also, for things that are time critical, it's generall just one or two little parts that make all the difference. You only need to worry about optimizing those inner loops where all the time is spent. Use a profiler, since programmers generally suck at identifying what needs optimising.
Keep it easy to read and maintain, unless speed is critical in a certian part. Then you can go nuts on hand optimization, but document it well.
Check out the LLVM demo page (Score:5, Interesting)
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
If you're not willing to TIME it... (Score:5, Insightful)
Never try to optimize anything unless you have measured the speed of the code before optimizing and have measured it again after optimizing.
Optimized code is almost always harder to understand, contains more possible code paths, and more likely to contain bugs than the most straightforward code. It's only worth it if it's really faster...
And you simply cannot tell whether it's faster unless you actually time it. It's absolutely mindboggling how often a change you are certain will speed up the code has no effect, or a truly negligible effect, or slows it down.
This has always been true. In these days of heavily optimized compilers and complex CPUs that are doing branch prediction and God knows what all, it is truer than ever. You cannot tell whether code is fast just by glancing at it. Well, maybe there are processor gurus who can accurately visualize the exact flow of all the bits through the pipeline, but I'm certainly not one of them.
A corollary is that since the optimized code is almost always trickier, harder to understand, and often contains more logic paths than the most straightforward code, you shouldn't optimize unless you are committed to spending the time to write a careful unit-test fixture that exercises everything tricky you've done, and write good comments in the code.
Premature Optimization (Score:5, Insightful)
The biggest mistake I see in my professional (and unprofessional) life is programmers who try to optimize their code is all sorts of "733+" ways, trying to "trick" the compiler into removing 1 or 2 lines of assembly, yet completely disregard that they are using a map instead of a hash_map, or doing a linear search when they could do a binary search, or doing the same lookup multiple times, when they could do it just once. It's just silly, and goes to show that lots of programmers don't know how to optimize effectively.
Compilers are good. They optimize code well. Don't try to help them out unless you know your code has a definite bottleneck in a tight loop that needs hand tuning. Focus on using correct algorithms and designing your code from a high level to process data efficiently. Write your code in a clear and easy to read manner, so that you or some other programmer can easily figure out what's going on a few months down the line when you need to add fixes or new functionality. These are the ways to build efficient and maintainable systems, not by writing stuff that you could enter in an obfuscated code contest.
Dear Lord (Score:5, Insightful)
1) Don't know when two things are obviously equivalent to any non-brain dead compiler.
2) Think something other than readability matters.
3) Think the non-idiomatic way of doing something is more readable.
But I'm sure I'm just repeating the comments I can't be bothered reading.
/. posters (Score:5, Insightful)
Somehow 99% of the readers took this to mean "What is the difference between NULL and the zero bit pattern and do you think it is a good idea to write clear code and do the profile/algorithm change cycle until there is nothing left to optimize or should I write low level optimized code from the start?"
sigh.. I've only found two comments with code so far after going through hundreds of posts. This is possibly the worst signal to noise ratio I've witnessed on
Wrong, wrong, wrong (Score:5, Informative)
"ptr == 0" must give the same result as "ptr == NULL", always.
Parent