© 1987 by British Computer Society
| ||||||||||||||||||||||||||||||||||||||||||||||||||
Performance of Quicksort Adapted for Virtual Memory Use
Department of Computer Science, University of Helsinki, Tukholmankatu 2, SF-00250 Helsinki, Finland
Several variants of quicksort are compared in order to find an efficient internal sorting algorithm for sorting large files in a virtual memory environment. The algorithms compared are original quicksort; ‘Esort’, which uses a fixed memory partition of two page frames; ‘Wsort’, which combines quicksort with merging and sorts one page at a time to reduce page fetches; and ‘Psort’, which uses manual replacement of pages guided by estimates of the interval to the next reference. The comparison is based on several sorting runs on different-size random-ordered files. A memory management simulator with fetch on demand and working set replacement strategy is used to achieve performance measures: the total execution time, the main memory space allocation, and the main memory space-time integral.
Quicksort achieves its best performance with a relatively small page size and a very small window size. Reducing page faults by increasing the window size results in excessive space allocation. In an optimal environment, Psort gives some 30-40% smaller space-time integral than quicksort. The space allocation sizes are close to each other, but Psort needs less that half of the page fetches of quicksort. The results for Esort are close to those of quicksort. Wsort does not compete favourably with the original quicksort. In a typical virtual memory environment with a large page size and a large window size, both Esort and Psort perform remarkably better than original quicksort. The space-time integral difference of Psort and quicksort is over 50%, and it increases with an increasing file size.
Received January 1986. revised March 1986.
* Department of Computer Science, University of Helsinki, Tukholmankatu 2, SF-00250 Helsinki, Finland