News for hackers. Stuff that matters.
Re:Stop Using Linked Lists by stormbrew on Wednesday May 22, 2013 @03:27PM (#5753161)
This strikes me as heap management more than a 'linked list implemented as an array'. The heap itself is, after all, equivalent to a giant array.

But it doesn't get you the same locality as an array at any rate. The idea is that, assuming your elements are smaller than a cache line and your array as a whole is larger, what you're avoiding with an array is N/M cache misses while you traverse rather than potentially (or even probably, depending on various other factors) having a cache miss on every nextItem(). You'll also miss more often because of the expansion of the elements.

There are no comments on this comment yet.