### Performance engineering case study: heap constructionPerformance engineering case study: heap construction

Access Restriction
Subscribed

 Author Bojesen, Jesper ♦ Katajainen, Jyrki ♦ Spork, Maz Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2000 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data Subject Keyword Algorithms ♦ Binary heaps ♦ Code tuning ♦ Experimentation ♦ Memory tuning ♦ Performance ♦ Theory Abstract The behaviour of three methods for constructing a binary heap on a computer with a hierarchical memory is studied. The methods considered are the original one proposed by Williams [1964], in which elements are repeatedly inserted into a single heap; the improvement by Floyd [1964], in which small heaps are repeatedly merged to bigger heaps; and a recent method proposed, e.g., by Fadel et al. [1999] in which a heap is built layerwise. Both the worst-case number of instructions and that of cache misses are analysed. It is well-known that Floyd's method has the best instruction count. Let $\textit{N}$ denote the size of the heap to be constructed, $\textit{B}$ the number of elements that fit into a cache line, and let $\textit{c}$ and $\textit{d}$ be some positive constants. Our analysis shows that, under reasonable assumptions, repeated insertion and layerwise construction both incur at most $\textit{cN/B}$ cache misses, whereas repeated merging, as programmed by Floyd, can incur more than $(\textit{dN}$ log2 $\textit{B})/\textit{B}$ cache misses. However, for our memory-tuned versions of repeated insertion and repeated merging the number of cache misses incurred is close to the optimal bound $\textit{N}/\textit{B}.$ In addition to these theoretical findings, we communicate many practical experiences which we hope to be valuable for others doing experimental algorithmic work. ISSN 10846654 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2000-12-01 Publisher Place New York e-ISSN 10846654 Journal Journal of Experimental Algorithmics (JEA) Volume Number 5

#### Open content in new tab

Source: ACM Digital Library