3 ms·
Under what circumstances to non-contiguous data structures run faster? I know of circumstances where structures with pointers make it easier to get better asymp
by chas 6y ago
Under what circumstances to non-contiguous data structures run faster? I know of circumstances where structures with pointers make it easier to get better asymptotic behavior with a large amount of data, but none where a linked structure out-performs the analogous contiguous one on moderate amounts (a few cache lines) of data.
- bluGill 6y agoI wondered when he learned that. I learned the same thing in 1996, but modern cpus were not yet (the the knowledge of the class, I'm sure they were doing it...) dining prediction in the cache to load the next required memory before it was required. This optimization changed things such that linear search often is faster than binary search (unless n is very large of course)