Archived

This topic is now archived and is closed to further replies.

"Premature Optimization": A discussion

This topic is 5148 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

"premature optimization is the root of all evil." Do you agree? I for one do not agree that all premature optimization is necessarily bad. I also think that there is a difference between premature optimization and using methods which aren''t a blatant waste of cycles. I''ll quote a recent article on this site:
quote:
Finally, a word about performance. While these idioms can help you write safer and more robust programs, there is a cost associated with them, both in code size and performance overhead. You may not be checking the bounds of std::vector or std::string, but the code inside them certainly is, and this costs CPU cycles. So, you might conclude that the moral of the story is that while this stuff is nice in theory, your application needs to scream, so in reality you''ll just continue using good old fashion pointers, arrays, and homegrown containers. Right? Wrong. As a wise programmer once said, premature optimization is the root of all evil. Do things the safe way first. If your program is slower than you need, *profile it* in a profiler and find the bottlenecks. Then and only then hand tune the offending code. Chances are -- especially in graphics applications and games -- the bottlenecks in your code won''t be in the C++ standard library, but rather in your algorithms.
If you want to use char instead of std::string because you don''t need the extra luggage then I don''t consider that "premature optimization" at all. Any thoughts on the topic? James Simmons MindEngine Development http://medev.sourceforge.net

Share this post


Link to post
Share on other sites
It all depends. Which is why premature optimization is the root of all evil: You often create problems that didn''t exist in the first place.

If you''re doing something where the overhead of std::string could possibly matter, you''d better be doing some seriously wicked data processing, and certainly not games. What kind of game plays with text in really tight loops?

Share this post


Link to post
Share on other sites
GOOD: Choice of appropriate algorithms, data structures, architechture etc at ANALYSIS and DESIGN time.

I wouldn''t call that optimisation but it plays a big part in the final performance of your software. Of course experience learnt from the profiling and optimisation of previous products helps intuition about which algorithms and data structures may be more suitable. [BTW: I definately don''t include micro optimisations in this]

BAD: Not planning/designing, making assumptions without a clear/complete picture of the overall system and making micro optimisations in the middle of coding (usually based on false assumptions about what the compiler will do).

IMO: all actual optimisation (as opposed to optimal design) should be profiler led and only performed after a module or the whole system is working and tested. Anything else is making assumptions and is stabbing in the dark - if you don''t profile, you end up wasting time optimising things which don''t matter and ignore the ones that do!

Share this post


Link to post
Share on other sites
I would say that premature micro-optimzations which decrease readability and maintainability are the root of all evil.

Well, okay, just some evil.

The main point to glean from a discussion of premature optimization is that there''s more to code than its tested execution speed. Code must be able to be understood and modified further down the road; it must in some cases be proven to be robust; it may need to be instrumented for unit testing; it may need to be ported to a system with different capabilities. When writing your code, you need to make design decisions such as what to optimize and how based on the impact of the decision on the entire development process. Far too many programmers get tunnel vision at this point, seeing only the execution trace, and hobble their code with optimizations.

neurokaotix, you say that one often shouldn''t use std::string because of the "extra luggage". Yet do you know what, exactly, that luggage is? do you know what its effect on runtime performance is? Do you know how a char-array would accomplish needed functionality without replicating that luggage in some other way? Many people wrongly assume that library containers such as std::string are a priori inefficient, simply because they are convenient. That equation--convenience and inefficiency--is a dated and dangerous holdover from the early days of high-level programming languages which needs to be nipped in the bud from the minds of neophyte programmers before it takes root. One of the major design concepts of modern languages such as C++ is to give programmers convenience _without_ sacrificing efficiency. A healthy understanding of how C++ does this, as well as knowledge of how to work within that framework by doing things like defining custom allocators instead of tossing it out the window and going back to calloc() and char*''s, is a very useful thing, much more useful than never using STL in time-critical code.


How appropriate. You fight like a cow.

Share this post


Link to post
Share on other sites
I agree that premature optimization is not a good idea when you have the time to develop. As long as you know what interface a class will have, you can easily implement a wrapper that really uses STL or the like and then later change the code to be faster while leaving the interface to be the same.
For example, I think memory management will be one bottleneck in my scripting language, so I did some research. I found that it in memory intensive applications, it can be a problem, and I found many solutions to the problem. I also found a very interesting thesis somebody did on it, and I really like the interface they used, so I copied their basic interface to the memory manager and for now just filled in the functions to use malloc and free. If, in the future, memory management becomes a speed problem, I''ll replace the calls to malloc and free inside the memory manager class with whatever complex algorithm seems appropriate. I even have a template function for allocating classes, so I can specialize it and have different classes get allocated in different ways if that seems efficient.

Share this post


Link to post
Share on other sites
quote:
Original post by neurokaotix
"premature optimization is the root of all evil."

Do you agree? I for one do not agree that all premature optimization is necessarily bad. I also think that there is a difference between premature optimization and using methods which aren't a blatant waste of cycles.



Premature, n: happening, arriving, existing, or performed before the proper, usual, or intended time.

Hence, premature optimization is always bad. The key is to know when the proper time is. And also to know what is a 'blatant waste of cycles' and what is inevitable overhead. Choosing the proper algorithms and data structures for a given problem is not premature optimization, it is design . And doing it right *is* difficult and takes more knowledge than 'noobs' think.

In the end, picking an O(n log n) algorithm over an O(n^3) will probably bring better results than writing your own dynamic array class.

Remember that the best optimization you can apply to a program is the one that takes it from a non-working state to a working state. There is no point to engaging into bit twiddling until you actually have a program that runs and can be profiled. How many projects here die because the programmers spend there time reinventing strings or linked lists "for performance" instead of working on getting the game done ?

quote:
If you want to use char instead of std::string because you don't need the extra luggage then I don't consider that "premature optimization" at all.


Does that mean you should use char*, with all their clunkiness all over your programs ? Don't you think it would be much smarter to use std::string in your program, and to strip it down to char* in the narrow spots where it is really necessary ? If you do it properly, the code calling your function should never notice the difference.

Especially on these boards, 'optimization' is often used to justify superstition; sloppy programming; ignorance of language features, idioms and libraries; and the infamous Not-Invented-Here Syndrome.

-- edit --
quote:
char <-> std::string was just an example, another might be std:list and your own list which you've specialized for your own purposes.


Which implies you had your list already written before your project started (code reuse). Otherwise that is premature optimization.

quote:
I'm simply making a blind assumption that std::string has extra luggage that slows things down. :/


My point, exactly. People make assumptions or rely on hearsay instead of actually learning how things work. Not attacking you personally, but, I wouldn't trust somebody making these assumptions with the job of efficiently reimplementing standard library components, nor to do it with a decent interface (STL-compatible == good)


[ Start Here ! | How To Ask Smart Questions | Recommended C++ Books | C++ FAQ Lite | Function Ptrs | CppTips Archive ]
[ Header Files | File Format Docs | LNK2001 | C++ STL Doc | STLPort | Free C++ IDE | Boost C++ Lib | MSVC6 Lib Fixes ]


[edited by - Fruny on November 5, 2003 5:35:32 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by neurokaotix
I''m simply making a blind assumption that std::string has extra luggage that slows things down. :/

Bad neurokaotix! No cha shu buns for you!

...aw, I just can''t stay mad at you. Here, have a cha shu bun.


How appropriate. You fight like a cow.

Share this post


Link to post
Share on other sites
you should never code at the beginning in a way that you need to write more than needed to solve the task..

my first scene manager was just that:

Intersectable[] objects;

yeah, a great ray-intersection accelerator for realtime raytracing!!

but hey, i could add objects into it, and render them.. so it WAS working.

and THEN you can check WHERE you spend most time, wich parts don''t SCALE well (very important to measure that, too!), and optimize then those..

but NEVER do it before you''re not sure it is a bottleneck.. always just fix the biggest worse bottleneck, don''t touch the rest..


now assuming you determine sqrt is the problem.. great.. because you simply call sqrt everywhere.. optimize that function and you get the speed everywhere. thats "generic code" actually:D

if you determine at one place, sqrt gets called so often, and is still too slow, you recheck that algorithm, if you can possibly use less precicion, or no sqrt at all.. or so.. and then optimize locally there..


never optimize before you got something running. first: working solution, THEN, bugfree solution, THEN, fast solution.

in THAT order.




If that''s not the help you''re after then you''re going to have to explain the problem better than what you have. - joanusdmentia

davepermen.net

Share this post


Link to post
Share on other sites
Sticky this post. I love it.

I see people posting "should I use variables" or "which is faster," when a great majority of the time they are wanting a general answer for a specific problem (theirs). Which makes no sense whatsoever.

Optimization isn''t choosing the right data structures. Thats proper design. You don''t use a linked list for something that is meant to be used as a lookup table. Premature optimization implies you haven''t profiled, which means you are wasting your time.

Share this post


Link to post
Share on other sites
I think especially gamedevelopers could have a set of optimizations ready for use, that the whole team know of. You would always use that particular optimization if it fits. It wouldn''t hurt the readability, because everyone would know about it. If it''s really ugly, you could wrap it into an inline function, or have a standard comment.

You would save much time if you do that, instead of profiling, and finding all those places in the code, you would already have that particular problem solved, and could concentrate on profiling other parts of the program.

I don''t think those kinds of premature optimizations are bad at all. Ok, you don''t know if the final code will benefit anything from it or not, because they might not be in a time critical part of the code. But you don''t loose any time or readability doing so either.

Algorithms are also another thing you should concentrate on, as that''s the most important thing for the final speed. You shouldn''t neccessarily implement the first algorithm you can think of, but instead think a little bit more, not too much, but a little bit, if you can think of a more effective algorithm.

Also using common sense you would know that the innermost rendering loop, will always be one of the bottlenecks, while some menu handling code almost for sure wont. If you weight that against the time it takes to come up with the algorithm you use, you will be fine in most cases.

The kinds of premature optimizations that are bad, are those that you have to think of, and that you solve in a special way for each case, without even knowing if it will actually be faster or not.

Share this post


Link to post
Share on other sites
It depends on what exactly the optimization is. To cite the example in the Lounge thread:
x % 4 == 0
versus
x & 3 == 0

Both are essentially equivalent. But the optimization is pointless. The former will almost certainly become the latter during code generation. Yet the former indicates far more clearly what you''re trying to do.


Minor optimizations that do a slight something without making code any messier or less readable is probably unimportant. Yeah it might help, but it really doesn''t matter. For example, there''s a tip in this issue of the GDNet newsletter about optimizing loops. Yeah it will speed up things in some cases, but it makes the intent far less clear, and a good optimizing compiler should be able to make the change itself anyway.

In truth, there are very few (almost no) microoptimizations that gain anything significant without making the code uglier or less readable or messier. If you happen to find one that has no downsides, more power to you. But it''s really not a big deal.


Focus on the things that matter.

Share this post


Link to post
Share on other sites
Did anyone read the gdnet news letter? There is an optimized loop using pointers in it that I thought was pretty interesting. If it is in fact faster than a normal loop then props to Sander.

edit: Promit beat me to it

James Simmons
MindEngine Development
http://medev.sourceforge.net

[edited by - neurokaotix on November 5, 2003 6:31:05 PM]

Share this post


Link to post
Share on other sites
To make things clear, the optimizations I''m talking about would all be real optimizations, take the example:
x % 4 == 0
versus
x & 3 == 0

from the previous post, originally from the lounge.


If you KNOW the compiler WONT optimize it, then that''s a thing you could use everywhere. But of course all those standard optimizations used has to be proved, otherewise there''s no point. The only thing you don''t know if it will actually benefit any in that particular place.

Share this post


Link to post
Share on other sites
EDIT - forgot my damn password, after writing a damn essay on this post :-(

Anyway ... here's a brief version of what I tried to say.

My normal machine is now an XP2600+, 1Gb high performance RAM, SATA HDD, Geforce FX etc. My test bed machine is a PII350 @ 392Mhz, 512Mb cheap RAM, Geforce 256 etc.

I had to extract data from an octree containing about 10 million stars, and display them in real time. On the main machine performance was great - but on the other machine, performance was crap. I messed around with linked lists, AoS, SoA, memory alignment, linked lists of linked lists etc. Anything to help the cache really. If I couldn't do on a low spec machine, there was no point in doing it.

As it happens, by early optimisation I managed to increase the speed by a factor of around 13 (that's a BIG increase) which meant I was able to go ahead with my plans.

Now, my question is - was that an improvemnt in algorithm, or an early optimisation? I'd suggest the latter. I'm not advocating optimising every single line of code you write - but SOMETIMES it's necessary to time things, and re-write accordingly. To say that early optimising is the 'root of all evil' can be a bit defeatist at times.

Regards
Mark

------------------------------------------------------

IDEA#1 Oh - and seeing as this is a game site ... Do you think that Doom 3 for example would be possible if JC hadn't tested and optimised the rendering from a very early point in development? I'm sure he didn't write a 'good' algorithm and hoped it worked!!!

IDEA#2 Don't flame me for encouraging this 'early optimisation' thing - I'm just saying that a balance is sometimes needed.

[edited by - Shag on November 5, 2003 10:04:05 PM]

Share this post


Link to post
Share on other sites
I always thought money was the root of all evil*. I guess I get to avoid paying for my father''s triple bypass afterall*.

* -> denotes joke. Please do not flame me needlessly.



Wizza Wuzza?

Share this post


Link to post
Share on other sites
I just can't resist this.

quote:
As a wise programmer once said, premature optimization is the root of all evil. Do things the safe way first. If your program is slower than you need, *profile it* in a profiler and find the bottlenecks. Then and only then hand tune the offending code. Chances are -- especially in graphics applications and games -- the bottlenecks in your code won't be in the C++ standard library, but rather in your algorithms.


According to this logic, C++ is a premature optimization. Write your code in Python and hand tune your mainloop/graphics routine in C++. All of your non game-related bugs (ie, memory) will dissipear.

Yes, I am exaggerating somewhat, but the point stands.

And before you flame, note that Humongous Games does exactly this. [http://www.onlamp.com/pub/a/python/2002/07/11/pythonnews.html]

--
Dustin
edit: typo

[edited by - thedustbustr on November 5, 2003 10:52:26 PM]

Share this post


Link to post
Share on other sites
Ah yes, there is nothing Python cannot do I''ve heard. I shall set about trying to get it to program me a new car to drive. And right about now we could use some random Lisp advocacy as well.

Share this post


Link to post
Share on other sites
quote:
Original post by antareus
Ah yes, there is nothing Python cannot do I''ve heard. I shall set about trying to get it to program me a new car to drive. And right about now we could use some random Lisp advocacy as well.
What''s with the sarcastic tone? Telling people to use a HLL and to optimize the relevant parts in C/C++ isn''t a good idea? If not, why not?

Share this post


Link to post
Share on other sites
quote:
Original post by Chris Hare
I always thought money was the root of all evil


The original quote is ''the love of money is a root of all kinds of evil'' from 1 Timothy 6:10

Donald Knuth''s quote was ''Premature optimization is the root of all evil in programming''. And yes he is a Christian. And no he isn''t saying that optimization is evil.

Share this post


Link to post
Share on other sites
quote:
On the main machine performance was great - but on the other machine, performance was crap . I messed around with linked lists, AoS, SoA, memory alignment, linked lists of linked lists etc. Anything to help the cache really. If I couldn''t do on a low spec machine, there was no point in doing it.

As it happens, by early optimisation I managed to increase the speed by a factor of around 13 (that''s a BIG increase) which meant I was able to go ahead with my plans.

Now, my question is - was that an improvemnt in algorithm, or an early optimisation?


The first quoted line above suggests that you *did* profile before performance tuning. If that''s the case, I wouldn''t call this an early optimization. I don''t think PITROAE means finish the entire application before tuning it.

--
Dave Mikesell Software & Consulting

Share this post


Link to post
Share on other sites