| Performance engineering case study: Heap construction | |
| Authors: | Jesper Bojesen, Jyrki Katajainen, and Maz Spork |
| Published in: | Proceedings of the 3rd International Workshop on Algorithm Engineering, Lecture Notes in Computer Science 1668, Springer-Verlag (1999), 301–315 |
| Full text: |  PS (582 kB) |
| DOI: | 10.1007/3-540-48318-7_24 |
| Copyright: | © Springer-Verlag |
| Abstract: | The behaviour of three methods for constructing a binary heap 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 N denote the size of the heap to be constructed, B the number of elements that fit into a cache line, and let c and d be some positive constants. Our analysis shows that, under reasonable assumptions, repeated insertion and layerwise construction both incur at most c N/B cache misses, whereas repeated merging, as programmed by Floyd, can incur more than (d N log2 B)/B cache misses. However, for a memory-tuned version of repeated merging the number of cache misses incurred is close to the optimal bound N/B. |
| Related: |  HTML (Slides) HTML (Slides) HTML (Technical report) HTML (Journal article) HTML (Errata) |
| BibLATEX: | @inproceedings{BKS1999aC,
author = {Jesper Bojesen and Jyrki Katajainen and Maz Spork},
title = {Performance engineering case study: {H}eap construction},
booktitle = {Proceedings of the 3rd International Workshop on Algorithm
Engineering},
series = {Lecture Notes in Computer Science},
volume = {1668},
publisher = {Springer-Verlag},
year = {1999},
pages = {301--315},
}
|