URL
https://opencores.org/ocsvn/openrisc/openrisc/trunk
Subversion Repositories openrisc
[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [libstdc++-v3/] [doc/] [xml/] [manual/] [test_policy_data_structures.xml] - Rev 742
Compare with Previous | Blame | View Log
<section xmlns="http://docbook.org/ns/docbook" version="5.0"xml:id="pbds.test" xreflabel="Test"><info><title>Testing</title></info><?dbhtml filename="policy_based_data_structures_test.html"?><!-- S01 regression --><section xml:id="pbds.test.regression"><info><title>Regression</title></info><para>The library contains a single comprehensive regression test.For a given container type in this library, the test createsan object of the container type and an object of thecorresponding standard type (e.g., <classname>std::set</classname>). Itthen performs a random sequence of methods with randomarguments (e.g., inserts, erases, and so forth) on bothobjects. At each operation, the test checks the return value ofthe method, and optionally both compares this library'sobject with the standard's object as well as performing otherconsistency checks on this library's object (e.g.,order preservation, when applicable, or node invariants, whenapplicable).</para><para>Additionally, the test integrally checks exception safetyand resource leaks. This is done as follows. A specialallocator type, written for the purpose of the test, bothrandomly throws an exceptions when allocations are performed,and tracks allocations and de-allocations. The exceptions thrownat allocations simulate memory-allocation failures; thetracking mechanism checks for memory-related bugs (e.g.,resource leaks and multiple de-allocations). Boththis library's containers and the containers' value-types areconfigured to use this allocator.</para><para>For granularity, the test is split into theseveral sources, each checking only some containers.</para><para>For more details, consult the files in<filename>testsuite/ext/pb_ds/regression</filename>.</para></section><!-- S02 performance --><section xml:id="pbds.test.performance"><info><title>Performance</title></info><section xml:id="performance.hash"><info><title>Hash-Based</title></info><para></para><!-- 01 <a href="hash_text_find_find_timing_test"> --><section xml:id="performance.hash.text_find"><info><title>Text <function>find</function></title></info><para></para><section xml:id="hash.text_find.info"><info><title>Description</title></info><para>This test inserts a number of values with keys from anarbitrary text (<xreflinkend="biblio.wickland96thirty"/>) into a container,then performs a series of finds using<function>find</function> . It measures the averagetime for <function>find</function> as a function ofthe number of values inserted.</para><para>It uses the test file:<filename>performance/ext/pb_ds/text_find_timing_test.cc</filename></para><para>And uses the data file:<filename>filethirty_years_among_the_dead_preproc.txt</filename></para><para>The test checks the effect of different range-hashingfunctions, trigger policies, and cache-hashing policies.</para></section><section xml:id="hash.text_find.results"><info><title>Results</title></info><para>The graphic below show the results for the nativeand collision-chaining hash types the the functionapplied being a text find timing test using<function>find</function>.</para><!-- results graphic --><informalfigure><mediaobject><imageobject><imagedata align="center" format="PDF" scale="75"fileref="../images/pbds_hash_text_find.pdf"/></imageobject><imageobject><imagedata align="center" format="PNG" scale="100"fileref="../images/pbds_hash_text_find.png"/></imageobject></mediaobject></informalfigure><para>The abbreviated names in the legend of the graphic above areinstantiated with the types in the following table.</para><informaltable frame="all"><tgroup cols="5" align="left" colsep="1" rowsep="1"><colspec colname="c1"/><colspec colname="c2"/><colspec colname="c3"/><colspec colname="c4"/><colspec colname="c5"/><thead><row><entry><emphasis>Name/Instantiating Type</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry></row></thead><tbody><!-- native --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c5">n_hash_map_ncah</entry></row><row><entry><classname>std::tr1::unordered_map</classname></entry><entry><classname>cache_hash_code</classname></entry><entry><constant>false</constant></entry><entry namest="c4" nameend="c5"></entry></row><!-- hash 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c5">cc_hash_mod_prime_1div1_nsth_map</entry></row><row><entry morerows="2" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mod_range_hashing</classname></entry><entry namest="c4" nameend="c5"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_prime_size_policy</classname></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/1</entry></row><!-- hash 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c5">cc_hash_mask_exp_1div2_sth_map</entry></row><row><entry morerows="2" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mask_range_hashing</classname></entry><entry namest="c4" nameend="c5"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_exponential_size_policy</classname></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2</entry></row><!-- hash 03 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c5">cc_hash_mask_exp_1div1_nsth_map</entry></row><row><entry morerows="2" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mask_range_hashing</classname></entry><entry namest="c4" nameend="c5"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_exponential_size_policy</classname></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/1</entry></row><!-- hash 04 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c5">cc_hash_mask_exp_1div2_nsth_map</entry></row><row><entry morerows="2" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mask_range_hashing</classname></entry><entry namest="c4" nameend="c5"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_exponential_size_policy</classname></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2</entry></row></tbody></tgroup></informaltable></section><section xml:id="hash.text_find.observations"><info><title>Observations</title></info><para>In this setting, the range-hashing scheme affects performancemore than other policies. As the results show, containers usingmod-based range-hashing (including the native hash-based container,which is currently hard-wired to this scheme) have lower performancethan those using mask-based range-hashing. A modulo-basedrange-hashing scheme's main benefit is that it takes into accountall hash-value bits. Standard string hash-functions are designed tocreate hash values that are nearly-uniform as is (<xreflinkend="biblio.knuth98sorting"/>).</para><para>Trigger policies, i.e. the load-checks constants, affectperformance to a lesser extent.</para><para>Perhaps surprisingly, storing the hash value alongside eachentry affects performance only marginally, at least in thislibrary's implementation. (Unfortunately, it was not possible to runthe tests with <classname>std::tr1::unordered_map</classname> 's<classname>cache_hash_code = true</classname> , as it appeared tomalfuntion.)</para></section></section><!-- 02 <a href="hash_int_find_timing_test"> --><section xml:id="performance.hash.int_find"><info><title>Integer <function>find</function></title></info><para></para><section xml:id="hash.int_find.info"><info><title>Description</title></info><para>This test inserts a number of values with uniforminteger keys into a container, then performs a series of findsusing <function>find</function>. It measures the average timefor <function>find</function> as a function of the number of valuesinserted.</para><para>It uses the test file:<filename>performance/ext/pb_ds/random_int_find_timing.cc</filename></para><para>The test checks the effect of different underlyinghash-tables,range-hashing functions, and trigger policies.</para></section><section xml:id="hash.int_find.results"><info><title>Results</title></info><para>There are two sets of results for this type, one forcollision-chaining hashes, and one for general-probe hashes.</para><para>The first graphic below shows the results for the native andcollision-chaining hash types. The function applied being a randominteger timing test using <function>find</function>.</para><!-- results graphic 01 --><informalfigure><mediaobject><imageobject><imagedata align="center" format="PDF" scale="75"fileref="../images/pbds_cc_hash_int_find.pdf"/></imageobject><imageobject><imagedata align="center" format="PNG" scale="100"fileref="../images/pbds_cc_hash_int_find.png"/></imageobject></mediaobject></informalfigure><para>The abbreviated names in the legend of the graphic above areinstantiated with the types in the following table.</para><informaltable frame="all"><tgroup cols="5" align="left" colsep="1" rowsep="1"><colspec colname="c1"/><colspec colname="c2"/><colspec colname="c3"/><colspec colname="c4"/><colspec colname="c5"/><thead><row><entry><emphasis>Name/Instantiating Type</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry></row></thead><tbody><!-- native --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c5">n_hash_map_ncah</entry></row><row><entry><classname>std::tr1::unordered_map</classname></entry><entry><classname>cache_hash_code</classname></entry><entry><constant>false</constant></entry><entry namest="c4" nameend="c5"></entry></row><!-- hash 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c5">cc_hash_mod_prime_1div1_nsth_map</entry></row><row><entry morerows="2" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mod_range_hashing</classname></entry><entry namest="c4" nameend="c5"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_prime_size_policy</classname></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/1</entry></row><!-- hash 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c5">cc_hash_mod_prime_1div2_nsth_map</entry></row><row><entry morerows="2" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mod_range_hashing</classname></entry><entry namest="c4" nameend="c5"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_prime_size_policy</classname></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2</entry></row><!-- hash 03 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c5">cc_hash_mask_exp_1div1_nsth_map</entry></row><row><entry morerows="2" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mask_range_hashing</classname></entry><entry namest="c4" nameend="c5"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_exponential_size_policy</classname></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/1</entry></row><!-- hash 04 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c5">cc_hash_mask_exp_1div2_nsth_map</entry></row><row><entry morerows="2" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mask_range_hashing</classname></entry><entry namest="c4" nameend="c5"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_exponential_size_policy</classname></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2</entry></row></tbody></tgroup></informaltable><para></para><para></para><para>And the second graphic shows the results for the native andgeneral-probe hash types. The function applied being a randominteger timing test using <function>find</function>.</para><!-- results graphic 02 --><informalfigure><mediaobject><imageobject><imagedata align="center" format="PDF" scale="75"fileref="../images/pbds_gp_hash_int_find.pdf"/></imageobject><imageobject><imagedata align="center" format="PNG" scale="100"fileref="../images/pbds_gp_hash_int_find.png"/></imageobject></mediaobject></informalfigure><para>The abbreviated names in the legend of the graphic above areinstantiated with the types in the following table.</para><informaltable frame="all"><tgroup cols="5" align="left" colsep="1" rowsep="1"><colspec colname="c1"/><colspec colname="c2"/><colspec colname="c3"/><colspec colname="c4"/><colspec colname="c5"/><thead><row><entry><emphasis>Name/Instantiating Type</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry></row></thead><tbody><!-- native --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c5">n_hash_map_ncah</entry></row><row><entry><classname>std::tr1::unordered_map</classname></entry><entry><classname>cache_hash_code</classname></entry><entry><constant>false</constant></entry><entry namest="c4" nameend="c5"></entry></row><!-- hash 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c5">gp_hash_mod_quadp_prime_1div2_nsth_map</entry></row><row><entry morerows="3" valign="top"><classname>gp_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mod_range_hashing</classname></entry><entry namest="c4" nameend="c5"></entry></row><row><entry><classname>Probe_Fn</classname></entry><entry><classname>quadratic_probe_fn</classname></entry><entry namest="c4" nameend="c5"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_prime_size_policy</classname></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2</entry></row><!-- hash 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c5">gp_hash_mask_linp_exp_1div2_nsth_map</entry></row><row><entry morerows="3" valign="top"><classname>gp_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mask_range_hashing</classname></entry><entry namest="c4" nameend="c5"></entry></row><row><entry><classname>Probe_Fn</classname></entry><entry><classname>linear_probe_fn</classname></entry><entry namest="c4" nameend="c5"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_exponential_size_policy</classname></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2</entry></row></tbody></tgroup></informaltable></section><section xml:id="hash.int_find.observations"><info><title>Observations</title></info><para>In this setting, the choice of underlying hash-table affectsperformance most, then the range-hashing scheme and, only finally,other policies.</para><para>When comparing probing and chaining containers, it isapparent that the probing containers are less efficient than thecollision-chaining containers (<classname>std::tr1::unordered_map</classname> usescollision-chaining) in this case.</para><para>Hash-Based Integer Subscript Insert Timing Test showsa different case, where the situation is reversed;</para><para>Within each type of hash-table, the range-hashing schemeaffects performance more than other policies; Hash-Based Text<function>find</function> Find Timing Test also shows this. In theabove graphics should be noted that<classname>std::tr1::unordered_map</classname> are hard-wiredcurrently to mod-based schemes.</para></section></section><!-- 03 <a href="hash_int_subscript_find_test"> --><section xml:id="performance.hash.int_subscript_find"><info><title>Integer Subscript <function>find</function></title></info><para></para><section xml:id="hash.int_subscript_find.info"><info><title>Description</title></info><para>This test inserts a number of values with uniforminteger keys into a container, then performs a series of findsusing <function>operator[]</function>. It measures the average timefor <function>operator[]</function> as a function of the number ofvalues inserted.</para><para>It uses the test file:<filename>performance/ext/pb_ds/random_int_subscript_find_timing.cc</filename></para><para>The test checks the effect of different underlyinghash-tables, range-hashing functions, and trigger policies.</para></section><section xml:id="hash.int_subscript_find.results"><info><title>Results</title></info><para>There are two sets of results for this type, one forcollision-chaining hashes, and one for general-probe hashes.</para><para>The first graphic below shows the results for the nativeand collision-chaining hash types, using as the functionapplied an integer subscript timing test with<function>find</function>.</para><!-- results graphic --><informalfigure><mediaobject><imageobject><imagedata align="center" format="PDF" scale="75"fileref="../images/pbds_cc_hash_int_subscript_find.pdf"/></imageobject><imageobject><imagedata align="center" format="PNG" scale="100"fileref="../images/pbds_cc_hash_int_subscript_find.png"/></imageobject></mediaobject></informalfigure><para>The abbreviated names in the legend of the graphic above areinstantiated with the types in the following table.</para><informaltable frame="all"><tgroup cols="5" align="left" colsep="1" rowsep="1"><colspec colname="c1"/><colspec colname="c2"/><colspec colname="c3"/><colspec colname="c4"/><colspec colname="c5"/><thead><row><entry><emphasis>Name/Instantiating Type</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry></row></thead><tbody><!-- native --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c5">n_hash_map_ncah</entry></row><row><entry><classname>std::tr1::unordered_map</classname></entry><entry><classname>cache_hash_code</classname></entry><entry><constant>false</constant></entry><entry namest="c4" nameend="c5"></entry></row><!-- hash 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c5">cc_hash_mod_prime_1div1_nsth_map</entry></row><row><entry morerows="2" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mod_range_hashing</classname></entry><entry namest="c4" nameend="c5"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_prime_size_policy</classname></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/1</entry></row><!-- hash 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c5">cc_hash_mod_prime_1div2_nsth_map</entry></row><row><entry morerows="2" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mod_range_hashing</classname></entry><entry namest="c4" nameend="c5"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_prime_size_policy</classname></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2</entry></row><!-- hash 03 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c5">cc_hash_mask_exp_1div1_nsth_map</entry></row><row><entry morerows="2" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mask_range_hashing</classname></entry><entry namest="c4" nameend="c5"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_exponential_size_policy</classname></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/1</entry></row><!-- hash 04 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c5">cc_hash_mask_exp_1div2_nsth_map</entry></row><row><entry morerows="2" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mask_range_hashing</classname></entry><entry namest="c4" nameend="c5"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_exponential_size_policy</classname></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2</entry></row></tbody></tgroup></informaltable><para></para><para></para><para>And the second graphic shows the results for the native andgeneral-probe hash types. The function applied being a randominteger timing test using <function>find</function>.</para><!-- results graphic 02 --><informalfigure><mediaobject><imageobject><imagedata align="center" format="PDF" scale="75"fileref="../images/pbds_gp_hash_int_subscript_find.pdf"/></imageobject><imageobject><imagedata align="center" format="PNG" scale="100"fileref="../images/pbds_gp_hash_int_subscript_find.png"/></imageobject></mediaobject></informalfigure><para>The abbreviated names in the legend of the graphic above areinstantiated with the types in the following table.</para><informaltable frame="all"><tgroup cols="5" align="left" colsep="1" rowsep="1"><colspec colname="c1"/><colspec colname="c2"/><colspec colname="c3"/><colspec colname="c4"/><colspec colname="c5"/><thead><row><entry><emphasis>Name/Instantiating Type</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry></row></thead><tbody><!-- native --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c5">n_hash_map_ncah</entry></row><row><entry><classname>std::tr1::unordered_map</classname></entry><entry><classname>cache_hash_code</classname></entry><entry><constant>false</constant></entry><entry namest="c4" nameend="c5"></entry></row><!-- hash 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c5">gp_hash_mod_quadp_prime_1div2_nsth_map</entry></row><row><entry morerows="3" valign="top"><classname>gp_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mod_range_hashing</classname></entry><entry namest="c4" nameend="c5"></entry></row><row><entry><classname>Probe_Fn</classname></entry><entry><classname>quadratic_probe_fn</classname></entry><entry namest="c4" nameend="c5"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_prime_size_policy</classname></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2</entry></row><!-- hash 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c5">gp_hash_mask_linp_exp_1div2_nsth_map</entry></row><row><entry morerows="3" valign="top"><classname>gp_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mask_range_hashing</classname></entry><entry namest="c4" nameend="c5"></entry></row><row><entry><classname>Probe_Fn</classname></entry><entry><classname>linear_probe_fn</classname></entry><entry namest="c4" nameend="c5"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_exponential_size_policy</classname></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2</entry></row></tbody></tgroup></informaltable></section><section xml:id="hash.int_subscript_find.observations"><info><title>Observations</title></info><para>This test shows similar results to Hash-BasedInteger <classname>find</classname> Find Timing test.</para></section></section><!-- 04 <a href="hash_random_int_subscript_insert_timing_test"> --><section xml:id="performance.hash.int_subscript_insert"><info><title>Integer Subscript <function>insert</function></title></info><para></para><section xml:id="hash.int_subscript_insert.info"><info><title>Description</title></info><para>This test inserts a number of values with uniform i.i.d.integer keys into a container, using<function>operator[]</function>. It measures the average time for<function>operator[]</function> as a function of the number ofvalues inserted.</para><para>It uses the test file:<filename>performance/ext/pb_ds/random_int_subscript_insert_timing.cc</filename></para><para>The test checks the effect of different underlyinghash-tables.</para></section><section xml:id="hash.int_subscript_insert.results"><info><title>Results</title></info><para>There are two sets of results for this type, one forcollision-chaining hashes, and one for general-probe hashes.</para><para>The first graphic below shows the results for the nativeand collision-chaining hash types, using as the functionapplied an integer subscript timing test with<function>insert</function>.</para><!-- results graphic --><informalfigure><mediaobject><imageobject><imagedata align="center" format="PDF" scale="75"fileref="../images/pbds_cc_hash_int_subscript_insert.pdf"/></imageobject><imageobject><imagedata align="center" format="PNG" scale="100"fileref="../images/pbds_cc_hash_int_subscript_insert.png"/></imageobject></mediaobject></informalfigure><para>The abbreviated names in the legend of the graphic above areinstantiated with the types in the following table.</para><informaltable frame="all"><tgroup cols="5" align="left" colsep="1" rowsep="1"><colspec colname="c1"/><colspec colname="c2"/><colspec colname="c3"/><colspec colname="c4"/><colspec colname="c5"/><thead><row><entry><emphasis>Name/Instantiating Type</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry></row></thead><tbody><!-- native --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c5">n_hash_map_ncah</entry></row><row><entry><classname>std::tr1::unordered_map</classname></entry><entry><classname>cache_hash_code</classname></entry><entry><constant>false</constant></entry><entry namest="c4" nameend="c5"></entry></row><!-- hash 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c5">cc_hash_mod_prime_1div1_nsth_map</entry></row><row><entry morerows="2" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mod_range_hashing</classname></entry><entry namest="c4" nameend="c5"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_prime_size_policy</classname></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/1</entry></row><!-- hash 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c5">cc_hash_mod_prime_1div2_nsth_map</entry></row><row><entry morerows="2" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mod_range_hashing</classname></entry><entry namest="c4" nameend="c5"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_prime_size_policy</classname></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2</entry></row><!-- hash 03 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c5">cc_hash_mask_exp_1div1_nsth_map</entry></row><row><entry morerows="2" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mask_range_hashing</classname></entry><entry namest="c4" nameend="c5"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_exponential_size_policy</classname></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/1</entry></row><!-- hash 04 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c5">cc_hash_mask_exp_1div2_nsth_map</entry></row><row><entry morerows="2" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mask_range_hashing</classname></entry><entry namest="c4" nameend="c5"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_exponential_size_policy</classname></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2</entry></row></tbody></tgroup></informaltable><para></para><para></para><para>And the second graphic shows the results for the native andgeneral-probe hash types. The function applied being a randominteger timing test using <function>find</function>.</para><!-- results graphic 02 --><informalfigure><mediaobject><imageobject><imagedata align="center" format="PDF" scale="75"fileref="../images/pbds_gp_hash_int_subscript_insert.pdf"/></imageobject><imageobject><imagedata align="center" format="PNG" scale="100"fileref="../images/pbds_gp_hash_int_subscript_insert.png"/></imageobject></mediaobject></informalfigure><para>The abbreviated names in the legend of the graphic above areinstantiated with the types in the following table.</para><informaltable frame="all"><tgroup cols="5" align="left" colsep="1" rowsep="1"><colspec colname="c1"/><colspec colname="c2"/><colspec colname="c3"/><colspec colname="c4"/><colspec colname="c5"/><thead><row><entry><emphasis>Name/Instantiating Type</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry></row></thead><tbody><!-- native --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c5">n_hash_map_ncah</entry></row><row><entry><classname>std::tr1::unordered_map</classname></entry><entry><classname>cache_hash_code</classname></entry><entry><constant>false</constant></entry><entry namest="c4" nameend="c5"></entry></row><!-- hash 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c5">gp_hash_mod_quadp_prime_1div2_nsth_map</entry></row><row><entry morerows="3" valign="top"><classname>gp_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mod_range_hashing</classname></entry><entry namest="c4" nameend="c5"></entry></row><row><entry><classname>Probe_Fn</classname></entry><entry><classname>quadratic_probe_fn</classname></entry><entry namest="c4" nameend="c5"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_prime_size_policy</classname></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2</entry></row><!-- hash 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c5">gp_hash_mask_linp_exp_1div2_nsth_map</entry></row><row><entry morerows="3" valign="top"><classname>gp_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mask_range_hashing</classname></entry><entry namest="c4" nameend="c5"></entry></row><row><entry><classname>Probe_Fn</classname></entry><entry><classname>linear_probe_fn</classname></entry><entry namest="c4" nameend="c5"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_exponential_size_policy</classname></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2</entry></row></tbody></tgroup></informaltable></section><section xml:id="hash.int_subscript_insert.observations"><info><title>Observations</title></info><para>In this setting, as in Hash-Based Text<function>find</function> Find Timing test and Hash-BasedInteger <function>find</function> Find Timing test , the choiceof underlying hash-table underlying hash-table affects performancemost, then the range-hashing scheme, andfinally any other policies.</para><para>There are some differences, however:</para><orderedlist><listitem><para>In this setting, probing tables function sometimes moreefficiently than collision-chaining tables.This is explained shortly.</para></listitem><listitem><para>The performance graphs have a "saw-tooth" shape. Theaverage insert time rises and falls. As values are insertedinto the container, the load factor grows larger. Eventually,a resize occurs. The reallocations and rehashing arerelatively expensive. After this, the load factor is smallerthan before.</para></listitem></orderedlist><para>Collision-chaining containers use indirection for greaterflexibility; probing containers store values contiguously, inan array (see Figure Motivation::Differentunderlying data structures A and B, respectively). Itfollows that for simple data types, probing containers accesstheir allocator less frequently than collision-chainingcontainers, (although they still have less efficient probingsequences). This explains why some probing containers farebetter than collision-chaining containers in this case.</para><para>Within each type of hash-table, the range-hashing scheme affectsperformance more than other policies. This is similar to thesituation in Hash-Based Text<function>find</function> Find Timing Test and Hash-BasedInteger <function>find</function> Find Timing Test.Unsurprisingly, however, containers with lower α<subscript>max</subscript> perform worse in this case,since more re-hashes are performed.</para></section></section><!-- 05 <a href="hash_zlob_random_int_find_find_timing_test"> --><!-- 05 <a href="hash_zlob_random_int_find_find_timing_test"> --><section xml:id="performance.hash.zlob_int_find"><info><title>Integer <function>find</function> with Skewed-Distribution</title></info><para></para><section xml:id="hash.zlob_int_find.info"><info><title>Description</title></info><para>This test inserts a number of values with a markedlynon-uniform integer keys into a container, then performsa series of finds using <function>find</function>. It measures the averagetime for <function>find</function> as a function of the number of values inthe containers. The keys are generated as follows. First, auniform integer is created. Then it is then shifted left 8 bits.</para><para>It uses the test file:<filename>performance/ext/pb_ds/hash_zlob_random_int_find_timing.cc</filename></para><para>The test checks the effect of different range-hashingfunctions and trigger policies.</para></section><section xml:id="hash.zlob_int_find.results"><info><title>Results</title></info><para>The graphic below show the results for the native, collision-chaining, and general-probing hash types.</para><!-- results graphic --><informalfigure><mediaobject><imageobject><imagedata align="center" format="PDF" scale="75"fileref="../images/pbds_hash_zlob_int_find.pdf"/></imageobject><imageobject><imagedata align="center" format="PNG" scale="100"fileref="../images/pbds_hash_zlob_int_find.png"/></imageobject></mediaobject></informalfigure><para>The abbreviated names in the legend of the graphic above areinstantiated with the types in the following table.</para><informaltable frame="all"><tgroup cols="5" align="left" colsep="1" rowsep="1"><colspec colname="c1"/><colspec colname="c2"/><colspec colname="c3"/><colspec colname="c4"/><colspec colname="c5"/><thead><row><entry><emphasis>Name/Instantiating Type</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry></row></thead><tbody><!-- native --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c5">n_hash_map_ncah</entry></row><row><entry><classname>std::tr1::unordered_map</classname></entry><entry><classname>cache_hash_code</classname></entry><entry><constant>false</constant></entry><entry namest="c4" nameend="c5"></entry></row><!-- hash 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c5">cc_hash_mod_prime_1div1_nsth_map</entry></row><row><entry morerows="2" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mod_range_hashing</classname></entry><entry namest="c4" nameend="c5"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_prime_size_policy</classname></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/1</entry></row><!-- hash 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c5">cc_hash_mask_exp_1div1_nsth_map</entry></row><row><entry morerows="2" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mask_range_hashing</classname></entry><entry namest="c4" nameend="c5"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_exponential_size_policy</classname></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/1</entry></row><!-- hash 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c5">gp_hash_mod_quadp_prime_1div2_nsth_map</entry></row><row><entry morerows="3" valign="top"><classname>gp_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mod_range_hashing</classname></entry><entry namest="c4" nameend="c5"></entry></row><row><entry><classname>Probe_Fn</classname></entry><entry><classname>quadratic_probe_fn</classname></entry><entry namest="c4" nameend="c5"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_prime_size_policy</classname></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2</entry></row></tbody></tgroup></informaltable></section><section xml:id="hash.zlob_int_find.observations"><info><title>Observations</title></info><para>In this setting, the distribution of keys is so skewed thatthe underlying hash-table type affects performance marginally.(This is in contrast with Hash-Based Text<function>find</function> Find Timing Test, Hash-BasedInteger <function>find</function> Find Timing Test, Hash-BasedInteger Subscript Find Timing Test and Hash-BasedInteger Subscript Insert Timing Test.)</para><para>The range-hashing scheme affects performance dramatically. Amask-based range-hashing scheme effectively maps all valuesinto the same bucket. Access degenerates into a search withinan unordered linked-list. In the graphic above, it should be noted that<classname>std::tr1::unordered_map</classname> is hard-wired currently to mod-based and mask-based schemes,respectively.</para><para>When observing the settings of this test, it is apparentthat the keys' distribution is far from natural. One might askif the test is not contrived to show that, in some cases,mod-based range hashing does better than mask-based rangehashing. This is, in fact just the case. Amore natural case in which mod-based range hashing is better was not encountered.Thus the inescapable conclusion: real-life key distributions are handled betterwith an appropriate hash function and a mask-basedrange-hashing function. (<filename>pb_ds/example/hash_shift_mask.cc</filename>shows an example of handling this a-priori known skeweddistribution with a mask-based range-hashing function). If hashperformance is bad, a χ<superscript>2</superscript> test can be usedto check how to transform it into a more uniformdistribution.</para><para>For this reason, this library's default range-hashingfunction is mask-based.</para></section></section><!-- 06 <a href="hash_random_int_erase_mem_usage_test"> --><!-- 06 <a href="hash_random_int_erase_mem_usage_test"> --><section xml:id="performance.hash.erase_mem"><info><title>Erase Memory Use</title></info><para></para><section xml:id="hash.erase_mem.info"><info><title>Description</title></info><para>This test inserts a number of uniform integer keysinto a container, then erases all keys except one. It measuresthe final size of the container.</para><para>It uses the test file:<filename>performance/ext/pb_ds/hash_random_int_erase_mem_usage.cc</filename></para><para>The test checks how containers adjust internally as theirlogical size decreases.</para></section><section xml:id="hash.erase_mem.results"><info><title>Results</title></info><para>The graphic below show the results for the native, collision-chaining, and general-probing hash types.</para><!-- results graphic --><informalfigure><mediaobject><imageobject><imagedata align="center" format="PDF" scale="75"fileref="../images/pbds_hash_int_erase_mem.pdf"/></imageobject><imageobject><imagedata align="center" format="PNG" scale="100"fileref="../images/pbds_hash_int_erase_mem.png"/></imageobject></mediaobject></informalfigure><para>The abbreviated names in the legend of the graphic above areinstantiated with the types in the following table.</para><informaltable frame="all"><tgroup cols="5" align="left" colsep="1" rowsep="1"><colspec colname="c1"/><colspec colname="c2"/><colspec colname="c3"/><colspec colname="c4"/><colspec colname="c5"/><thead><row><entry><emphasis>Name/Instantiating Type</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry></row></thead><tbody><!-- native --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c5">n_hash_map_ncah</entry></row><row><entry><classname>std::tr1::unordered_map</classname></entry><entry><classname>cache_hash_code</classname></entry><entry><constant>false</constant></entry><entry namest="c4" nameend="c5"></entry></row><!-- hash 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c5">cc_hash_mod_prime_1div1_nsth_map</entry></row><row><entry morerows="2" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mod_range_hashing</classname></entry><entry namest="c4" nameend="c5"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_prime_size_policy</classname></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/1</entry></row><!-- hash 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c5">cc_hash_mask_exp_1div2_nsth_map</entry></row><row><entry morerows="2" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mask_range_hashing</classname></entry><entry namest="c4" nameend="c5"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_exponential_size_policy</classname></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2</entry></row><!-- hash 03 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c5">gp_hash_mask_linp_exp_1div2_nsth_set</entry></row><row><entry morerows="3" valign="top"><classname>gp_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mask_range_hashing</classname></entry><entry namest="c4" nameend="c5"></entry></row><row><entry><classname>Probe_Fn</classname></entry><entry><classname>linear_probe_fn</classname></entry><entry namest="c4" nameend="c5"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_exponential_size_policy</classname></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2</entry></row></tbody></tgroup></informaltable></section><section xml:id="hash.erase_mem.observations"><info><title>Observations</title></info><para>The standard's hash-based containers act very differently than trees inthis respect. When erasing numerous keys from an standardassociative-container, the resulting memory user varies greatlydepending on whether the container is tree-based or hash-based.This is a fundamental consequence of the standard's interface forassociative containers, and it is not due to a specificimplementation.</para></section></section></section><section xml:id="performance.branch"><info><title>Branch-Based</title></info><para></para><!-- 01 <a href="tree_text_insert_timing_test"> --><section xml:id="performance.branch.text_insert"><info><title>Text <function>insert</function></title></info><para></para><section xml:id="branch.text_insert.info"><info><title>Description</title></info><para>This test inserts a number of values with keys from an arbitrarytext ([ wickland96thirty ]) into a containerusing <function>insert</function> . It measures the average timefor <function>insert</function> as a function of the number ofvalues inserted.</para><para>The test checks the effect of different underlyingdata structures.</para><para>It uses the test file:<filename>performance/ext/pb_ds/tree_text_insert_timing.cc</filename></para></section><section xml:id="branch.text_insert.results"><info><title>Results</title></info><para>The three graphics below show the results for the nativetree and this library's node-based trees, the native tree andthis library's vector-based trees, and the native treeand this library's PATRICIA-trie, respectively.</para><para>The graphic immediately below shows the results for thenative tree type and several node-based tree types.</para><!-- results graphic --><informalfigure><mediaobject><imageobject><imagedata align="center" format="PDF" scale="75"fileref="../images/pbds_tree_text_insert_node.pdf"/></imageobject><imageobject><imagedata align="center" format="PNG" scale="100"fileref="../images/pbds_tree_text_insert_node.png"/></imageobject></mediaobject><para>The abbreviated names in the legend of the graphic above areinstantiated with the types in the following table.</para></informalfigure><informaltable frame="all"><tgroup cols="3" align="left" colsep="1" rowsep="1"><colspec colname="c1"/><colspec colname="c2"/><colspec colname="c3"/><thead><row><entry><emphasis>Name/Instantiating Type</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry></row></thead><tbody><!-- native --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">n_map</entry></row><row><entry><classname>std::map</classname></entry><entry namest="c2" nameend="c3"></entry></row><!-- branch 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">splay_tree_map</entry></row><row><entry morerows="1" valign="top"><classname>tree</classname></entry><entry><classname>Tag</classname></entry><entry><classname>splay_tree_tag</classname></entry></row><row><entry><classname>Node_update</classname></entry><entry><classname>null_node_update</classname></entry></row><!-- branch 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">rb_tree_map</entry></row><row><entry morerows="1" valign="top"><classname>tree</classname></entry><entry><classname>Tag</classname></entry><entry><classname>rb_tree_tag</classname></entry></row><row><entry><classname>Node_update</classname></entry><entry><classname>null_node_update</classname></entry></row></tbody></tgroup></informaltable><para>The graphic below shows the results for thenative tree type and a vector-based tree type.</para><!-- results graphic --><informalfigure><mediaobject><imageobject><imagedata align="center" format="PDF" scale="75"fileref="../images/pbds_tree_text_insert_vector.pdf"/></imageobject><imageobject><imagedata align="center" format="PNG" scale="100"fileref="../images/pbds_tree_text_insert_vector.png"/></imageobject></mediaobject></informalfigure><para>The abbreviated names in the legend of the graphic above areinstantiated with the types in the following table.</para><informaltable frame="all"><tgroup cols="3" align="left" colsep="1" rowsep="1"><colspec colname="c1"/><colspec colname="c2"/><colspec colname="c3"/><thead><row><entry><emphasis>Name/Instantiating Type</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry></row></thead><tbody><!-- native --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">n_map</entry></row><row><entry><classname>std::map</classname></entry><entry namest="c2" nameend="c3"></entry></row><!-- branch 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">ov_tree_map</entry></row><row><entry morerows="1" valign="top"><classname>tree</classname></entry><entry><classname>Tag</classname></entry><entry><classname>ov_tree_tag</classname></entry></row><row><entry><classname>Node_update</classname></entry><entry><classname>null_node_update</classname></entry></row></tbody></tgroup></informaltable><para>The graphic below shows the results for thenative tree type and a PATRICIA trie type.</para><!-- results graphic --><informalfigure><mediaobject><imageobject><imagedata align="center" format="PDF" scale="75"fileref="../images/pbds_tree_text_insert_trie.pdf"/></imageobject><imageobject><imagedata align="center" format="PNG" scale="100"fileref="../images/pbds_tree_text_insert_trie.png"/></imageobject></mediaobject></informalfigure><para>The abbreviated names in the legend of the graphic above areinstantiated with the types in the following table.</para><informaltable frame="all"><tgroup cols="3" align="left" colsep="1" rowsep="1"><colspec colname="c1"/><colspec colname="c2"/><colspec colname="c3"/><thead><row><entry><emphasis>Name/Instantiating Type</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry></row></thead><tbody><!-- native --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">n_map</entry></row><row><entry><classname>std::map</classname></entry><entry namest="c2" nameend="c3"></entry></row><!-- branch 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">pat_trie_map</entry></row><row><entry morerows="1" valign="top"><classname>tree</classname></entry><entry><classname>Tag</classname></entry><entry><classname>pat_trie_tag</classname></entry></row><row><entry><classname>Node_update</classname></entry><entry><classname>null_node_update</classname></entry></row></tbody></tgroup></informaltable></section><section xml:id="branch.text_insert.observations"><info><title>Observations</title></info><para>Observing the first graphic implies that for this setting, a splay tree(<classname>tree</classname> with <classname>Tag</classname> = <classname>splay_tree_tag</classname>) does not dowell. See also the Branch-BasedText <function>find</function> Find Timing Test. The twored-black trees perform better.</para><para>Observing the second graphic, an ordered-vector tree(<classname>tree</classname> with <classname>Tag</classname> = <classname>ov_tree_tag</classname>) performsabysmally. Inserting into this type of tree has linear complexity[ austern00noset].</para><para>Observing the third and last graphic, A PATRICIA trie(<classname>trie</classname> with <classname>Tag</classname> = <classname>pat_trie_tag</classname>) has abysmalperformance, as well. This is not that surprising, since alarge-fan-out PATRICIA trie works like a hash table withcollisions resolved by a sub-trie. Each time a collision isencountered, a new "hash-table" is built A large fan-out PATRICIAtrie, however, doe does well in look-ups (see Branch-BasedText <function>find</function> Find Timing Test). It may bebeneficial in semi-static settings.</para></section></section><!-- 02 <a href="tree_text_find_find_timing_test"> --><section xml:id="performance.branch.text_find"><info><title>Text <function>find</function></title></info><para></para><section xml:id="branch.text_find.info"><info><title>Description</title></info><para>This test inserts a number of values with keys from anarbitrary text ([wickland96thirty]) intoa container, then performs a series of finds using<function>find</function>. It measures the average timefor <function>find</function> as a function of the number ofvalues inserted.</para><para>It uses the test file:<filename>performance/ext/pb_ds/text_find_timing.cc</filename></para><para>The test checks the effect of different underlyingdata structures.</para></section><section xml:id="branch.text_find.results"><info><title>Results</title></info><para>The graphic immediately below shows the results for thenative tree type and several other tree types.</para><!-- results graphic --><informalfigure><mediaobject><imageobject><imagedata align="center" format="PDF" scale="75"fileref="../images/pbds_tree_text_find.pdf"/></imageobject><imageobject><imagedata align="center" format="PNG" scale="100"fileref="../images/pbds_tree_text_find.png"/></imageobject></mediaobject></informalfigure><para>The abbreviated names in the legend of the graphic above areinstantiated with the types in the following table.</para><informaltable frame="all"><tgroup cols="3" align="left" colsep="1" rowsep="1"><colspec colname="c1"/><colspec colname="c2"/><colspec colname="c3"/><thead><row><entry><emphasis>Name/Instantiating Type</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry></row></thead><tbody><!-- native --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">n_map</entry></row><row><entry><classname>std::map</classname></entry><entry namest="c2" nameend="c3"></entry></row><!-- branch 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">splay_tree_map</entry></row><row><entry morerows="1" valign="top"><classname>tree</classname></entry><entry><classname>Tag</classname></entry><entry><classname>splay_tree_tag</classname></entry></row><row><entry><classname>Node_Update</classname></entry><entry><classname>null_node_update</classname></entry></row><!-- branch 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">rb_tree_map</entry></row><row><entry morerows="1" valign="top"><classname>tree</classname></entry><entry><classname>Tag</classname></entry><entry><classname>rb_tree_tag</classname></entry></row><row><entry><classname>Node_Update</classname></entry><entry><classname>null_node_update</classname></entry></row><!-- branch 03 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">ov_tree_map</entry></row><row><entry morerows="1" valign="top"><classname>tree</classname></entry><entry><classname>Tag</classname></entry><entry><classname>ov_tree_tag</classname></entry></row><row><entry><classname>Node_Update</classname></entry><entry><classname>null_node_update</classname></entry></row><!-- branch 05 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">pat_trie_map</entry></row><row><entry morerows="1" valign="top"><classname>tree</classname></entry><entry><classname>Tag</classname></entry><entry><classname>pat_trie_tag</classname></entry></row><row><entry><classname>Node_Update</classname></entry><entry><classname>null_node_update</classname></entry></row></tbody></tgroup></informaltable></section><section xml:id="branch.text_find.observations"><info><title>Observations</title></info><para>For this setting, a splay tree (<classname>tree</classname>with <classname>Tag</classname> = <classname>splay_tree_tag</classname>) does not dowell. This is possibly due to two reasons:</para><orderedlist><listitem><para>A splay tree is not guaranteed to be balanced [motwani95random]. If asplay tree contains n nodes, its average root-leafpath can be m >> log(n).</para></listitem><listitem><para>Assume a specific root-leaf search path has lengthm, and the search-target node has distance m'from the root. A red-black tree will require m + 1comparisons to find the required node; a splay tree willrequire 2 m' comparisons. A splay tree, consequently,can perform many more comparisons than a red-black tree.</para></listitem></orderedlist><para>An ordered-vector tree (<classname>tree</classname>with <classname>Tag</classname> = <classname>ov_tree_tag</classname>), a red-blacktree (<classname>tree</classname>with <classname>Tag</classname> = <classname>rb_tree_tag</classname>), and thenative red-black tree all share approximately the sameperformance.</para><para>An ordered-vector tree is slightly slower than red-blacktrees, since it requires, in order to find a key, more mathoperations than they do. Conversely, an ordered-vector treerequires far lower space than the others. ([austern00noset], however,seems to have an implementation that is also faster than ared-black tree).</para><para>A PATRICIA trie (<classname>trie</classname>with <classname>Tag</classname> = <classname>pat_trie_tag</classname>) has goodlook-up performance, due to its large fan-out in this case. Inthis setting, a PATRICIA trie has look-up performance comparableto a hash table (see Hash-Based Text<classname>find</classname> Timing Test), but it is orderpreserving. This is not that surprising, since a large-fan-outPATRICIA trie works like a hash table with collisions resolvedby a sub-trie. A large-fan-out PATRICIA trie does not do well onmodifications (see Tree-Based and Trie-BasedText Insert Timing Test). Therefore, it is possibly beneficial insemi-static settings.</para></section></section><!-- 03 <a href="tree_text_lor_find_find_timing_test"> --><section xml:id="performance.branch.text_lor_find"><info><title>Text <function>find</function> with Locality-of-Reference</title></info><para></para><section xml:id="branch.text_lor_find.info"><info><title>Description</title></info><para>This test inserts a number of values with keys from anarbitrary text ([ wickland96thirty ]) intoa container, then performs a series of finds using<function>find</function>. It is different than Tree-Based andTrie-Based Text <function>find</function> Find Timing Test in thesequence of finds it performs: this test performs multiple<function>find</function>s on the same key before moving on to the nextkey. It measures the average time for <function>find</function> as afunction of the number of values inserted.</para><para>It uses the test file:<filename>performance/ext/pb_ds/tree_text_lor_find_timing.cc</filename></para><para>The test checks the effect of different underlyingdata structures in a locality-of-reference setting.</para></section><section xml:id="branch.text_lor_find.results"><info><title>Results</title></info><para>The graphic immediately below shows the results for thenative tree type and several other tree types.</para><!-- results graphic --><informalfigure><mediaobject><imageobject><imagedata align="center" format="PDF" scale="75"fileref="../images/pbds_tree_text_lor_find.pdf"/></imageobject><imageobject><imagedata align="center" format="PNG" scale="100"fileref="../images/pbds_tree_text_lor_find.png"/></imageobject></mediaobject></informalfigure><para>The abbreviated names in the legend of the graphic above areinstantiated with the types in the following table.</para><informaltable frame="all"><tgroup cols="3" align="left" colsep="1" rowsep="1"><colspec colname="c1"/><colspec colname="c2"/><colspec colname="c3"/><thead><row><entry><emphasis>Name/Instantiating Type</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry></row></thead><tbody><!-- native --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">n_map</entry></row><row><entry><classname>std::map</classname></entry><entry namest="c2" nameend="c3"></entry></row><!-- branch 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">splay_tree_map</entry></row><row><entry morerows="1" valign="top"><classname>tree</classname></entry><entry><classname>Tag</classname></entry><entry><classname>splay_tree_tag</classname></entry></row><row><entry><classname>Node_Update</classname></entry><entry><classname>null_node_update</classname></entry></row><!-- branch 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">rb_tree_map</entry></row><row><entry morerows="1" valign="top"><classname>tree</classname></entry><entry><classname>Tag</classname></entry><entry><classname>rb_tree_tag</classname></entry></row><row><entry><classname>Node_Update</classname></entry><entry><classname>null_node_update</classname></entry></row><!-- branch 03 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">ov_tree_map</entry></row><row><entry morerows="1" valign="top"><classname>tree</classname></entry><entry><classname>Tag</classname></entry><entry><classname>ov_tree_tag</classname></entry></row><row><entry><classname>Node_Update</classname></entry><entry><classname>null_node_update</classname></entry></row><!-- branch 05 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">pat_trie_map</entry></row><row><entry morerows="1" valign="top"><classname>tree</classname></entry><entry><classname>Tag</classname></entry><entry><classname>pat_trie_tag</classname></entry></row><row><entry><classname>Node_Update</classname></entry><entry><classname>null_node_update</classname></entry></row></tbody></tgroup></informaltable></section><section xml:id="branch.text_lor_find.observations"><info><title>Observations</title></info><para>For this setting, an ordered-vector tree(<classname>tree</classname> with <classname>Tag</classname>= <classname>ov_tree_tag</classname>), a red-black tree(<classname>tree</classname> with <classname>Tag</classname>= <classname>rb_tree_tag</classname>), and the native red-blacktree all share approximately the same performance.</para><para>A splay tree (<classname>tree</classname>with <classname>Tag</classname> = <classname>splay_tree_tag</classname>) doesmuch better, since each (successful) find "bubbles" thecorresponding node to the root of the tree.</para></section></section><!-- 04 <a href="tree_split_join_timing_test"> --><section xml:id="performance.branch.split_join"><info><title><function>split</function> and <function>join</function></title></info><para></para><section xml:id="branch.split_join.info"><info><title>Description</title></info><para>This test a container, inserts into a number of values, splitsthe container at the median, and joins the two containers. (If thecontainers are one of this library's trees,it splits and joins with the <function>split</function> and<function>join</function> method; otherwise, it uses the <function>erase</function> and<function>insert</function> methods.) It measures the time for splittingand joining the containers as a function of the number ofvalues inserted.</para><para>It uses the test file:<filename>performance/ext/pb_ds/tree_split_join_timing.cc</filename></para><para>The test checks the performance difference of <function>join</function>as opposed to a sequence of <function>insert</function> operations; byimplication, this test checks the most efficient way to erase asub-sequence from a tree-like-based container, since this canalways be performed by a small sequence of splits and joins.</para></section><section xml:id="branch.split_join.results"><info><title>Results</title></info><para>The graphic immediately below shows the results for thenative tree type and several other tree types.</para><!-- results graphic --><informalfigure><mediaobject><imageobject><imagedata align="center" format="PDF" scale="75"fileref="../images/pbds_tree_split_join.pdf"/></imageobject><imageobject><imagedata align="center" format="PNG" scale="100"fileref="../images/pbds_tree_split_join.png"/></imageobject></mediaobject></informalfigure><para>The abbreviated names in the legend of the graphic above areinstantiated with the types in the following table.</para><informaltable frame="all"><tgroup cols="3" align="left" colsep="1" rowsep="1"><colspec colname="c1"/><colspec colname="c2"/><colspec colname="c3"/><thead><row><entry><emphasis>Name/Instantiating Type</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry></row></thead><tbody><!-- native --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">n_set</entry></row><row><entry><classname>std::set</classname></entry><entry namest="c2" nameend="c3"></entry></row><!-- branch 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">splay_tree_set</entry></row><row><entry morerows="1" valign="top"><classname>tree</classname></entry><entry><classname>Tag</classname></entry><entry><classname>splay_tree_tag</classname></entry></row><row><entry><classname>Node_Update</classname></entry><entry><classname>null_node_update</classname></entry></row><!-- branch 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">rb_tree_set</entry></row><row><entry morerows="1" valign="top"><classname>tree</classname></entry><entry><classname>Tag</classname></entry><entry><classname>rb_tree_tag</classname></entry></row><row><entry><classname>Node_Update</classname></entry><entry><classname>null_node_update</classname></entry></row><!-- branch 03 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">ov_tree_set</entry></row><row><entry morerows="1" valign="top"><classname>tree</classname></entry><entry><classname>Tag</classname></entry><entry><classname>ov_tree_tag</classname></entry></row><row><entry><classname>Node_Update</classname></entry><entry><classname>null_node_update</classname></entry></row><!-- branch 05 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">pat_trie_map</entry></row><row><entry morerows="1" valign="top"><classname>tree</classname></entry><entry><classname>Tag</classname></entry><entry><classname>pat_trie_tag</classname></entry></row><row><entry><classname>Node_Update</classname></entry><entry><classname>null_node_update</classname></entry></row></tbody></tgroup></informaltable></section><section xml:id="branch.split_join.observations"><info><title>Observations</title></info><para>In this test, the native red-black trees must be split andjoined externally, through a sequence of <function>erase</function> and<function>insert</function> operations. This is clearlysuper-linear, and it is not that surprising that the cost ishigh.</para><para>This library's tree-based containers use in this test the<function>split</function> and <function>join</function> methods,which have lower complexity: the <function>join</function> methodof a splay tree (<classname>tree</classname>with <classname>Tag </classname>= <classname>splay_tree_tag</classname>) is quadratic in thelength of the longest root-leaf path, and linear in the totalnumber of elements; the <function>join</function> method of ared-black tree (<classname>tree</classname>with <classname>Tag </classname>= <classname>rb_tree_tag</classname>) or an ordered-vector tree(<classname>tree</classname> with <classname>Tag </classname>= <classname>ov_tree_tag</classname>) is linear in the number ofelements.</para><para>Asides from orders of growth, this library's trees access theirallocator very little in these operations, and some of them do notaccess it at all. This leads to lower constants in theircomplexity, and, for some containers, to exception-free splits andjoins (which can be determinedvia <classname>container_traits</classname>).</para><para>It is important to note that <function>split</function> and<function>join</function> are not esoteric methods - they are the mostefficient means of erasing a contiguous range of values from atree based container.</para></section></section><!-- 05 <a href="tree_order_statistics_timing_test"> --><section xml:id="performance.branch.order_statistics"><info><title>Order-Statistics</title></info><para></para><section xml:id="branch.order_statistics.info"><info><title>Description</title></info><para>This test creates a container, inserts random integers into thethe container, and then checks the order-statistics of thecontainer's values. (If the container is one of thislibrary's trees, it does this withthe <function>order_of_key</function> method of<classname>tree_order_statistics_node_update</classname>; otherwise, it uses the <function>find</function> method and<function>std::distance</function>.) It measures the averagetime for such queries as a function of the number of valuesinserted.</para><para>It uses the test file:<filename>performance/ext/pb_ds/tree_order_statistics_timing.cc</filename></para><para>The test checks the performance difference of policies basedon node-invariant as opposed to a external functions.</para></section><section xml:id="branch.order_statistics.results"><info><title>Results</title></info><para>The graphic immediately below shows the results for thenative tree type and several other tree types.</para><!-- results graphic --><informalfigure><mediaobject><imageobject><imagedata align="center" format="PDF" scale="75"fileref="../images/pbds_tree_order_statistics.pdf"/></imageobject><imageobject><imagedata align="center" format="PNG" scale="100"fileref="../images/pbds_tree_order_statistics.png"/></imageobject></mediaobject></informalfigure><para>The abbreviated names in the legend of the graphic above areinstantiated with the types in the following table.</para><informaltable frame="all"><tgroup cols="3" align="left" colsep="1" rowsep="1"><colspec colname="c1"/><colspec colname="c2"/><colspec colname="c3"/><thead><row><entry><emphasis>Name/Instantiating Type</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry></row></thead><tbody><!-- native --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">n_set</entry></row><row><entry><classname>std::set</classname></entry><entry namest="c2" nameend="c3"></entry></row><!-- branch 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">splay_tree_ost_set</entry></row><row><entry morerows="1" valign="top"><classname>tree</classname></entry><entry><classname>Tag</classname></entry><entry><classname>splay_tree_tag</classname></entry></row><row><entry><classname>Node_Update</classname></entry><entry><classname>tree_order_statistics_node_update</classname></entry></row><!-- branch 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">rb_tree_ost_set</entry></row><row><entry morerows="1" valign="top"><classname>tree</classname></entry><entry><classname>Tag</classname></entry><entry><classname>rb_tree_tag</classname></entry></row><row><entry><classname>Node_Update</classname></entry><entry><classname>tree_order_statistics_node_update</classname></entry></row></tbody></tgroup></informaltable></section><section xml:id="branch.order_statistics.observations"><info><title>Observations</title></info><para>In this test, the native red-black tree can supportorder-statistics queries only externally, by performing a<classname>find</classname> (alternatively, <classname>lower_bound</classname> or<classname>upper_bound</classname> ) and then using <classname>std::distance</classname> .This is clearly linear, and it is not that surprising that thecost is high.</para><para>This library's tree-based containers use in this test the<classname>order_of_key</classname> method of <classname>tree_order_statistics_node_update</classname>.This method has only linear complexity in the length of theroot-node path. Unfortunately, the average path of a splay tree(<classname>tree</classname>with <classname>Tag =</classname> <classname>splay_tree_tag</classname> ) canbe higher than logarithmic; the longest path of a red-blacktree (<classname>tree</classname>with <classname>Tag =</classname> <classname>rb_tree_tag</classname> ) islogarithmic in the number of elements. Consequently, the splaytree has worse performance than the red-black tree.</para></section></section></section> <!-- branch --><section xml:id="performance.multimap"><info><title>Multimap</title></info><para></para><!-- 01 <a href="multimap_text_find_timing_test_small"> --><section xml:id="performance.multimap.text_find_small"><info><title>Text <function>find</function> with Small Secondary-to-Primary Key Ratios</title></info><para></para><section xml:id="multimap.text_find_small.info"><info><title>Description</title></info><para>This test inserts a number of pairs into a container. Thefirst item of each pair is a string from an arbitrary text[wickland96thirty], andthe second is a uniform i.i.d.integer. The container is a"multimap" - it considers the first member of each pair as aprimary key, and the second member of each pair as a secondarykey (see Motivation::AssociativeContainers::Alternative to Multiple Equivalent Keys). Thereare 400 distinct primary keys, and the ratio of secondary keysto primary keys ranges from 1 to 5.</para><para>The test measures the average find-time as a function of thenumber of values inserted. For this library's containers, itfinds the secondary key from a container obtained from findinga primary key. For the native multimaps, it searches a rangeobtained using <classname>std::equal_range</classname> on a primary key.</para><para>It uses the test file:<filename>performance/ext/pb_ds/multimap_text_find_timing_small.cc</filename></para><para>The test checks the find-time scalability of different"multimap" designs.</para></section><section xml:id="multimap.text_find_small.results"><info><title>Results</title></info><para>The graphic below show the results for "multimaps" whichuse a tree-based container for primary keys.</para><!-- results graphic --><informalfigure><mediaobject><imageobject><imagedata align="center" format="PNG" scale="100"fileref="../images/pbds_multimap_text_find_small_s2p_tree.png"/></imageobject><imageobject><imagedata align="center" format="PDF" scale="33"fileref="../images/pbds_multimap_text_find_small_s2p_tree.pdf"/></imageobject></mediaobject></informalfigure><para>The abbreviated names in the legend of the graphic above areinstantiated with the types in the following table.</para><informaltable frame="all"><tgroup cols="7" align="left" colsep="1" rowsep="1"><colspec colname="c1"/><colspec colname="c2"/><colspec colname="c3"/><colspec colname="c4"/><colspec colname="c5"/><colspec colname="c6"/><colspec colname="c7"/><thead><row><entry><emphasis>Name/Instantiating Type</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry></row></thead><tbody><!-- native --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c7">n_mmap</entry></row><row><entry><classname>std::multimap</classname></entry><entry namest="c2" nameend="c7"></entry></row><!-- multimap 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c7">rb_tree_mmap_lu_mtf_set</entry></row><row><entry morerows="2" valign="top"><classname>tree</classname></entry><entry><classname>Tag</classname></entry><entry><classname>rb_tree_tag</classname></entry><entry namest="c4" nameend="c7"></entry></row><row><entry><classname>Node_Update</classname></entry><entry><classname>null_node_update</classname></entry><entry namest="c4" nameend="c7"></entry></row><row><entry><classname>Mapped</classname></entry><entry><classname>list_update</classname></entry><entry><classname>Update_Policy</classname></entry><entry><classname>lu_move_to_front_policy</classname></entry><entry namest="c6" nameend="c7"></entry></row><!-- multimap 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c7">rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set</entry></row><row><entry morerows="4" valign="top"><classname>tree</classname></entry><entry><classname>Tag</classname></entry><entry><classname>rb_tree_tag</classname></entry><entry namest="c4" nameend="c7"></entry></row><row><entry><classname>Node_Update</classname></entry><entry><classname>null_node_update</classname></entry><entry namest="c4" nameend="c7"></entry></row><row><entry morerows="2" valign="top"><classname>Mapped</classname></entry><entry morerows="2" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mask_range_hashing</classname></entry><entry namest="c6" nameend="c7"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_exponential_size_policy</classname></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2</entry></row></tbody></tgroup></informaltable><para>The graphic below show the results for "multimaps" whichuse a hash-based container for primary keys.</para><!-- results graphic --><informalfigure><mediaobject><imageobject><imagedata align="center" format="PNG" scale="100"fileref="../images/pbds_multimap_text_find_small_s2p_hash.png"/></imageobject><imageobject><imagedata align="center" format="PDF" scale="33"fileref="../images/pbds_multimap_text_find_small_s2p_hash.pdf"/></imageobject></mediaobject></informalfigure><para>The abbreviated names in the legend of the graphic above areinstantiated with the types in the following table.</para><informaltable frame="all"><tgroup cols="7" align="left" colsep="1" rowsep="1"><colspec colname="c1"/><colspec colname="c2"/><colspec colname="c3"/><colspec colname="c4"/><colspec colname="c5"/><colspec colname="c6"/><colspec colname="c7"/><thead><row><entry><emphasis>Name/Instantiating Type</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry></row></thead><tbody><!-- native --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c7">n_hash_mmap</entry></row><row><entry><classname>std::tr1::unordered_multimap</classname></entry><entry namest="c2" nameend="c7"></entry></row><!-- multimap 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c7">rb_tree_mmap_lu_mtf_set</entry></row><row><entry morerows="3" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mask_range_hashing</classname></entry><entry namest="c4" nameend="c7"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_exponential_size_policy</classname></entry><entry namest="c6" nameend="c7"></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2</entry><entry namest="c6" nameend="c7"></entry></row><row><entry><classname>Mapped</classname></entry><entry><classname>list_update</classname></entry><entry><classname>Update_Policy</classname></entry><entry><classname>lu_move_to_front_policy</classname></entry><entry namest="c6" nameend="c7"></entry></row><!-- multimap 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c7">rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set</entry></row><row><entry morerows="5" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mask_range_hashing</classname></entry><entry namest="c4" nameend="c7"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_exponential_size_policy</classname></entry><entry namest="c6" nameend="c7"></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2</entry><entry namest="c6" nameend="c7"></entry></row><row><entry morerows="2" valign="top"><classname>Mapped</classname></entry><entry morerows="2" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mask_range_hashing</classname></entry><entry namest="c6" nameend="c7"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_exponential_size_policy</classname></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2</entry></row></tbody></tgroup></informaltable></section><section xml:id="multimap.text_find_small.observations"><info><title>Observations</title></info><para>See Observations::Mapping-SemanticsConsiderations.</para></section></section><!-- 02 <a href="multimap_text_find_timing_test_large"> --><section xml:id="performance.multimap.text_find_large"><info><title>Text <function>find</function> with Large Secondary-to-Primary Key Ratios</title></info><para></para><section xml:id="multimap.text_find_large.info"><info><title>Description</title></info><para>This test inserts a number of pairs into a container. Thefirst item of each pair is a string from an arbitrary text[wickland96thirty], andthe second is a uniform integer. The container is a"multimap" - it considers the first member of each pair as aprimary key, and the second member of each pair as a secondarykey. Thereare 400 distinct primary keys, and the ratio of secondary keysto primary keys ranges from 1 to 5.</para><para>The test measures the average find-time as a function of thenumber of values inserted. For this library's containers, itfinds the secondary key from a container obtained from findinga primary key. For the native multimaps, it searches a rangeobtained using <classname>std::equal_range</classname> on a primary key.</para><para>It uses the test file:<filename>performance/ext/pb_ds/multimap_text_find_timing_large.cc</filename></para><para>The test checks the find-time scalability of different"multimap" designs.</para></section><section xml:id="multimap.text_find_large.results"><info><title>Results</title></info><para>The graphic below show the results for "multimaps" whichuse a tree-based container for primary keys.</para><!-- results graphic --><informalfigure><mediaobject><imageobject><imagedata align="center" format="PNG" scale="100"fileref="../images/pbds_multimap_text_find_large_s2p_tree.png"/></imageobject><imageobject><imagedata align="center" format="PDF" scale="33"fileref="../images/pbds_multimap_text_find_large_s2p_tree.pdf"/></imageobject></mediaobject></informalfigure><para>The abbreviated names in the legend of the graphic above areinstantiated with the types in the following table.</para><informaltable frame="all"><tgroup cols="7" align="left" colsep="1" rowsep="1"><colspec colname="c1"/><colspec colname="c2"/><colspec colname="c3"/><colspec colname="c4"/><colspec colname="c5"/><colspec colname="c6"/><colspec colname="c7"/><thead><row><entry><emphasis>Name/Instantiating Type</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry></row></thead><tbody><!-- native --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c7">n_mmap</entry></row><row><entry><classname>std::multimap</classname></entry><entry namest="c2" nameend="c7"></entry></row><!-- multimap 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c7">rb_tree_mmap_lu_mtf_set</entry></row><row><entry morerows="2" valign="top"><classname>tree</classname></entry><entry><classname>Tag</classname></entry><entry><classname>rb_tree_tag</classname></entry><entry namest="c4" nameend="c7"></entry></row><row><entry><classname>Node_Update</classname></entry><entry><classname>null_node_update</classname></entry><entry namest="c4" nameend="c7"></entry></row><row><entry><classname>Mapped</classname></entry><entry><classname>list_update</classname></entry><entry><classname>Update_Policy</classname></entry><entry><classname>lu_move_to_front_policy</classname></entry><entry namest="c6" nameend="c7"></entry></row><!-- multimap 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c7">rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set</entry></row><row><entry morerows="4" valign="top"><classname>tree</classname></entry><entry><classname>Tag</classname></entry><entry><classname>rb_tree_tag</classname></entry><entry namest="c4" nameend="c7"></entry></row><row><entry><classname>Node_Update</classname></entry><entry><classname>null_node_update</classname></entry><entry namest="c4" nameend="c7"></entry></row><row><entry morerows="2" valign="top"><classname>Mapped</classname></entry><entry morerows="2" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mask_range_hashing</classname></entry><entry namest="c6" nameend="c7"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_exponential_size_policy</classname></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2</entry></row></tbody></tgroup></informaltable><para>The graphic below show the results for "multimaps" whichuse a hash-based container for primary keys.</para><!-- results graphic --><informalfigure><mediaobject><imageobject><imagedata align="center" format="PNG" scale="100"fileref="../images/pbds_multimap_text_find_large_s2p_hash.png"/></imageobject><imageobject><imagedata align="center" format="PDF" scale="33"fileref="../images/pbds_multimap_text_find_large_s2p_hash.pdf"/></imageobject></mediaobject></informalfigure><para>The abbreviated names in the legend of the graphic above areinstantiated with the types in the following table.</para><informaltable frame="all"><tgroup cols="7" align="left" colsep="1" rowsep="1"><colspec colname="c1"/><colspec colname="c2"/><colspec colname="c3"/><colspec colname="c4"/><colspec colname="c5"/><colspec colname="c6"/><colspec colname="c7"/><thead><row><entry><emphasis>Name/Instantiating Type</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry></row></thead><tbody><!-- native --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c7">n_hash_mmap</entry></row><row><entry><classname>std::tr1::unordered_multimap</classname></entry><entry namest="c2" nameend="c7"></entry></row><!-- multimap 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c7">rb_tree_mmap_lu_mtf_set</entry></row><row><entry morerows="3" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mask_range_hashing</classname></entry><entry namest="c4" nameend="c7"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_exponential_size_policy</classname></entry><entry namest="c6" nameend="c7"></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2</entry><entry namest="c6" nameend="c7"></entry></row><row><entry><classname>Mapped</classname></entry><entry><classname>list_update</classname></entry><entry><classname>Update_Policy</classname></entry><entry><classname>lu_move_to_front_policy</classname></entry><entry namest="c6" nameend="c7"></entry></row><!-- multimap 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c7">rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set</entry></row><row><entry morerows="5" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mask_range_hashing</classname></entry><entry namest="c4" nameend="c7"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_exponential_size_policy</classname></entry><entry namest="c6" nameend="c7"></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2</entry><entry namest="c6" nameend="c7"></entry></row><row><entry morerows="2" valign="top"><classname>Mapped</classname></entry><entry morerows="2" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mask_range_hashing</classname></entry><entry namest="c6" nameend="c7"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_exponential_size_policy</classname></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2</entry></row></tbody></tgroup></informaltable></section><section xml:id="multimap.text_find_large.observations"><info><title>Observations</title></info><para>See Observations::Mapping-SemanticsConsiderations.</para></section></section><!-- 03 <a href="multimap_text_insert_timing_test_small"> --><section xml:id="performance.multimap.text_insert_small"><info><title>Text <function>insert</function> with SmallSecondary-to-Primary Key Ratios</title></info><para></para><section xml:id="multimap.text_insert_small.info"><info><title>Description</title></info><para>This test inserts a number of pairs into a container. Thefirst item of each pair is a string from an arbitrary text[wickland96thirty], andthe second is a uniform integer. The container is a"multimap" - it considers the first member of each pair as aprimary key, and the second member of each pair as a secondarykey. Thereare 400 distinct primary keys, and the ratio of secondary keysto primary keys ranges from 1 to 5.</para><para>The test measures the average insert-time as a function ofthe number of values inserted. For this library's containers,it inserts a primary key into the primary associativecontainer, then a secondary key into the secondary associativecontainer. For the native multimaps, it obtains a range using<classname>std::equal_range</classname>, and inserts a value only if it wasnot contained already.</para><para>It uses the test file:<filename>performance/ext/pb_ds/multimap_text_insert_timing_small.cc</filename></para><para>The test checks the insert-time scalability of different"multimap" designs.</para></section><section xml:id="multimap.text_insert_small.results"><info><title>Results</title></info><para>The graphic below show the results for "multimaps" whichuse a tree-based container for primary keys.</para><!-- results graphic --><informalfigure><mediaobject><imageobject><imagedata align="center" format="PNG" scale="100"fileref="../images/pbds_multimap_text_insert_small_s2p_tree.png"/></imageobject><imageobject><imagedata align="center" format="PDF" scale="33"fileref="../images/pbds_multimap_text_insert_small_s2p_tree.pdf"/></imageobject></mediaobject></informalfigure><para>The abbreviated names in the legend of the graphic above areinstantiated with the types in the following table.</para><informaltable frame="all"><tgroup cols="7" align="left" colsep="1" rowsep="1"><colspec colname="c1"/><colspec colname="c2"/><colspec colname="c3"/><colspec colname="c4"/><colspec colname="c5"/><colspec colname="c6"/><colspec colname="c7"/><thead><row><entry><emphasis>Name/Instantiating Type</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry></row></thead><tbody><!-- native --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c7">n_mmap</entry></row><row><entry><classname>std::multimap</classname></entry><entry namest="c2" nameend="c7"></entry></row><!-- multimap 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c7">rb_tree_mmap_lu_mtf_set</entry></row><row><entry morerows="2" valign="top"><classname>tree</classname></entry><entry><classname>Tag</classname></entry><entry><classname>rb_tree_tag</classname></entry><entry namest="c4" nameend="c7"></entry></row><row><entry><classname>Node_Update</classname></entry><entry><classname>null_node_update</classname></entry><entry namest="c4" nameend="c7"></entry></row><row><entry><classname>Mapped</classname></entry><entry><classname>list_update</classname></entry><entry><classname>Update_Policy</classname></entry><entry><classname>lu_move_to_front_policy</classname></entry><entry namest="c6" nameend="c7"></entry></row><!-- multimap 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c7">rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set</entry></row><row><entry morerows="4" valign="top"><classname>tree</classname></entry><entry><classname>Tag</classname></entry><entry><classname>rb_tree_tag</classname></entry><entry namest="c4" nameend="c7"></entry></row><row><entry><classname>Node_Update</classname></entry><entry><classname>null_node_update</classname></entry><entry namest="c4" nameend="c7"></entry></row><row><entry morerows="2" valign="top"><classname>Mapped</classname></entry><entry morerows="2" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mask_range_hashing</classname></entry><entry namest="c6" nameend="c7"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_exponential_size_policy</classname></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2</entry></row></tbody></tgroup></informaltable><para>The graphic below show the results for "multimaps" whichuse a hash-based container for primary keys.</para><!-- results graphic --><informalfigure><mediaobject><imageobject><imagedata align="center" format="PNG" scale="100"fileref="../images/pbds_multimap_text_find_small_s2p_hash.png"/></imageobject><imageobject><imagedata align="center" format="PDF" scale="33"fileref="../images/pbds_multimap_text_find_small_s2p_hash.pdf"/></imageobject></mediaobject></informalfigure><para>The abbreviated names in the legend of the graphic above areinstantiated with the types in the following table.</para><informaltable frame="all"><tgroup cols="7" align="left" colsep="1" rowsep="1"><colspec colname="c1"/><colspec colname="c2"/><colspec colname="c3"/><colspec colname="c4"/><colspec colname="c5"/><colspec colname="c6"/><colspec colname="c7"/><thead><row><entry><emphasis>Name/Instantiating Type</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry></row></thead><tbody><!-- native --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c7">n_hash_mmap</entry></row><row><entry><classname>std::tr1::unordered_multimap</classname></entry><entry namest="c2" nameend="c7"></entry></row><!-- multimap 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c7">rb_tree_mmap_lu_mtf_set</entry></row><row><entry morerows="3" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mask_range_hashing</classname></entry><entry namest="c4" nameend="c7"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_exponential_size_policy</classname></entry><entry namest="c6" nameend="c7"></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2</entry><entry namest="c6" nameend="c7"></entry></row><row><entry><classname>Mapped</classname></entry><entry><classname>list_update</classname></entry><entry><classname>Update_Policy</classname></entry><entry><classname>lu_move_to_front_policy</classname></entry><entry namest="c6" nameend="c7"></entry></row><!-- multimap 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c7">rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set</entry></row><row><entry morerows="5" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mask_range_hashing</classname></entry><entry namest="c4" nameend="c7"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_exponential_size_policy</classname></entry><entry namest="c6" nameend="c7"></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2</entry><entry namest="c6" nameend="c7"></entry></row><row><entry morerows="2" valign="top"><classname>Mapped</classname></entry><entry morerows="2" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mask_range_hashing</classname></entry><entry namest="c6" nameend="c7"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_exponential_size_policy</classname></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2</entry></row></tbody></tgroup></informaltable></section><section xml:id="multimap.text_insert_small.observations"><info><title>Observations</title></info><para>See Observations::Mapping-SemanticsConsiderations.</para></section></section><!-- 04 <a href="multimap_text_insert_timing_test_large"> --><section xml:id="performance.multimap.text_insert_large"><info><title>Text <function>insert</function> with SmallSecondary-to-Primary Key Ratios</title></info><para></para><section xml:id="multimap.text_insert_large.info"><info><title>Description</title></info><para>This test inserts a number of pairs into a container. Thefirst item of each pair is a string from an arbitrary text[wickland96thirty], andthe second is a uniform integer. The container is a"multimap" - it considers the first member of each pair as aprimary key, and the second member of each pair as a secondarykey. Thereare 400 distinct primary keys, and the ratio of secondary keysto primary keys ranges from 1 to 5.</para><para>The test measures the average insert-time as a function ofthe number of values inserted. For this library's containers,it inserts a primary key into the primary associativecontainer, then a secondary key into the secondary associativecontainer. For the native multimaps, it obtains a range using<classname>std::equal_range</classname>, and inserts a value only if it wasnot contained already.</para><para>It uses the test file:<filename>performance/ext/pb_ds/multimap_text_insert_timing_large.cc</filename></para><para>The test checks the insert-time scalability of different"multimap" designs.</para></section><section xml:id="multimap.text_insert_large.results"><info><title>Results</title></info><para>The graphic below show the results for "multimaps" whichuse a tree-based container for primary keys.</para><!-- results graphic --><informalfigure><mediaobject><imageobject><imagedata align="center" format="PNG" scale="100"fileref="../images/pbds_multimap_text_insert_large_s2p_tree.png"/></imageobject><imageobject><imagedata align="center" format="PDF" scale="33"fileref="../images/pbds_multimap_text_insert_large_s2p_tree.pdf"/></imageobject></mediaobject></informalfigure><para>The abbreviated names in the legend of the graphic above areinstantiated with the types in the following table.</para><informaltable frame="all"><tgroup cols="7" align="left" colsep="1" rowsep="1"><colspec colname="c1"/><colspec colname="c2"/><colspec colname="c3"/><colspec colname="c4"/><colspec colname="c5"/><colspec colname="c6"/><colspec colname="c7"/><thead><row><entry><emphasis>Name/Instantiating Type</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry></row></thead><tbody><!-- native --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c7">n_mmap</entry></row><row><entry><classname>std::multimap</classname></entry><entry namest="c2" nameend="c7"></entry></row><!-- multimap 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c7">rb_tree_mmap_lu_mtf_set</entry></row><row><entry morerows="2" valign="top"><classname>tree</classname></entry><entry><classname>Tag</classname></entry><entry><classname>rb_tree_tag</classname></entry><entry namest="c4" nameend="c7"></entry></row><row><entry><classname>Node_Update</classname></entry><entry><classname>null_node_update</classname></entry><entry namest="c4" nameend="c7"></entry></row><row><entry><classname>Mapped</classname></entry><entry><classname>list_update</classname></entry><entry><classname>Update_Policy</classname></entry><entry><classname>lu_move_to_front_policy</classname></entry><entry namest="c6" nameend="c7"></entry></row><!-- multimap 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c7">rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set</entry></row><row><entry morerows="4" valign="top"><classname>tree</classname></entry><entry><classname>Tag</classname></entry><entry><classname>rb_tree_tag</classname></entry><entry namest="c4" nameend="c7"></entry></row><row><entry><classname>Node_Update</classname></entry><entry><classname>null_node_update</classname></entry><entry namest="c4" nameend="c7"></entry></row><row><entry morerows="2" valign="top"><classname>Mapped</classname></entry><entry morerows="2" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mask_range_hashing</classname></entry><entry namest="c6" nameend="c7"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_exponential_size_policy</classname></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2</entry></row></tbody></tgroup></informaltable><para>The graphic below show the results for "multimaps" whichuse a hash-based container for primary keys.</para><!-- results graphic --><informalfigure><mediaobject><imageobject><imagedata align="center" format="PNG" scale="100"fileref="../images/pbds_multimap_text_find_large_s2p_hash.png"/></imageobject><imageobject><imagedata align="center" format="PDF" scale="33"fileref="../images/pbds_multimap_text_find_large_s2p_hash.pdf"/></imageobject></mediaobject></informalfigure><para>The abbreviated names in the legend of the graphic above areinstantiated with the types in the following table.</para><informaltable frame="all"><tgroup cols="7" align="left" colsep="1" rowsep="1"><colspec colname="c1"/><colspec colname="c2"/><colspec colname="c3"/><colspec colname="c4"/><colspec colname="c5"/><colspec colname="c6"/><colspec colname="c7"/><thead><row><entry><emphasis>Name/Instantiating Type</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry></row></thead><tbody><!-- native --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c7">n_hash_mmap</entry></row><row><entry><classname>std::tr1::unordered_multimap</classname></entry><entry namest="c2" nameend="c7"></entry></row><!-- multimap 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c7">rb_tree_mmap_lu_mtf_set</entry></row><row><entry morerows="3" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mask_range_hashing</classname></entry><entry namest="c4" nameend="c7"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_exponential_size_policy</classname></entry><entry namest="c6" nameend="c7"></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2</entry><entry namest="c6" nameend="c7"></entry></row><row><entry><classname>Mapped</classname></entry><entry><classname>list_update</classname></entry><entry><classname>Update_Policy</classname></entry><entry><classname>lu_move_to_front_policy</classname></entry><entry namest="c6" nameend="c7"></entry></row><!-- multimap 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c7">rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set</entry></row><row><entry morerows="5" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mask_range_hashing</classname></entry><entry namest="c4" nameend="c7"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_exponential_size_policy</classname></entry><entry namest="c6" nameend="c7"></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2</entry><entry namest="c6" nameend="c7"></entry></row><row><entry morerows="2" valign="top"><classname>Mapped</classname></entry><entry morerows="2" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mask_range_hashing</classname></entry><entry namest="c6" nameend="c7"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_exponential_size_policy</classname></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2</entry></row></tbody></tgroup></informaltable></section><section xml:id="multimap.text_insert_large.observations"><info><title>Observations</title></info><para>See Observations::Mapping-SemanticsConsiderations.</para></section></section><!-- 05 <a href="multimap_text_insert_mem_usage_test_small"> --><section xml:id="performance.multimap.text_insert_mem_small"><info><title>Text <function>insert</function> with SmallSecondary-to-Primary Key Ratios Memory Use</title></info><para></para><section xml:id="multimap.text_insert_mem_small.info"><info><title>Description</title></info><para>This test inserts a number of pairs into a container. Thefirst item of each pair is a string from an arbitrary text[wickland96thirty], andthe second is a uniform integer. The container is a"multimap" - it considers the first member of each pair as aprimary key, and the second member of each pair as a secondarykey. Thereare 100 distinct primary keys, and the ratio of secondary keysto primary keys ranges to about 20.</para><para>The test measures the memory use as a function of the numberof values inserted.</para><para>It uses the test file:<filename>performance/ext/pb_ds/multimap_text_insert_mem_usage_small.cc</filename></para><para>The test checks the memory scalability of different"multimap" designs.</para></section><section xml:id="multimap.text_insert_mem_small.results"><info><title>Results</title></info><para>The graphic below show the results for "multimaps" whichuse a tree-based container for primary keys.</para><!-- results graphic --><informalfigure><mediaobject><imageobject><imagedata align="center" format="PNG" scale="100"fileref="../images/pbds_multimap_text_insert_mem_small_s2p_tree.png"/></imageobject><imageobject><imagedata align="center" format="PDF" scale="33"fileref="../images/pbds_multimap_text_insert_mem_small_s2p_tree.pdf"/></imageobject></mediaobject></informalfigure><para>The abbreviated names in the legend of the graphic above areinstantiated with the types in the following table.</para><informaltable frame="all"><tgroup cols="7" align="left" colsep="1" rowsep="1"><colspec colname="c1"/><colspec colname="c2"/><colspec colname="c3"/><colspec colname="c4"/><colspec colname="c5"/><colspec colname="c6"/><colspec colname="c7"/><thead><row><entry><emphasis>Name/Instantiating Type</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry></row></thead><tbody><!-- native --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c7">n_mmap</entry></row><row><entry><classname>std::multimap</classname></entry><entry namest="c2" nameend="c7"></entry></row><!-- multimap 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c7">rb_tree_mmap_lu_mtf_set</entry></row><row><entry morerows="2" valign="top"><classname>tree</classname></entry><entry><classname>Tag</classname></entry><entry><classname>rb_tree_tag</classname></entry><entry namest="c4" nameend="c7"></entry></row><row><entry><classname>Node_Update</classname></entry><entry><classname>null_node_update</classname></entry><entry namest="c4" nameend="c7"></entry></row><row><entry><classname>Mapped</classname></entry><entry><classname>list_update</classname></entry><entry><classname>Update_Policy</classname></entry><entry><classname>lu_move_to_front_policy</classname></entry><entry namest="c6" nameend="c7"></entry></row><!-- multimap 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c7">rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set</entry></row><row><entry morerows="4" valign="top"><classname>tree</classname></entry><entry><classname>Tag</classname></entry><entry><classname>rb_tree_tag</classname></entry><entry namest="c4" nameend="c7"></entry></row><row><entry><classname>Node_Update</classname></entry><entry><classname>null_node_update</classname></entry><entry namest="c4" nameend="c7"></entry></row><row><entry morerows="2" valign="top"><classname>Mapped</classname></entry><entry morerows="2" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mask_range_hashing</classname></entry><entry namest="c6" nameend="c7"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_exponential_size_policy</classname></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2</entry></row></tbody></tgroup></informaltable><para>The graphic below show the results for "multimaps" whichuse a hash-based container for primary keys.</para><!-- results graphic --><informalfigure><mediaobject><imageobject><imagedata align="center" format="PNG" scale="100"fileref="../images/pbds_multimap_text_find_large_s2p_hash.png"/></imageobject><imageobject><imagedata align="center" format="PDF" scale="33"fileref="../images/pbds_multimap_text_find_large_s2p_hash.pdf"/></imageobject></mediaobject></informalfigure><para>The abbreviated names in the legend of the graphic above areinstantiated with the types in the following table.</para><informaltable frame="all"><tgroup cols="7" align="left" colsep="1" rowsep="1"><colspec colname="c1"/><colspec colname="c2"/><colspec colname="c3"/><colspec colname="c4"/><colspec colname="c5"/><colspec colname="c6"/><colspec colname="c7"/><thead><row><entry><emphasis>Name/Instantiating Type</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry></row></thead><tbody><!-- native --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c7">n_hash_mmap</entry></row><row><entry><classname>std::tr1::unordered_multimap</classname></entry><entry namest="c2" nameend="c7"></entry></row><!-- multimap 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c7">rb_tree_mmap_lu_mtf_set</entry></row><row><entry morerows="3" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mask_range_hashing</classname></entry><entry namest="c4" nameend="c7"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_exponential_size_policy</classname></entry><entry namest="c6" nameend="c7"></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2</entry><entry namest="c6" nameend="c7"></entry></row><row><entry><classname>Mapped</classname></entry><entry><classname>list_update</classname></entry><entry><classname>Update_Policy</classname></entry><entry><classname>lu_move_to_front_policy</classname></entry><entry namest="c6" nameend="c7"></entry></row><!-- multimap 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c7">rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set</entry></row><row><entry morerows="5" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mask_range_hashing</classname></entry><entry namest="c4" nameend="c7"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_exponential_size_policy</classname></entry><entry namest="c6" nameend="c7"></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2</entry><entry namest="c6" nameend="c7"></entry></row><row><entry morerows="2" valign="top"><classname>Mapped</classname></entry><entry morerows="2" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mask_range_hashing</classname></entry><entry namest="c6" nameend="c7"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_exponential_size_policy</classname></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2</entry></row></tbody></tgroup></informaltable></section><section xml:id="multimap.text_insert_mem_small.observations"><info><title>Observations</title></info><para>See Observations::Mapping-SemanticsConsiderations.</para></section></section><!-- 06 <a href="multimap_text_insert_mem_usage_test_large"> --><section xml:id="performance.multimap.text_insert_mem_large"><info><title>Text <function>insert</function> with SmallSecondary-to-Primary Key Ratios Memory Use</title></info><para></para><section xml:id="multimap.text_insert_mem_large.info"><info><title>Description</title></info><para>This test inserts a number of pairs into a container. Thefirst item of each pair is a string from an arbitrary text[wickland96thirty], andthe second is a uniform integer. The container is a"multimap" - it considers the first member of each pair as aprimary key, and the second member of each pair as a secondarykey. Thereare 100 distinct primary keys, and the ratio of secondary keysto primary keys ranges to about 20.</para><para>The test measures the memory use as a function of the numberof values inserted.</para><para>It uses the test file:<filename>performance/ext/pb_ds/multimap_text_insert_mem_usage_large.cc</filename></para><para>The test checks the memory scalability of different"multimap" designs.</para></section><section xml:id="multimap.text_insert_mem_large.results"><info><title>Results</title></info><para>The graphic below show the results for "multimaps" whichuse a tree-based container for primary keys.</para><!-- results graphic --><informalfigure><mediaobject><imageobject><imagedata align="center" format="PNG" scale="100"fileref="../images/pbds_multimap_text_insert_mem_large_s2p_tree.png"/></imageobject><imageobject><imagedata align="center" format="PDF" scale="33"fileref="../images/pbds_multimap_text_insert_mem_large_s2p_tree.pdf"/></imageobject></mediaobject></informalfigure><para>The abbreviated names in the legend of the graphic above areinstantiated with the types in the following table.</para><informaltable frame="all"><tgroup cols="7" align="left" colsep="1" rowsep="1"><colspec colname="c1"/><colspec colname="c2"/><colspec colname="c3"/><colspec colname="c4"/><colspec colname="c5"/><colspec colname="c6"/><colspec colname="c7"/><thead><row><entry><emphasis>Name/Instantiating Type</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry></row></thead><tbody><!-- native --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c7">n_mmap</entry></row><row><entry><classname>std::multimap</classname></entry><entry namest="c2" nameend="c7"></entry></row><!-- multimap 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c7">rb_tree_mmap_lu_mtf_set</entry></row><row><entry morerows="2" valign="top"><classname>tree</classname></entry><entry><classname>Tag</classname></entry><entry><classname>rb_tree_tag</classname></entry><entry namest="c4" nameend="c7"></entry></row><row><entry><classname>Node_Update</classname></entry><entry><classname>null_node_update</classname></entry><entry namest="c4" nameend="c7"></entry></row><row><entry><classname>Mapped</classname></entry><entry><classname>list_update</classname></entry><entry><classname>Update_Policy</classname></entry><entry><classname>lu_move_to_front_policy</classname></entry><entry namest="c6" nameend="c7"></entry></row><!-- multimap 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c7">rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set</entry></row><row><entry morerows="4" valign="top"><classname>tree</classname></entry><entry><classname>Tag</classname></entry><entry><classname>rb_tree_tag</classname></entry><entry namest="c4" nameend="c7"></entry></row><row><entry><classname>Node_Update</classname></entry><entry><classname>null_node_update</classname></entry><entry namest="c4" nameend="c7"></entry></row><row><entry morerows="2" valign="top"><classname>Mapped</classname></entry><entry morerows="2" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mask_range_hashing</classname></entry><entry namest="c6" nameend="c7"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_exponential_size_policy</classname></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2</entry></row></tbody></tgroup></informaltable><para>The graphic below show the results for "multimaps" whichuse a hash-based container for primary keys.</para><!-- results graphic --><informalfigure><mediaobject><imageobject><imagedata align="center" format="PNG" scale="100"fileref="../images/pbds_multimap_text_find_large_s2p_hash.png"/></imageobject><imageobject><imagedata align="center" format="PDF" scale="33"fileref="../images/pbds_multimap_text_find_large_s2p_hash.pdf"/></imageobject></mediaobject></informalfigure><para>The abbreviated names in the legend of the graphic above areinstantiated with the types in the following table.</para><informaltable frame="all"><tgroup cols="7" align="left" colsep="1" rowsep="1"><colspec colname="c1"/><colspec colname="c2"/><colspec colname="c3"/><colspec colname="c4"/><colspec colname="c5"/><colspec colname="c6"/><colspec colname="c7"/><thead><row><entry><emphasis>Name/Instantiating Type</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry></row></thead><tbody><!-- native --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c7">n_hash_mmap</entry></row><row><entry><classname>std::tr1::unordered_multimap</classname></entry><entry namest="c2" nameend="c7"></entry></row><!-- multimap 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c7">rb_tree_mmap_lu_mtf_set</entry></row><row><entry morerows="3" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mask_range_hashing</classname></entry><entry namest="c4" nameend="c7"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_exponential_size_policy</classname></entry><entry namest="c6" nameend="c7"></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2</entry><entry namest="c6" nameend="c7"></entry></row><row><entry><classname>Mapped</classname></entry><entry><classname>list_update</classname></entry><entry><classname>Update_Policy</classname></entry><entry><classname>lu_move_to_front_policy</classname></entry><entry namest="c6" nameend="c7"></entry></row><!-- multimap 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c7">rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set</entry></row><row><entry morerows="5" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mask_range_hashing</classname></entry><entry namest="c4" nameend="c7"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_exponential_size_policy</classname></entry><entry namest="c6" nameend="c7"></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2</entry><entry namest="c6" nameend="c7"></entry></row><row><entry morerows="2" valign="top"><classname>Mapped</classname></entry><entry morerows="2" valign="top"><classname>cc_hash_table</classname></entry><entry><classname>Comb_Hash_Fn</classname></entry><entry><classname>direct_mask_range_hashing</classname></entry><entry namest="c6" nameend="c7"></entry></row><row><entry morerows="1" valign="top"><classname>Resize_Policy</classname></entry><entry morerows="1" valign="top"><classname>hash_standard_resize_policy</classname></entry><entry><classname>Size_Policy</classname></entry><entry><classname>hash_exponential_size_policy</classname></entry></row><row><entry valign="top"><classname>Trigger_Policy</classname></entry><entry><classname>hash_load_check_resize_trigger</classname> withα<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2</entry></row></tbody></tgroup></informaltable></section><section xml:id="multimap.text_insert_mem_large.observations"><info><title>Observations</title></info><para>See Observations::Mapping-SemanticsConsiderations.</para></section></section></section> <!-- multimap --><section xml:id="performance.priority_queue"><info><title>Priority Queue</title></info><!-- 01 <a href="priority_queue_text_push_timing_test"> --><section xml:id="performance.priority_queue.text_push"><info><title>Text <function>push</function></title></info><para></para><section xml:id="priority_queue.text_push.info"><info><title>Description</title></info><para>This test inserts a number of values with keys from anarbitrary text ([ wickland96thirty ]) intoa container using <function>push</function>. It measures the average timefor <function>push</function> as a function of the number of valuespushed.</para><para>It uses the test file:<filename>performance/ext/pb_ds/priority_queue_text_push_timing.cc</filename></para><para>The test checks the effect of different underlying datastructures.</para></section><section xml:id="priority_queue.text_push.results"><info><title>Results</title></info><para>The two graphics below show the results for the nativepriority_queues and this library's priority_queues.</para><para>The graphic immediately below shows the results for thenative priority_queue type instantiated with different underlyingcontainer types versus several different versions of library'spriority_queues.</para><!-- results graphic --><informalfigure><mediaobject><imageobject><imagedata align="center" format="PDF" scale="75"fileref="../images/pbds_priority_queue_text_push.pdf"/></imageobject><imageobject><imagedata align="center" format="PNG" scale="100"fileref="../images/pbds_priority_queue_text_push.png"/></imageobject></mediaobject></informalfigure><para>The abbreviated names in the legend of the graphic above areinstantiated with the types in the following table.</para><informaltable frame="all"><tgroup cols="3" align="left" colsep="1" rowsep="1"><colspec colname="c1"/><colspec colname="c2"/><colspec colname="c3"/><thead><row><entry><emphasis>Name/Instantiating Type</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry></row></thead><tbody><!-- native 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">n_pq_vector</entry></row><row><entry><classname>std::priority_queue</classname></entry><entry><classname>Sequence</classname></entry><entry><classname>std::vector</classname></entry></row><!-- native 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">n_pq_deque</entry></row><row><entry><classname>std::priority_queue</classname></entry><entry><classname>Sequence</classname></entry><entry><classname>std::deque</classname></entry></row><!-- priority_queue 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">binary_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>binary_heap_tag</classname></entry></row><!-- priority_queue 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">binomial_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>binomial_heap_tag</classname></entry></row><!-- priority_queue 03 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">rc_binomial_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>rc_binomial_heap_tag</classname></entry></row><!-- priority_queue 04 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">thin_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>thin_heap_tag</classname></entry></row><!-- priority_queue 05 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">pairing_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>pairing_heap_tag</classname></entry></row></tbody></tgroup></informaltable><para>The graphic below shows the results for the binary-heapbased native priority queues and this library's pairing-heappriority_queue data structures.</para><!-- results graphic --><informalfigure><mediaobject><imageobject><imagedata align="center" format="PDF" scale="75"fileref="../images/pbds_pairing_priority_queue_text_push.pdf"/></imageobject><imageobject><imagedata align="center" format="PNG" scale="100"fileref="../images/pbds_pairing_priority_queue_text_push.png"/></imageobject></mediaobject></informalfigure><para>The abbreviated names in the legend of the graphic above areinstantiated with the types in the following table.</para><informaltable frame="all"><tgroup cols="3" align="left" colsep="1" rowsep="1"><colspec colname="c1"/><colspec colname="c2"/><colspec colname="c3"/><thead><row><entry><emphasis>Name/Instantiating Type</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry></row></thead><tbody><!-- native 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">n_pq_vector</entry></row><row><entry><classname>std::priority_queue</classname></entry><entry><classname>Sequence</classname></entry><entry><classname>std::vector</classname></entry></row><!-- native 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">n_pq_deque</entry></row><row><entry><classname>std::priority_queue</classname></entry><entry><classname>Sequence</classname></entry><entry><classname>std::deque</classname></entry></row><!-- priority_queue 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">thin_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>thin_heap_tag</classname></entry></row><!-- priority_queue 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">pairing_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>pairing_heap_tag</classname></entry></row></tbody></tgroup></informaltable></section><section xml:id="priority_queue.text_push.observations"><info><title>Observations</title></info><para>Pairing heaps (<classname>priority_queue</classname> with<classname>Tag</classname> = <classname>pairing_heap_tag</classname>)are the most suited for sequences of <function>push</function> and<function>pop</function> operations of non-primitive types (e.g.<classname>std::string</classname>s). (See Priority QueueText <function>push</function> and <function>pop</function> Timing Test.) They areless constrained than binomial heaps, e.g., and sincethey are node-based, they outperform binary heaps. (SeePriorityQueue Random Integer <function>push</function> Timing Test for the caseof primitive types.)</para><para>The standard's priority queues do not seem to perform well inthis case: the <classname>std::vector</classname> implementation needs toperform a logarithmic sequence of string operations for eachoperation, and the deque implementation is possibly hampered byits need to manipulate a relatively-complex type (dequessupport a O(1) <function>push_front</function>, even though it isnot used by <classname>std::priority_queue</classname>.)</para></section></section><!-- 02 <a href="priority_queue_text_push_pop_timing_test"> --><section xml:id="performance.priority_queue.text_push_pop"><info><title>Text <function>push</function> and <function>pop</function></title></info><para></para><section xml:id="priority_queue.text_push_pop.info"><info><title>Description</title></info><para>This test inserts a number of values with keys from anarbitrary text ([ wickland96thirty ]) intoa container using <classname>push</classname> , then removes them using<classname>pop</classname> . It measures the average time for <classname>push</classname>as a function of the number of values.</para><para>It uses the test file:<filename>performance/ext/pb_ds/priority_queue_text_push_pop_timing.cc</filename></para><para>The test checks the effect of different underlying datastructures.</para></section><section xml:id="priority_queue.text_push_pop.results"><info><title>Results</title></info><para>The two graphics below show the results for the nativepriority_queues and this library's priority_queues.</para><para>The graphic immediately below shows the results for thenative priority_queue type instantiated with different underlyingcontainer types versus several different versions of library'spriority_queues.</para><!-- results graphic --><informalfigure><mediaobject><imageobject><imagedata align="center" format="PDF" scale="75"fileref="../images/pbds_priority_queue_text_push_pop.pdf"/></imageobject><imageobject><imagedata align="center" format="PNG" scale="100"fileref="../images/pbds_priority_queue_text_push_pop.png"/></imageobject></mediaobject></informalfigure><para>The abbreviated names in the legend of the graphic above areinstantiated with the types in the following table.</para><informaltable frame="all"><tgroup cols="3" align="left" colsep="1" rowsep="1"><colspec colname="c1"/><colspec colname="c2"/><colspec colname="c3"/><thead><row><entry><emphasis>Name/Instantiating Type</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry></row></thead><tbody><!-- native 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">n_pq_vector</entry></row><row><entry><classname>std::priority_queue</classname></entry><entry><classname>Sequence</classname></entry><entry><classname>std::vector</classname></entry></row><!-- native 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">n_pq_deque</entry></row><row><entry><classname>std::priority_queue</classname></entry><entry><classname>Sequence</classname></entry><entry><classname>std::deque</classname></entry></row><!-- priority_queue 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">binary_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>binary_heap_tag</classname></entry></row><!-- priority_queue 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">binomial_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>binomial_heap_tag</classname></entry></row><!-- priority_queue 03 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">rc_binomial_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>rc_binomial_heap_tag</classname></entry></row><!-- priority_queue 04 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">thin_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>thin_heap_tag</classname></entry></row><!-- priority_queue 05 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">pairing_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>pairing_heap_tag</classname></entry></row></tbody></tgroup></informaltable><para>The graphic below shows the results for the native priorityqueues and this library's pairing-heap priority_queue datastructures.</para><!-- results graphic --><informalfigure><mediaobject><imageobject><imagedata align="center" format="PDF" scale="75"fileref="../images/pbds_pairing_priority_queue_text_push_pop.pdf"/></imageobject><imageobject><imagedata align="center" format="PNG" scale="100"fileref="../images/pbds_pairing_priority_queue_text_push_pop.png"/></imageobject></mediaobject></informalfigure><para>The abbreviated names in the legend of the graphic above areinstantiated with the types in the following table.</para><informaltable frame="all"><tgroup cols="3" align="left" colsep="1" rowsep="1"><colspec colname="c1"/><colspec colname="c2"/><colspec colname="c3"/><thead><row><entry><emphasis>Name/Instantiating Type</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry></row></thead><tbody><!-- native 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">n_pq_vector</entry></row><row><entry><classname>std::priority_queue</classname> adapting <classname>std::vector</classname></entry><entry><classname>Sequence</classname></entry><entry><classname>std::vector</classname></entry></row><!-- native 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">n_pq_deque</entry></row><row><entry><classname>std::priority_queue</classname></entry><entry><classname>Sequence</classname></entry><entry><classname>std::deque</classname></entry></row><!-- priority_queue 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">pairing_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>pairing_heap_tag</classname></entry></row></tbody></tgroup></informaltable></section><section xml:id="priority_queue.text_push_pop.observations"><info><title>Observations</title></info><para>These results are very similar to Priority Queue Text<function>push</function> Timing Test. As stated there, pairing heaps(<classname>priority_queue</classname> with<classname>Tag</classname>= <classname>pairing_heap_tag</classname>) are most suitedfor <function>push</function> and <function>pop</function>sequences of non-primitive types such as strings. Observing thesetwo tests, one can note that a pairing heap outperforms the othersin terms of <function>push</function> operations, but equalsbinary heaps (<classname>priority_queue</classname> with<classname>Tag</classname>= <classname>binary_heap_tag</classname>) if the numberof <function>push</function> and <function>pop</function>operations is equal. As the number of <function>pop</function>operations is at most equal to the numberof <function>push</function> operations, pairing heaps are betterin this case. See Priority Queue RandomInteger <function>push</function> and <function>pop</function>Timing Test for a case which is different.</para></section></section><!-- 03 <a href="priority_queue_random_int_push_timing_test"> --><section xml:id="performance.priority_queue.int_push"><info><title>Integer <function>push</function></title></info><para></para><section xml:id="priority_queue.int_push.info"><info><title>Description</title></info><para>This test inserts a number of values with integer keysinto a container using <function>push</function>. Itmeasures the average time for <function>push</function> as afunction of the number of values.</para><para>It uses the test file:<filename>performance/ext/pb_ds/priority_queue_random_int_push_timing.cc</filename></para><para>The test checks the effect of different underlying datastructures.</para></section><section xml:id="priority_queue.int_push.results"><info><title>Results</title></info><para>The two graphics below show the results for the nativepriority_queues and this library's priority_queues.</para><para>The graphic immediately below shows the results for thenative priority_queue type instantiated with different underlyingcontainer types versus several different versions of library'spriority_queues.</para><!-- results graphic --><informalfigure><mediaobject><imageobject><imagedata align="center" format="PDF" scale="75"fileref="../images/pbds_priority_queue_int_push.pdf"/></imageobject><imageobject><imagedata align="center" format="PNG" scale="100"fileref="../images/pbds_priority_queue_int_push.png"/></imageobject></mediaobject></informalfigure><para>The abbreviated names in the legend of the graphic above areinstantiated with the types in the following table.</para><informaltable frame="all"><tgroup cols="3" align="left" colsep="1" rowsep="1"><colspec colname="c1"/><colspec colname="c2"/><colspec colname="c3"/><thead><row><entry><emphasis>Name/Instantiating Type</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry></row></thead><tbody><!-- native 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">n_pq_vector</entry></row><row><entry><classname>std::priority_queue</classname></entry><entry><classname>Sequence</classname></entry><entry><classname>std::vector</classname></entry></row><!-- native 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">n_pq_deque</entry></row><row><entry><classname>std::priority_queue</classname></entry><entry><classname>Sequence</classname></entry><entry><classname>std::deque</classname></entry></row><!-- priority_queue 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">binary_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>binary_heap_tag</classname></entry></row><!-- priority_queue 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">binomial_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>binomial_heap_tag</classname></entry></row><!-- priority_queue 03 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">rc_binomial_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>rc_binomial_heap_tag</classname></entry></row><!-- priority_queue 04 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">thin_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>thin_heap_tag</classname></entry></row><!-- priority_queue 05 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">pairing_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>pairing_heap_tag</classname></entry></row></tbody></tgroup></informaltable><para>The graphic below shows the results for the binary-heapbased native priority queues and this library'spriority_queue data structures.</para><!-- results graphic --><informalfigure><mediaobject><imageobject><imagedata align="center" format="PDF" scale="75"fileref="../images/pbds_binary_priority_queue_int_push.pdf"/></imageobject><imageobject><imagedata align="center" format="PNG" scale="100"fileref="../images/pbds_binary_priority_queue_int_push.png"/></imageobject></mediaobject></informalfigure><para>The abbreviated names in the legend of the graphic above areinstantiated with the types in the following table.</para><informaltable frame="all"><tgroup cols="3" align="left" colsep="1" rowsep="1"><colspec colname="c1"/><colspec colname="c2"/><colspec colname="c3"/><thead><row><entry><emphasis>Name/Instantiating Type</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry></row></thead><tbody><!-- native 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">n_pq_vector</entry></row><row><entry><classname>std::priority_queue</classname> adapting <classname>std::vector</classname></entry><entry><classname>Sequence</classname></entry><entry><classname>std::vector</classname></entry></row><!-- native 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">n_pq_deque</entry></row><row><entry><classname>std::priority_queue</classname></entry><entry><classname>Sequence</classname></entry><entry><classname>std::deque</classname></entry></row><!-- priority_queue 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">binary_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>binary_heap_tag</classname></entry></row></tbody></tgroup></informaltable></section><section xml:id="priority_queue.int_push.observations"><info><title>Observations</title></info><para>Binary heaps are the most suited for sequences of<function>push</function> and <function>pop</function> operations of primitive types(e.g. <type>int</type>s). They are less constrainedthan any other type, and since it is very efficient to storesuch types in arrays, they outperform even pairing heaps. (SeePriorityQueue Text <function>push</function> Timing Test for the case ofnon-primitive types.)</para></section></section><!-- 04 "priority_queue_random_int_push_pop_timing_test" --><section xml:id="performance.priority_queue.int_push_pop"><info><title>Integer <function>push</function></title></info><para></para><section xml:id="priority_queue.int_push_pop.info"><info><title>Description</title></info><para>This test inserts a number of values with integer keysinto a container using <function>push</function> , then removes themusing <function>pop</function> . It measures the average time for<function>push</function> and <function>pop</function> as a functionof the number of values.</para><para>It uses the test file:<filename>performance/ext/pb_ds/priority_queue_random_int_push_pop_timing.cc</filename></para><para>The test checks the effect of different underlying datastructures.</para></section><section xml:id="priority_queue.int_push_pop.results"><info><title>Results</title></info><para>The graphic immediately below shows the results for thenative priority_queue type instantiated with different underlyingcontainer types versus several different versions of library'spriority_queues.</para><!-- results graphic --><informalfigure><mediaobject><imageobject><imagedata align="center" format="PDF" scale="75"fileref="../images/pbds_priority_queue_int_push_pop.pdf"/></imageobject><imageobject><imagedata align="center" format="PNG" scale="100"fileref="../images/pbds_priority_queue_int_push_pop.png"/></imageobject></mediaobject></informalfigure><para>The abbreviated names in the legend of the graphic above areinstantiated with the types in the following table.</para><informaltable frame="all"><tgroup cols="3" align="left" colsep="1" rowsep="1"><colspec colname="c1"/><colspec colname="c2"/><colspec colname="c3"/><thead><row><entry><emphasis>Name/Instantiating Type</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry></row></thead><tbody><!-- native 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">n_pq_vector</entry></row><row><entry><classname>std::priority_queue</classname></entry><entry><classname>Sequence</classname></entry><entry><classname>std::vector</classname></entry></row><!-- native 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">n_pq_deque</entry></row><row><entry><classname>std::priority_queue</classname></entry><entry><classname>Sequence</classname></entry><entry><classname>std::deque</classname></entry></row><!-- priority_queue 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">binary_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>binary_heap_tag</classname></entry></row><!-- priority_queue 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">binomial_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>binomial_heap_tag</classname></entry></row><!-- priority_queue 03 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">rc_binomial_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>rc_binomial_heap_tag</classname></entry></row><!-- priority_queue 04 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">thin_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>thin_heap_tag</classname></entry></row><!-- priority_queue 05 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">pairing_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>pairing_heap_tag</classname></entry></row></tbody></tgroup></informaltable></section><section xml:id="priority_queue.int_push_pop.observations"><info><title>Observations</title></info><para>Binary heaps are the most suited for sequences of<function>push</function> and <function>pop</function> operations of primitive types(e.g. <type>int</type>s). This is explained inPriorityQueue Random Int <function>push</function> Timing Test. (See Priority QueueText <function>push</function> Timing Test for the case of primitivetypes.)</para><para>At first glance it seems that the standard's vector-basedpriority queue is approximately on par with thislibrary's corresponding priority queue. There are twodifferences however:</para><orderedlist><listitem><para>The standard's priority queue does not downsize the underlyingvector (or deque) as the priority queue becomes smaller(see Priority QueueText <function>pop</function> Memory Use Test). It is thereforegaining some speed at the expense of space.</para></listitem><listitem><para>From Priority Queue RandomInteger <function>push</function> and <function>pop</function>Timing Test, it seems that the standard's priority queue isslower in terms of <function>push</function> operations. Sincethe number of<function>pop</function> operations is at most that of <function>push</function>operations, the test here is the "best" for the standard'spriority queue.</para></listitem></orderedlist></section></section><!-- 05 <a href="priority_queue_text_pop_mem_usage_test"> --><section xml:id="performance.priority_queue.text_pop"><info><title>Text <function>pop</function> Memory Use</title></info><para></para><section xml:id="priority_queue.text_pop.info"><info><title>Description</title></info><para>This test inserts a number of values with keys from anarbitrary text ([ wickland96thirty ]) intoa container, then pops them until only one is left in thecontainer. It measures the memory use as a function of thenumber of values pushed to the container.</para><para>It uses the test file:<filename>performance/ext/pb_ds/priority_queue_text_pop_mem_usage.cc</filename></para><para>The test checks the effect of different underlying datastructures.</para></section><section xml:id="priority_queue.text_pop.results"><info><title>Results</title></info><para>The graphic immediately below shows the results for thenative priority_queue type instantiated with different underlyingcontainer types versus several different versions of library'spriority_queues.</para><!-- results graphic --><informalfigure><mediaobject><imageobject><imagedata align="center" format="PDF" scale="75"fileref="../images/pbds_priority_queue_text_pop_mem.pdf"/></imageobject><imageobject><imagedata align="center" format="PNG" scale="100"fileref="../images/pbds_priority_queue_text_pop_mem.png"/></imageobject></mediaobject></informalfigure><para>The abbreviated names in the legend of the graphic above areinstantiated with the types in the following table.</para><informaltable frame="all"><tgroup cols="3" align="left" colsep="1" rowsep="1"><colspec colname="c1"/><colspec colname="c2"/><colspec colname="c3"/><thead><row><entry><emphasis>Name/Instantiating Type</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry></row></thead><tbody><!-- native 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">n_pq_vector</entry></row><row><entry><classname>std::priority_queue</classname></entry><entry><classname>Sequence</classname></entry><entry><classname>std::vector</classname></entry></row><!-- native 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">n_pq_deque</entry></row><row><entry><classname>std::priority_queue</classname></entry><entry><classname>Sequence</classname></entry><entry><classname>std::deque</classname></entry></row><!-- priority_queue 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">binary_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>binary_heap_tag</classname></entry></row><!-- priority_queue 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">binomial_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>binomial_heap_tag</classname></entry></row><!-- priority_queue 03 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">rc_binomial_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>rc_binomial_heap_tag</classname></entry></row><!-- priority_queue 04 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">thin_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>thin_heap_tag</classname></entry></row><!-- priority_queue 05 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">pairing_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>pairing_heap_tag</classname></entry></row></tbody></tgroup></informaltable></section><section xml:id="priority_queue.text_pop.observations"><info><title>Observations</title></info><para>The priority queue implementations (excluding the standard's) usememory proportionally to the number of values they hold:node-based implementations (e.g., a pairing heap) do sonaturally; this library's binary heap de-allocates memory whena certain lower threshold is exceeded.</para><para>Note from Priority Queue Text <function>push</function>and <function>pop</function> Timing Test and Priority QueueRandom Integer <function>push</function>and <function>pop</function> Timing Test that this does notimpede performance compared to the standard's priorityqueues.</para><para>See Hash-Based EraseMemory Use Test for a similar phenomenon regarding priorityqueues.</para></section></section><!-- 06 <a href="priority_queue_text_join_timing_test"> --><section xml:id="performance.priority_queue.text_join"><info><title>Text <function>join</function></title></info><para></para><section xml:id="priority_queue.text_join.info"><info><title>Description</title></info><para>This test inserts a number of values with keys from anarbitrary text ([ wickland96thirty ]) intotwo containers, then merges the containers. It uses<function>join</function> for this library's priority queues; forthe standard's priority queues, it successively pops values fromone container and pushes them into the other. The test measuresthe average time as a function of the number of values.</para><para>It uses the test file:<filename>performance/ext/pb_ds/priority_queue_text_join_timing.cc</filename></para><para>The test checks the effect of different underlying datastructures.</para></section><section xml:id="priority_queue.text_join.results"><info><title>Results</title></info><para>The graphic immediately below shows the results for thenative priority_queue type instantiated with different underlyingcontainer types versus several different versions of library'spriority_queues.</para><!-- results graphic --><informalfigure><mediaobject><imageobject><imagedata align="center" format="PDF" scale="75"fileref="../images/pbds_priority_queue_text_join.pdf"/></imageobject><imageobject><imagedata align="center" format="PNG" scale="100"fileref="../images/pbds_priority_queue_text_join.png"/></imageobject></mediaobject></informalfigure><para>The abbreviated names in the legend of the graphic above areinstantiated with the types in the following table.</para><informaltable frame="all"><tgroup cols="3" align="left" colsep="1" rowsep="1"><colspec colname="c1"/><colspec colname="c2"/><colspec colname="c3"/><thead><row><entry><emphasis>Name/Instantiating Type</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry></row></thead><tbody><!-- native 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">n_pq_vector</entry></row><row><entry><classname>std::priority_queue</classname></entry><entry><classname>Sequence</classname></entry><entry><classname>std::vector</classname></entry></row><!-- native 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">n_pq_deque</entry></row><row><entry><classname>std::priority_queue</classname></entry><entry><classname>Sequence</classname></entry><entry><classname>std::deque</classname></entry></row><!-- priority_queue 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">binary_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>binary_heap_tag</classname></entry></row><!-- priority_queue 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">binomial_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>binomial_heap_tag</classname></entry></row><!-- priority_queue 03 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">rc_binomial_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>rc_binomial_heap_tag</classname></entry></row><!-- priority_queue 04 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">thin_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>thin_heap_tag</classname></entry></row><!-- priority_queue 05 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">pairing_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>pairing_heap_tag</classname></entry></row></tbody></tgroup></informaltable></section><section xml:id="priority_queue.text_join.observations"><info><title>Observations</title></info><para>In this test the node-based heaps perform <function>join</function> ineither logarithmic or constant time. The binary heap requireslinear time, since the well-known heapify algorithm [clrs2001] is linear.</para><para>It would be possible to apply the heapify algorithm to thestandard containers, if they would support iteration (which theydon't). Barring iterators, it is still somehow possible to performlinear-time merge on a <classname>std::vector</classname>-basedstandard priority queue, using <function>top()</function>and <function>size()</function> (since they are enough to exposethe underlying array), but this is impossible fora <classname>std::deque</classname>-based standard priority queue.Without heapify, the cost is super-linear.</para></section></section><!-- 07 <a href="priority_queue_text_push_timing_test"> --><section xml:id="performance.priority_queue.text_modify_up"><info><title>Text <function>modify</function> Up</title></info><para></para><section xml:id="priority_queue.text_modify_up.info"><info><title>Description</title></info><para>This test inserts a number of values with keys from anarbitrary text ([ wickland96thirty ]) intointo a container then modifies each one "up" (i.e., itmakes it larger). It uses <function>modify</function> for this library'spriority queues; for the standard's priority queues, it pops valuesfrom a container until it reaches the value that should bemodified, then pushes values back in. It measures the averagetime for <function>modify</function> as a function of the number ofvalues.</para><para>It uses the test file:<filename>performance/ext/pb_ds/priority_queue_text_modify_up_timing.cc</filename></para><para>The test checks the effect of different underlying datastructures for graph algorithms settings. Note that making anarbitrary value larger (in the sense of the priority queue'scomparison functor) corresponds to decrease-key in standard graphalgorithms [clrs2001].</para></section><section xml:id="priority_queue.text_modify_up.results"><info><title>Results</title></info><para>The two graphics below show the results for the nativepriority_queues and this library's priority_queues.</para><para>The graphic immediately below shows the results for thenative priority_queue type instantiated with different underlyingcontainer types versus several different versions of library'spriority_queues.</para><!-- results graphic --><informalfigure><mediaobject><imageobject><imagedata align="center" format="PDF" scale="75"fileref="../images/pbds_priority_queue_text_modify_up.pdf"/></imageobject><imageobject><imagedata align="center" format="PNG" scale="100"fileref="../images/pbds_priority_queue_text_modify_up.png"/></imageobject></mediaobject></informalfigure><para>The abbreviated names in the legend of the graphic above areinstantiated with the types in the following table.</para><informaltable frame="all"><tgroup cols="3" align="left" colsep="1" rowsep="1"><colspec colname="c1"/><colspec colname="c2"/><colspec colname="c3"/><thead><row><entry><emphasis>Name/Instantiating Type</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry></row></thead><tbody><!-- native 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">n_pq_vector</entry></row><row><entry><classname>std::priority_queue</classname></entry><entry><classname>Sequence</classname></entry><entry><classname>std::vector</classname></entry></row><!-- native 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">n_pq_deque</entry></row><row><entry><classname>std::priority_queue</classname></entry><entry><classname>Sequence</classname></entry><entry><classname>std::deque</classname></entry></row><!-- priority_queue 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">binary_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>binary_heap_tag</classname></entry></row><!-- priority_queue 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">binomial_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>binomial_heap_tag</classname></entry></row><!-- priority_queue 03 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">rc_binomial_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>rc_binomial_heap_tag</classname></entry></row><!-- priority_queue 04 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">thin_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>thin_heap_tag</classname></entry></row><!-- priority_queue 05 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">pairing_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>pairing_heap_tag</classname></entry></row></tbody></tgroup></informaltable><para>The graphic below shows the results for thenative priority queues and this library's pairing and thin heappriority_queue data structures.</para><!-- results graphic --><informalfigure><mediaobject><imageobject><imagedata align="center" format="PDF" scale="75"fileref="../images/pbds_pairing_priority_queue_text_modify_up_thin.pdf"/></imageobject><imageobject><imagedata align="center" format="PNG" scale="100"fileref="../images/pbds_pairing_priority_queue_text_modify_up_thin.png"/></imageobject></mediaobject></informalfigure><para>The abbreviated names in the legend of the graphic above areinstantiated with the types in the following table.</para><informaltable frame="all"><tgroup cols="3" align="left" colsep="1" rowsep="1"><colspec colname="c1"/><colspec colname="c2"/><colspec colname="c3"/><thead><row><entry><emphasis>Name/Instantiating Type</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry></row></thead><tbody><!-- priority_queue 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">thin_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>thin_heap_tag</classname></entry></row><!-- priority_queue 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">pairing_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>pairing_heap_tag</classname></entry></row></tbody></tgroup></informaltable></section><section xml:id="priority_queue.text_modify_up.observations"><info><title>Observations</title></info><para>As noted above, increasing an arbitrary value (in the sense ofthe priority queue's comparison functor) is very common ingraph-related algorithms. In this case, a thin heap(<classname>priority_queue</classname> with<classname>Tag</classname> = <classname>thin_heap_tag</classname>)outperforms a pairing heap (<classname>priority_queue</classname> with<classname>Tag</classname> = <classname>pairing_heap_tag</classname>).Conversely, Priority Queue Text<function>push</function> Timing Test, Priority QueueText <function>push</function> and <function>pop</function> Timing Test, PriorityQueue Random Integer <function>push</function> Timing Test, andPriorityQueue Random Integer <function>push</function> and <function>pop</function> TimingTest show that the situation is reversed for otheroperations. It is not clear when to prefer one of these twodifferent types.</para><para>In this test this library's binary heapseffectively perform modify in linear time. As explained inPriority Queue Design::Traits, given a valid point-type iterator,a binary heap can perform<function>modify</function> logarithmically. The problem is that binaryheaps invalidate their find iterators with each modifyingoperation, and so the only way to obtain a valid point-typeiterator is to iterate using a range-type iterator untilfinding the appropriate value, then use the range-type iteratorfor the <function>modify</function> operation.</para><para>The explanation for the standard's priority queues' performanceis similar to that in Priority Queue Text<function>join</function> Timing Test.</para></section></section><!-- 08 <a href="priority_queue_text_modify_down_timing_test"> --><section xml:id="performance.priority_queue.text_modify_down"><info><title>Text <function>modify</function> Down</title></info><para></para><section xml:id="priority_queue.text_modify_down.info"><info><title>Description</title></info><para>This test inserts a number of values with keys from anarbitrary text ([ wickland96thirty ]) intointo a container then modifies each one "down" (i.e., itmakes it smaller). It uses <function>modify</function> for this library'spriority queues; for the standard's priority queues, it pops valuesfrom a container until it reaches the value that should bemodified, then pushes values back in. It measures the averagetime for <function>modify</function> as a function of the number ofvalues.</para><para>It uses the test file:<filename>performance/ext/pb_ds/priority_queue_text_modify_down_timing.cc</filename></para><para>The main purpose of this test is to contrast Priority QueueText <classname>modify</classname> Up Timing Test.</para></section><section xml:id="priority_queue.text_modify_down.results"><info><title>Results</title></info><para>The two graphics below show the results for the nativepriority_queues and this library's priority_queues.</para><para>The graphic immediately below shows the results for thenative priority_queue type instantiated with different underlyingcontainer types versus several different versions of library'spriority_queues.</para><!-- results graphic --><informalfigure><mediaobject><imageobject><imagedata align="center" format="PDF" scale="75"fileref="../images/pbds_priority_queue_text_modify_down.pdf"/></imageobject><imageobject><imagedata align="center" format="PNG" scale="100"fileref="../images/pbds_priority_queue_text_modify_down.png"/></imageobject></mediaobject></informalfigure><para>The abbreviated names in the legend of the graphic above areinstantiated with the types in the following table.</para><informaltable frame="all"><tgroup cols="3" align="left" colsep="1" rowsep="1"><colspec colname="c1"/><colspec colname="c2"/><colspec colname="c3"/><thead><row><entry><emphasis>Name/Instantiating Type</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry></row></thead><tbody><!-- native 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">n_pq_vector</entry></row><row><entry><classname>std::priority_queue</classname></entry><entry><classname>Sequence</classname></entry><entry><classname>std::vector</classname></entry></row><!-- native 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">n_pq_deque</entry></row><row><entry><classname>std::priority_queue</classname></entry><entry><classname>Sequence</classname></entry><entry><classname>std::deque</classname></entry></row><!-- priority_queue 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">binary_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>binary_heap_tag</classname></entry></row><!-- priority_queue 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">binomial_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>binomial_heap_tag</classname></entry></row><!-- priority_queue 03 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">rc_binomial_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>rc_binomial_heap_tag</classname></entry></row><!-- priority_queue 04 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">thin_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>thin_heap_tag</classname></entry></row><!-- priority_queue 05 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">pairing_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>pairing_heap_tag</classname></entry></row></tbody></tgroup></informaltable><para>The graphic below shows the results for thenative priority queues and this library's pairing and thin heappriority_queue data structures.</para><!-- results graphic --><informalfigure><mediaobject><imageobject><imagedata align="center" format="PDF" scale="75"fileref="../images/pbds_pairing_priority_queue_text_modify_down_thin.pdf"/></imageobject><imageobject><imagedata align="center" format="PNG" scale="100"fileref="../images/pbds_pairing_priority_queue_text_modify_down_thin.png"/></imageobject></mediaobject></informalfigure><para>The abbreviated names in the legend of the graphic above areinstantiated with the types in the following table.</para><informaltable frame="all"><tgroup cols="3" align="left" colsep="1" rowsep="1"><colspec colname="c1"/><colspec colname="c2"/><colspec colname="c3"/><thead><row><entry><emphasis>Name/Instantiating Type</emphasis></entry><entry><emphasis>Parameter</emphasis></entry><entry><emphasis>Details</emphasis></entry></row></thead><tbody><!-- priority_queue 01 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">thin_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>thin_heap_tag</classname></entry></row><!-- priority_queue 02 --><row><?dbhtml bgcolor="#B0B0B0" ?><entry namest="c1" nameend="c3">pairing_heap</entry></row><row><entry><classname>priority_queue</classname></entry><entry><classname>Tag</classname></entry><entry><classname>pairing_heap_tag</classname></entry></row></tbody></tgroup></informaltable></section><section xml:id="priority_queue.text_modify_down.observations"><info><title>Observations</title></info><para>Most points in these results are similar to Priority QueueText <function>modify</function> Up Timing Test.</para><para>It is interesting to note, however, that as opposed to thattest, a thin heap (<classname>priority_queue</classname> with<classname>Tag</classname> = <classname>thin_heap_tag</classname>) isoutperformed by a pairing heap (<classname>priority_queue</classname> with<classname>Tag</classname> = <classname>pairing_heap_tag</classname>).In this case, both heaps essentially perform an <function>erase</function>operation followed by a <function>push</function> operation. As the othertests show, a pairing heap is usually far more efficient than athin heap, so this is not surprising.</para><para>Most algorithms that involve priority queues increase values(in the sense of the priority queue's comparison functor), andso Priority QueueText <classname>modify</classname> Up Timing Test - is more interestingthan this test.</para></section></section></section> <!-- priority_queue --><section xml:id="pbds.test.performance.observations"><info><title>Observations</title></info><section xml:id="observations.associative"><info><title>Associative</title></info><section xml:id="observations.associative.underlying"><info><title>Underlying Data-Structure Families</title></info><para>In general, hash-based containers have better timing performancethan containers based on different underlying-data structures. Themain reason to choose a tree-based or trie-based container is if abyproduct of the tree-like structure is required: eitherorder-preservation, or the ability to utilize node invariants. Ifmemory-use is the major factor, an ordered-vector tree givesoptimal results (albeit with high modificiation costs), and alist-based container gives reasonable results.</para></section><section xml:id="observations.associative.hash"><info><title>Hash-Based Containers</title></info><para>Hash-based containers are typically either collisionchaining or probing. Collision-chainingcontainers are more flexible internally, and so offer bettertiming performance. Probing containers, if used for simplevalue-types, manage memory more efficiently (they perform farfewer allocation-related calls). In general, therefore, acollision-chaining table should be used. A probing container,conversely, might be used efficiently for operations such aseliminating duplicates in a sequence, or counting the number ofoccurrences within a sequence. Probing containers might be moreuseful also in multithreaded applications where each threadmanipulates a hash-based container: in the standard, allocators haveclass-wise semantics (see [meyers96more] - Item 10); aprobing container might incur less contention in this case.</para></section><section xml:id="observations.associative.hash_policies"><info><title>Hash Policies</title></info><para>In hash-based containers, the range-hashing scheme seems toaffect performance more than other considerations. In mostsettings, a mask-based scheme works well (or can be made towork well). If the key-distribution can be estimated a-priori,a simple hash function can produce nearly uniform hash-valuedistribution. In many other cases (e.g., text hashing,floating-point hashing), the hash function is powerful enoughto generate hash values with good uniformity properties[knuth98sorting];a modulo-based scheme, taking into account all bits of the hashvalue, appears to overlap the hash function in its effort.</para><para>The range-hashing scheme determines many of the otherpolicies. A mask-based scheme workswell with an exponential-size policy; forprobing-based containers, it goes well with a linear-probefunction.</para><para>An orthogonal consideration is the trigger policy. Thispresents difficult tradeoffs. E.g., different loadfactors in a load-check trigger policy yield aspace/amortized-cost tradeoff.</para></section><section xml:id="observations.associative.branch"><info><title>Branch-Based Containers</title></info><para>In general, there are several families of tree-basedunderlying data structures: balanced node-based trees(e.g., red-black or AVL trees), high-probabilitybalanced node-based trees (e.g., random treaps orskip-lists), competitive node-based trees (e.g., splaytrees), vector-based "trees", and tries. (Additionally, thereare disk-residing or network-residing trees, such as B-Treesand their numerous variants. An interface for this would haveto deal with the execution model and ACID guarantees; this isout of the scope of this library.) Following are someobservations on their application to different settings.</para><para>Of the balanced node-based trees, this library includes ared-black tree, as does standard (inpractice). This type of tree is the "workhorse" of tree-basedcontainers: it offers both reasonable modification andreasonable lookup time. Unfortunately, this data structurestores a huge amount of metadata. Each node must contain,besides a value, three pointers and a boolean. This type mightbe avoided if space is at a premium [austern00noset].</para><para>High-probability balanced node-based trees suffer thedrawbacks of deterministic balanced trees. Although they arefascinating data structures, preliminary tests with them showedtheir performance was worse than red-black trees. The librarydoes not contain any such trees, therefore.</para><para>Competitive node-based trees have two drawbacks. They areusually somewhat unbalanced, and they perform a large number ofcomparisons. Balanced trees perform one comparison per eachnode they encounter on a search path; a splay tree performs twocomparisons. If the keys are complex objects, e.g.,<classname>std::string</classname>, this can increase the running time.Conversely, such trees do well when there is much locality ofreference. It is difficult to determine in which case to prefersuch trees over balanced trees. This library includes a splaytree.</para><para>Ordered-vector trees use very little space[austern00noset].They do not have any other advantages (at least in thisimplementation).</para><para>Large-fan-out PATRICIA tries have excellent lookupperformance, but they do so through maintaining, for each node,a miniature "hash-table". Their space efficiency is low, andtheir modification performance is bad. These tries might beused for semi-static settings, where order preservation isimportant. Alternatively, red-black trees cross-referenced withhash tables can be used. [okasaki98mereable]discusses small-fan-out PATRICIA tries for integers, but thecited results seem to indicate that the amortized cost ofmaintaining such trees is higher than that of balanced trees.Moderate-fan-out trees might be useful for sequences where eachelement has a limited number of choices, e.g., DNAstrings.</para></section><section xml:id="observations.associative.mapping_semantics"><info><title>Mapping-Semantics</title></info><para>Different mapping semantics were discussed in the introduction and design sections.Herethe focus will be on the case where a keys can be composed intoprimary keys and secondary keys. (In the case where some keysare completely identical, it is trivial that one should use anassociative container mapping values to size types.) In thiscase there are (at least) five possibilities:</para><orderedlist><listitem><para>Use an associative container that allows equivalent-keyvalues (such as <classname>std::multimap</classname>)</para></listitem><listitem><para>Use a unique-key value associative container that mapseach primary key to some complex associative container ofsecondary keys, say a tree-based or hash-based container.</para></listitem><listitem><para>Use a unique-key value associative container that mapseach primary key to some simple associative container ofsecondary keys, say a list-based container.</para></listitem><listitem><para>Use a unique-key value associative container that mapseach primary key to some non-associative container(e.g., <classname>std::vector</classname>)</para></listitem><listitem><para>Use a unique-key value associative container that takesinto account both primary and secondary keys.</para></listitem></orderedlist><para>Stated simply: there is a simple answer for this. (Excludingoption 1, which should be avoided in all cases).</para><para>If the expected ratio of secondary keys to primary keys issmall, then 3 and 4 seem reasonable. Both types of secondarycontainers are relatively lightweight (in terms of memory useand construction time), and so creating an entire containerobject for each primary key is not too expensive. Option 4might be preferable to option 3 if changing the secondary keyof some primary key is frequent - one cannot modify anassociative container's key, and the only possibility,therefore, is erasing the secondary key and inserting anotherone instead; a non-associative container, conversely, cansupport in-place modification. The actual cost of erasing asecondary key and inserting another one depends also on theallocator used for secondary associative-containers (The testsabove used the standard allocator, but in practice one mightchoose to use, e.g., [boost_pool]). Option 2 isdefinitely an overkill in this case. Option 1 loses out eitherimmediately (when there is one secondary key per primary key)or almost immediately after that. Option 5 has the samedrawbacks as option 2, but it has the additional drawback thatfinding all values whose primary key is equivalent to some key,might be linear in the total number of values stored (forexample, if using a hash-based container).</para><para>If the expected ratio of secondary keys to primary keys islarge, then the answer is more complicated. It depends on thedistribution of secondary keys to primary keys, thedistribution of accesses according to primary keys, and thetypes of operations most frequent.</para><para>To be more precise, assume there are m primary keys,primary key i is mapped to n<subscript>i</subscript>secondary keys, and each primary key is mapped, on average, ton secondary keys (i.e.,E(n<subscript>i</subscript>) = n).</para><para>Suppose one wants to find a specific pair of primary andsecondary keys. Using 1 with a tree based container(<classname>std::multimap</classname>), the expected cost isE(Θ(log(m) + n<subscript>i</subscript>)) = Θ(log(m) +n); using 1 with a hash-based container(<classname>std::tr1::unordered_multimap</classname>), the expected cost isΘ(n). Using 2 with a primary hash-based containerand secondary hash-based containers, the expected cost isO(1); using 2 with a primary tree-based container andsecondary tree-based containers, the expected cost is (usingthe Jensen inequality [motwani95random])E(O(log(m) + log(n<subscript>i</subscript>)) = O(log(m)) +E(O(log(n<subscript>i</subscript>)) = O(log(m)) + O(log(n)),assuming that primary keys are accessed equiprobably. 3 and 4are similar to 1, but with lower constants. Using 5 with ahash-based container, the expected cost is O(1); using 5with a tree based container, the cost isE(Θ(log(mn))) = Θ(log(m) +log(n)).</para><para>Suppose one needs the values whose primary key matches somegiven key. Using 1 with a hash-based container, the expectedcost is Θ(n), but the values will not be orderedby secondary keys (which may or may not be required); using 1with a tree-based container, the expected cost isΘ(log(m) + n), but with high constants; again thevalues will not be ordered by secondary keys. 2, 3, and 4 aresimilar to 1, but typically with lower constants (and,additionally, if one uses a tree-based container for secondarykeys, they will be ordered). Using 5 with a hash-basedcontainer, the cost is Θ(mn).</para><para>Suppose one wants to assign to a primary key all secondarykeys assigned to a different primary key. Using 1 with ahash-based container, the expected cost is Θ(n),but with very high constants; using 1 with a tree-basedcontainer, the cost is Θ(nlog(mn)). Using 2, 3,and 4, the expected cost is Θ(n), but typicallywith far lower costs than 1. 5 is similar to 1.</para></section></section><section xml:id="observations.priority_queue"><info><title>Priority_Queue</title></info><section xml:id="observations.priority_queue.complexity"><info><title>Complexity</title></info><para>The following table shows the complexities of the differentunderlying data structures in terms of orders of growth. It isinteresting to note that this table implies something about theconstants of the operations as well (see Amortized <function>push</function>and <function>pop</function> operations).</para><informaltable frame="all"><tgroup cols="6" align="left" colsep="1" rowsep="1"><colspec colname="c1"/><colspec colname="c2"/><colspec colname="c3"/><colspec colname="c4"/><colspec colname="c5"/><colspec colname="c6"/><thead><row><entry></entry><entry><emphasis><function>push</function></emphasis></entry><entry><emphasis><function>pop</function></emphasis></entry><entry><emphasis><function>modify</function></emphasis></entry><entry><emphasis><function>erase</function></emphasis></entry><entry><emphasis><function>join</function></emphasis></entry></row></thead><tbody><row><entry><classname>std::priority_queue</classname></entry><entry>Θ(n) worstΘ(log(n)) amortized</entry><entry>Θ(log(n)) Worst</entry><entry>Θ(n log(n)) Worst<subscript>[std note 1]</subscript></entry><entry>Θ(n log(n))<subscript>[std note 2]</subscript></entry><entry>Θ(n log(n))<subscript>[std note 1]</subscript></entry></row><row><entry><classname>priority_queue</classname><<classname>Tag</classname> =<classname>pairing_heap_tag</classname>></entry><entry>O(1)</entry><entry>Θ(n) worstΘ(log(n)) amortized</entry><entry>Θ(n) worstΘ(log(n)) amortized</entry><entry>Θ(n) worstΘ(log(n)) amortized</entry><entry>O(1)</entry></row><row><entry><classname>priority_queue</classname><<classname>Tag</classname> =<classname>binary_heap_tag</classname>></entry><entry>Θ(n) worstΘ(log(n)) amortized</entry><entry>Θ(n) worstΘ(log(n)) amortized</entry><entry>Θ(n)</entry><entry>Θ(n)</entry><entry>Θ(n)</entry></row><row><entry><classname>priority_queue</classname><<classname>Tag</classname> =<classname>binomial_heap_tag</classname>></entry><entry>Θ(log(n)) worstO(1) amortized</entry><entry>Θ(log(n))</entry><entry>Θ(log(n))</entry><entry>Θ(log(n))</entry><entry>Θ(log(n))</entry></row><row><entry><classname>priority_queue</classname><<classname>Tag</classname> =<classname>rc_binomial_heap_tag</classname>></entry><entry>O(1)</entry><entry>Θ(log(n))</entry><entry>Θ(log(n))</entry><entry>Θ(log(n))</entry><entry>Θ(log(n))</entry></row><row><entry><classname>priority_queue</classname><<classname>Tag</classname> =<classname>thin_heap_tag</classname>></entry><entry>O(1)</entry><entry>Θ(n) worstΘ(log(n)) amortized</entry><entry>Θ(log(n)) worstO(1) amortized,or Θ(log(n)) amortized<subscript>[thin_heap_note]</subscript></entry><entry>Θ(n) worstΘ(log(n)) amortized</entry><entry>Θ(n)</entry></row></tbody></tgroup></informaltable><para>[std note 1] Thisis not a property of the algorithm, but rather due to the factthat the standard's priority queue implementation does not supportiterators (and consequently the ability to access a specificvalue inside it). If the priority queue is adapting an<classname>std::vector</classname>, then it is still possible to reduce thisto Θ(n) by adapting over the standard's adapter andusing the fact that <function>top</function> returns a reference to thefirst value; if, however, it is adapting an<classname>std::deque</classname>, then this is impossible.</para><para>[std note 2] Aswith [std note 1], this is not aproperty of the algorithm, but rather the standard's implementation.Again, if the priority queue is adapting an<classname>std::vector</classname> then it is possible to reduce this toΘ(n), but with a very high constant (one must call<function>std::make_heap</function> which is an expensive linearoperation); if the priority queue is adapting an<classname>std::deque</classname>, then this is impossible.</para><para>[thin_heap_note] A thin heap hasΘ(log(n)) worst case <function>modify</function> timealways, but the amortized time depends on the nature of theoperation: I) if the operation increases the key (in the senseof the priority queue's comparison functor), then the amortizedtime is O(1), but if II) it decreases it, then theamortized time is the same as the worst case time. Note thatfor most algorithms, I) is important and II) is not.</para></section><section xml:id="observations.priority_queue.amortized_ops"><info><title>Amortized <function>push</function>and <function>pop</function> operations</title></info><para>In many cases, a priority queue is needed primarily forsequences of <function>push</function> and <function>pop</function> operations. All ofthe underlying data structures have the same amortizedlogarithmic complexity, but they differ in terms ofconstants.</para><para>The table above shows that the different data structures are"constrained" in some respects. In general, if a data structurehas lower worst-case complexity than another, then it willperform slower in the amortized sense. Thus, for example aredundant-counter binomial heap (<classname>priority_queue</classname> with<classname>Tag</classname> = <classname>rc_binomial_heap_tag</classname>)has lower worst-case <function>push</function> performance than a binomialheap (<classname>priority_queue</classname>with <classname>Tag</classname> = <classname>binomial_heap_tag</classname>),and so its amortized <function>push</function> performance is slower interms of constants.</para><para>As the table shows, the "least constrained" underlyingdata structures are binary heaps and pairing heaps.Consequently, it is not surprising that they perform best interms of amortized constants.</para><orderedlist><listitem><para>Pairing heaps seem to perform best for non-primitivetypes (e.g., <classname>std::string</classname>s), as shown byPriorityQueue Text <function>push</function> Timing Test and PriorityQueue Text <function>push</function> and <function>pop</function> TimingTest</para></listitem><listitem><para>binary heaps seem to perform best for primitive types(e.g., <type>int</type>s), as shown by PriorityQueue Random Integer <function>push</function> Timing Test andPriorityQueue Random Integer <function>push</function> and <function>pop</function> TimingTest.</para></listitem></orderedlist></section><section xml:id="observations.priority_queue.graphs"><info><title>Graph Algorithms</title></info><para>In some graph algorithms, a decrease-key operation isrequired [clrs2001];this operation is identical to <function>modify</function> if a value isincreased (in the sense of the priority queue's comparisonfunctor). The table above and Priority QueueText <function>modify</function> Up Timing Test show that a thin heap(<classname>priority_queue</classname> with<classname>Tag</classname> = <classname>thin_heap_tag</classname>)outperforms a pairing heap (<classname>priority_queue</classname> with<classname>Tag</classname> = <classname>Tag</classname> = <classname>pairing_heap_tag</classname>),but the rest of the tests show otherwise.</para><para>This makes it difficult to decide which implementation to use inthis case. Dijkstra's shortest-path algorithm, for example, requiresΘ(n) <function>push</function> and <function>pop</function> operations(in the number of vertices), but O(n<superscript>2</superscript>)<function>modify</function> operations, which can be in practice Θ(n)as well. It is difficult to find an a-priori characterization ofgraphs in which the actual number of <function>modify</function>operations will dwarf the number of <function>push</function> and<function>pop</function> operations.</para></section></section> <!-- priority_queue --></section></section> <!-- performance --></section>