On Wed, 17 Sep 2014 00:03:55 +0100 Maxime Coste <frrr...@gmail.com> wrote:
> Ok, so on a modern processor, data access pattern matters, with your linked > list, > you basically have a cache miss at each access to the next element when you > iterate, > when you use an array, you get linear access in memory, which means you > please the > prefetcher and avoid most cache misses. That effect on performance is huge, > and > in practice largely dominate the algorithmic complexity. It's always funny to read when people try to game their compiler or processor into doing something. In reality, the most modern processors are far from the cache-hit-or-miss-machine often described even in academic system-theory. Instead, they _normally_ run and run until they miss cache, so all this fancy stuff you C++-advocates try to sell us for "better performance" is bullshit. Of course linked lists come with an overhead and arrays are faster. Nothing new. But you're wrong in trying to pull in the processor to explain why. Cheers FRIGN -- FRIGN <d...@frign.de>