We’ve seen how crucial it is to understand data dependencies in order to optimize code. Especially hidden memory dependencies between load and stores can greatly influence performance of work loops. Understanding the data dependency graph of code is often where the real performance gains lie, yet very little attention is given to it in the blogosphere. I’ve read many articles about the impact of branch mispredictions, importance of data locality and caches, but much less about data dependencies. I bet that a question like “why are linked lists slow?” is answered by many in terms of locality, caches or unpredictable random memory access. At least I’ve heard those reasons often, even Stroustrup says as much. Those reasons can play a part, but it’s not the main reason. Fundamentally iterating a linked list has a load-to-use on the critical path, making it 5 times slower than iterating a flat array. Furthermore accessing flat arrays allow loop unrolling which can further improve ILP.
From the article: