diff options
Diffstat (limited to 'libs/sort/doc/html/index.html')
| -rw-r--r-- | libs/sort/doc/html/index.html | 668 |
1 files changed, 668 insertions, 0 deletions
diff --git a/libs/sort/doc/html/index.html b/libs/sort/doc/html/index.html new file mode 100644 index 000000000..7fd9278c0 --- /dev/null +++ b/libs/sort/doc/html/index.html @@ -0,0 +1,668 @@ +<html> +<head> +<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII"> +<title>Boost.Sort</title> +<link rel="stylesheet" href="../../../../doc/src/boostbook.css" type="text/css"> +<meta name="generator" content="DocBook XSL Stylesheets V1.78.1"> +<link rel="home" href="index.html" title="Boost.Sort"> +<link rel="next" href="sort/sort_hpp.html" title="Spreadsort"> +</head> +<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> +<table cellpadding="2" width="100%"><tr> +<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../boost.png"></td> +<td align="center"><a href="../../../../index.html">Home</a></td> +<td align="center"><a href="../../../../libs/libraries.htm">Libraries</a></td> +<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> +<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> +<td align="center"><a href="../../../../more/index.htm">More</a></td> +</tr></table> +<hr> +<div class="spirit-nav"><a accesskey="n" href="sort/sort_hpp.html"><img src="../../../../doc/src/images/next.png" alt="Next"></a></div> +<div class="chapter"> +<div class="titlepage"><div> +<div><h2 class="title"> +<a name="sort"></a>Boost.Sort</h2></div> +<div><div class="author"><h3 class="author"> +<span class="firstname">Steven</span> <span class="surname">Ross</span> +</h3></div></div> +<div><p class="copyright">Copyright © 2014 Steven Ross</p></div> +<div><div class="legalnotice"> +<a name="sort.legal"></a><p> + Distributed under the <a href="http://boost.org/LICENSE_1_0.txt" target="_top">Boost + Software License, Version 1.0</a>. + </p> +</div></div> +</div></div> +<div class="toc"> +<p><b>Table of Contents</b></p> +<dl class="toc"> +<dt><span class="section"><a href="index.html#sort.overview">Overview</a></span></dt> +<dd><dl> +<dt><span class="section"><a href="index.html#sort.overview.intro">Introduction</a></span></dt> +<dt><span class="section"><a href="index.html#sort.overview.overloading">Overloading</a></span></dt> +<dt><span class="section"><a href="index.html#sort.overview.performance">Performance</a></span></dt> +<dt><span class="section"><a href="index.html#sort.overview.tuning">Tuning</a></span></dt> +</dl></dd> +<dt><span class="section"><a href="sort/sort_hpp.html">Spreadsort</a></span></dt> +<dd><dl> +<dt><span class="section"><a href="sort/sort_hpp.html#sort.sort_hpp.header_spreadsort">Header <code class="computeroutput"><span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">sort</span><span class="special">/</span><span class="identifier">spreadsort</span><span class="special">/</span><span class="identifier">spreadsort</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span></code></a></span></dt> +<dd><dl><dt><span class="section"><a href="sort/sort_hpp.html#sort.sort_hpp.header_spreadsort.spreadsort_examples">Spreadsort + Examples</a></span></dt></dl></dd> +<dt><span class="section"><a href="sort/sort_hpp/integer_sort.html">Integer Sort</a></span></dt> +<dd><dl><dt><span class="section"><a href="sort/sort_hpp/integer_sort.html#sort.sort_hpp.integer_sort.integersort_examples">Integer + Sort Examples</a></span></dt></dl></dd> +<dt><span class="section"><a href="sort/sort_hpp/float_sort.html">Float Sort</a></span></dt> +<dd><dl><dt><span class="section"><a href="sort/sort_hpp/float_sort.html#sort.sort_hpp.float_sort.floatsort_examples">Float + Sort Examples</a></span></dt></dl></dd> +<dt><span class="section"><a href="sort/sort_hpp/string_sort.html">String Sort</a></span></dt> +<dd><dl><dt><span class="section"><a href="sort/sort_hpp/string_sort.html#sort.sort_hpp.string_sort.stringsort_examples">String + Sort Examples</a></span></dt></dl></dd> +<dt><span class="section"><a href="sort/sort_hpp/rationale.html">Rationale</a></span></dt> +<dd><dl> +<dt><span class="section"><a href="sort/sort_hpp/rationale.html#sort.sort_hpp.rationale.radix_sorting">Radix Sorting</a></span></dt> +<dt><span class="section"><a href="sort/sort_hpp/rationale/hybrid_radix.html">Hybrid Radix</a></span></dt> +<dt><span class="section"><a href="sort/sort_hpp/rationale/why_spreadsort.html">Why spreadsort?</a></span></dt> +<dt><span class="section"><a href="sort/sort_hpp/rationale/unstable_sort.html">Unstable Sorting</a></span></dt> +<dt><span class="section"><a href="sort/sort_hpp/rationale/optimization.html">Unused X86 optimization</a></span></dt> +<dt><span class="section"><a href="sort/sort_hpp/rationale/lookup.html">Lookup Table?</a></span></dt> +</dl></dd> +</dl></dd> +<dt><span class="section"><a href="sort/definitions.html">Definitions</a></span></dt> +<dt><span class="section"><a href="sort/faq.html">Frequently Asked Questions</a></span></dt> +<dt><span class="section"><a href="sort/acks.html">Acknowledgements</a></span></dt> +<dt><span class="section"><a href="sort/bibliog.html">Bibliography</a></span></dt> +<dt><span class="section"><a href="sort/history.html">History</a></span></dt> +<dt><span class="section"><a href="boost_sort_c___reference.html">Boost.Sort C++ Reference</a></span></dt> +<dd><dl> +<dt><span class="section"><a href="boost_sort_c___reference.html#header.boost.sort.spreadsort.float_sort_hpp">Header <boost/sort/spreadsort/float_sort.hpp></a></span></dt> +<dd><dl></dl></dd> +<dt><span class="section"><a href="header/boost/sort/spreadsort/integer_sort_hpp.html">Header <boost/sort/spreadsort/integer_sort.hpp></a></span></dt> +<dd><dl></dl></dd> +<dt><span class="section"><a href="header/boost/sort/spreadsort/spreadsort_hpp.html">Header <boost/sort/spreadsort/spreadsort.hpp></a></span></dt> +<dd><dl></dl></dd> +<dt><span class="section"><a href="header/boost/sort/spreadsort/string_sort_hpp.html">Header <boost/sort/spreadsort/string_sort.hpp></a></span></dt> +<dd><dl></dl></dd> +</dl></dd> +<dt><span class="section"><a href="index/s09.html">Function Index</a></span></dt> +<dt><span class="section"><a href="index/s10.html">Index</a></span></dt> +</dl> +</div> +<div class="section"> +<div class="titlepage"><div><div><h2 class="title" style="clear: both"> +<a name="sort.overview"></a><a class="link" href="index.html#sort.overview" title="Overview">Overview</a> +</h2></div></div></div> +<div class="toc"><dl class="toc"> +<dt><span class="section"><a href="index.html#sort.overview.intro">Introduction</a></span></dt> +<dt><span class="section"><a href="index.html#sort.overview.overloading">Overloading</a></span></dt> +<dt><span class="section"><a href="index.html#sort.overview.performance">Performance</a></span></dt> +<dt><span class="section"><a href="index.html#sort.overview.tuning">Tuning</a></span></dt> +</dl></div> +<div class="section"> +<div class="titlepage"><div><div><h3 class="title"> +<a name="sort.overview.intro"></a><a class="link" href="index.html#sort.overview.intro" title="Introduction">Introduction</a> +</h3></div></div></div> +<p> + The Boost.Sort library provides a generic implementation of high-speed sorting + algorithms that outperform those in the C++ standard in both average and + worst case performance when there are over 1000 elements in the list to sort. + </p> +<p> + They fall back to <a href="http://www.cplusplus.com/reference/algorithm/sort/" target="_top">STL + std::sort</a> on small data sets. + </p> +<div class="warning"><table border="0" summary="Warning"> +<tr> +<td rowspan="2" align="center" valign="top" width="25"><img alt="[Warning]" src="../../../../doc/src/images/warning.png"></td> +<th align="left">Warning</th> +</tr> +<tr><td align="left" valign="top"><p> + These algorithms all only work on <a href="http://www.cplusplus.com/reference/iterator/RandomAccessIterator/" target="_top">random + access iterators</a>. + </p></td></tr> +</table></div> +<p> + They are hybrids using both radix and comparison-based sorting, specialized + to sorting common data types, such as integers, floats, and strings. + </p> +<p> + These algorithms are encoded in a generic fashion and accept functors, enabling + them to sort any object that can be processed like these basic data types. + In the case of <code class="literal"><code class="computeroutput"><a class="link" href="boost/sort/spreadsort/string_sort_idp48004640.html" title="Function template string_sort">string_sort</a></code></code>, + this includes anything with a defined strict-weak-ordering that <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a> + can sort, but writing efficient functors for some complex key types may not + be worth the additional effort relative to just using <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a>, + depending on how important speed is to your application. Sample usages are + available in the example directory. + </p> +<p> + Unlike many radix-based algorithms, the underlying <code class="literal"><code class="computeroutput"><a class="link" href="boost/sort/spreadsort/spreadsort_idp47957744.html" title="Function template spreadsort">spreadsort</a></code></code> + algorithm is designed around <span class="bold"><strong>worst-case performance</strong></span>. + It performs better on chunky data (where it is not widely distributed), so + that on real data it can perform substantially better than on random data. + Conceptually, <code class="literal"><code class="computeroutput"><a class="link" href="boost/sort/spreadsort/spreadsort_idp47957744.html" title="Function template spreadsort">spreadsort</a></code></code> + can sort any data for which an absolute ordering can be determined, and + <code class="literal"><code class="computeroutput"><a class="link" href="boost/sort/spreadsort/string_sort_idp48004640.html" title="Function template string_sort">string_sort</a></code></code> + is sufficiently flexible that this should be possible. + </p> +<p> + Situations where <code class="literal"><code class="computeroutput"><a class="link" href="boost/sort/spreadsort/spreadsort_idp47957744.html" title="Function template spreadsort">spreadsort</a></code></code> + is fastest relative to <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a>: + </p> +<div class="orderedlist"><ol class="orderedlist" type="1"> +<li class="listitem"> + Large number of elements to sort (<span class="emphasis"><em>N</em></span> >= 10000). + </li> +<li class="listitem"> + Slow comparison function (such as floating-point numbers on x86 processors + or strings). + </li> +<li class="listitem"> + Large data elements (such as key + data sorted on a key). + </li> +<li class="listitem"> + Completely sorted data when <code class="literal"><code class="computeroutput"><a class="link" href="boost/sort/spreadsort/spreadsort_idp47957744.html" title="Function template spreadsort">spreadsort</a></code></code> + has an optimization to quit early in this case. + </li> +</ol></div> +<p> + Situations where <code class="literal"><code class="computeroutput"><a class="link" href="boost/sort/spreadsort/spreadsort_idp47957744.html" title="Function template spreadsort">spreadsort</a></code></code> + is slower than <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a>: + </p> +<div class="orderedlist"><ol class="orderedlist" type="1"> +<li class="listitem"> + Data sorted in reverse order. Both <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a> + and <code class="literal"><code class="computeroutput"><a class="link" href="boost/sort/spreadsort/spreadsort_idp47957744.html" title="Function template spreadsort">spreadsort</a></code></code> + are faster on reverse-ordered data than randomized data, but <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a> + speeds up more in this special case. + </li> +<li class="listitem"> + Very small amounts of data (< 1000 elements). For this reason there + is a fallback in <code class="literal"><code class="computeroutput"><a class="link" href="boost/sort/spreadsort/spreadsort_idp47957744.html" title="Function template spreadsort">spreadsort</a></code></code> + to <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a> + if the input size is less than 1000, so performance is identical for + small amounts of data in practice. + </li> +</ol></div> +<p> + These functions are defined in <code class="computeroutput"><span class="keyword">namespace</span> + <span class="identifier">boost</span><span class="special">::</span><span class="identifier">sort</span><span class="special">::</span><span class="identifier">spreadsort</span></code>. + </p> +</div> +<div class="section"> +<div class="titlepage"><div><div><h3 class="title"> +<a name="sort.overview.overloading"></a><a class="link" href="index.html#sort.overview.overloading" title="Overloading">Overloading</a> +</h3></div></div></div> +<div class="tip"><table border="0" summary="Tip"> +<tr> +<td rowspan="2" align="center" valign="top" width="25"><img alt="[Tip]" src="../../../../doc/src/images/tip.png"></td> +<th align="left">Tip</th> +</tr> +<tr><td align="left" valign="top"><p> + In the Boost.Sort C++ Reference section, click on the appropriate overload, + for example <code class="computeroutput"><span class="identifier">float_sort</span><span class="special">(</span><span class="identifier">RandomAccessIter</span><span class="special">,</span> <span class="identifier">RandomAccessIter</span><span class="special">,</span> <span class="identifier">Right_shift</span><span class="special">,</span> <span class="identifier">Compare</span><span class="special">);</span></code> to get full details of that overload. + </p></td></tr> +</table></div> +<p> + Each of <code class="literal"><code class="computeroutput"><a class="link" href="boost/sort/spreadsort/integer_sort_idp41299456.html" title="Function template integer_sort">integer_sort</a></code></code>, + <code class="literal"><code class="computeroutput"><a class="link" href="boost/sort/spreadsort/float_sort_idp47034528.html" title="Function template float_sort">float_sort</a></code></code>, + and <code class="literal"><code class="computeroutput"><a class="link" href="boost/sort/spreadsort/string_sort_idp48004640.html" title="Function template string_sort">string_sort</a></code></code> + have 3 main versions: The base version, which takes a first iterator and + a last iterator, just like <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a>: + </p> +<pre class="programlisting"><span class="identifier">integer_sort</span><span class="special">(</span><span class="identifier">array</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span> <span class="identifier">array</span><span class="special">.</span><span class="identifier">end</span><span class="special">());</span> +<span class="identifier">float_sort</span><span class="special">(</span><span class="identifier">array</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span> <span class="identifier">array</span><span class="special">.</span><span class="identifier">end</span><span class="special">());</span> +<span class="identifier">string_sort</span><span class="special">(</span><span class="identifier">array</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span> <span class="identifier">array</span><span class="special">.</span><span class="identifier">end</span><span class="special">());</span> +</pre> +<p> + The version with an overridden shift functor, providing flexibility in case + the <code class="computeroutput"><span class="keyword">operator</span><span class="special">>></span></code> + already does something other than a bitshift. The rightshift functor takes + two args, first the data type, and second a natural number of bits to shift + right. + </p> +<p> + For <code class="literal"><code class="computeroutput"><a class="link" href="boost/sort/spreadsort/string_sort_idp48004640.html" title="Function template string_sort">string_sort</a></code></code> + this variant is slightly different; it needs a bracket functor equivalent + to <code class="computeroutput"><span class="keyword">operator</span></code>[], taking a number + corresponding to the character offset, along with a second <code class="computeroutput"><span class="identifier">getlength</span></code> functor to get the length of + the string in characters. In all cases, this operator must return an integer + type that compares with the <code class="computeroutput"><span class="keyword">operator</span><span class="special"><</span></code> to provide the intended order (integers + can be negated to reverse their order). + </p> +<p> + In other words: + </p> +<pre class="programlisting"><span class="identifier">rightshift</span><span class="special">(</span><span class="identifier">A</span><span class="special">,</span> <span class="identifier">n</span><span class="special">)</span> <span class="special"><</span> <span class="identifier">rightshift</span><span class="special">(</span><span class="identifier">B</span><span class="special">,</span> <span class="identifier">n</span><span class="special">)</span> <span class="special">-></span> <span class="identifier">A</span> <span class="special"><</span> <span class="identifier">B</span> +</pre> +<pre class="programlisting"><span class="identifier">integer_sort</span><span class="special">(</span><span class="identifier">array</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span> <span class="identifier">array</span><span class="special">.</span><span class="identifier">end</span><span class="special">(),</span> <span class="identifier">rightshift</span><span class="special">());</span> +</pre> +<pre class="programlisting"><span class="identifier">string_sort</span><span class="special">(</span><span class="identifier">array</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span> <span class="identifier">array</span><span class="special">.</span><span class="identifier">end</span><span class="special">(),</span> <span class="identifier">bracket</span><span class="special">(),</span> <span class="identifier">getsize</span><span class="special">());</span> +</pre> +<p> + See <a href="../../example/rightshiftsample.cpp" target="_top">rightshiftsample.cpp</a> + for a working example of integer sorting with a rightshift functor. + </p> +<p> + And a version with a comparison functor for maximum flexibility. This functor + must provide the same sorting order as the integers returned by the rightshift: + </p> +<pre class="programlisting"><span class="identifier">rightshift</span><span class="special">(</span><span class="identifier">A</span><span class="special">,</span> <span class="identifier">n</span><span class="special">)</span> <span class="special"><</span> <span class="identifier">rightshift</span><span class="special">(</span><span class="identifier">B</span><span class="special">,</span> <span class="identifier">n</span><span class="special">)</span> <span class="special">-></span> <span class="identifier">compare</span><span class="special">(</span><span class="identifier">A</span><span class="special">,</span> <span class="identifier">B</span><span class="special">)</span> +</pre> +<pre class="programlisting"><span class="identifier">integer_sort</span><span class="special">(</span><span class="identifier">array</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span> <span class="identifier">array</span><span class="special">.</span><span class="identifier">end</span><span class="special">(),</span> <span class="identifier">negrightshift</span><span class="special">(),</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">greater</span><span class="special"><</span><span class="identifier">DATA_TYPE</span><span class="special">>());</span> +</pre> +<p> + Examples of functors are: + </p> +<pre class="programlisting"><span class="keyword">struct</span> <span class="identifier">lessthan</span> <span class="special">{</span> + <span class="keyword">inline</span> <span class="keyword">bool</span> <span class="keyword">operator</span><span class="special">()(</span><span class="keyword">const</span> <span class="identifier">DATA_TYPE</span> <span class="special">&</span><span class="identifier">x</span><span class="special">,</span> <span class="keyword">const</span> <span class="identifier">DATA_TYPE</span> <span class="special">&</span><span class="identifier">y</span><span class="special">)</span> <span class="keyword">const</span> <span class="special">{</span> + <span class="keyword">return</span> <span class="identifier">x</span><span class="special">.</span><span class="identifier">a</span> <span class="special"><</span> <span class="identifier">y</span><span class="special">.</span><span class="identifier">a</span><span class="special">;</span> + <span class="special">}</span> +<span class="special">};</span> +</pre> +<pre class="programlisting"><span class="keyword">struct</span> <span class="identifier">bracket</span> <span class="special">{</span> + <span class="keyword">inline</span> <span class="keyword">unsigned</span> <span class="keyword">char</span> <span class="keyword">operator</span><span class="special">()(</span><span class="keyword">const</span> <span class="identifier">DATA_TYPE</span> <span class="special">&</span><span class="identifier">x</span><span class="special">,</span> <span class="identifier">size_t</span> <span class="identifier">offset</span><span class="special">)</span> <span class="keyword">const</span> <span class="special">{</span> + <span class="keyword">return</span> <span class="identifier">x</span><span class="special">.</span><span class="identifier">a</span><span class="special">[</span><span class="identifier">offset</span><span class="special">];</span> + <span class="special">}</span> +<span class="special">};</span> +</pre> +<pre class="programlisting"><span class="keyword">struct</span> <span class="identifier">getsize</span> <span class="special">{</span> + <span class="keyword">inline</span> <span class="identifier">size_t</span> <span class="keyword">operator</span><span class="special">()(</span><span class="keyword">const</span> <span class="identifier">DATA_TYPE</span> <span class="special">&</span><span class="identifier">x</span><span class="special">)</span> <span class="keyword">const</span><span class="special">{</span> <span class="keyword">return</span> <span class="identifier">x</span><span class="special">.</span><span class="identifier">a</span><span class="special">.</span><span class="identifier">size</span><span class="special">();</span> <span class="special">}</span> +<span class="special">};</span> +</pre> +<p> + and these functors are used thus: + </p> +<pre class="programlisting"><span class="identifier">string_sort</span><span class="special">(</span><span class="identifier">array</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span> <span class="identifier">array</span><span class="special">.</span><span class="identifier">end</span><span class="special">(),</span> <span class="identifier">bracket</span><span class="special">(),</span> <span class="identifier">getsize</span><span class="special">(),</span> <span class="identifier">lessthan</span><span class="special">());</span> +</pre> +<p> + See <a href="../../example/stringfunctorsample.cpp" target="_top">stringfunctorsample.cpp</a> + for a working example of sorting strings with all functors. + </p> +</div> +<div class="section"> +<div class="titlepage"><div><div><h3 class="title"> +<a name="sort.overview.performance"></a><a class="link" href="index.html#sort.overview.performance" title="Performance">Performance</a> +</h3></div></div></div> +<p> + The <code class="literal"><code class="computeroutput"><a class="link" href="boost/sort/spreadsort/spreadsort_idp47957744.html" title="Function template spreadsort">spreadsort</a></code></code> + algorithm is a hybrid algorithm; when the number of elements being sorted + is below a certain number, comparison-based sorting is used. Above it, radix + sorting is used. The radix-based algorithm will thus cut up the problem into + small pieces, and either completely sort the data based upon its radix if + the data is clustered, or finish sorting the cut-down pieces with comparison-based + sorting. + </p> +<p> + The Spreadsort algorithm dynamically chooses either comparison-based or radix-based + sorting when recursing, whichever provides better worst-case performance. + This way worst-case performance is guaranteed to be the better of <span class="emphasis"><em>𝑶(N⋅log2(N))</em></span> + comparisons and <span class="emphasis"><em>𝑶(N⋅log2(K/S + S))</em></span> operations where + </p> +<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> +<li class="listitem"> + <span class="emphasis"><em>N</em></span> is the number of elements being sorted, + </li> +<li class="listitem"> + <span class="emphasis"><em>K</em></span> is the length in bits of the key, and + </li> +<li class="listitem"> + <span class="emphasis"><em>S</em></span> is a constant. + </li> +</ul></div> +<p> + This results in substantially improved performance for large <span class="emphasis"><em>N</em></span>; + <code class="literal"><code class="computeroutput"><a class="link" href="boost/sort/spreadsort/integer_sort_idp41299456.html" title="Function template integer_sort">integer_sort</a></code></code> + tends to be 50% to 2X faster than <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a>, + while <code class="literal"><code class="computeroutput"><a class="link" href="boost/sort/spreadsort/float_sort_idp47034528.html" title="Function template float_sort">float_sort</a></code></code> + and _string_sort are roughly 2X faster than <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a>. + </p> +<p> + Performance graphs are provided for <code class="literal"><code class="computeroutput"><a class="link" href="boost/sort/spreadsort/integer_sort_idp41299456.html" title="Function template integer_sort">integer_sort</a></code></code>, + <code class="literal"><code class="computeroutput"><a class="link" href="boost/sort/spreadsort/float_sort_idp47034528.html" title="Function template float_sort">float_sort</a></code></code>, + and <code class="literal"><code class="computeroutput"><a class="link" href="boost/sort/spreadsort/string_sort_idp48004640.html" title="Function template string_sort">string_sort</a></code></code> + in their description. + </p> +<p> + Runtime Performance comparisons and graphs were made on a Core 2 Duo laptop + running Windows Vista 64 with MSVC 8.0, and an old G4 laptop running Mac + OSX with gcc. <a href="http://www.boost.org/build/doc/html/" target="_top">Boost bjam/b2</a> + was used to control compilation. + </p> +<p> + Direct performance comparisons on a newer x86 system running Ubuntu, with + the fallback to <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a> + at lower input sizes disabled are below. + </p> +<div class="note"><table border="0" summary="Note"> +<tr> +<td rowspan="2" align="center" valign="top" width="25"><img alt="[Note]" src="../../../../doc/src/images/note.png"></td> +<th align="left">Note</th> +</tr> +<tr><td align="left" valign="top"><p> + The fallback to <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a> + for smaller input sizes prevents the worse performance seen on the left + sides of the first two graphs. + </p></td></tr> +</table></div> +<p> + <code class="literal"><code class="computeroutput"><a class="link" href="boost/sort/spreadsort/integer_sort_idp41299456.html" title="Function template integer_sort">integer_sort</a></code></code> + starts to become faster than <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a> + at about 1000 integers (4000 bytes), and <code class="literal"><code class="computeroutput"><a class="link" href="boost/sort/spreadsort/string_sort_idp48004640.html" title="Function template string_sort">string_sort</a></code></code> + becomes faster than <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a> + at slightly fewer bytes (as few as 30 strings). + </p> +<div class="note"><table border="0" summary="Note"> +<tr> +<td rowspan="2" align="center" valign="top" width="25"><img alt="[Note]" src="../../../../doc/src/images/note.png"></td> +<th align="left">Note</th> +</tr> +<tr><td align="left" valign="top"><p> + The 4-threaded graph has 4 threads doing <span class="bold"><strong>separate + sorts simultaneously</strong></span> (not splitting up a single sort) as a test + for thread cache collision and other multi-threaded performance issues. + </p></td></tr> +</table></div> +<p> + <code class="literal"><code class="computeroutput"><a class="link" href="boost/sort/spreadsort/float_sort_idp47034528.html" title="Function template float_sort">float_sort</a></code></code> + times are very similar to <code class="literal"><code class="computeroutput"><a class="link" href="boost/sort/spreadsort/integer_sort_idp41299456.html" title="Function template integer_sort">integer_sort</a></code></code> + times. + </p> +<p> + <span class="inlinemediaobject"><img src="../images/single_threaded.png"></span> + <span class="inlinemediaobject"><img src="../images/4_threaded.png"></span> + <span class="inlinemediaobject"><img src="../images/entropy.png"></span> + <span class="inlinemediaobject"><img src="../images/bits_per_byte.png"></span> + </p> +<p> + Histogramming with a fixed maximum number of splits is used because it reduces + the number of cache misses, thus improving performance relative to the approach + described in detail in the <a href="http://en.wikipedia.org/wiki/Spreadsort" target="_top">original + SpreadSort publication</a>. + </p> +<p> + The importance of cache-friendly histogramming is described in <a href="http://www.nik.no/2002/Maus.pdf" target="_top">Arne + Maus, Adaptive Left Reflex</a>, though without the worst-case handling + described below. + </p> +<p> + The time taken per radix iteration is: + </p> +<p> + <span class="emphasis"><em>𝑶(N)</em></span> iterations over the data + </p> +<p> + <span class="emphasis"><em>𝑶(N)</em></span> integer-type comparisons (even for _float_sort and + <code class="literal"><code class="computeroutput"><a class="link" href="boost/sort/spreadsort/string_sort_idp48004640.html" title="Function template string_sort">string_sort</a></code></code>) + </p> +<p> + <span class="emphasis"><em>𝑶(N)</em></span> swaps + </p> +<p> + <span class="emphasis"><em>𝑶(2<sup>S</sup>)</em></span> bin operations. + </p> +<p> + To obtain <span class="emphasis"><em>𝑶(N)</em></span> worst-case performance per iteration, + the restriction <span class="emphasis"><em>S <= log2(N)</em></span> is applied, and <span class="emphasis"><em>𝑶(2<sup>S</sup>)</em></span> + becomes <span class="emphasis"><em>𝑶(N)</em></span>. For each such iteration, the number of + unsorted bits log2(range) (referred to as <span class="emphasis"><em>K</em></span>) per element + is reduced by <span class="emphasis"><em>S</em></span>. As <span class="emphasis"><em>S</em></span> decreases + depending upon the amount of elements being sorted, it can drop from a maximum + of <span class="emphasis"><em>S<sub>max</sub></em></span> to the minimum of <span class="emphasis"><em>S<sub>min</sub></em></span>. + </p> +<p> + Assumption: <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a> + is assumed to be <span class="emphasis"><em>𝑶(N*log2(N))</em></span>, as <a href="http://en.wikipedia.org/wiki/Introsort" target="_top">introsort</a> + exists and is commonly used. (If you have a quibble with this please take + it up with the implementor of your <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a>; + you're welcome to replace the recursive calls to <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a> + to calls to <a href="http://en.wikipedia.org/wiki/Introsort" target="_top">introsort</a> + if your <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a> + library call is poorly implemented). + </p> +<p> + <a href="http://en.wikipedia.org/wiki/Introsort" target="_top">Introsort</a> is + not included with this algorithm for simplicity and because the implementor + of the <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a> + call is assumed to know what they're doing. + </p> +<p> + To maintain a minimum value for <span class="emphasis"><em>S (S<sub>min</sub>)</em></span>, comparison-based + sorting has to be used to sort when <span class="emphasis"><em>n <= log2(meanbinsize)</em></span>, + where <span class="emphasis"><em>log2(meanbinsize) (lbs)</em></span> is a small constant, usually + between 0 and 4, used to minimize bin overhead per element. There is a small + corner-case where if <span class="emphasis"><em>K < S<sub>min</sub></em></span> and <span class="emphasis"><em>n >= + 2^K</em></span>, then the data can be sorted in a single radix-based iteration + with an <span class="emphasis"><em>S = K</em></span> (this bucketsorting special case is by + default only applied to <code class="literal"><code class="computeroutput"><a class="link" href="boost/sort/spreadsort/float_sort_idp47034528.html" title="Function template float_sort">float_sort</a></code></code>). + So for the final recursion, worst-case performance is: + </p> +<p> + 1 radix-based iteration if <span class="emphasis"><em>K <= S<sub>min</sub></em></span>, + </p> +<p> + or <span class="emphasis"><em>S<sub>min</sub> + lbs</em></span> comparison-based iterations if <span class="emphasis"><em>K + > S<sub>min</sub></em></span> but <span class="emphasis"><em>n <= 2<sup>(S<sub>min</sub> + lbs)</sup></em></span>. + </p> +<p> + So for the final iteration, worst-case runtime is <span class="emphasis"><em>𝑶(N*(S<sub>min</sub> + lbs))</em></span> + but if <span class="emphasis"><em>K > S<sub>min</sub></em></span> and <span class="emphasis"><em>N > 2<sup>(S<sub>min</sub> + lbs)</sup></em></span> + then more than 1 radix recursion will be required. + </p> +<p> + For the second to last iteration, <span class="emphasis"><em>K <= S<sub>min</sub> * 2 + 1</em></span> + can be handled, (if the data is divided into <span class="emphasis"><em>2<sup>(S<sub>min</sub> + 1)</sup></em></span> + pieces) or if <span class="emphasis"><em>N < 2<sup>(S<sub>min</sub> + lbs + 1)</sup></em></span>, then it is faster + to fallback to <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a>. + </p> +<p> + In the case of a radix-based sort plus recursion, it will take <span class="emphasis"><em>𝑶(N*(S<sub>min</sub> + + lbs)) + 𝑶(N) = 𝑶(N*(S<sub>min</sub> + lbs + 1))</em></span> worst-case time, as <span class="emphasis"><em>K_remaining + = K_start - (S<sub>min</sub> + 1)</em></span>, and <span class="emphasis"><em>K_start <= S<sub>min</sub> * 2 + 1</em></span>. + </p> +<p> + Alternatively, comparison-based sorting is used if <span class="emphasis"><em>N < 2<sup>(S<sub>min</sub> + + lbs + 1)</sup></em></span>, which will take <span class="emphasis"><em>𝑶(N*(S<sub>min</sub> + lbs + 1))</em></span> + time. + </p> +<p> + So either way <span class="emphasis"><em>𝑶(N*(S<sub>min</sub> + lbs + 1))</em></span> is the worst-case + time for the second to last iteration, which occurs if <span class="emphasis"><em>K <= + S<sub>min</sub> * 2 + </em></span>1 or <span class="emphasis"><em>N < 2<sup>(S<sub>min</sub> + lbs + 1)</sup></em></span>. + </p> +<p> + This continues as long as <span class="emphasis"><em>S<sub>min</sub> <= S <= S<sub>max</sub></em></span>, so + that for <span class="emphasis"><em>K_m <= K_(m-1) + S<sub>min</sub> + m</em></span> where <span class="emphasis"><em>m</em></span> + is the maximum number of iterations after this one has finished, or where + <span class="emphasis"><em>N < 2<sup>(S<sub>min</sub> + lbs + m)</sup></em></span>, then the worst-case runtime + is <span class="emphasis"><em>𝑶(N*(S<sub>min</sub> + lbs + m))</em></span>. + </p> +<p> +    <span class="emphasis"><em>K_m</em></span> at <span class="emphasis"><em>m <= (S<sub>max</sub> - S<sub>min</sub>)</em></span> works + out to: + </p> +<p> +    <span class="emphasis"><em>K_1 <= (S<sub>min</sub>) + S<sub>min</sub> + 1 <= 2S<sub>min</sub> + 1</em></span> + </p> +<p> +    <span class="emphasis"><em>K_2 <= (2S<sub>min</sub> + 1) + S<sub>min</sub> + 2</em></span> + </p> +<p> + as the sum from 0 to <span class="emphasis"><em>m</em></span> is <span class="emphasis"><em>m(m + 1)/2</em></span> + </p> +<p> +    <span class="emphasis"><em>K_m <= (m + 1)S<sub>min</sub> + m(m + 1)/2 <= (S<sub>min</sub> + m/2)(m + 1)</em></span> + </p> +<p> + substituting in S<sub>max</sub> - S<sub>min</sub> for m + </p> +<p> +    <span class="emphasis"><em>K_(S<sub>max</sub> - S<sub>min</sub>) <= (S<sub>min</sub> + (S<sub>max</sub> - S<sub>min</sub>)/2)*(S<sub>max</sub> - S<sub>min</sub> + 1)</em></span> + </p> +<p> +    <span class="emphasis"><em>K_(S<sub>max</sub> - S<sub>min</sub>) <= (S<sub>min</sub> + S<sub>max</sub>) * (S<sub>max</sub> - S<sub>min</sub> + 1)/2</em></span> + </p> +<p> + Since this involves <span class="emphasis"><em>S<sub>max</sub> - S<sub>min</sub> + 1</em></span> iterations, this works + out to dividing <span class="emphasis"><em>K</em></span> into an average <span class="emphasis"><em>(S<sub>min</sub> + S<sub>max</sub>)</em></span>/2 + pieces per iteration. + </p> +<p> + To finish the problem from this point takes <span class="emphasis"><em>𝑶(N * (S<sub>max</sub> - S<sub>min</sub>))</em></span> + for <span class="emphasis"><em>m</em></span> iterations, plus the worst-case of <span class="emphasis"><em>𝑶(N*(S<sub>min</sub> + + lbs))</em></span> for the last iteration, for a total of <span class="emphasis"><em>𝑶(N *(S<sub>max</sub> + + lbs))</em></span> time. + </p> +<p> + When <span class="emphasis"><em>m > S<sub>max</sub> - S<sub>min</sub></em></span>, the problem is divided into + <span class="emphasis"><em>S<sub>max</sub></em></span> pieces per iteration, or <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a> + is called if <span class="emphasis"><em>N < 2^(m + S<sub>min</sub> + lbs)</em></span>. For this range: + </p> +<p> +    <span class="emphasis"><em>K_m <= K_(m - 1) + S<sub>max</sub></em></span>, providing runtime of + </p> +<p> +    <span class="emphasis"><em>𝑶(N *((K - K_(S<sub>max</sub> - S<sub>min</sub>))/S<sub>max</sub> + S<sub>max</sub> + lbs))</em></span> if recursive, + </p> +<p> + or <span class="emphasis"><em>𝑶(N * log(2^(m + S<sub>min</sub> + lbs)))</em></span> if comparison-based, + </p> +<p> + which simplifies to <span class="emphasis"><em>𝑶(N * (m + S<sub>min</sub> + lbs))</em></span>, which substitutes + to <span class="emphasis"><em>𝑶(N * ((m - (S<sub>max</sub> - S<sub>min</sub>)) + S<sub>max</sub> + lbs))</em></span>, which given + that <span class="emphasis"><em>m - (S<sub>max</sub> - S<sub>min</sub>) <= (K - K_(S<sub>max</sub> - S<sub>min</sub>))/S<sub>max</sub></em></span> + (otherwise a lesser number of radix-based iterations would be used) + </p> +<p> + also comes out to <span class="emphasis"><em>𝑶(N *((K - K_(S<sub>max</sub> - S<sub>min</sub>))/S<sub>max</sub> + S<sub>max</sub> + lbs))</em></span>. + </p> +<p> + Asymptotically, for large <span class="emphasis"><em>N</em></span> and large <span class="emphasis"><em>K</em></span>, + this simplifies to: + </p> +<p> +    <span class="emphasis"><em>𝑶(N * (K/S<sub>max</sub> + S<sub>max</sub> + lbs))</em></span>, + </p> +<p> + simplifying out the constants related to the <span class="emphasis"><em>S<sub>max</sub> - S<sub>min</sub></em></span> + range, providing an additional <span class="emphasis"><em>𝑶(N * (S<sub>max</sub> + lbs))</em></span> runtime + on top of the <span class="emphasis"><em>𝑶(N * (K/S))</em></span> performance of LSD <a href="http://en.wikipedia.org/wiki/Radix_sort" target="_top">radix sort</a>, but without + the <span class="emphasis"><em>𝑶(N)</em></span> memory overhead. For simplicity, because <span class="emphasis"><em>lbs</em></span> + is a small constant (0 can be used, and performs reasonably), it is ignored + when summarizing the performance in further discussions. By checking whether + comparison-based sorting is better, Spreadsort is also <span class="emphasis"><em>𝑶(N*log(N))</em></span>, + whichever is better, and unlike LSD <a href="http://en.wikipedia.org/wiki/Radix_sort" target="_top">radix + sort</a>, can perform much better than the worst-case if the data is + either evenly distributed or highly clustered. + </p> +<p> + This analysis was for <code class="literal"><code class="computeroutput"><a class="link" href="boost/sort/spreadsort/integer_sort_idp41299456.html" title="Function template integer_sort">integer_sort</a></code></code> + and <code class="literal"><code class="computeroutput"><a class="link" href="boost/sort/spreadsort/float_sort_idp47034528.html" title="Function template float_sort">float_sort</a></code></code>. + <code class="literal"><code class="computeroutput"><a class="link" href="boost/sort/spreadsort/string_sort_idp48004640.html" title="Function template string_sort">string_sort</a></code></code> + differs in that <span class="emphasis"><em>S<sub>min</sub> = S<sub>max</sub> = sizeof(Char_type) * 8</em></span>, + <span class="emphasis"><em>lbs</em></span> is 0, and that <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a>'s + comparison is not a constant-time operation, so strictly speaking <code class="literal"><code class="computeroutput"><a class="link" href="boost/sort/spreadsort/string_sort_idp48004640.html" title="Function template string_sort">string_sort</a></code></code> + runtime is + </p> +<p> +    <span class="emphasis"><em>𝑶(N * (K/S<sub>max</sub> + (S<sub>max</sub> comparisons)))</em></span>. + </p> +<p> + Worst-case, this ends up being <span class="emphasis"><em>𝑶(N * K)</em></span> (where <span class="emphasis"><em>K</em></span> + is the mean string length in bytes), as described for <a href="http://en.wikipedia.org/wiki/American_flag_sort" target="_top">American + flag sort</a>, which is better than the + </p> +<p> +    <span class="emphasis"><em>𝑶(N * K * log(N))</em></span> + </p> +<p> + worst-case for comparison-based sorting. + </p> +</div> +<div class="section"> +<div class="titlepage"><div><div><h3 class="title"> +<a name="sort.overview.tuning"></a><a class="link" href="index.html#sort.overview.tuning" title="Tuning">Tuning</a> +</h3></div></div></div> +<p> + <code class="literal"><code class="computeroutput"><a class="link" href="boost/sort/spreadsort/integer_sort_idp41299456.html" title="Function template integer_sort">integer_sort</a></code></code> + and <code class="literal"><code class="computeroutput"><a class="link" href="boost/sort/spreadsort/float_sort_idp47034528.html" title="Function template float_sort">float_sort</a></code></code> + have tuning constants that control how the radix-sorting portion of those + algorithms work. The ideal constant values for <code class="literal"><code class="computeroutput"><a class="link" href="boost/sort/spreadsort/integer_sort_idp41299456.html" title="Function template integer_sort">integer_sort</a></code></code> + and <code class="literal"><code class="computeroutput"><a class="link" href="boost/sort/spreadsort/float_sort_idp47034528.html" title="Function template float_sort">float_sort</a></code></code> + vary depending on the platform, compiler, and data being sorted. By far the + most important constant is <span class="emphasis"><em>max_splits</em></span>, which defines + how many pieces the radix-sorting portion splits the data into per iteration. + </p> +<p> + The ideal value of <span class="emphasis"><em>max_splits</em></span> depends upon the size + of the L1 processor cache, and is between 10 and 13 on many systems. A default + value of 11 is used. For mostly-sorted data, a much larger value is better, + as swaps (and thus cache misses) are rare, but this hurts runtime severely + for unsorted data, so is not recommended. + </p> +<p> + On some x86 systems, when the total number of elements being sorted is small + ( less than 1 million or so), the ideal <span class="emphasis"><em>max_splits</em></span> can + be substantially larger, such as 17. This is suspected to be because all + the data fits into the L2 cache, and misses from L1 cache to L2 cache do + not impact performance as severely as misses to main memory. Modifying tuning + constants other than <span class="emphasis"><em>max_splits</em></span> is not recommended, + as the performance improvement for changing other constants is usually minor. + </p> +<p> + If you can afford to let it run for a day, and have at least 1GB of free + memory, the perl command: <code class="computeroutput"><span class="special">./</span><span class="identifier">tune</span><span class="special">.</span><span class="identifier">pl</span> + <span class="special">-</span><span class="identifier">large</span> + <span class="special">-</span><span class="identifier">tune</span></code> + (UNIX) or <code class="computeroutput"><span class="identifier">perl</span> <span class="identifier">tune</span><span class="special">.</span><span class="identifier">pl</span> <span class="special">-</span><span class="identifier">large</span> <span class="special">-</span><span class="identifier">tune</span> <span class="special">-</span><span class="identifier">windows</span></code> (Windows) can be used to automatically + tune these constants. This should be run from the <code class="computeroutput"><span class="identifier">libs</span><span class="special">/</span><span class="identifier">sort</span> <span class="identifier">directory</span></code> inside the boost home directory. + This will work to identify the <code class="computeroutput"><span class="identifier">ideal</span> + <span class="identifier">constants</span><span class="special">.</span><span class="identifier">hpp</span></code> settings for your system, testing on + various distributions in a 20 million element (80MB) file, and additionally + verifies that all sorting routines sort correctly across various data distributions. + Alternatively, you can test with the file size you're most concerned with + <code class="computeroutput"><span class="special">./</span><span class="identifier">tune</span><span class="special">.</span><span class="identifier">pl</span> <span class="identifier">number</span> + <span class="special">-</span><span class="identifier">tune</span></code> + (UNIX) or <code class="computeroutput"><span class="identifier">perl</span> <span class="identifier">tune</span><span class="special">.</span><span class="identifier">pl</span> <span class="identifier">number</span> + <span class="special">-</span><span class="identifier">tune</span> + <span class="special">-</span><span class="identifier">windows</span></code> + (Windows). Substitute the number of elements you want to test with for <code class="computeroutput"><span class="identifier">number</span></code>. Otherwise, just use the options + it comes with, they're decent. With default settings <code class="computeroutput"><span class="special">./</span><span class="identifier">tune</span><span class="special">.</span><span class="identifier">pl</span> + <span class="special">-</span><span class="identifier">tune</span></code> + (UNIX) <code class="computeroutput"><span class="identifier">perl</span> <span class="identifier">tune</span><span class="special">.</span><span class="identifier">pl</span> <span class="special">-</span><span class="identifier">tune</span> <span class="special">-</span><span class="identifier">windows</span></code> (Windows), the script will take + hours to run (less than a day), but may not pick the correct <span class="emphasis"><em>max_splits</em></span> + if it is over 10. Alternatively, you can add the <code class="computeroutput"><span class="special">-</span><span class="identifier">small</span></code> option to make it take just a few + minutes, tuning for smaller vector sizes (one hundred thousand elements), + but the resulting constants may not be good for large files (see above note + about <span class="emphasis"><em>max_splits</em></span> on Windows). + </p> +<p> + The tuning script can also be used just to verify that sorting works correctly + on your system, and see how much of a speedup it gets, by omiting the "-tune" + option. This runs at the end of tuning runs. Default args will take about + an hour to run and give accurate results on decent-sized test vectors. <code class="computeroutput"><span class="special">./</span><span class="identifier">tune</span><span class="special">.</span><span class="identifier">pl</span> <span class="special">-</span><span class="identifier">small</span></code> (UNIX) <code class="computeroutput"><span class="identifier">perl</span> + <span class="identifier">tune</span><span class="special">.</span><span class="identifier">pl</span> <span class="special">-</span><span class="identifier">small</span> + <span class="special">-</span><span class="identifier">windows</span></code> + (Windows) is a faster option, that tests on smaller vectors and isn't as + accurate. + </p> +<p> + If any differences are encountered during tuning, please call <code class="computeroutput"><span class="identifier">tune</span><span class="special">.</span><span class="identifier">pl</span></code> + with <code class="computeroutput"><span class="special">-</span><span class="identifier">debug</span> + <span class="special">></span> <span class="identifier">log_file_name</span></code>. + If the resulting log file contains compilation or permissions issues, it + is likely an issue with your setup. If some other type of error is encountered + (or result differences), please send them to the library author at spreadsort@gmail.com. + Including the zipped <code class="computeroutput"><span class="identifier">input</span><span class="special">.</span><span class="identifier">txt</span></code> that + was being used is also helpful. + </p> +</div> +</div> +</div> +<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> +<td align="left"><p><small>Last revised: April 07, 2015 at 22:47:04 GMT</small></p></td> +<td align="right"><div class="copyright-footer"></div></td> +</tr></table> +<hr> +<div class="spirit-nav"><a accesskey="n" href="sort/sort_hpp.html"><img src="../../../../doc/src/images/next.png" alt="Next"></a></div> +</body> +</html> |