The new forums will be named Coin Return (based on the most recent vote)! You can check on the status and timeline of the transition to the new forums here.
The Guiding Principles and New Rules document is now in effect.
Making really fast, efficient programs.
Silicon Dioxide
Registered User regular
Registered User regular
So I'm doing an assignment where speed is a very critical issue. What general tips are there to speed up a program? Of course I will be coding in C++/C. I know that C is faster in some regards, but in what ways? Things I'm considering:
1) When possible, do iteration instead of recursion. In fact, should I just avoid function calls in general?
2) When possible, flatten out for loops by just copy and pasting the same code.
3) Should I use custom classes instead of the STL classes? For example, STL vector is a template, and I've heard that has overhead. Should I instead just use a pseudo C class where I have a data structure that's accessed by functions and all memory manipulation is done manually by pointers?
What other general tips are there? For this assignment, style is of no concern; all that matters is raw speed.
1) When possible, do iteration instead of recursion. In fact, should I just avoid function calls in general?
2) When possible, flatten out for loops by just copy and pasting the same code.
3) Should I use custom classes instead of the STL classes? For example, STL vector is a template, and I've heard that has overhead. Should I instead just use a pseudo C class where I have a data structure that's accessed by functions and all memory manipulation is done manually by pointers?
What other general tips are there? For this assignment, style is of no concern; all that matters is raw speed.
Silicon Dioxide on
0
Posts
You'll be surprised about what optimizations are actually worthless since the compiler is already doing them for you. Also, templates don't have any runtime overhead, just compilation. STL containers are extremely efficient. C++ is not inherently slower than C, as a large part of how bitchy it is was based on not forcing the programmer to accept any performance detriment from the language itself. I have heard that you may get a boost from disabling exceptions, and C++ exceptions are terrible anyway and there is no reason to use them. (Forget how to do this though.)
I would recommend the book "Code Complete" by Steve McConnell. It has several chapters confronting just these problems, and it will be extraordinarily helpful in other ways besides. Optimization is not my strong suit, and I'm not going to reproduce McConnell's chapter on "code tuning", but suffice to say there are other things to do that are more significant than just avoiding function calls.
An example: arrange branching control structures so that the most common condition is the one that is tested first.
The only thing you want to worry about during the initial writing is choosing the right containers and algorithms that have the best time complexity for your current problem. Shit like how many function calls you make just doesn't matter any more, and you can do that later once you've gotten the program working under sane conditions.
You sound kind of new to software dev, I'd worry about getting it done at all first, then figuring out optimizations later.
Otherwise, as Lone said, write as you normally would and then figure out how to pare it down.
Haha, you're right - he could, but I think he might be shooting himself in the foot if he tried. Assuming he's writing for modern x86 platforms, writing code in assembly that outperforms compiler generated code is only half the battle.
The other half is knowing about the implementation of the x86 architecture itself (e.g. stuff like pipelines, how the CISC instruction set breaks down into its micro-operation (RISC?) equivalents and can be potentially executed out of order, branch predictions, cache prefetching - etc...) to fully realise which order he should shuffle registers around/make memory accesses, etc...
And even then, I've read it's a bit of a black art involving tons of profiling to see if reordering two instructions really does make a difference.
But yeah. To echo what was said:
Write your programme with what you think are the best containers/algorithms.
Then get a profiler. Find out where you're spending most of your time, and why. Then optimise that part if it's not fast enough.
Why do you need it to be fast anyway? For example, is it a real time system?
Try to find the most efficient algorithms in most cases. I'm guessing they're making you sort stuff and prodding you to use Merge Sort.
The most important part as Doc said is to make a correct program, above all other things. Make it correct, and make it neat. Also, the STL algorithms are designed to be extremely efficient, so feel free to use them. Templates don't create overhead because all that business is dealt with at compile time.
The compiler does most of the petty optimisations you mentioned already if it deems it necessary. Focus on correctness and efficient *algorithms* (sorting, searching) and you'll be fine.
In the end though, probably basically everyone is going to be using the exact same algorithm with the same data structures for the assignment, so clever optimizations will determine the victor. I don't want any hints specific to the problem, because that's sort of cheating, so don't tell me any problem specific tips if by some sort of voodoo magic you've figured out which problem I'm solving. Any general optimizations I can make/pointing me to good resources like that book are much appreciated, though.
Oh, I see theSquid already said that. His last paragraph is spot on.
Pshhh. If you really care about speed, you write a single-clock Verilog implementation and then get a board custom fabbed in a Taiwanese plant.
Really though, the compiler is probably a much better optimizer than you are, especially in the realm of stuff like loop unrolling. As has been mentioned, make sure you're using an efficient algorithm and you'll be okay.
I've only ever used gprof to profile a program... I'm sure there's something similar for Windows, but I have no idea what kinds of tools are out there.
Make it and then make it better
Yeah, that's sort of the point I meant to make. The only way to squeeze every last clock cycle out of your algorithm is to write hand optimized assembly, but the odds of completing the assignment on time and correctly would probably very low unless it's trivial.
Of course, there is one other option:
Also the obvious one is making sure you compile with the highest optimization numbers. This will unroll the loops for you generally and do some really nice things.
And yeah, compiling with the highest optimization possible.
Just make some tight code and the rest will work itself out.
I'm Jacob Wilson. | facebook | thegreat2nd | [url="aim:goim?screenname=TheGreatSecond&message=Hello+from+the+Penny+Arcade+Forums!"]aim[/url]
If I were you, I'd just write it, and if you have time at the end, profile it and optimise it. Don't sacrifice quality for speed, as a working but slow program will be marked much better than a blisteringly fast but buggy program.
Your questions:
1) Iteration is faster than recursion. But don't avoid function calls, as this will be a nightmare to program.
2) Nah. Sounds like a recipe for bugs, and compilers often magically do this sort of thing.
3) Nah. The STL is already optimised, probably better than you could do. Just find out which the faster containers are, and use them in preference over the slower.
[/perl_troll]
I agree with people saying to write it first, benchmark it, and then try things out to see how it affects it the speed, you'll probably find that there won't be much you can do since the compiler has done a lot of it for you.
This is the best advice on the thread. All the crap about loop unrolling and getting rid of functions and iteration vs. recursion is stuff that was (mostly) true in the very early days of computing, but too much has changed since then. By buying into these memes, you're experiencing cargo-cult programming at its finest.
Some advice for you, not knowing anything about your domain or your algorithm:
There are a small number of cases where looking at the assembly level can help, and in these cases usually you want to take what an optimizing compiler already did and disassemble that first. But this is so rarely worth the effort that it's a step of last resort.
It sounds like the edge you want is going to be in using STL (or whatever) in a smart way. Don't do stuff like resize vectors, use the right kind of container for the job, and work in fixed memory. Trying to outsmart the compiler is probably going to get you in trouble.
I guess if you're really trying to trim cycles you can do stuff like ++i instead of i++, but that's unlikely to get you any noticeable gains unless you're doing some serious number-crunching.
No, that's a horrible idea. Perl is terribly slow.
Believe me, I tried to write something slightly computationally intensive in Perl and it was ridiculously slow. Switched it to Java and it was a reasonable speed.
Also, like I said, the algorithms and the optimal data structures are given to us. Of course the first priority will be getting the algorithm working correctly, however that looks to be pretty easy. I will not be able to improve on the asymptotic time.
And Java is not exactly the speed beast itself...
Also, assembly for a RISC processor like MIPS is hard enough. Add in crazy things like non-standard instruction lengths, and I wouldn't touch x86 assembly with a ten-foot pole.
GT: Tanky the Tank
Black: 1377 6749 7425
Okay, just to be clear about the assembly thing:
I was kidding. Mainly because of all the reasons DrFrylock stated.
A profiler is a tool that will run an executable and collect run-time statistics on how much raw cpu time was spent in each function, how many times each function was called, how much time was spent waiting on I/O, etc. It will collect more information than you know what to do with, really. You use the compiler to add extra instrumentation to your code at compile time, and use the profiler at run-time to collect the statistics. On Linux (or other Unix clones), the go-to tool is gprof (part of the gcc toolchain). Google around and you can find some information on how to use it.
There's definitely a learning curve, but if you're a CS student and plan on doing any sort of software development for a living, learning how to use a profiler, debugger, etc are really good skills to learn.
EDIT: But to add something constructive, remember that your biggest efficiency gains will come from improving the slowest part of your program. Seek the bottleneck, improve it till something else is the bottleneck, and repeat.