research-article

Free access

Analysis of branch misses in quicksort

Authors:

Conrado Martínez,

Markus E. Nebel,

Sebastian WildAuthors Info & Claims

Proceedings of the Meeting on Analytic Algorithmics and Combinatorics

Pages 114 - 128

Published: 04 January 2015 Publication History

Abstract

The analysis of algorithms mostly relies on counting classic elementary operations like additions, multiplications, comparisons, swaps etc. This approach is often sufficient to quantify an algorithm's efficiency. In some cases, however, features of modern processor architectures like pipelined execution and memory hierarchies have significant impact on running time and need to be taken into account to get a reliable picture. One such example is Quicksort: It has been demonstrated experimentally that under certain conditions on the hardware the classically optimal balanced choice of the pivot as median of a sample gets harmful. The reason lies in mispredicted branches whose rollback costs become dominating.

In this paper, we give the first precise analytical investigation of the influence of pipelining and the resulting branch mispredictions on the efficiency of (classic) Quicksort and Yaroslavskiy's dual-pivot Quicksort as implemented in Oracle's Java 7 library. For the latter it is still not fully understood why experiments prove it 10% faster than a highly engineered implementation of a classic single-pivot version. For different branch prediction strategies, we give precise asymptotics for the expected number of branch misses caused by the aforementioned Quicksort variants when their pivots are chosen from a sample of the input. We conclude that the difference in branch misses is too small to explain the superiority of the dual-pivot algorithm.

References

[1]

P. Biggar, N. Nash, K. Williams, and D. Gregg. An experimental study of sorting and branch prediction. Journal of Experimental Algorithmics, 12: 1, June 2008.

Digital Library

[2]

G. Brodal and G. Moruz. Tradeoffs between branch mispredictions and comparisons for sorting algorithms. In WADS 2005, volume 3608 of LNCS, pages 385--395. Springer, 2005.

Digital Library

[3]

A. Fog. The microarchitecture of Intel, AMD and VIA CPUs, 2014. URL http://www.agner.org/optimize/#manuals.

[4]

R. L. Graham, D. E. Knuth, and O. Patashnik. Concrete mathematics: a foundation for computer science. Addison-Wesley, 1994. ISBN 978-0-20-155802-9.

Digital Library

[5]

P. Hennequin. Analyse en moyenne d'algorithmes: tri rapide et arbres de recherche. PhD Thesis, Ecole Politechnique, Palaiseau, 1991.

[6]

C. A. R. Hoare. Algorithm 63: Partition. Communications of the ACM, 4(7):321, July 1961.

Digital Library

[7]

K. Kaligosi and P. Sanders. How branch mispredictions affect quicksort. In T. Erlebach and Y. Azar, editors, ESA 2006, volume 4168 of LNCS, pages 780--791. Springer, 2006.

Digital Library

[8]

S. Kushagra, A. López-Ortiz, A. Qiao, and J. I. Munro. Multi-Pivot Quicksort: Theory and Experiments. In ALENEX 2014, pages 47--60. SIAM, 2014.

Digital Library

[9]

H. M. Mahmoud. Sorting: A distribution theory. John Wiley & Sons, 2000. ISBN 1-118-03288-8.

[10]

C. Martínez and S. Roura. Optimal Sampling Strategies in Quicksort and Quickselect. SIAM Journal on Computing, 31(3):683, 2001.

Digital Library

[11]

M. E. Nebel and S. Wild. Pivot Sampling in Dual-Pivot Quicksort. In AofA 2014, 2014. URL http://arxiv.org/abs/1403.6602.

[12]

S. Roura. Improved Master Theorems for Divide-and-Conquer Recurrences. Journal of the ACM, 48 (2):170--205, 2001.

Digital Library

[13]

R. Sedgewick. Quicksort. PhD Thesis, Stanford University, 1975.

[14]

R. Sedgewick. Implementing Quicksort programs. Communications of the ACM, 21(10):847--857, 1978.

Digital Library

[15]

S. Wild. Java 7's Dual Pivot Quicksort. Master thesis, University of Kaiserslautern, 2012.

[16]

S. Wild and M. E. Nebel. Average Case Analysis of Java 7's Dual Pivot Quicksort. In L. Epstein and P. Ferragina, editors, ESA 2012, volume 7501 of LNCS, pages 825--836. Springer, 2012.

Digital Library

[17]

S. Wild, M. E. Nebel, and R. Neininger. Average Case and Distributional Analysis of Dual-Pivot Quicksort, 2013. URL http://arxiv.org/abs/1304.0988.

Cited By

Edelkamp SWeiß A(2019)BlockQuicksortACM Journal of Experimental Algorithmics10.1145/327466024(1-22)Online publication date: 30-Jan-2019
https://dl.acm.org/doi/10.1145/3274660
Aumüller MDietzfelbinger MKlaue P(2016)How Good Is Multi-Pivot Quicksort?ACM Transactions on Algorithms10.1145/296310213:1(1-47)Online publication date: 10-Oct-2016
https://dl.acm.org/doi/10.1145/2963102
Aumüller MDietzfelbinger M(2015)Optimal Partitioning for Dual-Pivot QuicksortACM Transactions on Algorithms10.1145/274302012:2(1-36)Online publication date: 17-Nov-2015
https://dl.acm.org/doi/10.1145/2743020

Index Terms

Analysis of branch misses in quicksort
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Combinatorial algorithms
      2. Enumeration
2. Theory of computation
  1. Design and analysis of algorithms
    1. Data structures design and analysis
      1. Sorting and searching

Recommendations

Analysis of Pivot Sampling in Dual-Pivot Quicksort: A Holistic Analysis of Yaroslavskiy's Partitioning Scheme

The new dual-pivot Quicksort by Vladimir Yaroslavskiy--used in Oracle's Java runtime library since version 7--features intriguing asymmetries. They make a basic variant of this algorithm use less comparisons than classic single-pivot Quicksort. In this ...
Engineering quicksort

This paper describes the results of a large empirical study to measure the run-time behavior of Quicksort by using various methods of computing the pivot element for medium to large size randomly generated integer data. The results of our study ...
Some performance tests of “quicksort” and descendants

Detailed performance evaluations are presented for six ACM algorithms: quicksort (No. 64), Shellsort (No. 201), stringsort (No. 207), “TREESORT3” (No. 245), quickersort (No. 271), and qsort (No. 402). Algorithms 271 and 402 are refinements of algorithm ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Proceedings of the Meeting on Analytic Algorithmics and Combinatorics

January 2015

137 pages

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 04 January 2015

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
71
Total Downloads

Downloads (Last 12 months)50
Downloads (Last 6 weeks)15

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Edelkamp SWeiß A(2019)BlockQuicksortACM Journal of Experimental Algorithmics10.1145/327466024(1-22)Online publication date: 30-Jan-2019
https://dl.acm.org/doi/10.1145/3274660
Aumüller MDietzfelbinger MKlaue P(2016)How Good Is Multi-Pivot Quicksort?ACM Transactions on Algorithms10.1145/296310213:1(1-47)Online publication date: 10-Oct-2016
https://dl.acm.org/doi/10.1145/2963102
Aumüller MDietzfelbinger M(2015)Optimal Partitioning for Dual-Pivot QuicksortACM Transactions on Algorithms10.1145/274302012:2(1-36)Online publication date: 17-Nov-2015
https://dl.acm.org/doi/10.1145/2743020

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents