{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:52:53Z","timestamp":1750308773536,"version":"3.41.0"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2008,6,1]],"date-time":"2008-06-01T00:00:00Z","timestamp":1212278400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2008,6]]},"abstract":"<jats:p>Sorting is one of the most important and well-studied problems in computer science. Many good algorithms are known which offer various trade-offs in efficiency, simplicity, memory use, and other factors. However, these algorithms do not take into account features of modern computer architectures that significantly influence performance. Caches and branch predictors are two such features and, while there has been a significant amount of research into the cache performance of general purpose sorting algorithms, there has been little research on their branch prediction properties. In this paper, we empirically examine the behavior of the branches in all the most common sorting algorithms. We also consider the interaction of cache optimization on the predictability of the branches in these algorithms. We find insertion sort to have the fewest branch mispredictions of any comparison-based sorting algorithm, that bubble and shaker sort operate in a fashion that makes their branches highly unpredictable, that the unpredictability of shellsort's branches improves its caching behavior, and that several cache optimizations have little effect on mergesort's branch mispredictions. We find also that optimizations to quicksort, for example the choice of pivot, have a strong influence on the predictability of its branches. We point out a simple way of removing branch instructions from a classic heapsort implementation and also show that unrolling a loop in a cache-optimized heapsort implementation improves the predicitability of its branches. Finally, we note that when sorting random data two-level adaptive branch predictors are usually no better than simpler bimodal predictors. This is despite the fact that two-level adaptive predictors are almost always superior to bimodal predictors, in general.<\/jats:p>","DOI":"10.1145\/1227161.1370599","type":"journal-article","created":{"date-parts":[[2008,10,8]],"date-time":"2008-10-08T13:57:58Z","timestamp":1223474278000},"page":"1-39","source":"Crossref","is-referenced-by-count":8,"title":["An experimental study of sorting and branch prediction"],"prefix":"10.1145","volume":"12","author":[{"given":"Paul","family":"Biggar","sequence":"first","affiliation":[{"name":"Trinity College Dublin, Ireland"}]},{"given":"Nicholas","family":"Nash","sequence":"additional","affiliation":[{"name":"Trinity College Dublin, Ireland"}]},{"given":"Kevin","family":"Williams","sequence":"additional","affiliation":[{"name":"Trinity College Dublin, Ireland"}]},{"given":"David","family":"Gregg","sequence":"additional","affiliation":[{"name":"Trinity College Dublin, Ireland"}]}],"member":"320","published-online":{"date-parts":[[2008,6,12]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1145\/235968.233336"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1145\/48529.48535"},{"unstructured":"Austin T. Ernst D. Larson E. Weaver C. Raj Desikan R. N. Huh J. Yoder B. Burger D. and Keckler S. 2001. SimpleScalar Tutorial (for release 4.0).","key":"e_1_2_1_3_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1002\/spe.4380231105"},{"key":"e_1_2_1_5_1","volume-title":"Tech. Rep. TCD-CS-05-57 (Aug.) University of Dublin","author":"Biggar P.","year":"2005","unstructured":"Biggar, P. and Gregg, D. 2005. Sorting in the presence of branch prediction and caches. Tech. Rep. TCD-CS-05-57 (Aug.) University of Dublin, Trinity College."},{"doi-asserted-by":"publisher","unstructured":"Brodal G. S. and Moruz G. 2005. Tradeoffs between branch mispredictions and comparisons for sorting algorithms. In WADS. 385--395. 10.1007\/11534273_34","key":"e_1_2_1_6_1","DOI":"10.1007\/11534273_34"},{"volume-title":"Proceedings of the 7th Workshop on Algorithm Engineering and Experiments. 130--140","author":"Brodal G. S.","unstructured":"Brodal, G. S., Fagerberg, R., and Moruz, G. 2005. On the adaptiveness of quicksort. In Proceedings of the 7th Workshop on Algorithm Engineering and Experiments. 130--140.","key":"e_1_2_1_7_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1145\/1227161.1227164"},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1147\/sj.451.0059"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1145\/355588.365103"},{"doi-asserted-by":"publisher","key":"e_1_2_1_11_1","DOI":"10.1145\/320831.320833"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.5555\/795665.796479"},{"key":"e_1_2_1_13_1","volume-title":"Pascal and C","author":"Gonnet G. H.","unstructured":"Gonnet, G. H. and Baeza-Yates, R. 1991. Pascal and C, 2nd ed. Addison-Wesley Longman Publ., Reading, MA.","edition":"2"},{"unstructured":"Haahr M. 2006. Random.org: True random number service. Web resource available at http:\/\/www.random.org.","key":"e_1_2_1_14_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.5555\/77493"},{"unstructured":"Hinton G. Sager D. Upton M. Carmean D. Kyker A. and Roussel P. 2001. The microarchitecture of the pentium 4 processor. Intel Technol. J. Q1.","key":"e_1_2_1_16_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_17_1","DOI":"10.1093\/comjnl\/5.1.10"},{"unstructured":"Intel. 2001. Desktop performance and optimization for intel pentium 4 processor. Tech. Rept.","key":"e_1_2_1_18_1"},{"unstructured":"Intel. 2004. Ia-32 intel architecture optimization \u2014 reference manual. Tech. Rept.","key":"e_1_2_1_19_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1007\/11841036_69"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.5555\/642136.642138"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.5555\/260999"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.5555\/280635"},{"doi-asserted-by":"publisher","key":"e_1_2_1_25_1","DOI":"10.1145\/235141.235145"},{"doi-asserted-by":"publisher","key":"e_1_2_1_26_1","DOI":"10.5555\/314161.314324"},{"doi-asserted-by":"publisher","key":"e_1_2_1_27_1","DOI":"10.1109\/CGO.2005.24"},{"unstructured":"Mucci P. J. 2004. PapiEx Man Page.","key":"e_1_2_1_28_1"},{"unstructured":"Mudge T. Chen I.-C. and Coffey J. 1996. Limits to branch prediction. Tech. Rept. CSE-TR-282-96. 2.","key":"e_1_2_1_29_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_30_1","DOI":"10.1145\/191839.191884"},{"doi-asserted-by":"publisher","key":"e_1_2_1_31_1","DOI":"10.1145\/945394.945401"},{"key":"e_1_2_1_32_1","volume-title":"Algorithms ESA 2004: 12th Annual European Symposium, S. Albers and T. Radzik, Eds. Lecture Notes in Computer Science","volume":"3221","author":"Sanders P.","unstructured":"Sanders, P. and Winkel, S. 2004. Super scalar sample sort. In Algorithms ESA 2004: 12th Annual European Symposium, S. Albers and T. Radzik, Eds. Lecture Notes in Computer Science, vol. 3221. Springer, Berlin. 784--796."},{"doi-asserted-by":"publisher","key":"e_1_2_1_33_1","DOI":"10.1145\/359619.359631"},{"doi-asserted-by":"publisher","key":"e_1_2_1_34_1","DOI":"10.5555\/558760"},{"doi-asserted-by":"publisher","key":"e_1_2_1_35_1","DOI":"10.1145\/368370.368387"},{"doi-asserted-by":"publisher","key":"e_1_2_1_36_1","DOI":"10.1109\/2.589913"},{"doi-asserted-by":"publisher","key":"e_1_2_1_37_1","DOI":"10.1145\/944618.944627"},{"doi-asserted-by":"publisher","key":"e_1_2_1_38_1","DOI":"10.1145\/512274.512284"},{"doi-asserted-by":"publisher","key":"e_1_2_1_39_1","DOI":"10.1145\/351827.384245"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1227161.1370599","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1227161.1370599","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:37Z","timestamp":1750278157000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1227161.1370599"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6]]},"references-count":38,"alternative-id":["10.1145\/1227161.1370599"],"URL":"https:\/\/doi.org\/10.1145\/1227161.1370599","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2008,6]]}}}