Performance Rant (part 2)

Last time I argued performance is still as relevant as ever. This time I'm gonna point out some common coding mistakes to watch out for.

First and foremost: Know your datastructures. This should be trivial computer science 101 material but I'm amazed at how often people get this wrong. Understand BigO notation for worst case runtime and memory behaviour of your algorithms. Understand why worst case isn't all that matters and that the little omitted "constant factor" may just make an O(n log(n)) algorithm a better choice than an O(n) at times. Be aware of the tradeoffs in your particular situation and make a conscious descision. Be wary of programming languages and libraries that blur the distinction and consider it an unimportant implementation detail. There is no such thing as an "ArrayList" and suggesting otherwise should be a criminal offence (yes, I'm looking at you Java). In the same vein, there is a huge difference between an associative container and a plain array. Be very suspicious of languages that treat one like the other and allow indexing arrays with strings (PHP...). And if you do decide to use associative containers (i.e. maps or dictionaries) know whether you are dealing with hash based or tree based implementations. That's a non trivial difference with potentially huge consequences for your code!

Choose the proper tool for the job. Some programming languages are good for one-off scripts or quick prototypes. Be careful trying to morph a proof of concept prototype developed in a fast-to-develop-in but slow-to-execute language into the final product. There is a real and inherent speed difference between different programming languages. And it's not trivial either but can be up to 100x. Trying to optimize a slow program in a slow language is possible, but is like making a top athlete run a marathon in rubber boots. He'll probably still arrive, but why not start in proper running shoes to begin with?

Choose the proper default case when designing your interfaces and decomposing your problem into functions. The common mistake here is to do one matrix-vector multiplication, draw one sprite, measure one line of text, perform one ray-polygon intersection. But is that the most common usage scenario of your functions? Really? Isn't it rather that you usually have lots of similar items and n=1 is the exception rather than the rule? Transform all vertex positions by the view matrix, draw all enemy UFOs, measure the whole text box content and hit test against the full environment? If you design your interfaces to work in batches you'll increase locality, minimize graphics hardware state changes and reduce redundant/repeated set ups and tear downs. Too many libraries get this wrong.

I've mentioned this in the previous paragraph, but it merits repeating: Locality is really important. Keep related data close together in physical memory. Compared to the speed at which modern CPUs operate main memory accesses are glacially slow. You want to take maximum advantage of the CPU's cache hierarchy. The best way to really screw up the cache is to scatter memory accesses all over the place and intermix write and read accesses. This has some interesting consequences. First, simple (sorted) arrays often beat more complex datastructures although theory and BigO analysis would indicate otherwise. Second, classical object oriented object hierarchies are your enemy. Traversing down a nested tree of objects in a loop to call render() on the leaf nodes is really expensive. Keep your hierachies flat and put related objects together.

I've riled against garbage collection before, but this is another reason why you should avoid it. If all your objects have to reside on an automatically managed heap you are completely at the mercy of your runtime environment to make the right decisions which objects to put where.

I could go on for a while, but I think this is a big enough wall of text for one post. Fear the next installment!

PS: Do follow the links - they point to articles, talks and slides of people far more knowledgable and eloquent on the topic than I can ever hope to be.