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 Algorithmics 24 (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 (2206-0083)
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
Community search over big graphs
Huang X., Lakshmanan L., Xu J.,  Morgan&Claypool Publishers, San Rafael, CA, 2019. 208 pp. Type: Book (978-1-681735-95-5)
Dec 19 2019
Centrality and diversity in search: roles in A.I., machine learning, social networks, and pattern recognition
Murty M., Biswas A.,  Springer International Publishing, New York, NY, 2019. 94 pp. Type: Book (978-3-030247-12-6)
Dec 10 2019
Constant time parallel sorting: an empirical view
Gasarch W., Golub E., Kruskal C.  Journal of Computer and System Sciences 67(1): 63-91, 2003. Type: Article
Nov 21 2003
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright © 2000-2022 ThinkLoud, Inc.
Terms of Use
| Privacy Policy