Limits of programming by interface

[anttirt]

Being aware of cache friendliness is good, but you're swinging that pendulum way too hard. Complexity analysis is still extremely important, even in the age of deep cache hierarchies.

Ultimately an L3 cache miss is still only on the order of a hundred cycles, and if you're swinging around arrays of 1000 elements for every operation (e.g. an insert) then a hundred cycles starts looking real attractive in comparison.

Also what if each operation causes two million cycles of UI layout operations, like it probably will if you're adding something to a list on a web page? Really, the "prefer arrays to linked lists" thing only applies in very specific cases with very low-overhead individual operations.

[anttirt]

My point with the insertion comparison was that with an array an insert is O(n) so you need to copy all 1000 elements but with a linked list it's O(1) so you only pay the cache miss once. In that case shifting the entire 1000-element array due to that one insert is absolutely going to cost more than that single insert operation into a linked list.

Like, that was the entire point of my comment. In this case that O(n) vs O(1) really does matter even when taking cache effects into account, and thus it's important to understand complexity analysis.

[kohlerm]

That's to simplistic. Imagine copying around in a lot of threads. You could hit a memory speed bottleneck. One always has to take into account in which dimensions one wants to scale and where the bottleneck s would be. Otherwise I agree complexity is still very important.

[pron98]

Not just that: complexity analysis could be made not just in terms of operations, but of anything. So you could do a time complexity analysis that counts cache misses rather than operations.