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 Random Int 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 Random Integer <tt>push</tt> Timing 13 Test</h1> 14<h2><a name="description" id="description">Description</a></h2> 15<p>This test inserts a number of values with i.i.d integer keys 16 into a container using <tt>push</tt> . It measures the average 17 time for <tt>push</tt> as a function of the number of 18 values.</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_random_int_push_timing.cc"><tt> 20 priority_queue_random_intpush_timing_test</tt></a> 21 thirty_years_among_the_dead_preproc.txt 200 200 2100)</p> 22<h2><a name="purpose" id="purpose">Purpose</a></h2> 23<p>The test checks the effect of different underlying 24 data structures (see <a href="pq_design.html#pq_imp">Design::Priority 25 Queues::Implementations</a>).</p> 26<h2><a name="results" id="results">Results</a></h2> 27<p>Figures <a href="#NPG">NPG</a>, <a href="#NPM">NPM</a>, and 28 <a href="#NPL">NPL</a> show the results for the native priority 29 queues and <tt>pb_ds</tt> 's priority queues in <a href="assoc_performance_tests.html#gcc"><u>g++</u></a>, <a href="assoc_performance_tests.html#msvc"><u>msvc++</u></a>, and 30 <a href="assoc_performance_tests.html#local"><u>local</u></a>, 31 respectively; Figures <a href="#NBPG">NBPG</a>, <a href="#NBPM">NBPM</a>, and <a href="#NBPL">NBPL</a> shows the 32 results for the binary-heap based native priority queues and 33 <tt>pb_ds</tt> 's priority queues in <a href="assoc_performance_tests.html#gcc"><u>g++</u></a>, <a href="assoc_performance_tests.html#msvc"><u>msvc++</u></a>, and 34 <a href="assoc_performance_tests.html#local"><u>local</u></a>, 35 respectively</p> 36<div id="NPG_res_div"> 37<div id="NPG_gcc"> 38<div id="NPG_priority_queue_random_int_push_timing_test"> 39<div id="NPG_pq"> 40<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_random_int_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> 41<ol> 42<li> 43rc_binomial_heap- 44<a href="priority_queue.html"><tt>priority_queue</tt></a> 45 with <tt>Tag</tt> = <a href="rc_binomial_heap_tag.html"><tt>rc_binomial_heap_tag</tt></a> 46</li> 47<li> 48binomial_heap- 49<a href="priority_queue.html"><tt>priority_queue</tt></a> 50 with <tt>Tag</tt> = <a href="binomial_heap_tag.html"><tt>binomial_heap_tag</tt></a> 51</li> 52<li> 53n_pq_deque- 54<tt>std::priority_queue</tt> adapting <tt>std::deque</tt></li> 55<li> 56pairing_heap- 57<a href="priority_queue.html"><tt>priority_queue</tt></a> 58 with <tt>Tag</tt> = <a href="pairing_heap_tag.html"><tt>pairing_heap_tag</tt></a> 59</li> 60<li> 61thin_heap- 62<a href="priority_queue.html"><tt>priority_queue</tt></a> 63 with <tt>Tag</tt> = <a href="thin_heap_tag.html"><tt>thin_heap_tag</tt></a> 64</li> 65<li> 66n_pq_vector- 67<tt>std::priority_queue</tt> adapting <tt>std::vector</tt></li> 68<li> 69binary_heap- 70<a href="priority_queue.html"><tt>priority_queue</tt></a> 71 with <tt>Tag</tt> = <a href="binary_heap_tag.html"><tt>binary_heap_tag</tt></a> 72</li> 73</ol> 74</div><div style="width: 100%; height: 20px"></div></div> 75</div> 76</div> 77</div> 78</div> 79<div id="NPM_res_div"> 80<div id="NPM_msvc"> 81<div id="NPM_priority_queue_random_int_push_timing_test"> 82<div id="NPM_pq"> 83<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_random_int_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> 84<ol> 85<li> 86rc_binomial_heap- 87<a href="priority_queue.html"><tt>priority_queue</tt></a> 88 with <tt>Tag</tt> = <a href="rc_binomial_heap_tag.html"><tt>rc_binomial_heap_tag</tt></a> 89</li> 90<li> 91binomial_heap- 92<a href="priority_queue.html"><tt>priority_queue</tt></a> 93 with <tt>Tag</tt> = <a href="binomial_heap_tag.html"><tt>binomial_heap_tag</tt></a> 94</li> 95<li> 96pairing_heap- 97<a href="priority_queue.html"><tt>priority_queue</tt></a> 98 with <tt>Tag</tt> = <a href="pairing_heap_tag.html"><tt>pairing_heap_tag</tt></a> 99</li> 100<li> 101thin_heap- 102<a href="priority_queue.html"><tt>priority_queue</tt></a> 103 with <tt>Tag</tt> = <a href="thin_heap_tag.html"><tt>thin_heap_tag</tt></a> 104</li> 105<li> 106n_pq_deque- 107<tt>std::priority_queue</tt> adapting <tt>std::deque</tt></li> 108<li> 109n_pq_vector- 110<tt>std::priority_queue</tt> adapting <tt>std::vector</tt></li> 111<li> 112binary_heap- 113<a href="priority_queue.html"><tt>priority_queue</tt></a> 114 with <tt>Tag</tt> = <a href="binary_heap_tag.html"><tt>binary_heap_tag</tt></a> 115</li> 116</ol> 117</div><div style="width: 100%; height: 20px"></div></div> 118</div> 119</div> 120</div> 121</div> 122<div id="NPL_res_div"> 123<div id="NPL_local"> 124<div id="NPL_priority_queue_random_int_push_timing_test"> 125<div id="NPL_pq"> 126<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_random_int_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> 127</div> 128</div> 129</div> 130</div> 131<div id="NBPG_res_div"> 132<div id="NBPG_gcc"> 133<div id="NBPG_binary_priority_queue_random_int_push_timing_test"> 134<div id="NBPG_pq"> 135<div id="NBPG_Native_and__tt_pb_ds_455tt__binary_priority_queue__tt_push_455tt__timing_test"><div style="border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class="c1"><a name="NBPG" id="NBPG"><img src="binary_priority_queue_random_int_push_timing_test_gcc.png" alt="no image" /></a></h6>NBPG: Native and <tt>pb ds</tt> binary 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> 136<ol> 137<li> 138n_pq_deque- 139<tt>std::priority_queue</tt> adapting <tt>std::deque</tt></li> 140<li> 141n_pq_vector- 142<tt>std::priority_queue</tt> adapting <tt>std::vector</tt></li> 143<li> 144binary_heap- 145<a href="priority_queue.html"><tt>priority_queue</tt></a> 146 with <tt>Tag</tt> = <a href="binary_heap_tag.html"><tt>binary_heap_tag</tt></a> 147</li> 148</ol> 149</div><div style="width: 100%; height: 20px"></div></div> 150</div> 151</div> 152</div> 153</div> 154<div id="NBPM_res_div"> 155<div id="NBPM_msvc"> 156<div id="NBPM_binary_priority_queue_random_int_push_timing_test"> 157<div id="NBPM_pq"> 158<div id="NBPM_Native_and__tt_pb_ds_455tt__binary_priority_queue__tt_push_455tt__timing_test"><div style="border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class="c1"><a name="NBPM" id="NBPM"><img src="binary_priority_queue_random_int_push_timing_test_msvc.png" alt="no image" /></a></h6>NBPM: Native and <tt>pb ds</tt> binary 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> 159<ol> 160<li> 161n_pq_deque- 162<tt>std::priority_queue</tt> adapting <tt>std::deque</tt></li> 163<li> 164n_pq_vector- 165<tt>std::priority_queue</tt> adapting <tt>std::vector</tt></li> 166<li> 167binary_heap- 168<a href="priority_queue.html"><tt>priority_queue</tt></a> 169 with <tt>Tag</tt> = <a href="binary_heap_tag.html"><tt>binary_heap_tag</tt></a> 170</li> 171</ol> 172</div><div style="width: 100%; height: 20px"></div></div> 173</div> 174</div> 175</div> 176</div> 177<div id="NBPL_res_div"> 178<div id="NBPL_local"> 179<div id="NBPL_binary_priority_queue_random_int_push_timing_test"> 180<div id="NBPL_pq"> 181<div id="NBPL_Native_and__tt_pb_ds_455tt__binary_priority_queue__tt_push_455tt__timing_test"><div style = "border-style: dotted; border-width: 1px; border-color: lightgray"><h6 class="c1"><a name="NBPL" id= "NBPL"><img src="binary_priority_queue_random_int_push_timing_test_local.png" alt="no image" /></a></h6>NBPL: Native and <tt>pb ds</tt> binary 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> 182</div> 183</div> 184</div> 185</div> 186<h2><a name="observations" id="observations">Observations</a></h2> 187<p>Binary heaps are the most suited for sequences of 188 <tt>push</tt> and <tt>pop</tt> operations of primitive types 189 (<i>e.g.</i> <tt><b>int</b></tt>s). They are less constrained 190 than any other type, and since it is very efficient to store 191 such types in arrays, they outperform even pairing heaps. (See 192 <a href="priority_queue_text_push_timing_test.html">Priority 193 Queue Text <tt>push</tt> Timing Test</a> for the case of 194 non-primitive types.)</p> 195<p><a href="pq_performance_tests.html#pq_observations">Priority-Queue 196 Performance Tests::Observations</a> discusses this further and 197 summarizes.</p> 198</div> 199</body> 200</html> 201