There are two basic ways of storing a sequence of values on a computer: in an array, where adjacent elements sit next to each other in memory, or in a linked list, where each value is stored with a reference to the next one in a structure called a node, and the nodes could be located anywhere in memory (see diagram below).

You may already know that array storage is very fast for random access (jumping to any element by index). On the other hand, linked lists are geared towards sequential access (e.g., iterating over the elements). In this question we'll explore how expensive these operations are in the presence of a cache.

Suppose we have a two-level memory system where the memory access time is 245 cycles and cache access time is 5 cycles. The cache holds lines of 64 bytes, meaning that we copy data from RAM to cache in chunks of 64 bytes.

Say we have an array of 1000 ints and we iterate over it from beginning to end something like this: a. As we iterate over the array, we will have some cache hits and some cache misses. When there's a miss, how many array elements will be loaded into cache at once? (Assume that ints are 4 bytes and remember that cache lines are 64 bytes.)

b. Based on that, approximately how many cache misses will there be across the 1000 times we access array elements?

c. Now assume a similar situation but with a linked list instead of array: we have a linked list of 1000 ints and are iterating over all of them in order. In the best possible case, all the linked list nodes are consecutive in memory: each node value is immediately followed by the reference, and then the next node is immediately after it. Now, when there's a miss, approximately how many linked list elements will be loaded into the cache at once? (Assume that ints are still 4 bytes and references are 8 bytes.)

d. Based on that, approximately how many cache misses will there be across the 1000 times we access linked list elements?

e. Based on your answers above, which of the two storage methods array and linked list is likely to benefit more from cache? Explain. (As you think about this, keep in mind that in a realistic linked list, the nodes are not likely to be consecutive in memory: the selling point of linked lists is that it's fast to insert and delete nodes, and when you do enough of that, they're not consecutive in memory anymore!)

Array storage 25 17 91 42 Two methods of storing the same sequence of numbers Linked list storage value ref 25 42 91 17 node for (int i = 0; i