Code for Game Developers - Processor Pipeline
Without any algorithmic changes we can process the exact same amount of data 40% faster by sorting the data so that the processor can correctly predict branches, thereby keeping the processor's pipeline full.
NB: These days processor pipelines are much longer than the four steps I listed here. In fact processors no longer even always execute code in the same order that it's specified in the program. This just makes thinking about mispredictions all that more important, because as the demo shows the penalty for mispredictions is high.
I feel like saying this again because it's amazing: No algorithmic changes, the exact same amount of data, same optimization level. The only thing that was changed was the order of the data, and we got a 40% perf increase. Wow.
So thinking about your data layout in memory can have huge dividends on how responsive your program is, which will make your players happy.
A few people have mentioned that you can easily remove the if statement. That's true - but it's missing the point. If you remove the if statement you get the exact same speedup as you do by sorting the data. So the penalty from the if statement is because of the branch misprediction, not because of the if statement itself. The if statement doesn't have to be removed, it's more important to think about your data and whether your branches are being well predicted.
Find the source code here: https://github.com/BSVino/MathForGame...
New video every Thursday. Question? Leave a comment below, or ask me on Twitter: / vinobs