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 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="../../../../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> 42n_pq_vector- 43<tt>std::priority_queue</tt> adapting <tt>std::vector</tt></li> 44<li> 45n_pq_deque- 46<tt>std::priority_queue</tt> adapting <tt>std::deque</tt></li> 47<li> 48binary_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> 53rc_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> 58thin_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> 63binomial_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> 68pairing_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> 85n_pq_deque- 86<tt>std::priority_queue</tt> adapting <tt>std::deque</tt></li> 87<li> 88rc_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> 93binary_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> 98binomial_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> 103n_pq_vector- 104<tt>std::priority_queue</tt> adapting <tt>std::vector</tt></li> 105<li> 106pairing_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> 111thin_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> 137n_pq_vector- 138<tt>std::priority_queue</tt> adapting <tt>std::vector</tt></li> 139<li> 140n_pq_deque- 141<tt>std::priority_queue</tt> adapting <tt>std::deque</tt></li> 142<li> 143thin_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> 148pairing_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> 165n_pq_deque- 166<tt>std::priority_queue</tt> adapting <tt>std::deque</tt></li> 167<li> 168n_pq_vector- 169<tt>std::priority_queue</tt> adapting <tt>std::vector</tt></li> 170<li> 171pairing_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> 176thin_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> 220
