Performance Testing for Complex Computations
What are some helpful tips and / or techniques to optimize and improve the computing performance of heavy programs. I'm talking about things like computation of graphics complication or mathematical and simulation types of programming where every second is kept useful, as opposed to heavy IO programs where only a certain amount of speed-up is useful.
Although changing the algorithm is often cited as the most efficient method here, I am trying to figure out how efficient the different algorithms are, so I want to create as efficient as possible with each algorithm. The "problem" I'm solving is not something that is well known, so there are several algorithms on the internet, but I'm looking for any helpful advice on how to proceed and what to look for.
I study the differences in efficiency between evolutionary algorithms and simpler approaches to a specific group of related problems. I have already written three evolutionary algorithms for the problem and now I have written a brute force method which I am trying to do as quickly as possible.
Edit: specify a little more. I am using C # and my algorithms revolve around computing and solving constraint type problems for expressions (using expression trees). By expressions, I mean things like x ^ 2 + 4 or something similar that would be parsed in an expression tree. My algorithms create and process these trees to try and find better approximations. But I wanted to ask a question in general if it helps someone else.
I'm trying to figure out if a useful evolutionary algorithm can be written to find expressions that are a good approximation for various properties. And because I want to know what a good approximation is and see how evolutionary material compares to traditional methods.
a source to share
If your optimization problem is (quasi) convex or can be transformed into this form, there are much more efficient algorithms than evolutionary search.
If you have large matrices, take a look at linear algebra routines. The correct algorithm can make shaving an order of magnitude less computation time, especially if your matrices are sparse.
Think about how data is loaded into memory. Even if you think that you spend most of your time on pure arithmetic, you actually spend a lot of time moving between cache levels, etc. Do the best you can with data in the fastest memory.
Try to avoid unnecessary memory allocation and cancellation. Here's where it might make sense to deviate from a pure OO approach.
a source to share
It's pretty much the same process as any other optimization: profile, experiment, test, repeat.
First, you need to figure out which sections of your code are taking up time. Then try different methods to speed them up (merit-based methods are better than trying at random). A test to see if you have actually accelerated them. If you did, replace the old method with the new one. Profile again.
a source to share
I would recommend against the brute force approach if it is at all possible for others to do so. But, here are some guidelines that should help you speed up your code anyway.
There are many, many different optimizations that you could apply to your code, but before you do anything, you need a profile to figure out where the bottleneck is. Here are some profilers that should give you a good idea of where the hotspots are in your code:
They all use fetch to retrieve their data, so the overhead of running them with your code should be minimal. GProf only requires you to recompile your code. Also, the last three allow you to do both timing and hardware performance counter , so as soon as you hit the time (or CPU cycle), you can get closer to hotter regions and figure out why they might be slower (cache misses, instruction counts FP, etc.).
Beyond that, you need to think about how best to rebuild your code, and it depends on the problem. Perhaps you just got a loop that the compiler doesn't optimize, and you can inline or move things in / out of the loop to help the compiler exit. Or, if you are working as fast as you can using basic arithmetic operations, you can try using vector instructions (SSE, etc.). If your code is concurrent, load balancing issues may arise and you may need to restructure your code so that data is better distributed across cores.
These are just a few examples. Optimizing for performance is tricky and it may not help you nearly enough if you start out with brute force.
For more information on how people have optimized the situation, a few good examples have been presented recently . Why are you coding during the build process? ...
a source to share
It is rather a hint for finding holes in the algorithm itself ...
For maximum performance, simplify everything inside the innermost loop at the expense of everything else.
One example of keeping things simple is the classic ball animation. You can implement gravity by looking at the definition in your physics book and including numbers, or you can do it this way and save precious clock cycles:
initialize:
float y = 0; // y coordinate
float yi = 0; // incremental variable
loop:
y += yi;
yi += 0.001;
if (y > 10)
yi = -yi;
But now tell me you need to do it with nested loops in an N-body simulation where every particle is attracted to every other particle. This can be extremely challenging when you are dealing with thousands of particles.
You should, of course, take the same approach as simplifying everything within the innermost loop. But more than that, at the simplest level, you also need to use data types wisely. For example, math operations are faster when dealing with integers than floating point variables. Also, addition is faster than multiplication, and multiplication is faster than division.
So with all this in mind, you should be able to simplify the innermost loop by using integer addition and multiplication in the first place. And then any scaling you may need can be done later. To take y and yi as an example, if yi is an integer that you change inside the inner loop, then you can scale it after the loop like this:
y += yi * 0.01;
These are very simple low-level performance guidelines, but they are all I try to keep in mind when I work with algorithm-intensive processors. Of course, if you then take these ideas and apply them to parallel processing on a GPU, then you can take it to the next level. =)
a source to share
Well, how you do it depends on what language you use. However, the key is in any language in the profiler. Profile your code. See which features / operations are taking the most time and then determine if you can make those expensive operations more efficient.
The standard bottlenecks in numeric algorithms are memory usage (you access matrices in the order the elements are stored in memory); communication overhead, etc. They may differ from other non-numerical programs.
In addition, many other factors such as prior preparation, etc. can lead to a sharp variation in the performance of the SAME algorithm for the same problem. Make sure you define the optimal parameters for your implementations.
As for comparing different algorithms, I recommend reading the article
"Software for Optimizing Benchmarking with Performance Profiles", Jorge More and Elizabeth D. Dolan, Mathematical Programming 91 (2002), 201-213.
It provides a nice, uniform way to compare different algorithms: it applies to the same set of problems. This should be better known outside the optimistic community (in my not very humble opinion at least).
Good luck!
a source to share