next up previous contents
Next: Analysis Up: Tuning the cache behavior Previous: Tuning the cache behavior

Motivation.- Performance of the implicit heap

Using heaplab, a plot of the running time for the standard heapsort described in chapter 2 on two different machines was produced with an element size of 8 bytes. The result is in figure 5.1.

   figure158
Figure 5.1: Standard Heapsort on PowerPC 332MHz and P2SC 160MHz

It is immediately observed that the performance of heapsort does not follow the theory very well. Especially on the faster machine the curve is far from the straight line it should be if the running time truly was tex2html_wrap_inline1235 . This is of course due to an increased cache miss rate when the problem size grows.

The cache size of the P2SC is 16K elements while the PPC has a first level cache of 4K elements and a second level cache of 32K elements. These numbers fits nicely with the points where the curves breaks.



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