1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
|
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
<title>Why spreadsort?</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="up" href="../rationale.html" title="Rationale">
<link rel="prev" href="hybrid_radix.html" title="Hybrid Radix">
<link rel="next" href="unstable_sort.html" title="Unstable Sorting">
</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="p" href="hybrid_radix.html"><img src="../../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../rationale.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="unstable_sort.html"><img src="../../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
<div class="section">
<div class="titlepage"><div><div><h4 class="title">
<a name="sort.sort_hpp.rationale.why_spreadsort"></a><a class="link" href="why_spreadsort.html" title="Why spreadsort?">Why spreadsort?</a>
</h4></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 used in this library is designed to provide best possible worst-case
performance, while still being cache-friendly. It provides the better of
<span class="emphasis"><em>𝑶(N*log(K/S + S))</em></span> and <span class="emphasis"><em>𝑶(N*log(N))</em></span>
worst-case time, where <span class="emphasis"><em>K</em></span> is the log of the range.
The log of the range is normally the length in bits of the data type; 32
for a 32-bit integer.
</p>
<p>
<code class="computeroutput"><span class="identifier">flash_sort</span></code> (another hybrid
algorithm), by comparison is <span class="emphasis"><em>𝑶(N)</em></span> for evenly distributed
lists. The problem is, <code class="computeroutput"><span class="identifier">flash_sort</span></code>
is merely an MSD <a href="http://en.wikipedia.org/wiki/Radix_sort" target="_top">radix
sort</a> combined with <span class="emphasis"><em>𝑶(N*N)</em></span> insertion sort to
deal with small subsets where the MSD Radix Sort is inefficient, so it
is inefficient with chunks of data around the size at which it switches
to <code class="computeroutput"><span class="identifier">insertion_sort</span></code>, and
ends up operating as an enhanced MSD Radix Sort. For uneven distributions
this makes it especially inefficient.
</p>
<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>
use <a href="http://en.wikipedia.org/wiki/Introsort" target="_top">introsort</a>
instead, which provides <span class="emphasis"><em>𝑶(N*log(N))</em></span> performance for
these medium-sized pieces. Also, <code class="computeroutput"><span class="identifier">flash_sort</span></code>'s
<span class="emphasis"><em>𝑶(N)</em></span> performance for even distributions comes at the
cost of cache misses, which on modern architectures are extremely expensive,
and in testing on modern systems ends up being slower than cutting up the
data in multiple, cache-friendly steps. Also worth noting is that on most
modern computers, <code class="computeroutput"><span class="identifier">log2</span><span class="special">(</span><span class="identifier">available</span>
<span class="identifier">RAM</span><span class="special">)/</span><span class="identifier">log2</span><span class="special">(</span><span class="identifier">L1</span> <span class="identifier">cache</span>
<span class="identifier">size</span><span class="special">)</span></code>
is around 3, where a cache miss takes more than 3 times as long as an in-cache
random-access, and the size of <span class="emphasis"><em>max_splits</em></span> is tuned
to the size of the cache. On a computer where cache misses aren't this
expensive, <span class="emphasis"><em>max_splits</em></span> could be increased to a large
value, or eliminated entirely, and <code class="computeroutput"><span class="identifier">integer_sort</span><span class="special">/</span><span class="identifier">float_sort</span></code>
would have the same <span class="emphasis"><em>𝑶(N)</em></span> performance on even distributions.
</p>
<p>
Adaptive Left Radix (ALR) is similar to <code class="computeroutput"><span class="identifier">flash_sort</span></code>,
but more cache-friendly. It still uses insertion_sort. Because ALR uses
<span class="emphasis"><em>𝑶(N*N)</em></span> <code class="computeroutput"><span class="identifier">insertion_sort</span></code>,
it isn't efficient to use the comparison-based fallback sort on large lists,
and if the data is clustered in small chunks just over the fallback size
with a few outliers, radix-based sorting iterates many times doing little
sorting with high overhead. Asymptotically, ALR is still <span class="emphasis"><em>𝑶(N*log(K/S
+ S))</em></span>, but with a very small <span class="emphasis"><em>S</em></span> (about 2
in the worst case), which compares unfavorably with the 11 default value
of <span class="emphasis"><em>max_splits</em></span> for Spreadsort.
</p>
<p>
ALR also does not have the <span class="emphasis"><em>𝑶(N*log(N))</em></span> fallback, so
for small lists that are not evenly distributed it is extremely inefficient.
See the <code class="computeroutput"><span class="identifier">alrbreaker</span></code> and
<code class="computeroutput"><span class="identifier">binaryalrbreaker</span></code> testcases
for examples; either replace the call to sort with a call to ALR and update
the ALR_THRESHOLD at the top, or as a quick comparison make <code class="computeroutput"><span class="identifier">get_max_count</span> <span class="keyword">return</span>
<span class="identifier">ALR_THRESHOLD</span></code> (20 by default
based upon the paper). These small tests take 4-10 times as long with ALR
as <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a>
in the author's testing, depending on the test system, because they are
trying to sort a highly uneven distribution. Normal Spreadsort does much
better with them, because <code class="computeroutput"><span class="identifier">get_max_count</span></code>
is designed around minimizing worst-case runtime.
</p>
<p>
<code class="computeroutput"><span class="identifier">burst_sort</span></code> is an efficient
hybrid algorithm for strings that uses substantial additional memory.
</p>
<p>
<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>
uses minimal additional memory by comparison. Speed comparisons between
the two haven't been made, but the better memory efficiency makes <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>
more general.
</p>
<p>
<code class="computeroutput"><span class="identifier">postal_sort</span></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>
are similar. A direct performance comparison would be welcome, but an efficient
version of <code class="computeroutput"><span class="identifier">postal_sort</span></code>
was not found in a search for source.
</p>
<p>
<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 most similar to the <a href="http://en.wikipedia.org/wiki/American_flag_sort" target="_top">American
flag sort</a> algorithm. The main difference is that it doesn't bother
trying to optimize how empty buckets/piles are handled, instead just checking
to see if all characters at the current index are equal. Other differences
are using <a href="http://en.cppreference.com/w/cpp/algorithm/sort" target="_top">std::sort</a>
as the fallback algorithm, and a larger fallback size (256 vs. 16), which
makes empty pile handling less important.
</p>
<p>
Another difference is not applying the stack-size restriction. Because
of the equality check in <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>,
it would take <span class="emphasis"><em>m*m</em></span> memory worth of strings to force
<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>
to create a stack of depth <span class="emphasis"><em>m</em></span>. This problem isn't a
realistic one on modern systems with multi-megabyte stacksize limits, where
main memory would be exhausted holding the long strings necessary to exceed
the stacksize limit. <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>
can be thought of as modernizing <a href="http://en.wikipedia.org/wiki/American_flag_sort" target="_top">American
flag sort</a> to take advantage of <a href="http://en.wikipedia.org/wiki/Introsort" target="_top">introsort</a>
as a fallback algorithm. In the author's testing, <a href="http://en.wikipedia.org/wiki/American_flag_sort" target="_top">American
flag sort</a> (on <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">strings</span></code>)
had comparable runtime to <a href="http://en.wikipedia.org/wiki/Introsort" target="_top">introsort</a>,
but making a hybrid of the two allows reduced overhead and substantially
superior performance.
</p>
</div>
<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
<td align="left"></td>
<td align="right"><div class="copyright-footer">Copyright © 2014 Steven Ross<p>
Distributed under the <a href="http://boost.org/LICENSE_1_0.txt" target="_top">Boost
Software License, Version 1.0</a>.
</p>
</div></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="hybrid_radix.html"><img src="../../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../rationale.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="unstable_sort.html"><img src="../../../../../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
|
