TAOCP 5.4.9 Exercise 20

Section 5.4.9: Disks and Drums

Exercise 20. ▶ [25] Modern hardware/software systems provide programmers with a virtual memory: Programs are written as if there were a very large internal memory, able to contain all of the data. This memory is divided into pages, only a few of which are in the actual internal memory at any one time; the others are on disks or drums. Programmers need not concern themselves with such details, since the system takes care of everything; new pages are automatically brought into memory when needed.

It would seem that the advent of virtual memory technology makes external sorting methods obsolete, since the job can simply be done using the techniques developed for internal sorting. Discuss this situation; in what ways might a hand-tailored external sorting method be better than the application of a general-purpose paging technique to an internal sorting method?

Verified: no
Solve time: 1m36s

Solution

Virtual memory systems provide the illusion of a large uniform memory by automatically paging data between fast internal memory and slower external storage. While this abstraction simplifies programming, relying on it for sorting massive datasets is generally inferior to a hand‑tailored external sorting algorithm for several reasons:

1. Page size and I/O granularity. Virtual memory typically uses a fixed page size (e.g., 4 KiB) that is much smaller than the optimal block size for disk transfers (tracks or cylinders). A hand‑tailored method can read/write entire tracks or cylinders, amortizing seek and latency overhead over many records. Internal sorting algorithms, when run under paging, generate many small, non‑sequential page faults, increasing total I/O time.

2. Access pattern awareness. External sorting algorithms (e.g., replacement selection, multiway merge) are designed to produce long sequential runs and to merge them with sequential access patterns. The paging system, by contrast, has no knowledge of the algorithm’s future accesses; it must rely on general‑purpose replacement policies (LRU, clock) that cannot anticipate the regular, predictable access patterns of a merge sort. This leads to unnecessary page faults and thrashing when the working set exceeds physical memory.

3. Buffer management and overlap. Hand‑tailored sorts explicitly manage input/output buffers to overlap I/O with computation (double buffering, asynchronous I/O). Virtual memory systems generally do not overlap page fault handling with useful computation in the same way; a page fault typically blocks the process until the page is fetched.

4. Optimization for disk geometry. External sorts can exploit cylinder‑oriented allocation to minimize seek time, and they can use techniques like reading partial tracks without full latency delay (as described in Section 5.4.9). A paging system treats the disk as a linear array of pages and cannot optimize for rotational latency or cylinder boundaries.

5. Control over merge order and run formation. Replacement selection adapts run length to the existing order in the input, often producing runs much longer than the internal memory size. An internal sort like quicksort or heapsort run under paging has no such adaptive mechanism; it simply sorts the entire dataset as if it were in memory, generating a chaotic page reference string.

6. Multiple disks and parallelism. External sorting can stripe data across multiple disks and overlap reads/writes on different devices. Virtual memory typically uses a single swap area and cannot parallelize I/O across multiple disks for a single process.

7. Predictable performance and worst‑case bounds. A well‑designed external sort has a guaranteed number of passes (⌈logₚ R⌉) and total I/O volume proportional to N log N. Paging an internal sort can exhibit highly variable performance depending on the interplay between the algorithm’s access pattern and the replacement policy; worst‑case paging behavior can be dramatically worse than the theoretical I/O complexity.

8. Space overhead. Virtual memory requires page tables and may reserve swap space for the entire virtual address space. External sorting uses only the necessary disk space for the data and temporary files.

In summary, virtual memory is a general‑purpose mechanism that cannot match the specialized I/O optimization, buffer management, and hardware‑aware algorithms of a dedicated external sort. For large‑scale sorting, hand‑tailored methods remain significantly faster and more predictable.

Notes

The argument above applies equally to modern SSDs and HDDs: although seek time and rotational latency are absent on SSDs, the principles of block‑oriented I/O, sequential access optimization, explicit buffer management, and parallelism across channels still make external sorting algorithms superior to paging‑based internal sorts for massive datasets.