1<html> 2<head> 3<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 4<title>The Average Case</title> 5<link rel="stylesheet" href="../../../../../../../doc/src/boostbook.css" type="text/css"> 6<meta name="generator" content="DocBook XSL Stylesheets V1.79.1"> 7<link rel="home" href="../../../index.html" title="Boost.Sort"> 8<link rel="up" href="../pdqsort.html" title="2.2.- pdqsort"> 9<link rel="prev" href="pdqsort_best.html" title="The Best Case"> 10<link rel="next" href="pdqsort_worst.html" title="The Worst Case"> 11</head> 12<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> 13<table cellpadding="2" width="100%"><tr> 14<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../../boost.png"></td> 15<td align="center"><a href="../../../../../../../index.html">Home</a></td> 16<td align="center"><a href="../../../../../../../libs/libraries.htm">Libraries</a></td> 17<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> 18<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> 19<td align="center"><a href="../../../../../../../more/index.htm">More</a></td> 20</tr></table> 21<hr> 22<div class="spirit-nav"> 23<a accesskey="p" href="pdqsort_best.html"><img src="../../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../pdqsort.html"><img src="../../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../../index.html"><img src="../../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="pdqsort_worst.html"><img src="../../../../../../../doc/src/images/next.png" alt="Next"></a> 24</div> 25<div class="section"> 26<div class="titlepage"><div><div><h4 class="title"> 27<a name="sort.single_thread.pdqsort.pdqsort_avg"></a><a class="link" href="pdqsort_avg.html" title="The Average Case">The Average 28 Case</a> 29</h4></div></div></div> 30<p> 31 On average case data where no patterns are detected <code class="literal"><code class="computeroutput">pdqsort</code></code> is effectively 32 a quicksort that uses median-of-3 pivot selection, switching to insertion 33 sort if the number of elements to be (recursively) sorted is small. The 34 overhead associated with detecting the patterns for the best case is so 35 small it lies within the error of measurement. 36 </p> 37<p> 38 <code class="literal"><code class="computeroutput">pdqsort</code></code> 39 gets a great speedup over the traditional way of implementing quicksort 40 when sorting large arrays (1000+ elements). This is due to a new technique 41 described in "BlockQuicksort: How Branch Mispredictions don't affect 42 Quicksort" by Stefan Edelkamp and Armin Weiss. In short, we bypass 43 the branch predictor by using small buffers (entirely in L1 cache) of the 44 indices of elements that need to be swapped. We fill these buffers in a 45 branch-free way that's quite elegant (in pseudocode): 46 </p> 47<pre class="programlisting">buffer_num = 0; buffer_max_size = 64; 48for (int i = 0; i < buffer_max_size; ++i) { 49 // With branch: 50 if (elements[i] < pivot) { buffer[buffer_num] = i; buffer_num++; } 51 // Without: 52 buffer[buffer_num] = i; buffer_num += (elements[i] < pivot); 53} 54</pre> 55</div> 56<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 57<td align="left"></td> 58<td align="right"><div class="copyright-footer">Copyright © 2014-2017 Steven 59 Ross, Francisco Tapia, Orson Peters<p> 60 Distributed under the <a href="http://boost.org/LICENSE_1_0.txt" target="_top">Boost 61 Software License, Version 1.0</a>. 62 </p> 63</div></td> 64</tr></table> 65<hr> 66<div class="spirit-nav"> 67<a accesskey="p" href="pdqsort_best.html"><img src="../../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../pdqsort.html"><img src="../../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../../index.html"><img src="../../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="pdqsort_worst.html"><img src="../../../../../../../doc/src/images/next.png" alt="Next"></a> 68</div> 69</body> 70</html> 71
