Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
BlockQuicksort: avoiding branch mispredictions in Quicksort
Edelkamp S., Weiß A. Journal of Experimental Algorithmics24 (1):1-22,2019.Type:Article
Date Reviewed: Apr 1 2022

Quite often algorithms with bad worst-case complexity perform better on the average. Quicksort falls into this class. However, one of the drawbacks of Quicksort is that it is vulnerable to branch mispredictions, that is, branch misses. Modern processors have long pipelines that have to be filled fresh for every miss, causing undesirable execution delay. The authors address this problem by adopting what they call a “partially decoupling control from dataflow.”

As presented in the paper, partitioning is achieved by dividing the array to be sorted into equally sized blocks. Each block element is then compared with the pivot, and the results are stored in a buffer. In the second pass, an interchange of respective elements takes place, thereby avoiding conditional branches. The average number of branch mispredictions turns out to be εnlogn + Ο(n) where ε is a small positive number that is a function of block size. The authors also report an 80 percent increase in sorting speed over the GCC implementation of Quicksort (C++ std::sort).

Quicksort has another disadvantage: it is sensitive to ties. I have worked on several improved versions of Quicksort--including some developed by my own scholars--and have found that, despite the improvements, this disadvantage remains. It is therefore of interest to see how far the authors’ version can tackle this sensitivity.

The paper is interesting and should be of use to advanced undergraduate and postgraduate students, researchers, and practitioners of computing science.

Reviewer:  Soubhik Chakraborty Review #: CR147426
Bookmark and Share
  Editor Recommended
Featured Reviewer
 
 
Sorting/ Searching (E.5 ... )
 
 
General (F.0 )
 
Would you recommend this review?
yes
no
Other reviews under "Sorting/Searching": Date
New techniques for best-match retrieval
Shasha D. (ed), Wang T. ACM Transactions on Information Systems 8(2): 140-158, 2001. Type: Article
Jun 1 1991
An adaptation of a root finding method to searching ordered disk files
Armenakis A., Garey L., Gupta R. BIT 25(4): 562-568, 1985. Type: Article
Mar 1 1987
Approximating shortest superstrings with constraints
Jiang T., Li M. (ed) Theoretical Computer Science 134(2): 473-491, 1994. Type: Article
Nov 1 1995
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy