| Branchless search programs | |
| Authors: | Amr Elmasry and Jyrki Katajainen |
| Published in: | Proceedings of the 12th International Symposium on Experimental Algorithms, Lecture Notes in Computer Science 7933, Springer-Verlag (2013), 127-138 |
| Full text: |  PDF (279 kB) |
| DOI: | 10.1007/978-3-642-38527-8_13 |
| Copyright: | © Springer-Verlag GmbH Berlin Heidelberg |
| Abstract: | It was reported in a study by Brodal and Moruz that, due to branch mispredictions, skewed search trees may perform better than perfectly balanced search trees. In this paper we take the search procedures under microscopic examination, and show that perfectly balanced search trees—when programmed carefully—are better than skewed search trees. As in the previous study, we only focus on the static case. We demonstrate that, by decoupling element comparisons from conditional branches and by writing branchless code in general, harmful effects caused by branch mispredictions can be avoided. Being able to store perfectly balanced search trees implicitly, such trees get a further advantage over skewed search trees following an improved cache behaviour. |
| Related: |  HTML (Source code) HTML (Slides) |
| BibLATEX: | @inproceedings{EK2013C,
author = {Amr Elmasry and Jyrki Katajainen},
title = {Branchless search programs},
booktitle = {Proceedings of the 12th International Symposium on Experimental
Algorithms},
series = {Lecture Notes in Computer Science},
volume = {7933},
publisher = {Springer-Verlag},
year = {2013},
pages = {127--138},
}
|