Cache

Questions 1 to 5 of 6

1. 1. A linked list of 1,000,000 nodes with random links and an array of 1,000,000 ints are each walked once. With 16 ints in each 64-byte cache line, about how many cache-line loads does the array walk need?

   1662,5001,000,0004,000,000
2. 2. Walking a linked list of n nodes once takes O(n) steps, the same count as an array walk. Why is each step of a randomly linked list so expensive, according to the lesson?

   Each node holds an 8-byte pointer, so each step reads two valuesEach step does an extra multiplication to work out the next addressThe list is searched from the head for every node, which makes the walk O(n squared)Each step needs the address from the previous read, so each one is a separate slow trip to main memory
3. 3. Why does a loop over an array run faster than a loop over a linked list of the same length?

   Arrays store pointers, which the processor reads faster than node valuesNeighbouring array items share cache lines, so one trip to memory brings in 16 ints, while list nodes can each sit in a separate lineThe processor skips the addition for list nodes, so the array loop does fewer additionsArrays always live in registers, while list nodes always stay in main memory
4. 4. On the test machine, the array row went from 0.22 ns per item at -O2 to about 3 ns at -O0, while the random list stayed near 130 ns. Which explanation fits the lesson?

   -O0 moves the array into a larger cache line, which slows the array-O0 uses 64-bit ints, which doubles the number of trips to memory for the arrayAt -O2 the compiler reorders the list nodes in memory, so the list gets fasterAt -O2 the compiler can add several numbers in one instruction, but the list still waits for each pointer
5. 5. A linked list whose nodes are linked in random order is walked with p = p->next. True or false: the processor cannot start loading the next node until the current node's next pointer has arrived.

   True, because each address comes from the read before it, so the next read cannot start earlyFalse, because a 16-byte node always fits in one cache line, so the next read is always already loaded