Cache locality

Questions 1 to 5 of 6

1. 1. The timing program's largest run builds a linked list of 1,000,000 nodes in allocation order. How many nodes does sum_list visit when it walks that list once from the head?

   Type a number.

2. 2. The array scan and the list walk both visit every value once. Which statement gives the right time complexity for each?

   O(log n) for the array and O(n) for the listO(n) for the array and O(n squared) for the shuffled listO(n) for both, so the list is slower by a constant factor that comes from cache missesO(1) for both, because each run is timed once
3. 3. Why is the walk in shuffled order much slower than the walk in allocation order over the same number of nodes?

   Each step lands on a random place in memory, so almost every node read is a cache missThe shuffled list has more nodes than the allocation-order listThe shuffled walk calls sum_list twice for each nodeCPython skips the bytecode loop for lists whose nodes are not in order
4. 4. On most current desktop and server chips, what is the size of a cache line, and how many 4-byte array('i') items fit in one line?

   64 bytes, 4 items32 bytes, 8 items64 bytes, 16 items128 bytes, 32 items
5. 5. The best_ms helper in the timing program runs the work five times and keeps the fastest time, so one slow run caused by background work does not change the reported time.

   False, because it averages all five runs, so one slow run still countsTrue, because a slow run caused by background work is dropped when only the fastest run is kept