It doesn’t sound like you are mentally modeling cache misses correctly. Any access to any array (dense or holey) that isn’t already in cache will result in a mi

It doesn’t sound like you are mentally modeling cache misses correctly. Any access to any array (dense or holey) that isn’t already in cache will result in a miss. A goal is to minimize misses by taking advantage of locality and prefetching. Let’s assume you have an array of objects that are small enough that 4 can fit in a cache line. You take advantage of locality by densely packing them into an array so that you can process 4 adjacent (and aligned) items for the price of only 1 cache miss. The array with holes can reduce your utilization by mixing live and dead data in a single cache line. Worst case would be 1 live item followed by a hole that means the next 3 in the cache line are dead bytes. That cache line only buys you 1 item to process. But, if the hole continues for several more cache lines it’s shouldn’t matter because you should have a means in place to skip all of that dead data and go straight to the next live item. You take advantage of prefetching by processing your array linearly from start to finish so that the CPU will notice and start fetching cache lines further down the array before you even try to access them. Arrays with holes can mess this up by making your access pattern irregular. If your array is very sparse you will be accessing cache lines without a repeating pattern and the CPU won’t be able to figure out how to help. But, the goal is for your array to be fairly dense (or at least reasonably defragmented) so that you end up accessing long, continuous spans of cache lines that make the prefetcher happy. At a minimum, the goal is to do better than most multilevel/tree-based data structures. Check out the writings and presentations of Martin Thompson (“mechanical sympathy” guy). He has made a career of getting good performance out of Java by coding it in the style of embedded-device C programs.