WarStalkeR wrote:
Hello Kovarex, as True God of Optimization, can you please post some short tips for optimization for Stellaris developers? Either they have hard time or just can't into optimization as they should (as almost everybody else). Just post these tips here and I will make sure that they will see them one way or another. Thanks!
I'm no kovarex but the high-level ideas for low-level optimizations applies equally to pretty much every code regardless of language or CPU used.
*) Before starting with *any* optimizations, run your code in a profiler to see what really takes the most time. There are tools that use special CPU instructions to profile your code without causing massive overhead. VTune is probably the best but costs a ton. MSVC also has something similar and is free
*) Before looking for chances of low-level optimizations, see if you could use more efficient algorithms
*) Try to allocate-free memory rarely as possible. Both are VERY expensive operations.
*) keep your data structures together in memory (arrays instead of linked lists wherever it makes sense)
*) if you have to iterate over the same array multiple times, try to replace it with a single iteration where you do all the operations at same time
*) Conditional branching (if then else) is relatively expensive, try to minimize them. If you can replace an if with a simple-ish calculation, it usually makes sense to do it.
*) Lookup tables are often but not always cheaper than re-calculating stuff as needed. Just make sure they're not big enough to trash the cache
*) Using binary search in arrays of ~100 elements is slower than linear iteration over it assuming check is relatively simple (checking for boolean or a couple of numeric values). In addition, you won't have to keep it sorted to even allow for binary search.
*) Use the smallest data types you can get away with (32bit int instead of 64, float instead of double)
*) If you use SIMD anywhere, make absolutely sure that your arrays are cache line aligned and preferrably get your data structures to be small enough to fit in a cache line.
*) Object oriented programming with class hierarchies and virtual functions usually makes code easier to write but calling virtual functions can be extremely expensive. Similarly, c++ templates can generate a huge amount of code that ends up trashing your memory.
*) Move as much stuff out of loops as you can. E.g if you loop over an array and check its size as the end condition, that check can be quite expensive if it's some kind of a relatively complex thingy (e.g child object inside a virtual class). I have had a case where moving such a check out from loop header made the *overall* application run several percentages faster and the program was anything but trivial.
*) Most modern languages have some basic forms of code parallelization built-in (usually some kind of parallel for loop). If you have calculations you perform on a ton of objects that don't have side effects, using those can give some "free" performance.
*) When working with arrays with more than one dimension, make sure you iterate over the elements in the order they are laid out in memory.
*) When filling arrays with data, try to figure out their final size before allocating them. Doing x.append(y) or x.add(y) can become awfully slow when the library has to reallocate the buffer every time it runs out of space.
There are a ton more tricks but those are some of the things that come to mind right now. Of these, profiling and figuring out better algorithms are by far the most important ones.