An experimental study of sorting and branch prediction

ABSTRACT

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.

REFERENCES

• 1: Ramesh C. Agarwal, A super scalar sort algorithm for RISC processors, ACM SIGMOD Record, v.25 n.2, p.240-246, June 1996
• 2: Alok Aggarwal , Jeffrey,S. Vitter, The input/output complexity of sorting and related problems, Communications of the ACM, v.31 n.9, p.1116-1127, Sept. 1988 [doi>10.1145/48529.48535]
• 3: 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).
• 4: Jon L. Bentley , M. Douglas McIlroy, Engineering a sort function, Software—Practice & Experience, v.23 n.11, p.1249-1265, Nov. 1993 [doi>10.1002/spe.4380231105]
• 5: 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.
• 6: Brodal, G. S. and Moruz, G. 2005. Tradeoffs between branch mispredictions and comparisons for sorting algorithms. In WADS. 385--395.
• 7: 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.
• 8: Gerth Stølting Brodal , Rolf Fagerberg , Kristoffer Vinther, Engineering a cache-oblivious sorting algorithm, Journal of Experimental Algorithmics (JEA), 12, June 2008
• 9: A. E. Eichenberger , J. K. O'Brien , K. M. O'Brien , P. Wu , T. Chen , P. H. Oden , D. A. Prener , J. C. Shepherd , B. So , Z. Sura , A. Wang , T. Zhang , P. Zhao , M. K. Gschwind , R. Archambault , Y. Gao , R. Koo, Using advanced compiler technology to exploit the performance of the Cell Broadband Engine^TM architecture, IBM Systems Journal, v.45 n.1, p.59-84, January 2006
• 10: Floyd, R. W. 1964. Treesort 3: Algorithm 245. Communi. ACM 7, 12, 701.
• 11: Edward H. Friend, Sorting on Electronic Computer Systems, Journal of the ACM (JACM), v.3 n.3, p.134-168, July 1956 [doi>10.1145/320831.320833]
• 12: Matteo Frigo , Charles E. Leiserson , Harald Prokop , Sridhar Ramachandran, Cache-Oblivious Algorithms, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.285, October 17-18, 1999
• 13: Gonnet, G. H. and Baeza-Yates, R. 1991. Pascal and C, 2nd ed. Addison-Wesley Longman Publ., Reading, MA.
• 14: Haahr, M. 2006. Random.org: True random number service. Web resource, available at http://www.random.org.
• 15: David A. Patterson , John L. Hennessy, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 16: 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.
• 17: Hoare, C. A. R. 1962. Quicksort. Comput. J. 5, 1, 10--15.
• 18: Intel. 2001. Desktop performance and optimization for intel pentium 4 processor. Tech. Rept.
• 19: Intel. 2004. Ia-32 intel architecture optimization — reference manual. Tech. Rept.
• 20: Kanela Kaligosi , Peter Sanders, How branch mispredictions affect quicksort, Proceedings of the 14th conference on Annual European Symposium, p.780-791, September 11-13, 2006, Zurich, Switzerland [doi>10.1007/11841036_69]
• 21: Jyrki Katajainen , Tomi Pasanen , Jukka Teuhola, Practical in-place mergesort, Nordic Journal of Computing, v.3 n.1, p.27-40, Spring 1996
• 22: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 23: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 24: Anthony George Lamarca , Richard E. Ladner, Caches and algorithms, University of Washington, 1996
• 25: Anthony LaMarca , Richard Ladner, The influence of caches on the performance of heaps, Journal of Experimental Algorithmics (JEA), 1, p.4-es, 1996 [doi>10.1145/235141.235145]
• 26: Anthony LaMarca , Richard E. Ladner, The influence of caches on the performance of sorting, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.370-379, January 05-07, 1997, New Orleans, Louisiana, United States
• 27: Xiaoming Li , Maria Jesus Garzaran , David Padua, Optimizing Sorting with Genetic Algorithms, Proceedings of the international symposium on Code generation and optimization, p.99-110, March 20-23, 2005 [doi>10.1109/CGO.2005.24]
• 28: Mucci, P. J. 2004. PapiEx Man Page.
• 29: Mudge, T., Chen, I.-C., and Coffey, J. 1996. Limits to branch prediction. Tech. Rept. CSE-TR-282-96. 2.
• 30: Chris Nyberg , Tom Barclay , Zarka Cvetanovic , Jim Gray , Dave Lomet, AlphaSort: a RISC machine sort, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.233-242, May 24-27, 1994, Minneapolis, Minnesota, United States
• 31: Naila Rahman , Rajeev Raman, Adapting Radix Sort to the Memory Hierarchy, Journal of Experimental Algorithmics (JEA), 6, p.7-es, 2001 [doi>10.1145/945394.945401]
• 32: 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.
• 33: Robert Sedgewick, Implementing Quicksort programs, Communications of the ACM, v.21 n.10, p.847-857, Oct. 1978 [doi>10.1145/359619.359631]
• 34: Robert Sedgewick, Algorithms in C, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2002
• 35: D. L. Shell, A high-speed sorting procedure, Communications of the ACM, v.2 n.7, p.30-32, July 1959 [doi>10.1145/368370.368387]
• 36: Augustus K. Uht , Vijay Sindagi , Sajee Somanathan, Branch Effect Reduction Techniques, Computer, v.30 n.5, p.71-81, May 1997 [doi>10.1109/2.589913]
• 37: Rajiv Wickremesinghe , Lars Arge , Jeffrey S. Chase , Jeffrey Scott Vitter, Efficient sorting using registers and caches, Journal of Experimental Algorithmics (JEA), 7, p.9, 2002 [doi>10.1145/944618.944627]
• 38: Williams, J. W. J. 1964. Heapsort: Algorithm 232. Commun. ACM 7, 6, 347--348.
• 39: Li Xiao , Xiaodong Zhang , Stefan A. Kubricht, Improving memory performance of sorting algorithms, Journal of Experimental Algorithmics (JEA), 5, p.3-es, 2000 [doi>10.1145/351827.384245]

INDEX TERMS

Primary Classification:
  E. Data
  E.5 FILES
      Subjects: Sorting/searching

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Pipeline processors

General Terms:
Algorithms, Experimentation, Measurement, Performance

Keywords:
Sorting, branch prediction, caching, pipeline architectures