+---+---+ +---+---+ +---+---+ | * | *----- >| * | *------>| * | *----> ... +-|-+---+ +-|-+---+ +-|-+---+ | | | V V V element1 element2 element3Note that in the above diagram, element1, element2, etc. may themselves be arbitrary objects, including pairs.
The Scheme system has the freedom to change the location in memory of a pair, provided that it appropriately updates all the pointers pointing to that pair to reflect the new address. One possible strategy would be for the system to try to relocate pairs so that the car pointer usually points to another location on the same page of memory. Another possible strategy would be to try to relocate pairs so that the cdr pointer usually points to another location on the same page. Which strategy is likely to have better performance in a demand-paged virtual memory system? Why?
Instructor: Max Hailperin