| 1 |
424 |
jeremybenn |
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
|
| 2 |
|
|
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
|
| 3 |
|
|
|
| 4 |
|
|
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
|
| 5 |
|
|
<head>
|
| 6 |
|
|
<meta name="generator" content="HTML Tidy for Linux/x86 (vers 12 April 2005), see www.w3.org" />
|
| 7 |
|
|
<title>Priority Queue Text Push Timing Test</title>
|
| 8 |
|
|
<meta http-equiv="Content-Type" content="text/html; charset=us-ascii" />
|
| 9 |
|
|
</head>
|
| 10 |
|
|
<body>
|
| 11 |
|
|
<div id="page">
|
| 12 |
|
|
<h1>Priority Queue Text <tt>push</tt> Timing Test</h1>
|
| 13 |
|
|
<h2><a name="description" id="description">Description</a></h2>
|
| 14 |
|
|
<p>This test inserts a number of values with keys from an
|
| 15 |
|
|
arbitrary text ([ <a href="references.html#wickland96thirty">wickland96thirty</a> ]) into
|
| 16 |
|
|
a container using <tt>push</tt> . It measures the average time
|
| 17 |
|
|
for <tt>push</tt> as a function of the number of values
|
| 18 |
|
|
pushed.</p>
|
| 19 |
|
|
<p>(The test was executed with <a href="http://gcc.gnu.org/viewcvs/*checkout*/trunk/libstdc%2B%2B-v3/testsuite/performance/ext/pb_ds/priority_queue_text_push_timing.cc"><tt>priority_queue_text_push_timing_test</tt></a>
|
| 20 |
|
|
thirty_years_among_the_dead_preproc.txt 200 200 2100)</p>
|
| 21 |
|
|
<h2><a name="purpose" id="purpose">Purpose</a></h2>
|
| 22 |
|
|
<p>The test checks the effect of different underlying
|
| 23 |
|
|
data structures (see <a href="pq_design.html#pq_imp">Design::Priority
|
| 24 |
|
|
Queues::Implementations</a>).</p>
|
| 25 |
|
|
<h2><a name="results" id="results">Results</a></h2>
|
| 26 |
|
|
<p>Figures <a href="#NPG">NPG</a>, <a href="#NPM">NPM</a>, and
|
| 27 |
|
|
<a href="#NPL">NPL</a> show the results for the native priority
|
| 28 |
|
|
queues and <tt>pb_ds</tt> 's priority queues in <a href="pq_performance_tests.html#gcc"><u>g++</u></a>, <a href="pq_performance_tests.html#msvc"><u>msvc++</u></a>, and
|
| 29 |
|
|
<a href="pq_performance_tests.html#local"><u>local</u></a>,
|
| 30 |
|
|
respectively; Figures <a href="#NBRG">NBRG</a>, <a href="#NBRM">NBRM</a>, and <a href="#NBRL">NBRL</a> shows the
|
| 31 |
|
|
results for the binary-heap based native priority queues and
|
| 32 |
|
|
<tt>pb_ds</tt>'s pairing-heap priority queues in <a href="pq_performance_tests.html#gcc"><u>g++</u></a>, <a href="pq_performance_tests.html#msvc"><u>msvc++</u></a>, and
|
| 33 |
|
|
<a href="pq_performance_tests.html#local"><u>local</u></a>,
|
| 34 |
|
|
respectively</p>
|
| 35 |
|
|
<div id="NPG_res_div">
|
| 36 |
|
|
<div id="NPG_gcc">
|
| 37 |
|
|
<div id="NPG_priority_queue_text_push_timing_test">
|
| 38 |
|
|
<div id="NPG_pq">
|
| 39 |
|
|
<div id="NPG_Native_and__tt_pb_ds_455tt__priority_queue__tt_push_455tt__timing_test"><div style="border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class="c1"><a name="NPG" id="NPG"><img src="priority_queue_text_push_timing_test_gcc.png" alt="no image" /></a></h6>NPG: Native and <tt>pb ds</tt> priority queue <tt>push</tt> timing test - <a href="pq_performance_tests.html#gcc">g++</a><p>In the above figure, the names in the legends have the following meaning:</p>
|
| 40 |
|
|
<ol>
|
| 41 |
|
|
<li>
|
| 42 |
|
|
n_pq_vector-
|
| 43 |
|
|
<tt>std::priority_queue</tt> adapting <tt>std::vector</tt></li>
|
| 44 |
|
|
<li>
|
| 45 |
|
|
n_pq_deque-
|
| 46 |
|
|
<tt>std::priority_queue</tt> adapting <tt>std::deque</tt></li>
|
| 47 |
|
|
<li>
|
| 48 |
|
|
binary_heap-
|
| 49 |
|
|
<a href="priority_queue.html"><tt>priority_queue</tt></a>
|
| 50 |
|
|
with <tt>Tag</tt> = <a href="binary_heap_tag.html"><tt>binary_heap_tag</tt></a>
|
| 51 |
|
|
</li>
|
| 52 |
|
|
<li>
|
| 53 |
|
|
rc_binomial_heap-
|
| 54 |
|
|
<a href="priority_queue.html"><tt>priority_queue</tt></a>
|
| 55 |
|
|
with <tt>Tag</tt> = <a href="rc_binomial_heap_tag.html"><tt>rc_binomial_heap_tag</tt></a>
|
| 56 |
|
|
</li>
|
| 57 |
|
|
<li>
|
| 58 |
|
|
thin_heap-
|
| 59 |
|
|
<a href="priority_queue.html"><tt>priority_queue</tt></a>
|
| 60 |
|
|
with <tt>Tag</tt> = <a href="thin_heap_tag.html"><tt>thin_heap_tag</tt></a>
|
| 61 |
|
|
</li>
|
| 62 |
|
|
<li>
|
| 63 |
|
|
binomial_heap-
|
| 64 |
|
|
<a href="priority_queue.html"><tt>priority_queue</tt></a>
|
| 65 |
|
|
with <tt>Tag</tt> = <a href="binomial_heap_tag.html"><tt>binomial_heap_tag</tt></a>
|
| 66 |
|
|
</li>
|
| 67 |
|
|
<li>
|
| 68 |
|
|
pairing_heap-
|
| 69 |
|
|
<a href="priority_queue.html"><tt>priority_queue</tt></a>
|
| 70 |
|
|
with <tt>Tag</tt> = <a href="pairing_heap_tag.html"><tt>pairing_heap_tag</tt></a>
|
| 71 |
|
|
</li>
|
| 72 |
|
|
</ol>
|
| 73 |
|
|
</div><div style="width: 100%; height: 20px"></div></div>
|
| 74 |
|
|
</div>
|
| 75 |
|
|
</div>
|
| 76 |
|
|
</div>
|
| 77 |
|
|
</div>
|
| 78 |
|
|
<div id="NPM_res_div">
|
| 79 |
|
|
<div id="NPM_msvc">
|
| 80 |
|
|
<div id="NPM_priority_queue_text_push_timing_test">
|
| 81 |
|
|
<div id="NPM_pq">
|
| 82 |
|
|
<div id="NPM_Native_and__tt_pb_ds_455tt__priority_queue__tt_push_455tt__timing_test"><div style="border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class="c1"><a name="NPM" id="NPM"><img src="priority_queue_text_push_timing_test_msvc.png" alt="no image" /></a></h6>NPM: Native and <tt>pb ds</tt> priority queue <tt>push</tt> timing test - <a href="pq_performance_tests.html#msvc">msvc++</a><p>In the above figure, the names in the legends have the following meaning:</p>
|
| 83 |
|
|
<ol>
|
| 84 |
|
|
<li>
|
| 85 |
|
|
n_pq_deque-
|
| 86 |
|
|
<tt>std::priority_queue</tt> adapting <tt>std::deque</tt></li>
|
| 87 |
|
|
<li>
|
| 88 |
|
|
rc_binomial_heap-
|
| 89 |
|
|
<a href="priority_queue.html"><tt>priority_queue</tt></a>
|
| 90 |
|
|
with <tt>Tag</tt> = <a href="rc_binomial_heap_tag.html"><tt>rc_binomial_heap_tag</tt></a>
|
| 91 |
|
|
</li>
|
| 92 |
|
|
<li>
|
| 93 |
|
|
binary_heap-
|
| 94 |
|
|
<a href="priority_queue.html"><tt>priority_queue</tt></a>
|
| 95 |
|
|
with <tt>Tag</tt> = <a href="binary_heap_tag.html"><tt>binary_heap_tag</tt></a>
|
| 96 |
|
|
</li>
|
| 97 |
|
|
<li>
|
| 98 |
|
|
binomial_heap-
|
| 99 |
|
|
<a href="priority_queue.html"><tt>priority_queue</tt></a>
|
| 100 |
|
|
with <tt>Tag</tt> = <a href="binomial_heap_tag.html"><tt>binomial_heap_tag</tt></a>
|
| 101 |
|
|
</li>
|
| 102 |
|
|
<li>
|
| 103 |
|
|
n_pq_vector-
|
| 104 |
|
|
<tt>std::priority_queue</tt> adapting <tt>std::vector</tt></li>
|
| 105 |
|
|
<li>
|
| 106 |
|
|
pairing_heap-
|
| 107 |
|
|
<a href="priority_queue.html"><tt>priority_queue</tt></a>
|
| 108 |
|
|
with <tt>Tag</tt> = <a href="pairing_heap_tag.html"><tt>pairing_heap_tag</tt></a>
|
| 109 |
|
|
</li>
|
| 110 |
|
|
<li>
|
| 111 |
|
|
thin_heap-
|
| 112 |
|
|
<a href="priority_queue.html"><tt>priority_queue</tt></a>
|
| 113 |
|
|
with <tt>Tag</tt> = <a href="thin_heap_tag.html"><tt>thin_heap_tag</tt></a>
|
| 114 |
|
|
</li>
|
| 115 |
|
|
</ol>
|
| 116 |
|
|
</div><div style="width: 100%; height: 20px"></div></div>
|
| 117 |
|
|
</div>
|
| 118 |
|
|
</div>
|
| 119 |
|
|
</div>
|
| 120 |
|
|
</div>
|
| 121 |
|
|
<div id="NPL_res_div">
|
| 122 |
|
|
<div id="NPL_local">
|
| 123 |
|
|
<div id="NPL_priority_queue_text_push_timing_test">
|
| 124 |
|
|
<div id="NPL_pq">
|
| 125 |
|
|
<div id="NPL_Native_and__tt_pb_ds_455tt__priority_queue__tt_push_455tt__timing_test"><div style = "border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class="c1"><a name="NPL" id= "NPL"><img src="priority_queue_text_push_timing_test_local.png" alt="no image" /></a></h6>NPL: Native and <tt>pb ds</tt> priority queue <tt>push</tt> timing test - <a href = "pq_performance_tests.html#local">local</a></div><div style = "width: 100%; height: 20px"></div></div>
|
| 126 |
|
|
</div>
|
| 127 |
|
|
</div>
|
| 128 |
|
|
</div>
|
| 129 |
|
|
</div>
|
| 130 |
|
|
<div id="NBRG_res_div">
|
| 131 |
|
|
<div id="NBRG_gcc">
|
| 132 |
|
|
<div id="NBRG_pairing_priority_queue_text_push_timing_test">
|
| 133 |
|
|
<div id="NBRG_pq">
|
| 134 |
|
|
<div id="NBRG_Native_and__tt_pb_ds_455tt__pairing_priority_queue__tt_push_455tt__timing_test"><div style="border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class="c1"><a name="NBRG" id="NBRG"><img src="pairing_priority_queue_text_push_timing_test_gcc.png" alt="no image" /></a></h6>NBRG: Native and <tt>pb ds</tt> pairing priority queue <tt>push</tt> timing test - <a href="pq_performance_tests.html#gcc">g++</a><p>In the above figure, the names in the legends have the following meaning:</p>
|
| 135 |
|
|
<ol>
|
| 136 |
|
|
<li>
|
| 137 |
|
|
n_pq_vector-
|
| 138 |
|
|
<tt>std::priority_queue</tt> adapting <tt>std::vector</tt></li>
|
| 139 |
|
|
<li>
|
| 140 |
|
|
n_pq_deque-
|
| 141 |
|
|
<tt>std::priority_queue</tt> adapting <tt>std::deque</tt></li>
|
| 142 |
|
|
<li>
|
| 143 |
|
|
thin_heap-
|
| 144 |
|
|
<a href="priority_queue.html"><tt>priority_queue</tt></a>
|
| 145 |
|
|
with <tt>Tag</tt> = <a href="thin_heap_tag.html"><tt>thin_heap_tag</tt></a>
|
| 146 |
|
|
</li>
|
| 147 |
|
|
<li>
|
| 148 |
|
|
pairing_heap-
|
| 149 |
|
|
<a href="priority_queue.html"><tt>priority_queue</tt></a>
|
| 150 |
|
|
with <tt>Tag</tt> = <a href="pairing_heap_tag.html"><tt>pairing_heap_tag</tt></a>
|
| 151 |
|
|
</li>
|
| 152 |
|
|
</ol>
|
| 153 |
|
|
</div><div style="width: 100%; height: 20px"></div></div>
|
| 154 |
|
|
</div>
|
| 155 |
|
|
</div>
|
| 156 |
|
|
</div>
|
| 157 |
|
|
</div>
|
| 158 |
|
|
<div id="NBRM_res_div">
|
| 159 |
|
|
<div id="NBRM_msvc">
|
| 160 |
|
|
<div id="NBRM_pairing_priority_queue_text_push_timing_test">
|
| 161 |
|
|
<div id="NBRM_pq">
|
| 162 |
|
|
<div id="NBRM_Native_and__tt_pb_ds_455tt__pairing_priority_queue__tt_push_455tt__timing_test"><div style="border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class="c1"><a name="NBRM" id="NBRM"><img src="pairing_priority_queue_text_push_timing_test_msvc.png" alt="no image" /></a></h6>NBRM: Native and <tt>pb ds</tt> pairing priority queue <tt>push</tt> timing test - <a href="pq_performance_tests.html#msvc">msvc++</a><p>In the above figure, the names in the legends have the following meaning:</p>
|
| 163 |
|
|
<ol>
|
| 164 |
|
|
<li>
|
| 165 |
|
|
n_pq_deque-
|
| 166 |
|
|
<tt>std::priority_queue</tt> adapting <tt>std::deque</tt></li>
|
| 167 |
|
|
<li>
|
| 168 |
|
|
n_pq_vector-
|
| 169 |
|
|
<tt>std::priority_queue</tt> adapting <tt>std::vector</tt></li>
|
| 170 |
|
|
<li>
|
| 171 |
|
|
pairing_heap-
|
| 172 |
|
|
<a href="priority_queue.html"><tt>priority_queue</tt></a>
|
| 173 |
|
|
with <tt>Tag</tt> = <a href="pairing_heap_tag.html"><tt>pairing_heap_tag</tt></a>
|
| 174 |
|
|
</li>
|
| 175 |
|
|
<li>
|
| 176 |
|
|
thin_heap-
|
| 177 |
|
|
<a href="priority_queue.html"><tt>priority_queue</tt></a>
|
| 178 |
|
|
with <tt>Tag</tt> = <a href="thin_heap_tag.html"><tt>thin_heap_tag</tt></a>
|
| 179 |
|
|
</li>
|
| 180 |
|
|
</ol>
|
| 181 |
|
|
</div><div style="width: 100%; height: 20px"></div></div>
|
| 182 |
|
|
</div>
|
| 183 |
|
|
</div>
|
| 184 |
|
|
</div>
|
| 185 |
|
|
</div>
|
| 186 |
|
|
<div id="NBRL_res_div">
|
| 187 |
|
|
<div id="NBRL_local">
|
| 188 |
|
|
<div id="NBRL_pairing_priority_queue_text_push_timing_test">
|
| 189 |
|
|
<div id="NBRL_pq">
|
| 190 |
|
|
<div id="NBRL_Native_and__tt_pb_ds_455tt__pairing_priority_queue__tt_push_455tt__timing_test"><div style = "border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class="c1"><a name="NBRL" id= "NBRL"><img src="pairing_priority_queue_text_push_timing_test_local.png" alt="no image" /></a></h6>NBRL: Native and <tt>pb ds</tt> pairing priority queue <tt>push</tt> timing test - <a href = "pq_performance_tests.html#local">local</a></div><div style = "width: 100%; height: 20px"></div></div>
|
| 191 |
|
|
</div>
|
| 192 |
|
|
</div>
|
| 193 |
|
|
</div>
|
| 194 |
|
|
</div>
|
| 195 |
|
|
<h2><a name="observations" id="observations">Observations</a></h2>
|
| 196 |
|
|
<p>Pairing heaps (<a href="priority_queue.html"><tt>priority_queue</tt></a> with
|
| 197 |
|
|
<tt>Tag</tt> = <a href="pairing_heap_tag.html"><tt>pairing_heap_tag</tt></a>)
|
| 198 |
|
|
are the most suited for sequences of <tt>push</tt> and
|
| 199 |
|
|
<tt>pop</tt> operations of non-primitive types (<i>e.g.</i>
|
| 200 |
|
|
<tt>std::string</tt>s). (see also <a href="priority_queue_text_push_pop_timing_test.html">Priority Queue
|
| 201 |
|
|
Text <tt>push</tt> and <tt>pop</tt> Timing Test</a>.) They are
|
| 202 |
|
|
less constrained than binomial heaps, <i>e.g.</i>, and since
|
| 203 |
|
|
they are node-based, they outperform binary heaps. (See
|
| 204 |
|
|
<a href="priority_queue_random_int_push_timing_test.html">Priority
|
| 205 |
|
|
Queue Random Integer <tt>push</tt> Timing Test</a> for the case
|
| 206 |
|
|
of primitive types.)</p>
|
| 207 |
|
|
<p>The STL's priority queues do not seem to perform well in
|
| 208 |
|
|
this case: the <tt>std::vector</tt> implementation needs to
|
| 209 |
|
|
perform a logarithmic sequence of string operations for each
|
| 210 |
|
|
operation, and the deque implementation is possibly hampered by
|
| 211 |
|
|
its need to manipulate a relatively-complex type (deques
|
| 212 |
|
|
support a <i>O(1)</i> <tt>push_front</tt>, even though it is
|
| 213 |
|
|
not used by <tt>std::priority_queue</tt>.)</p>
|
| 214 |
|
|
<p><a href="pq_performance_tests.html#pq_observations">Priority-Queue
|
| 215 |
|
|
Performance Tests::Observations</a> discusses this further and
|
| 216 |
|
|
summarizes.</p>
|
| 217 |
|
|
</div>
|
| 218 |
|
|
</body>
|
| 219 |
|
|
</html>
|
