next up previous contents
Next: Heaps with holes Up: Performance tuning. Improving the Previous: Avoiding merges

Tuning the page size

  The choice of the page size is in a sense not very critical. It was observed in section 6.3 the internal cost of heapsort does not depend on the page size. Anyway the logical page size should be chosen at least as large as a single page of the memory level that is considered internal. Also, if the alignment of the heap can not be controlled, there is good reason to prefer a much larger page size.

A reasonable upper limit for the page size is 1/4 of the total available buffer space. During siftdown there must be room in memory for 4 pages. 3 pages are used for the parent and its childrens, and one page is used as a merge area.

There are two good arguments for selecting this maximum value as the page size.

First, when the logical page size is larger than the physical page size, the external memory references tend to become sequential. Since most storage systems (including ordinary main memory) favor this type of spatial locality, it can be expected to be good for the performance.

Second, if the program is used in a memory hierarchy with more than two levels, a large value is more likely to help on the lower levels of the memory system as well.

Jesper Bojesen
Sat Apr 3 18:07:59 METDST 1999