Access Restriction

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

   Open content in new tab
Source: ACM Digital Library