1<!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 Performance Tests</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 Performance Tests</h1> 13<h2><a name="settings" id="settings">Settings</a></h2> 14<p>This section describes performance tests and their results. 15 In the following, <a href="#gcc"><u>g++</u></a>, <a href="#msvc"><u>msvc++</u></a>, and <a href="#local"><u>local</u></a> (the build used for generating this 16 documentation) stand for three different builds:</p> 17<div id="gcc_settings_div"> 18<div class="c1"> 19<h3><a name="gcc" id="gcc"><u>g++</u></a></h3> 20<ul> 21<li>CPU speed - cpu MHz : 2660.644</li> 22<li>Memory - MemTotal: 484412 kB</li> 23<li>Platform - 24 Linux-2.6.12-9-386-i686-with-debian-testing-unstable</li> 25<li>Compiler - g++ (GCC) 4.0.2 20050808 (prerelease) 26 (Ubuntu 4.0.1-4ubuntu9) Copyright (C) 2005 Free Software 27 Foundation, Inc. This is free software; see the source 28 for copying conditions. There is NO warranty; not even 29 for MERCHANTABILITY or FITNESS FOR A PARTICULAR 30 PURPOSE.</li> 31</ul> 32</div> 33<div class="c2"></div> 34</div> 35<div id="msvc_settings_div"> 36<div class="c1"> 37<h3><a name="msvc" id="msvc"><u>msvc++</u></a></h3> 38<ul> 39<li>CPU speed - cpu MHz : 2660.554</li> 40<li>Memory - MemTotal: 484412 kB</li> 41<li>Platform - Windows XP Pro</li> 42<li>Compiler - Microsoft (R) 32-bit C/C++ Optimizing 43 Compiler Version 13.10.3077 for 80x86 Copyright (C) 44 Microsoft Corporation 1984-2002. All rights 45 reserved.</li> 46</ul> 47</div> 48<div class="c2"></div> 49</div> 50<div id="local_settings_div"><div style = "border-style: dotted; border-width: 1px; border-color: lightgray"><h3><a name = "local"><u>local</u></a></h3><ul> 51<li>CPU speed - cpu MHz : 2250.000</li> 52<li>Memory - MemTotal: 2076248 kB</li> 53<li>Platform - Linux-2.6.16-1.2133_FC5-i686-with-redhat-5-Bordeaux</li> 54<li>Compiler - g++ (GCC) 4.1.1 20060525 (Red Hat 4.1.1-1) 55Copyright (C) 2006 Free Software Foundation, Inc. 56This is free software; see the source for copying conditions. There is NO 57warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 58</li> 59</ul> 60</div><div style = "width: 100%; height: 20px"></div></div> 61<h2><a name="pq_tests" id="pq_tests">Tests</a></h2> 62<ol> 63<li><a href="priority_queue_text_push_timing_test.html">Priority Queue 64 Text <tt>push</tt> Timing Test</a></li> 65<li><a href="priority_queue_text_push_pop_timing_test.html">Priority 66 Queue Text <tt>push</tt> and <tt>pop</tt> Timing 67 Test</a></li> 68<li><a href="priority_queue_random_int_push_timing_test.html">Priority 69 Queue Random Integer <tt>push</tt> Timing Test</a></li> 70<li><a href="priority_queue_random_int_push_pop_timing_test.html">Priority 71 Queue Random Integer <tt>push</tt> and <tt>pop</tt> Timing 72 Test</a></li> 73<li><a href="priority_queue_text_pop_mem_usage_test.html">Priority Queue 74 Text <tt>pop</tt> Memory Use Test</a></li> 75<li><a href="priority_queue_text_join_timing_test.html">Priority Queue 76 Text <tt>join</tt> Timing Test</a></li> 77<li><a href="priority_queue_text_modify_up_timing_test.html">Priority 78 Queue Text <tt>modify</tt> Timing Test - I</a></li> 79<li><a href="priority_queue_text_modify_down_timing_test.html">Priority 80 Queue Text <tt>modify</tt> Timing Test - II</a></li> 81</ol> 82<h2><a name="pq_observations" id="pq_observations">Observations</a></h2> 83<h3><a name="pq_observations_cplx" id="pq_observations_cplx">Underlying Data Structures 84 Complexity</a></h3> 85<p>The following table shows the complexities of the different 86 underlying data structures in terms of orders of growth. It is 87 interesting to note that this table implies something about the 88 constants of the operations as well (see <a href="#pq_observations_amortized_push_pop">Amortized <tt>push</tt> 89 and <tt>pop</tt> operations</a>).</p> 90<table class="c1" width="100%" border="1" summary="pq complexities"> 91<tr> 92<td align="left"></td> 93<td align="left"><tt>push</tt></td> 94<td align="left"><tt>pop</tt></td> 95<td align="left"><tt>modify</tt></td> 96<td align="left"><tt>erase</tt></td> 97<td align="left"><tt>join</tt></td> 98</tr> 99<tr> 100<td align="left"> 101<p><tt>std::priority_queue</tt></p> 102</td> 103<td align="left"> 104<p><i>Θ(n)</i> worst</p> 105<p><i>Θ(log(n))</i> amortized</p> 106</td> 107<td align="left"> 108<p class="c1">Θ(log(n)) Worst</p> 109</td> 110<td align="left"> 111<p><i>Theta;(n log(n))</i> Worst</p> 112<p><sub><a href="#std_mod1">[std note 1]</a></sub></p> 113</td> 114<td align="left"> 115<p class="c3">Θ(n log(n))</p> 116<p><sub><a href="#std_mod2">[std note 2]</a></sub></p> 117</td> 118<td align="left"> 119<p class="c3">Θ(n log(n))</p> 120<p><sub><a href="#std_mod1">[std note 1]</a></sub></p> 121</td> 122</tr> 123<tr> 124<td align="left"> 125<p><a href="priority_queue.html"><tt>priority_queue</tt></a></p> 126<p>with <tt>Tag</tt> =</p> 127<p><a href="pairing_heap_tag.html"><tt>pairing_heap_tag</tt></a></p> 128</td> 129<td align="left"> 130<p class="c1">O(1)</p> 131</td> 132<td align="left"> 133<p><i>Θ(n)</i> worst</p> 134<p><i>Θ(log(n))</i> amortized</p> 135</td> 136<td align="left"> 137<p><i>Θ(n)</i> worst</p> 138<p><i>Θ(log(n))</i> amortized</p> 139</td> 140<td align="left"> 141<p><i>Θ(n)</i> worst</p> 142<p><i>Θ(log(n))</i> amortized</p> 143</td> 144<td align="left"> 145<p class="c1">O(1)</p> 146</td> 147</tr> 148<tr> 149<td align="left"> 150<p><a href="priority_queue.html"><tt>priority_queue</tt></a></p> 151<p>with <tt>Tag</tt> =</p> 152<p><a href="binary_heap_tag.html"><tt>binary_heap_tag</tt></a></p> 153</td> 154<td align="left"> 155<p><i>Θ(n)</i> worst</p> 156<p><i>Θ(log(n))</i> amortized</p> 157</td> 158<td align="left"> 159<p><i>Θ(n)</i> worst</p> 160<p><i>Θ(log(n))</i> amortized</p> 161</td> 162<td align="left"> 163<p class="c1">Θ(n)</p> 164</td> 165<td align="left"> 166<p class="c1">Θ(n)</p> 167</td> 168<td align="left"> 169<p class="c1">Θ(n)</p> 170</td> 171</tr> 172<tr> 173<td align="left"> 174<p><a href="priority_queue.html"><tt>priority_queue</tt></a></p> 175<p>with <tt>Tag</tt> =</p> 176<p><a href="binomial_heap_tag.html"><tt>binomial_heap_tag</tt></a></p> 177</td> 178<td align="left"> 179<p><i>Θ(log(n))</i> worst</p> 180<p><i>O(1)</i> amortized</p> 181</td> 182<td align="left"> 183<p class="c1">Θ(log(n))</p> 184</td> 185<td align="left"> 186<p class="c1">Θ(log(n))</p> 187</td> 188<td align="left"> 189<p class="c1">Θ(log(n))</p> 190</td> 191<td align="left"> 192<p class="c1">Θ(log(n))</p> 193</td> 194</tr> 195<tr> 196<td align="left"> 197<p><a href="priority_queue.html"><tt>priority_queue</tt></a></p> 198<p>with <tt>Tag</tt> =</p> 199<p><a href="rc_binomial_heap_tag.html"><tt>rc_binomial_heap_tag</tt></a></p> 200</td> 201<td align="left"> 202<p class="c1">O(1)</p> 203</td> 204<td align="left"> 205<p class="c1">Θ(log(n))</p> 206</td> 207<td align="left"> 208<p class="c1">Θ(log(n))</p> 209</td> 210<td align="left"> 211<p class="c1">Θ(log(n))</p> 212</td> 213<td align="left"> 214<p class="c1">Θ(log(n))</p> 215</td> 216</tr> 217<tr> 218<td align="left"> 219<p><a href="priority_queue.html"><tt>priority_queue</tt></a></p> 220<p>with <tt>Tag</tt> =</p> 221<p><a href="thin_heap_tag.html"><tt>thin_heap_tag</tt></a></p> 222</td> 223<td align="left"> 224<p class="c1">O(1)</p> 225</td> 226<td align="left"> 227<p><i>Θ(n)</i> worst</p> 228<p><i>Θ(log(n))</i> amortized</p> 229</td> 230<td align="left"> 231<p><i>Θ(log(n))</i> worst</p> 232<p><i>O(1)</i> amortized,</p>or 233 234 <p><i>Θ(log(n))</i> amortized</p> 235<p><sub><a href="#thin_heap_note">[thin_heap_note]</a></sub></p> 236</td> 237<td align="left"> 238<p><i>Θ(n)</i> worst</p> 239<p><i>Θ(log(n))</i> amortized</p> 240</td> 241<td align="left"> 242<p class="c1">Θ(n)</p> 243</td> 244</tr> 245</table> 246<p><sub><a name="std_mod1" id="std_mod1">[std note 1]</a> This 247 is not a property of the algorithm, but rather due to the fact 248 that the STL's priority queue implementation does not support 249 iterators (and consequently the ability to access a specific 250 value inside it). If the priority queue is adapting an 251 <tt>std::vector</tt>, then it is still possible to reduce this 252 to <i>Θ(n)</i> by adapting over the STL's adapter and 253 using the fact that <tt>top</tt> returns a reference to the 254 first value; if, however, it is adapting an 255 <tt>std::deque</tt>, then this is impossible.</sub></p> 256<p><sub><a name="std_mod2" id="std_mod2">[std note 2]</a> As 257 with <a href="#std_mod1">[std note 1]</a>, this is not a 258 property of the algorithm, but rather the STL's implementation. 259 Again, if the priority queue is adapting an 260 <tt>std::vector</tt> then it is possible to reduce this to 261 <i>Θ(n)</i>, but with a very high constant (one must call 262 <tt>std::make_heap</tt> which is an expensive linear 263 operation); if the priority queue is adapting an 264 <tt>std::dequeu</tt>, then this is impossible.</sub></p> 265<p><sub><a name="thin_heap_note" id="thin_heap_note">[thin_heap_note]</a> A thin heap has 266 <i>&Theta(log(n))</i> worst case <tt>modify</tt> time 267 always, but the amortized time depends on the nature of the 268 operation: I) if the operation increases the key (in the sense 269 of the priority queue's comparison functor), then the amortized 270 time is <i>O(1)</i>, but if II) it decreases it, then the 271 amortized time is the same as the worst case time. Note that 272 for most algorithms, I) is important and II) is not.</sub></p> 273<h3><a name="pq_observations_amortized_push_pop" id="pq_observations_amortized_push_pop">Amortized <tt>push</tt> 274 and <tt>pop</tt> operations</a></h3> 275<p>In many cases, a priority queue is needed primarily for 276 sequences of <tt>push</tt> and <tt>pop</tt> operations. All of 277 the underlying data structures have the same amortized 278 logarithmic complexity, but they differ in terms of 279 constants.</p> 280<p>The table above shows that the different data structures are 281 "constrained" in some respects. In general, if a data structure 282 has lower worst-case complexity than another, then it will 283 perform slower in the amortized sense. Thus, for example a 284 redundant-counter binomial heap (<a href="priority_queue.html"><tt>priority_queue</tt></a> with 285 <tt>Tag</tt> = <a href="rc_binomial_heap_tag.html"><tt>rc_binomial_heap_tag</tt></a>) 286 has lower worst-case <tt>push</tt> performance than a binomial 287 heap (<a href="priority_queue.html"><tt>priority_queue</tt></a> 288 with <tt>Tag</tt> = <a href="binomial_heap_tag.html"><tt>binomial_heap_tag</tt></a>), 289 and so its amortized <tt>push</tt> performance is slower in 290 terms of constants.</p> 291<p>As the table shows, the "least constrained" underlying 292 data structures are binary heaps and pairing heaps. 293 Consequently, it is not surprising that they perform best in 294 terms of amortized constants.</p> 295<ol> 296<li>Pairing heaps seem to perform best for non-primitive 297 types (<i>e.g.</i>, <tt>std::string</tt>s), as shown by 298 <a href="priority_queue_text_push_timing_test.html">Priority 299 Queue Text <tt>push</tt> Timing Test</a> and <a href="priority_queue_text_push_pop_timing_test.html">Priority 300 Queue Text <tt>push</tt> and <tt>pop</tt> Timing 301 Test</a></li> 302<li>binary heaps seem to perform best for primitive types 303 (<i>e.g.</i>, <tt><b>int</b></tt>s), as shown by <a href="priority_queue_random_int_push_timing_test.html">Priority 304 Queue Random Integer <tt>push</tt> Timing Test</a> and 305 <a href="priority_queue_random_int_push_pop_timing_test.html">Priority 306 Queue Random Integer <tt>push</tt> and <tt>pop</tt> Timing 307 Test</a>.</li> 308</ol> 309<h3><a name="pq_observations_graph" id="pq_observations_graph">Graph Algorithms</a></h3> 310<p>In some graph algorithms, a decrease-key operation is 311 required [<a href="references.html#clrs2001">clrs2001</a>]; 312 this operation is identical to <tt>modify</tt> if a value is 313 increased (in the sense of the priority queue's comparison 314 functor). The table above and <a href="priority_queue_text_modify_up_timing_test.html">Priority Queue 315 Text <tt>modify</tt> Timing Test - I</a> show that a thin heap 316 (<a href="priority_queue.html"><tt>priority_queue</tt></a> with 317 <tt>Tag</tt> = <a href="thin_heap_tag.html"><tt>thin_heap_tag</tt></a>) 318 outperforms a pairing heap (<a href="priority_queue.html"><tt>priority_queue</tt></a> with 319 <tt>Tag</tt> =<tt>Tag</tt> = <a href="pairing_heap_tag.html"><tt>pairing_heap_tag</tt></a>), 320 but the rest of the tests show otherwise.</p> 321<p>This makes it difficult to decide which implementation to 322 use in this case. Dijkstra's shortest-path algorithm, for 323 example, requires <i>Θ(n)</i> <tt>push</tt> and 324 <tt>pop</tt> operations (in the number of vertices), but 325 <i>O(n<sup>2</sup>)</i> <tt>modify</tt> operations, which can 326 be in practice <i>Θ(n)</i> as well. It is difficult to 327 find an <i>a-priori</i> characterization of graphs in which the 328 <u>actual</u> number of <tt>modify</tt> operations will dwarf 329 the number of <tt>push</tt> and <tt>pop</tt> operations.</p> 330</div> 331</body> 332</html> 333