title: Does retrieval from NSArray exhibit cache locality?
body: <p>When looping through a normal C array, the CPU intelligently grabs surrounding cells from RAM and sticks them in CPU cache. The CPU knows that if you're grabbing index 6, you're likely going to need index 7 soon after. Do Objective-C NSArrays also exibit <a href="https://en.wikipedia.org/wiki/Locality_of_reference" rel="nofollow">locality of reference</a>?</p>
  
  <pre><code>for (id item in array) {
    NSLog(@"%@", item);
  }
  
  for (NSUInteger i = 0; i &lt; array.count; i++) {
    NSLog(@"%@", array[i];
  }
  </code></pre>
  
  <p>People working outside of Apple don't have the internal implementation of NSArray. However, one can guess that NSMutableArray is likely implemented with a linked list since it has methods to slice the array from any index. If we assume that NSArray is backed by the same data store as NSMutableArray, then all NSArray do not exhibit locality of reference.</p>
  
  <p>The reason I ask is that I'm optimizing UITableViewCell height calculations by storing the heights in a cache. The cache would be more easily implemented as an NSMutableDictionary than NSMutableArray, so that I don't have to deal with gaps in arrays (which are not allowed). If NSArray provides locality of reference, then I would switch to NSArray for extra performance and endure this extra complexity.</p>