Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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.



Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: