| <?xml version="1.0" encoding="UTF-8" standalone="no"?> |
| <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>Testing</title><meta name="generator" content="DocBook XSL-NS Stylesheets V1.78.1" /><meta name="keywords" content="ISO C++, policy, container, data, structure, associated, tree, trie, hash, metaprogramming" /><meta name="keywords" content="ISO C++, library" /><meta name="keywords" content="ISO C++, runtime, library" /><link rel="home" href="../index.html" title="The GNU C++ Library" /><link rel="up" href="policy_data_structures.html" title="Chapter 22. Policy-Based Data Structures" /><link rel="prev" href="policy_data_structures_design.html" title="Design" /><link rel="next" href="policy_data_structures_ack.html" title="Acknowledgments" /></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Testing</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="policy_data_structures_design.html">Prev</a> </td><th width="60%" align="center">Chapter 22. Policy-Based Data Structures</th><td width="20%" align="right"> <a accesskey="n" href="policy_data_structures_ack.html">Next</a></td></tr></table><hr /></div><div class="section"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="pbds.test"></a>Testing</h2></div></div></div><div class="section"><div class="titlepage"><div><div><h3 class="title"><a id="pbds.test.regression"></a>Regression</h3></div></div></div><p>The library contains a single comprehensive regression test. |
| For a given container type in this library, the test creates |
| an object of the container type and an object of the |
| corresponding standard type (e.g., <code class="classname">std::set</code>). It |
| then performs a random sequence of methods with random |
| arguments (e.g., inserts, erases, and so forth) on both |
| objects. At each operation, the test checks the return value of |
| the method, and optionally both compares this library's |
| object with the standard's object as well as performing other |
| consistency checks on this library's object (e.g., |
| order preservation, when applicable, or node invariants, when |
| applicable).</p><p>Additionally, the test integrally checks exception safety |
| and resource leaks. This is done as follows. A special |
| allocator type, written for the purpose of the test, both |
| randomly throws an exceptions when allocations are performed, |
| and tracks allocations and de-allocations. The exceptions thrown |
| at allocations simulate memory-allocation failures; the |
| tracking mechanism checks for memory-related bugs (e.g., |
| resource leaks and multiple de-allocations). Both |
| this library's containers and the containers' value-types are |
| configured to use this allocator.</p><p>For granularity, the test is split into the |
| several sources, each checking only some containers.</p><p>For more details, consult the files in |
| <code class="filename">testsuite/ext/pb_ds/regression</code>. |
| </p></div><div class="section"><div class="titlepage"><div><div><h3 class="title"><a id="pbds.test.performance"></a>Performance</h3></div></div></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="performance.hash"></a>Hash-Based</h4></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.hash.text_find"></a> |
| Text <code class="function">find</code> |
| </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="hash.text_find.info"></a> |
| Description |
| </h6></div></div></div><p> |
| This test inserts a number of values with keys from an |
| arbitrary text (<a class="xref" href="policy_data_structures.html#biblio.wickland96thirty" title="Thirty Years Among the Dead">[biblio.wickland96thirty]</a>) into a container, |
| then performs a series of finds using |
| <code class="function">find</code> . It measures the average |
| time for <code class="function">find</code> as a function of |
| the number of values inserted.</p><p> |
| It uses the test file: |
| <code class="filename">performance/ext/pb_ds/text_find_timing_test.cc</code> |
| </p><p> |
| And uses the data file: |
| <code class="filename">filethirty_years_among_the_dead_preproc.txt</code> |
| </p><p>The test checks the effect of different range-hashing |
| functions, trigger policies, and cache-hashing policies. |
| </p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="hash.text_find.results"></a> |
| Results |
| </h6></div></div></div><p>The graphic below show the results for the native |
| and collision-chaining hash types the the function |
| applied being a text find timing test using |
| <code class="function">find</code>. |
| </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_hash_text_find.png" align="middle" /></div></div><p> |
| The abbreviated names in the legend of the graphic above are |
| instantiated with the types in the following table. |
| </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="5" align="left"> |
| n_hash_map_ncah |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::tr1::unordered_map</code> |
| </td><td align="left"> |
| <code class="classname">cache_hash_code</code> |
| </td><td align="left"> |
| <code class="constant">false</code> |
| </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left"> |
| cc_hash_mod_prime_1div1_nsth_map |
| </td></tr><tr><td rowspan="3" align="left" valign="top"> |
| <code class="classname">cc_hash_table</code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mod_range_hashing</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_prime_size_policy</code> |
| </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/1 |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left"> |
| cc_hash_mask_exp_1div2_sth_map |
| </td></tr><tr><td rowspan="3" align="left" valign="top"> |
| <code class="classname"> |
| cc_hash_table |
| </code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mask_range_hashing</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_exponential_size_policy</code> |
| </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2 |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left"> |
| cc_hash_mask_exp_1div1_nsth_map |
| </td></tr><tr><td rowspan="3" align="left" valign="top"> |
| <code class="classname">cc_hash_table</code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mask_range_hashing</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_exponential_size_policy</code> |
| </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/1 |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left"> |
| cc_hash_mask_exp_1div2_nsth_map |
| </td></tr><tr><td rowspan="3" align="left" valign="top"> |
| <code class="classname">cc_hash_table</code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mask_range_hashing</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_exponential_size_policy</code> |
| </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2 |
| </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="hash.text_find.observations"></a> |
| Observations |
| </h6></div></div></div><p>In this setting, the range-hashing scheme affects performance |
| more than other policies. As the results show, containers using |
| mod-based range-hashing (including the native hash-based container, |
| which is currently hard-wired to this scheme) have lower performance |
| than those using mask-based range-hashing. A modulo-based |
| range-hashing scheme's main benefit is that it takes into account |
| all hash-value bits. Standard string hash-functions are designed to |
| create hash values that are nearly-uniform as is (<a class="xref" href="policy_data_structures.html#biblio.knuth98sorting" title="The Art of Computer Programming - Sorting and Searching">[biblio.knuth98sorting]</a>).</p><p>Trigger policies, i.e. the load-checks constants, affect |
| performance to a lesser extent.</p><p>Perhaps surprisingly, storing the hash value alongside each |
| entry affects performance only marginally, at least in this |
| library's implementation. (Unfortunately, it was not possible to run |
| the tests with <code class="classname">std::tr1::unordered_map</code> 's |
| <code class="classname">cache_hash_code = true</code> , as it appeared to |
| malfuntion.)</p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.hash.int_find"></a> |
| Integer <code class="function">find</code> |
| </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="hash.int_find.info"></a> |
| Description |
| </h6></div></div></div><p>This test inserts a number of values with uniform |
| integer keys into a container, then performs a series of finds |
| using <code class="function">find</code>. It measures the average time |
| for <code class="function">find</code> as a function of the number of values |
| inserted.</p><p> |
| It uses the test file: |
| <code class="filename">performance/ext/pb_ds/random_int_find_timing.cc</code> |
| </p><p>The test checks the effect of different underlying |
| hash-tables, |
| range-hashing functions, and trigger policies.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="hash.int_find.results"></a> |
| Results |
| </h6></div></div></div><p> |
| There are two sets of results for this type, one for |
| collision-chaining hashes, and one for general-probe hashes. |
| </p><p>The first graphic below shows the results for the native and |
| collision-chaining hash types. The function applied being a random |
| integer timing test using <code class="function">find</code>. |
| </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_cc_hash_int_find.png" align="middle" /></div></div><p> |
| The abbreviated names in the legend of the graphic above are |
| instantiated with the types in the following table. |
| </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="5" align="left"> |
| n_hash_map_ncah |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::tr1::unordered_map</code> |
| </td><td align="left"> |
| <code class="classname">cache_hash_code</code> |
| </td><td align="left"> |
| <code class="constant">false</code> |
| </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left"> |
| cc_hash_mod_prime_1div1_nsth_map |
| </td></tr><tr><td rowspan="3" align="left" valign="top"> |
| <code class="classname">cc_hash_table</code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mod_range_hashing</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_prime_size_policy</code> |
| </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/1 |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left"> |
| cc_hash_mod_prime_1div2_nsth_map |
| </td></tr><tr><td rowspan="3" align="left" valign="top"> |
| <code class="classname"> |
| cc_hash_table |
| </code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mod_range_hashing</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_prime_size_policy</code> |
| </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2 |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left"> |
| cc_hash_mask_exp_1div1_nsth_map |
| </td></tr><tr><td rowspan="3" align="left" valign="top"> |
| <code class="classname">cc_hash_table</code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mask_range_hashing</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_exponential_size_policy</code> |
| </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/1 |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left"> |
| cc_hash_mask_exp_1div2_nsth_map |
| </td></tr><tr><td rowspan="3" align="left" valign="top"> |
| <code class="classname">cc_hash_table</code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mask_range_hashing</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_exponential_size_policy</code> |
| </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2 |
| </td></tr></tbody></table></div><p> |
| </p><p> |
| </p><p>And the second graphic shows the results for the native and |
| general-probe hash types. The function applied being a random |
| integer timing test using <code class="function">find</code>. |
| </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_gp_hash_int_find.png" align="middle" /></div></div><p> |
| The abbreviated names in the legend of the graphic above are |
| instantiated with the types in the following table. |
| </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="5" align="left"> |
| n_hash_map_ncah |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::tr1::unordered_map</code> |
| </td><td align="left"> |
| <code class="classname">cache_hash_code</code> |
| </td><td align="left"> |
| <code class="constant">false</code> |
| </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left"> |
| gp_hash_mod_quadp_prime_1div2_nsth_map |
| </td></tr><tr><td rowspan="4" align="left" valign="top"> |
| <code class="classname">gp_hash_table</code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mod_range_hashing</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td align="left"> |
| <code class="classname">Probe_Fn</code> |
| </td><td align="left"> |
| <code class="classname">quadratic_probe_fn</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_prime_size_policy</code> |
| </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2 |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left"> |
| gp_hash_mask_linp_exp_1div2_nsth_map |
| </td></tr><tr><td rowspan="4" align="left" valign="top"> |
| <code class="classname"> |
| gp_hash_table |
| </code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mask_range_hashing</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td align="left"> |
| <code class="classname">Probe_Fn</code> |
| </td><td align="left"> |
| <code class="classname">linear_probe_fn</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_exponential_size_policy</code> |
| </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2 |
| </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="hash.int_find.observations"></a> |
| Observations |
| </h6></div></div></div><p>In this setting, the choice of underlying hash-table affects |
| performance most, then the range-hashing scheme and, only finally, |
| other policies.</p><p>When comparing probing and chaining containers, it is |
| apparent that the probing containers are less efficient than the |
| collision-chaining containers ( |
| <code class="classname">std::tr1::unordered_map</code> uses |
| collision-chaining) in this case.</p><p>Hash-Based Integer Subscript Insert Timing Test shows |
| a different case, where the situation is reversed; |
| </p><p>Within each type of hash-table, the range-hashing scheme |
| affects performance more than other policies; Hash-Based Text |
| <code class="function">find</code> Find Timing Test also shows this. In the |
| above graphics should be noted that |
| <code class="classname">std::tr1::unordered_map</code> are hard-wired |
| currently to mod-based schemes. |
| </p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.hash.int_subscript_find"></a> |
| Integer Subscript <code class="function">find</code> |
| </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="hash.int_subscript_find.info"></a> |
| Description |
| </h6></div></div></div><p>This test inserts a number of values with uniform |
| integer keys into a container, then performs a series of finds |
| using <code class="function">operator[]</code>. It measures the average time |
| for <code class="function">operator[]</code> as a function of the number of |
| values inserted.</p><p> |
| It uses the test file: |
| <code class="filename">performance/ext/pb_ds/random_int_subscript_find_timing.cc</code> |
| </p><p>The test checks the effect of different underlying |
| hash-tables, range-hashing functions, and trigger policies.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="hash.int_subscript_find.results"></a> |
| Results |
| </h6></div></div></div><p> |
| There are two sets of results for this type, one for |
| collision-chaining hashes, and one for general-probe hashes. |
| </p><p>The first graphic below shows the results for the native |
| and collision-chaining hash types, using as the function |
| applied an integer subscript timing test with |
| <code class="function">find</code>. |
| </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_cc_hash_int_subscript_find.png" align="middle" /></div></div><p> |
| The abbreviated names in the legend of the graphic above are |
| instantiated with the types in the following table. |
| </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="5" align="left"> |
| n_hash_map_ncah |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::tr1::unordered_map</code> |
| </td><td align="left"> |
| <code class="classname">cache_hash_code</code> |
| </td><td align="left"> |
| <code class="constant">false</code> |
| </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left"> |
| cc_hash_mod_prime_1div1_nsth_map |
| </td></tr><tr><td rowspan="3" align="left" valign="top"> |
| <code class="classname">cc_hash_table</code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mod_range_hashing</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_prime_size_policy</code> |
| </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/1 |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left"> |
| cc_hash_mod_prime_1div2_nsth_map |
| </td></tr><tr><td rowspan="3" align="left" valign="top"> |
| <code class="classname">cc_hash_table</code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mod_range_hashing</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_prime_size_policy</code> |
| </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2 |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left"> |
| cc_hash_mask_exp_1div1_nsth_map |
| </td></tr><tr><td rowspan="3" align="left" valign="top"> |
| <code class="classname">cc_hash_table</code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mask_range_hashing</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_exponential_size_policy</code> |
| </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/1 |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left"> |
| cc_hash_mask_exp_1div2_nsth_map |
| </td></tr><tr><td rowspan="3" align="left" valign="top"> |
| <code class="classname">cc_hash_table</code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mask_range_hashing</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_exponential_size_policy</code> |
| </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2 |
| </td></tr></tbody></table></div><p> |
| </p><p> |
| </p><p>And the second graphic shows the results for the native and |
| general-probe hash types. The function applied being a random |
| integer timing test using <code class="function">find</code>. |
| </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_gp_hash_int_subscript_find.png" align="middle" /></div></div><p> |
| The abbreviated names in the legend of the graphic above are |
| instantiated with the types in the following table. |
| </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="5" align="left"> |
| n_hash_map_ncah |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::tr1::unordered_map</code> |
| </td><td align="left"> |
| <code class="classname">cache_hash_code</code> |
| </td><td align="left"> |
| <code class="constant">false</code> |
| </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left"> |
| gp_hash_mod_quadp_prime_1div2_nsth_map |
| </td></tr><tr><td rowspan="4" align="left" valign="top"> |
| <code class="classname">gp_hash_table</code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mod_range_hashing</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td align="left"> |
| <code class="classname">Probe_Fn</code> |
| </td><td align="left"> |
| <code class="classname">quadratic_probe_fn</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_prime_size_policy</code> |
| </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2 |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left"> |
| gp_hash_mask_linp_exp_1div2_nsth_map |
| </td></tr><tr><td rowspan="4" align="left" valign="top"> |
| <code class="classname"> |
| gp_hash_table |
| </code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mask_range_hashing</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td align="left"> |
| <code class="classname">Probe_Fn</code> |
| </td><td align="left"> |
| <code class="classname">linear_probe_fn</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_exponential_size_policy</code> |
| </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2 |
| </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="hash.int_subscript_find.observations"></a> |
| Observations |
| </h6></div></div></div><p>This test shows similar results to Hash-Based |
| Integer <code class="classname">find</code> Find Timing test.</p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.hash.int_subscript_insert"></a> |
| Integer Subscript <code class="function">insert</code> |
| </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="hash.int_subscript_insert.info"></a> |
| Description |
| </h6></div></div></div><p>This test inserts a number of values with uniform i.i.d. |
| integer keys into a container, using |
| <code class="function">operator[]</code>. It measures the average time for |
| <code class="function">operator[]</code> as a function of the number of |
| values inserted.</p><p> |
| It uses the test file: |
| <code class="filename">performance/ext/pb_ds/random_int_subscript_insert_timing.cc</code> |
| </p><p>The test checks the effect of different underlying |
| hash-tables.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="hash.int_subscript_insert.results"></a> |
| Results |
| </h6></div></div></div><p> |
| There are two sets of results for this type, one for |
| collision-chaining hashes, and one for general-probe hashes. |
| </p><p>The first graphic below shows the results for the native |
| and collision-chaining hash types, using as the function |
| applied an integer subscript timing test with |
| <code class="function">insert</code>. |
| </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_cc_hash_int_subscript_insert.png" align="middle" /></div></div><p> |
| The abbreviated names in the legend of the graphic above are |
| instantiated with the types in the following table. |
| </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="5" align="left"> |
| n_hash_map_ncah |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::tr1::unordered_map</code> |
| </td><td align="left"> |
| <code class="classname">cache_hash_code</code> |
| </td><td align="left"> |
| <code class="constant">false</code> |
| </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left"> |
| cc_hash_mod_prime_1div1_nsth_map |
| </td></tr><tr><td rowspan="3" align="left" valign="top"> |
| <code class="classname">cc_hash_table</code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mod_range_hashing</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_prime_size_policy</code> |
| </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/1 |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left"> |
| cc_hash_mod_prime_1div2_nsth_map |
| </td></tr><tr><td rowspan="3" align="left" valign="top"> |
| <code class="classname">cc_hash_table</code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mod_range_hashing</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_prime_size_policy</code> |
| </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2 |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left"> |
| cc_hash_mask_exp_1div1_nsth_map |
| </td></tr><tr><td rowspan="3" align="left" valign="top"> |
| <code class="classname">cc_hash_table</code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mask_range_hashing</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_exponential_size_policy</code> |
| </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/1 |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left"> |
| cc_hash_mask_exp_1div2_nsth_map |
| </td></tr><tr><td rowspan="3" align="left" valign="top"> |
| <code class="classname">cc_hash_table</code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mask_range_hashing</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_exponential_size_policy</code> |
| </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2 |
| </td></tr></tbody></table></div><p> |
| </p><p> |
| </p><p>And the second graphic shows the results for the native and |
| general-probe hash types. The function applied being a random |
| integer timing test using <code class="function">find</code>. |
| </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_gp_hash_int_subscript_insert.png" align="middle" /></div></div><p> |
| The abbreviated names in the legend of the graphic above are |
| instantiated with the types in the following table. |
| </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="5" align="left"> |
| n_hash_map_ncah |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::tr1::unordered_map</code> |
| </td><td align="left"> |
| <code class="classname">cache_hash_code</code> |
| </td><td align="left"> |
| <code class="constant">false</code> |
| </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left"> |
| gp_hash_mod_quadp_prime_1div2_nsth_map |
| </td></tr><tr><td rowspan="4" align="left" valign="top"> |
| <code class="classname">gp_hash_table</code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mod_range_hashing</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td align="left"> |
| <code class="classname">Probe_Fn</code> |
| </td><td align="left"> |
| <code class="classname">quadratic_probe_fn</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_prime_size_policy</code> |
| </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2 |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left"> |
| gp_hash_mask_linp_exp_1div2_nsth_map |
| </td></tr><tr><td rowspan="4" align="left" valign="top"> |
| <code class="classname"> |
| gp_hash_table |
| </code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mask_range_hashing</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td align="left"> |
| <code class="classname">Probe_Fn</code> |
| </td><td align="left"> |
| <code class="classname">linear_probe_fn</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_exponential_size_policy</code> |
| </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2 |
| </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="hash.int_subscript_insert.observations"></a> |
| Observations |
| </h6></div></div></div><p>In this setting, as in Hash-Based Text |
| <code class="function">find</code> Find Timing test and Hash-Based |
| Integer <code class="function">find</code> Find Timing test , the choice |
| of underlying hash-table underlying hash-table affects performance |
| most, then the range-hashing scheme, and |
| finally any other policies.</p><p>There are some differences, however:</p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>In this setting, probing tables function sometimes more |
| efficiently than collision-chaining tables. |
| This is explained shortly.</p></li><li class="listitem"><p>The performance graphs have a "saw-tooth" shape. The |
| average insert time rises and falls. As values are inserted |
| into the container, the load factor grows larger. Eventually, |
| a resize occurs. The reallocations and rehashing are |
| relatively expensive. After this, the load factor is smaller |
| than before.</p></li></ol></div><p>Collision-chaining containers use indirection for greater |
| flexibility; probing containers store values contiguously, in |
| an array (see Figure Motivation::Different |
| underlying data structures A and B, respectively). It |
| follows that for simple data types, probing containers access |
| their allocator less frequently than collision-chaining |
| containers, (although they still have less efficient probing |
| sequences). This explains why some probing containers fare |
| better than collision-chaining containers in this case.</p><p> |
| Within each type of hash-table, the range-hashing scheme affects |
| performance more than other policies. This is similar to the |
| situation in Hash-Based Text |
| <code class="function">find</code> Find Timing Test and Hash-Based |
| Integer <code class="function">find</code> Find Timing Test. |
| Unsurprisingly, however, containers with lower α<sub>max</sub> perform worse in this case, |
| since more re-hashes are performed.</p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.hash.zlob_int_find"></a> |
| Integer <code class="function">find</code> with Skewed-Distribution |
| </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="hash.zlob_int_find.info"></a> |
| Description |
| </h6></div></div></div><p>This test inserts a number of values with a markedly |
| non-uniform integer keys into a container, then performs |
| a series of finds using <code class="function">find</code>. It measures the average |
| time for <code class="function">find</code> as a function of the number of values in |
| the containers. The keys are generated as follows. First, a |
| uniform integer is created. Then it is then shifted left 8 bits.</p><p> |
| It uses the test file: |
| <code class="filename">performance/ext/pb_ds/hash_zlob_random_int_find_timing.cc</code> |
| </p><p>The test checks the effect of different range-hashing |
| functions and trigger policies.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="hash.zlob_int_find.results"></a> |
| Results |
| </h6></div></div></div><p>The graphic below show the results for the native, collision-chaining, and general-probing hash types. |
| </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_hash_zlob_int_find.png" align="middle" /></div></div><p> |
| The abbreviated names in the legend of the graphic above are |
| instantiated with the types in the following table. |
| </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="5" align="left"> |
| n_hash_map_ncah |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::tr1::unordered_map</code> |
| </td><td align="left"> |
| <code class="classname">cache_hash_code</code> |
| </td><td align="left"> |
| <code class="constant">false</code> |
| </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left"> |
| cc_hash_mod_prime_1div1_nsth_map |
| </td></tr><tr><td rowspan="3" align="left" valign="top"> |
| <code class="classname">cc_hash_table</code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mod_range_hashing</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_prime_size_policy</code> |
| </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/1 |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left"> |
| cc_hash_mask_exp_1div1_nsth_map |
| </td></tr><tr><td rowspan="3" align="left" valign="top"> |
| <code class="classname"> |
| cc_hash_table |
| </code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mask_range_hashing</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_exponential_size_policy</code> |
| </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/1 |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left"> |
| gp_hash_mod_quadp_prime_1div2_nsth_map |
| </td></tr><tr><td rowspan="4" align="left" valign="top"> |
| <code class="classname">gp_hash_table</code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mod_range_hashing</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td align="left"> |
| <code class="classname">Probe_Fn</code> |
| </td><td align="left"> |
| <code class="classname">quadratic_probe_fn</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_prime_size_policy</code> |
| </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2 |
| </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="hash.zlob_int_find.observations"></a> |
| Observations |
| </h6></div></div></div><p>In this setting, the distribution of keys is so skewed that |
| the underlying hash-table type affects performance marginally. |
| (This is in contrast with Hash-Based Text |
| <code class="function">find</code> Find Timing Test, Hash-Based |
| Integer <code class="function">find</code> Find Timing Test, Hash-Based |
| Integer Subscript Find Timing Test and Hash-Based |
| Integer Subscript Insert Timing Test.)</p><p>The range-hashing scheme affects performance dramatically. A |
| mask-based range-hashing scheme effectively maps all values |
| into the same bucket. Access degenerates into a search within |
| an unordered linked-list. In the graphic above, it should be noted that |
| <code class="classname">std::tr1::unordered_map</code> is hard-wired currently to mod-based and mask-based schemes, |
| respectively.</p><p>When observing the settings of this test, it is apparent |
| that the keys' distribution is far from natural. One might ask |
| if the test is not contrived to show that, in some cases, |
| mod-based range hashing does better than mask-based range |
| hashing. This is, in fact just the case. A |
| more natural case in which mod-based range hashing is better was not encountered. |
| Thus the inescapable conclusion: real-life key distributions are handled better |
| with an appropriate hash function and a mask-based |
| range-hashing function. (<code class="filename">pb_ds/example/hash_shift_mask.cc</code> |
| shows an example of handling this a-priori known skewed |
| distribution with a mask-based range-hashing function). If hash |
| performance is bad, a χ<sup>2</sup> test can be used |
| to check how to transform it into a more uniform |
| distribution.</p><p>For this reason, this library's default range-hashing |
| function is mask-based.</p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.hash.erase_mem"></a> |
| Erase Memory Use |
| </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="hash.erase_mem.info"></a> |
| Description |
| </h6></div></div></div><p>This test inserts a number of uniform integer keys |
| into a container, then erases all keys except one. It measures |
| the final size of the container.</p><p> |
| It uses the test file: |
| <code class="filename">performance/ext/pb_ds/hash_random_int_erase_mem_usage.cc</code> |
| </p><p>The test checks how containers adjust internally as their |
| logical size decreases.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="hash.erase_mem.results"></a> |
| Results |
| </h6></div></div></div><p>The graphic below show the results for the native, collision-chaining, and general-probing hash types. |
| </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_hash_int_erase_mem.png" align="middle" /></div></div><p> |
| The abbreviated names in the legend of the graphic above are |
| instantiated with the types in the following table. |
| </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="5" align="left"> |
| n_hash_map_ncah |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::tr1::unordered_map</code> |
| </td><td align="left"> |
| <code class="classname">cache_hash_code</code> |
| </td><td align="left"> |
| <code class="constant">false</code> |
| </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left"> |
| cc_hash_mod_prime_1div1_nsth_map |
| </td></tr><tr><td rowspan="3" align="left" valign="top"> |
| <code class="classname">cc_hash_table</code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mod_range_hashing</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_prime_size_policy</code> |
| </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/1 |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left"> |
| cc_hash_mask_exp_1div2_nsth_map |
| </td></tr><tr><td rowspan="3" align="left" valign="top"> |
| <code class="classname"> |
| cc_hash_table |
| </code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mask_range_hashing</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_exponential_size_policy</code> |
| </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2 |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="5" align="left"> |
| gp_hash_mask_linp_exp_1div2_nsth_set |
| </td></tr><tr><td rowspan="4" align="left" valign="top"> |
| <code class="classname">gp_hash_table</code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mask_range_hashing</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td align="left"> |
| <code class="classname">Probe_Fn</code> |
| </td><td align="left"> |
| <code class="classname">linear_probe_fn</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_exponential_size_policy</code> |
| </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2 |
| </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="hash.erase_mem.observations"></a> |
| Observations |
| </h6></div></div></div><p>The standard's hash-based containers act very differently than trees in |
| this respect. When erasing numerous keys from an standard |
| associative-container, the resulting memory user varies greatly |
| depending on whether the container is tree-based or hash-based. |
| This is a fundamental consequence of the standard's interface for |
| associative containers, and it is not due to a specific |
| implementation.</p></div></div></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="performance.branch"></a>Branch-Based</h4></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.branch.text_insert"></a> |
| Text <code class="function">insert</code> |
| </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="branch.text_insert.info"></a> |
| Description |
| </h6></div></div></div><p>This test inserts a number of values with keys from an arbitrary |
| text ([ wickland96thirty ]) into a container |
| using <code class="function">insert</code> . It measures the average time |
| for <code class="function">insert</code> as a function of the number of |
| values inserted.</p><p>The test checks the effect of different underlying |
| data structures.</p><p> |
| It uses the test file: |
| <code class="filename">performance/ext/pb_ds/tree_text_insert_timing.cc</code> |
| </p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="branch.text_insert.results"></a> |
| Results |
| </h6></div></div></div><p>The three graphics below show the results for the native |
| tree and this library's node-based trees, the native tree and |
| this library's vector-based trees, and the native tree |
| and this library's PATRICIA-trie, respectively. |
| </p><p>The graphic immediately below shows the results for the |
| native tree type and several node-based tree types. |
| </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_tree_text_insert_node.png" align="middle" /></div><p> |
| The abbreviated names in the legend of the graphic above are |
| instantiated with the types in the following table. |
| </p></div><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| n_map |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::map</code> |
| </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| splay_tree_map |
| </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">tree</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">splay_tree_tag</code> |
| </td></tr><tr><td align="left"> |
| <code class="classname">Node_update</code> |
| </td><td align="left"> |
| <code class="classname">null_node_update</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| rb_tree_map |
| </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">tree</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">rb_tree_tag</code> |
| </td></tr><tr><td align="left"> |
| <code class="classname">Node_update</code> |
| </td><td align="left"> |
| <code class="classname">null_node_update</code> |
| </td></tr></tbody></table></div><p>The graphic below shows the results for the |
| native tree type and a vector-based tree type. |
| </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_tree_text_insert_vector.png" align="middle" /></div></div><p> |
| The abbreviated names in the legend of the graphic above are |
| instantiated with the types in the following table. |
| </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| n_map |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::map</code> |
| </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| ov_tree_map |
| </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">tree</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">ov_tree_tag</code> |
| </td></tr><tr><td align="left"> |
| <code class="classname">Node_update</code> |
| </td><td align="left"> |
| <code class="classname">null_node_update</code> |
| </td></tr></tbody></table></div><p>The graphic below shows the results for the |
| native tree type and a PATRICIA trie type. |
| </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_tree_text_insert_trie.png" align="middle" /></div></div><p> |
| The abbreviated names in the legend of the graphic above are |
| instantiated with the types in the following table. |
| </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| n_map |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::map</code> |
| </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| pat_trie_map |
| </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">tree</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">pat_trie_tag</code> |
| </td></tr><tr><td align="left"> |
| <code class="classname">Node_update</code> |
| </td><td align="left"> |
| <code class="classname">null_node_update</code> |
| </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="branch.text_insert.observations"></a> |
| Observations |
| </h6></div></div></div><p>Observing the first graphic implies that for this setting, a splay tree |
| (<code class="classname">tree</code> with <code class="classname">Tag |
| </code> = <code class="classname">splay_tree_tag</code>) does not do |
| well. See also the Branch-Based |
| Text <code class="function">find</code> Find Timing Test. The two |
| red-black trees perform better.</p><p>Observing the second graphic, an ordered-vector tree |
| (<code class="classname">tree</code> with <code class="classname">Tag |
| </code> = <code class="classname">ov_tree_tag</code>) performs |
| abysmally. Inserting into this type of tree has linear complexity |
| [ austern00noset].</p><p>Observing the third and last graphic, A PATRICIA trie |
| (<code class="classname">trie</code> with <code class="classname">Tag |
| </code> = <code class="classname">pat_trie_tag</code>) has abysmal |
| performance, as well. This is not that surprising, since a |
| large-fan-out PATRICIA trie works like a hash table with |
| collisions resolved by a sub-trie. Each time a collision is |
| encountered, a new "hash-table" is built A large fan-out PATRICIA |
| trie, however, doe does well in look-ups (see Branch-Based |
| Text <code class="function">find</code> Find Timing Test). It may be |
| beneficial in semi-static settings.</p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.branch.text_find"></a> |
| Text <code class="function">find</code> |
| </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="branch.text_find.info"></a> |
| Description |
| </h6></div></div></div><p>This test inserts a number of values with keys from an |
| arbitrary text ([wickland96thirty]) into |
| a container, then performs a series of finds using |
| <code class="function">find</code>. It measures the average time |
| for <code class="function">find</code> as a function of the number of |
| values inserted.</p><p> |
| It uses the test file: |
| <code class="filename">performance/ext/pb_ds/text_find_timing.cc</code> |
| </p><p>The test checks the effect of different underlying |
| data structures.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="branch.text_find.results"></a> |
| Results |
| </h6></div></div></div><p>The graphic immediately below shows the results for the |
| native tree type and several other tree types. |
| </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_tree_text_find.png" align="middle" /></div></div><p> |
| The abbreviated names in the legend of the graphic above are |
| instantiated with the types in the following table. |
| </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| n_map |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::map</code> |
| </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| splay_tree_map |
| </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">tree</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">splay_tree_tag</code> |
| </td></tr><tr><td align="left"> |
| <code class="classname">Node_Update</code> |
| </td><td align="left"> |
| <code class="classname">null_node_update</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| rb_tree_map |
| </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">tree</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">rb_tree_tag</code> |
| </td></tr><tr><td align="left"> |
| <code class="classname">Node_Update</code> |
| </td><td align="left"> |
| <code class="classname">null_node_update</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| ov_tree_map |
| </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">tree</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">ov_tree_tag</code> |
| </td></tr><tr><td align="left"> |
| <code class="classname">Node_Update</code> |
| </td><td align="left"> |
| <code class="classname">null_node_update</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| pat_trie_map |
| </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">tree</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">pat_trie_tag</code> |
| </td></tr><tr><td align="left"> |
| <code class="classname">Node_Update</code> |
| </td><td align="left"> |
| <code class="classname">null_node_update</code> |
| </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="branch.text_find.observations"></a> |
| Observations |
| </h6></div></div></div><p>For this setting, a splay tree (<code class="classname">tree</code> |
| with <code class="classname">Tag |
| </code> = <code class="classname">splay_tree_tag</code>) does not do |
| well. This is possibly due to two reasons:</p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>A splay tree is not guaranteed to be balanced [motwani95random]. If a |
| splay tree contains n nodes, its average root-leaf |
| path can be m >> log(n).</p></li><li class="listitem"><p>Assume a specific root-leaf search path has length |
| m, and the search-target node has distance m' |
| from the root. A red-black tree will require m + 1 |
| comparisons to find the required node; a splay tree will |
| require 2 m' comparisons. A splay tree, consequently, |
| can perform many more comparisons than a red-black tree.</p></li></ol></div><p>An ordered-vector tree (<code class="classname">tree</code> |
| with <code class="classname">Tag</code> = <code class="classname">ov_tree_tag</code>), a red-black |
| tree (<code class="classname">tree</code> |
| with <code class="classname">Tag</code> = <code class="classname">rb_tree_tag</code>), and the |
| native red-black tree all share approximately the same |
| performance.</p><p>An ordered-vector tree is slightly slower than red-black |
| trees, since it requires, in order to find a key, more math |
| operations than they do. Conversely, an ordered-vector tree |
| requires far lower space than the others. ([austern00noset], however, |
| seems to have an implementation that is also faster than a |
| red-black tree).</p><p>A PATRICIA trie (<code class="classname">trie</code> |
| with <code class="classname">Tag</code> = <code class="classname">pat_trie_tag</code>) has good |
| look-up performance, due to its large fan-out in this case. In |
| this setting, a PATRICIA trie has look-up performance comparable |
| to a hash table (see Hash-Based Text |
| <code class="classname">find</code> Timing Test), but it is order |
| preserving. This is not that surprising, since a large-fan-out |
| PATRICIA trie works like a hash table with collisions resolved |
| by a sub-trie. A large-fan-out PATRICIA trie does not do well on |
| modifications (see Tree-Based and Trie-Based |
| Text Insert Timing Test). Therefore, it is possibly beneficial in |
| semi-static settings.</p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.branch.text_lor_find"></a> |
| Text <code class="function">find</code> with Locality-of-Reference |
| </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="branch.text_lor_find.info"></a> |
| Description |
| </h6></div></div></div><p>This test inserts a number of values with keys from an |
| arbitrary text ([ wickland96thirty ]) into |
| a container, then performs a series of finds using |
| <code class="function">find</code>. It is different than Tree-Based and |
| Trie-Based Text <code class="function">find</code> Find Timing Test in the |
| sequence of finds it performs: this test performs multiple |
| <code class="function">find</code>s on the same key before moving on to the next |
| key. It measures the average time for <code class="function">find</code> as a |
| function of the number of values inserted.</p><p> |
| It uses the test file: |
| <code class="filename">performance/ext/pb_ds/tree_text_lor_find_timing.cc</code> |
| </p><p>The test checks the effect of different underlying |
| data structures in a locality-of-reference setting.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="branch.text_lor_find.results"></a> |
| Results |
| </h6></div></div></div><p>The graphic immediately below shows the results for the |
| native tree type and several other tree types. |
| </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_tree_text_lor_find.png" align="middle" /></div></div><p> |
| The abbreviated names in the legend of the graphic above are |
| instantiated with the types in the following table. |
| </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| n_map |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::map</code> |
| </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| splay_tree_map |
| </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">tree</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">splay_tree_tag</code> |
| </td></tr><tr><td align="left"> |
| <code class="classname">Node_Update</code> |
| </td><td align="left"> |
| <code class="classname">null_node_update</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| rb_tree_map |
| </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">tree</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">rb_tree_tag</code> |
| </td></tr><tr><td align="left"> |
| <code class="classname">Node_Update</code> |
| </td><td align="left"> |
| <code class="classname">null_node_update</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| ov_tree_map |
| </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">tree</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">ov_tree_tag</code> |
| </td></tr><tr><td align="left"> |
| <code class="classname">Node_Update</code> |
| </td><td align="left"> |
| <code class="classname">null_node_update</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| pat_trie_map |
| </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">tree</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">pat_trie_tag</code> |
| </td></tr><tr><td align="left"> |
| <code class="classname">Node_Update</code> |
| </td><td align="left"> |
| <code class="classname">null_node_update</code> |
| </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="branch.text_lor_find.observations"></a> |
| Observations |
| </h6></div></div></div><p>For this setting, an ordered-vector tree |
| (<code class="classname">tree</code> with <code class="classname">Tag</code> |
| = <code class="classname">ov_tree_tag</code>), a red-black tree |
| (<code class="classname">tree</code> with <code class="classname">Tag</code> |
| = <code class="classname">rb_tree_tag</code>), and the native red-black |
| tree all share approximately the same performance.</p><p>A splay tree (<code class="classname">tree</code> |
| with <code class="classname">Tag</code> = <code class="classname">splay_tree_tag</code>) does |
| much better, since each (successful) find "bubbles" the |
| corresponding node to the root of the tree.</p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.branch.split_join"></a> |
| <code class="function">split</code> and <code class="function">join</code> |
| </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="branch.split_join.info"></a> |
| Description |
| </h6></div></div></div><p>This test a container, inserts into a number of values, splits |
| the container at the median, and joins the two containers. (If the |
| containers are one of this library's trees, |
| it splits and joins with the <code class="function">split</code> and |
| <code class="function">join</code> method; otherwise, it uses the <code class="function">erase</code> and |
| <code class="function">insert</code> methods.) It measures the time for splitting |
| and joining the containers as a function of the number of |
| values inserted.</p><p> |
| It uses the test file: |
| <code class="filename">performance/ext/pb_ds/tree_split_join_timing.cc</code> |
| </p><p>The test checks the performance difference of <code class="function">join</code> |
| as opposed to a sequence of <code class="function">insert</code> operations; by |
| implication, this test checks the most efficient way to erase a |
| sub-sequence from a tree-like-based container, since this can |
| always be performed by a small sequence of splits and joins. |
| </p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="branch.split_join.results"></a> |
| Results |
| </h6></div></div></div><p>The graphic immediately below shows the results for the |
| native tree type and several other tree types. |
| </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_tree_split_join.png" align="middle" /></div></div><p> |
| The abbreviated names in the legend of the graphic above are |
| instantiated with the types in the following table. |
| </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| n_set |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::set</code> |
| </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| splay_tree_set |
| </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">tree</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">splay_tree_tag</code> |
| </td></tr><tr><td align="left"> |
| <code class="classname">Node_Update</code> |
| </td><td align="left"> |
| <code class="classname">null_node_update</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| rb_tree_set |
| </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">tree</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">rb_tree_tag</code> |
| </td></tr><tr><td align="left"> |
| <code class="classname">Node_Update</code> |
| </td><td align="left"> |
| <code class="classname">null_node_update</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| ov_tree_set |
| </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">tree</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">ov_tree_tag</code> |
| </td></tr><tr><td align="left"> |
| <code class="classname">Node_Update</code> |
| </td><td align="left"> |
| <code class="classname">null_node_update</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| pat_trie_map |
| </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">tree</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">pat_trie_tag</code> |
| </td></tr><tr><td align="left"> |
| <code class="classname">Node_Update</code> |
| </td><td align="left"> |
| <code class="classname">null_node_update</code> |
| </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="branch.split_join.observations"></a> |
| Observations |
| </h6></div></div></div><p>In this test, the native red-black trees must be split and |
| joined externally, through a sequence of <code class="function">erase</code> and |
| <code class="function">insert</code> operations. This is clearly |
| super-linear, and it is not that surprising that the cost is |
| high.</p><p>This library's tree-based containers use in this test the |
| <code class="function">split</code> and <code class="function">join</code> methods, |
| which have lower complexity: the <code class="function">join</code> method |
| of a splay tree (<code class="classname">tree</code> |
| with <code class="classname">Tag </code> |
| = <code class="classname">splay_tree_tag</code>) is quadratic in the |
| length of the longest root-leaf path, and linear in the total |
| number of elements; the <code class="function">join</code> method of a |
| red-black tree (<code class="classname">tree</code> |
| with <code class="classname">Tag </code> |
| = <code class="classname">rb_tree_tag</code>) or an ordered-vector tree |
| (<code class="classname">tree</code> with <code class="classname">Tag </code> |
| = <code class="classname">ov_tree_tag</code>) is linear in the number of |
| elements.</p><p>Asides from orders of growth, this library's trees access their |
| allocator very little in these operations, and some of them do not |
| access it at all. This leads to lower constants in their |
| complexity, and, for some containers, to exception-free splits and |
| joins (which can be determined |
| via <code class="classname">container_traits</code>).</p><p>It is important to note that <code class="function">split</code> and |
| <code class="function">join</code> are not esoteric methods - they are the most |
| efficient means of erasing a contiguous range of values from a |
| tree based container.</p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.branch.order_statistics"></a> |
| Order-Statistics |
| </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="branch.order_statistics.info"></a> |
| Description |
| </h6></div></div></div><p>This test creates a container, inserts random integers into the |
| the container, and then checks the order-statistics of the |
| container's values. (If the container is one of this |
| library's trees, it does this with |
| the <code class="function">order_of_key</code> method of |
| <code class="classname">tree_order_statistics_node_update</code> |
| ; otherwise, it uses the <code class="function">find</code> method and |
| <code class="function">std::distance</code>.) It measures the average |
| time for such queries as a function of the number of values |
| inserted.</p><p> |
| It uses the test file: |
| <code class="filename">performance/ext/pb_ds/tree_order_statistics_timing.cc</code> |
| </p><p>The test checks the performance difference of policies based |
| on node-invariant as opposed to a external functions.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="branch.order_statistics.results"></a> |
| Results |
| </h6></div></div></div><p>The graphic immediately below shows the results for the |
| native tree type and several other tree types. |
| </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_tree_order_statistics.png" align="middle" /></div></div><p> |
| The abbreviated names in the legend of the graphic above are |
| instantiated with the types in the following table. |
| </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| n_set |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::set</code> |
| </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| splay_tree_ost_set |
| </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">tree</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">splay_tree_tag</code> |
| </td></tr><tr><td align="left"> |
| <code class="classname">Node_Update</code> |
| </td><td align="left"> |
| <code class="classname">tree_order_statistics_node_update</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| rb_tree_ost_set |
| </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">tree</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">rb_tree_tag</code> |
| </td></tr><tr><td align="left"> |
| <code class="classname">Node_Update</code> |
| </td><td align="left"> |
| <code class="classname">tree_order_statistics_node_update</code> |
| </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="branch.order_statistics.observations"></a> |
| Observations |
| </h6></div></div></div><p>In this test, the native red-black tree can support |
| order-statistics queries only externally, by performing a |
| <code class="classname">find</code> (alternatively, <code class="classname">lower_bound</code> or |
| <code class="classname">upper_bound</code> ) and then using <code class="classname">std::distance</code> . |
| This is clearly linear, and it is not that surprising that the |
| cost is high.</p><p>This library's tree-based containers use in this test the |
| <code class="classname">order_of_key</code> method of <code class="classname">tree_order_statistics_node_update</code>. |
| This method has only linear complexity in the length of the |
| root-node path. Unfortunately, the average path of a splay tree |
| (<code class="classname">tree</code> |
| with <code class="classname">Tag =</code> <code class="classname">splay_tree_tag</code> ) can |
| be higher than logarithmic; the longest path of a red-black |
| tree (<code class="classname">tree</code> |
| with <code class="classname">Tag =</code> <code class="classname">rb_tree_tag</code> ) is |
| logarithmic in the number of elements. Consequently, the splay |
| tree has worse performance than the red-black tree.</p></div></div></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="performance.multimap"></a>Multimap</h4></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.multimap.text_find_small"></a> |
| Text <code class="function">find</code> with Small Secondary-to-Primary Key Ratios |
| </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_find_small.info"></a> |
| Description |
| </h6></div></div></div><p>This test inserts a number of pairs into a container. The |
| first item of each pair is a string from an arbitrary text |
| [wickland96thirty], and |
| the second is a uniform i.i.d.integer. The container is a |
| "multimap" - it considers the first member of each pair as a |
| primary key, and the second member of each pair as a secondary |
| key (see Motivation::Associative |
| Containers::Alternative to Multiple Equivalent Keys). There |
| are 400 distinct primary keys, and the ratio of secondary keys |
| to primary keys ranges from 1 to 5.</p><p>The test measures the average find-time as a function of the |
| number of values inserted. For this library's containers, it |
| finds the secondary key from a container obtained from finding |
| a primary key. For the native multimaps, it searches a range |
| obtained using <code class="classname">std::equal_range</code> on a primary key.</p><p> |
| It uses the test file: |
| <code class="filename">performance/ext/pb_ds/multimap_text_find_timing_small.cc</code> |
| </p><p>The test checks the find-time scalability of different |
| "multimap" designs.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_find_small.results"></a> |
| Results |
| </h6></div></div></div><p>The graphic below show the results for "multimaps" which |
| use a tree-based container for primary keys. |
| </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_multimap_text_find_small_s2p_tree.png" align="middle" /></div></div><p> |
| The abbreviated names in the legend of the graphic above are |
| instantiated with the types in the following table. |
| </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /><col align="left" class="c6" /><col align="left" class="c7" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="7" align="left"> |
| n_mmap |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::multimap</code> |
| </td><td colspan="6" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left"> |
| rb_tree_mmap_lu_mtf_set |
| </td></tr><tr><td rowspan="3" align="left" valign="top"> |
| <code class="classname">tree</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">rb_tree_tag</code> |
| </td><td colspan="4" align="left"> </td></tr><tr><td align="left"> |
| <code class="classname">Node_Update</code> |
| </td><td align="left"> |
| <code class="classname">null_node_update</code> |
| </td><td colspan="4" align="left"> </td></tr><tr><td align="left"> |
| <code class="classname">Mapped</code> |
| </td><td align="left"> |
| <code class="classname">list_update</code> |
| </td><td align="left"> |
| <code class="classname">Update_Policy</code> |
| </td><td align="left"> |
| <code class="classname">lu_move_to_front_policy</code> |
| </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left"> |
| rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set |
| </td></tr><tr><td rowspan="5" align="left" valign="top"> |
| <code class="classname">tree</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">rb_tree_tag</code> |
| </td><td colspan="4" align="left"> </td></tr><tr><td align="left"> |
| <code class="classname">Node_Update</code> |
| </td><td align="left"> |
| <code class="classname">null_node_update</code> |
| </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="3" align="left" valign="top"> |
| <code class="classname">Mapped</code> |
| </td><td rowspan="3" align="left" valign="top"> |
| <code class="classname">cc_hash_table</code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mask_range_hashing</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_exponential_size_policy</code> |
| </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2 |
| </td></tr></tbody></table></div><p>The graphic below show the results for "multimaps" which |
| use a hash-based container for primary keys. |
| </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_multimap_text_find_small_s2p_hash.png" align="middle" /></div></div><p> |
| The abbreviated names in the legend of the graphic above are |
| instantiated with the types in the following table. |
| </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /><col align="left" class="c6" /><col align="left" class="c7" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="7" align="left"> |
| n_hash_mmap |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::tr1::unordered_multimap</code> |
| </td><td colspan="6" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left"> |
| rb_tree_mmap_lu_mtf_set |
| </td></tr><tr><td rowspan="4" align="left" valign="top"> |
| <code class="classname"> |
| cc_hash_table |
| </code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mask_range_hashing</code> |
| </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_exponential_size_policy</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2 |
| </td><td colspan="2" align="left"> </td></tr><tr><td align="left"> |
| <code class="classname">Mapped</code> |
| </td><td align="left"> |
| <code class="classname">list_update</code> |
| </td><td align="left"> |
| <code class="classname">Update_Policy</code> |
| </td><td align="left"> |
| <code class="classname">lu_move_to_front_policy</code> |
| </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left"> |
| rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set |
| </td></tr><tr><td rowspan="6" align="left" valign="top"> |
| <code class="classname"> |
| cc_hash_table |
| </code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mask_range_hashing</code> |
| </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_exponential_size_policy</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2 |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="3" align="left" valign="top"> |
| <code class="classname">Mapped</code> |
| </td><td rowspan="3" align="left" valign="top"> |
| <code class="classname">cc_hash_table</code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mask_range_hashing</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_exponential_size_policy</code> |
| </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2 |
| </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_find_small.observations"></a> |
| Observations |
| </h6></div></div></div><p>See Observations::Mapping-Semantics |
| Considerations.</p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.multimap.text_find_large"></a> |
| Text <code class="function">find</code> with Large Secondary-to-Primary Key Ratios |
| </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_find_large.info"></a> |
| Description |
| </h6></div></div></div><p>This test inserts a number of pairs into a container. The |
| first item of each pair is a string from an arbitrary text |
| [wickland96thirty], and |
| the second is a uniform integer. The container is a |
| "multimap" - it considers the first member of each pair as a |
| primary key, and the second member of each pair as a secondary |
| key. There |
| are 400 distinct primary keys, and the ratio of secondary keys |
| to primary keys ranges from 1 to 5.</p><p>The test measures the average find-time as a function of the |
| number of values inserted. For this library's containers, it |
| finds the secondary key from a container obtained from finding |
| a primary key. For the native multimaps, it searches a range |
| obtained using <code class="classname">std::equal_range</code> on a primary key.</p><p> |
| It uses the test file: |
| <code class="filename">performance/ext/pb_ds/multimap_text_find_timing_large.cc</code> |
| </p><p>The test checks the find-time scalability of different |
| "multimap" designs.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_find_large.results"></a> |
| Results |
| </h6></div></div></div><p>The graphic below show the results for "multimaps" which |
| use a tree-based container for primary keys. |
| </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_multimap_text_find_large_s2p_tree.png" align="middle" /></div></div><p> |
| The abbreviated names in the legend of the graphic above are |
| instantiated with the types in the following table. |
| </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /><col align="left" class="c6" /><col align="left" class="c7" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="7" align="left"> |
| n_mmap |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::multimap</code> |
| </td><td colspan="6" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left"> |
| rb_tree_mmap_lu_mtf_set |
| </td></tr><tr><td rowspan="3" align="left" valign="top"> |
| <code class="classname">tree</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">rb_tree_tag</code> |
| </td><td colspan="4" align="left"> </td></tr><tr><td align="left"> |
| <code class="classname">Node_Update</code> |
| </td><td align="left"> |
| <code class="classname">null_node_update</code> |
| </td><td colspan="4" align="left"> </td></tr><tr><td align="left"> |
| <code class="classname">Mapped</code> |
| </td><td align="left"> |
| <code class="classname">list_update</code> |
| </td><td align="left"> |
| <code class="classname">Update_Policy</code> |
| </td><td align="left"> |
| <code class="classname">lu_move_to_front_policy</code> |
| </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left"> |
| rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set |
| </td></tr><tr><td rowspan="5" align="left" valign="top"> |
| <code class="classname">tree</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">rb_tree_tag</code> |
| </td><td colspan="4" align="left"> </td></tr><tr><td align="left"> |
| <code class="classname">Node_Update</code> |
| </td><td align="left"> |
| <code class="classname">null_node_update</code> |
| </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="3" align="left" valign="top"> |
| <code class="classname">Mapped</code> |
| </td><td rowspan="3" align="left" valign="top"> |
| <code class="classname">cc_hash_table</code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mask_range_hashing</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_exponential_size_policy</code> |
| </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2 |
| </td></tr></tbody></table></div><p>The graphic below show the results for "multimaps" which |
| use a hash-based container for primary keys. |
| </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_multimap_text_find_large_s2p_hash.png" align="middle" /></div></div><p> |
| The abbreviated names in the legend of the graphic above are |
| instantiated with the types in the following table. |
| </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /><col align="left" class="c6" /><col align="left" class="c7" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="7" align="left"> |
| n_hash_mmap |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::tr1::unordered_multimap</code> |
| </td><td colspan="6" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left"> |
| rb_tree_mmap_lu_mtf_set |
| </td></tr><tr><td rowspan="4" align="left" valign="top"> |
| <code class="classname"> |
| cc_hash_table |
| </code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mask_range_hashing</code> |
| </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_exponential_size_policy</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2 |
| </td><td colspan="2" align="left"> </td></tr><tr><td align="left"> |
| <code class="classname">Mapped</code> |
| </td><td align="left"> |
| <code class="classname">list_update</code> |
| </td><td align="left"> |
| <code class="classname">Update_Policy</code> |
| </td><td align="left"> |
| <code class="classname">lu_move_to_front_policy</code> |
| </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left"> |
| rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set |
| </td></tr><tr><td rowspan="6" align="left" valign="top"> |
| <code class="classname"> |
| cc_hash_table |
| </code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mask_range_hashing</code> |
| </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_exponential_size_policy</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2 |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="3" align="left" valign="top"> |
| <code class="classname">Mapped</code> |
| </td><td rowspan="3" align="left" valign="top"> |
| <code class="classname">cc_hash_table</code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mask_range_hashing</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_exponential_size_policy</code> |
| </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2 |
| </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_find_large.observations"></a> |
| Observations |
| </h6></div></div></div><p>See Observations::Mapping-Semantics |
| Considerations.</p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.multimap.text_insert_small"></a> |
| Text <code class="function">insert</code> with Small |
| Secondary-to-Primary Key Ratios |
| </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_small.info"></a> |
| Description |
| </h6></div></div></div><p>This test inserts a number of pairs into a container. The |
| first item of each pair is a string from an arbitrary text |
| [wickland96thirty], and |
| the second is a uniform integer. The container is a |
| "multimap" - it considers the first member of each pair as a |
| primary key, and the second member of each pair as a secondary |
| key. There |
| are 400 distinct primary keys, and the ratio of secondary keys |
| to primary keys ranges from 1 to 5.</p><p>The test measures the average insert-time as a function of |
| the number of values inserted. For this library's containers, |
| it inserts a primary key into the primary associative |
| container, then a secondary key into the secondary associative |
| container. For the native multimaps, it obtains a range using |
| <code class="classname">std::equal_range</code>, and inserts a value only if it was |
| not contained already.</p><p> |
| It uses the test file: |
| <code class="filename">performance/ext/pb_ds/multimap_text_insert_timing_small.cc</code> |
| </p><p>The test checks the insert-time scalability of different |
| "multimap" designs.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_small.results"></a> |
| Results |
| </h6></div></div></div><p>The graphic below show the results for "multimaps" which |
| use a tree-based container for primary keys. |
| </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_multimap_text_insert_small_s2p_tree.png" align="middle" /></div></div><p> |
| The abbreviated names in the legend of the graphic above are |
| instantiated with the types in the following table. |
| </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /><col align="left" class="c6" /><col align="left" class="c7" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="7" align="left"> |
| n_mmap |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::multimap</code> |
| </td><td colspan="6" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left"> |
| rb_tree_mmap_lu_mtf_set |
| </td></tr><tr><td rowspan="3" align="left" valign="top"> |
| <code class="classname">tree</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">rb_tree_tag</code> |
| </td><td colspan="4" align="left"> </td></tr><tr><td align="left"> |
| <code class="classname">Node_Update</code> |
| </td><td align="left"> |
| <code class="classname">null_node_update</code> |
| </td><td colspan="4" align="left"> </td></tr><tr><td align="left"> |
| <code class="classname">Mapped</code> |
| </td><td align="left"> |
| <code class="classname">list_update</code> |
| </td><td align="left"> |
| <code class="classname">Update_Policy</code> |
| </td><td align="left"> |
| <code class="classname">lu_move_to_front_policy</code> |
| </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left"> |
| rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set |
| </td></tr><tr><td rowspan="5" align="left" valign="top"> |
| <code class="classname">tree</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">rb_tree_tag</code> |
| </td><td colspan="4" align="left"> </td></tr><tr><td align="left"> |
| <code class="classname">Node_Update</code> |
| </td><td align="left"> |
| <code class="classname">null_node_update</code> |
| </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="3" align="left" valign="top"> |
| <code class="classname">Mapped</code> |
| </td><td rowspan="3" align="left" valign="top"> |
| <code class="classname">cc_hash_table</code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mask_range_hashing</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_exponential_size_policy</code> |
| </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2 |
| </td></tr></tbody></table></div><p>The graphic below show the results for "multimaps" which |
| use a hash-based container for primary keys. |
| </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_multimap_text_find_small_s2p_hash.png" align="middle" /></div></div><p> |
| The abbreviated names in the legend of the graphic above are |
| instantiated with the types in the following table. |
| </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /><col align="left" class="c6" /><col align="left" class="c7" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="7" align="left"> |
| n_hash_mmap |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::tr1::unordered_multimap</code> |
| </td><td colspan="6" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left"> |
| rb_tree_mmap_lu_mtf_set |
| </td></tr><tr><td rowspan="4" align="left" valign="top"> |
| <code class="classname"> |
| cc_hash_table |
| </code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mask_range_hashing</code> |
| </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_exponential_size_policy</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2 |
| </td><td colspan="2" align="left"> </td></tr><tr><td align="left"> |
| <code class="classname">Mapped</code> |
| </td><td align="left"> |
| <code class="classname">list_update</code> |
| </td><td align="left"> |
| <code class="classname">Update_Policy</code> |
| </td><td align="left"> |
| <code class="classname">lu_move_to_front_policy</code> |
| </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left"> |
| rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set |
| </td></tr><tr><td rowspan="6" align="left" valign="top"> |
| <code class="classname"> |
| cc_hash_table |
| </code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mask_range_hashing</code> |
| </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_exponential_size_policy</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2 |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="3" align="left" valign="top"> |
| <code class="classname">Mapped</code> |
| </td><td rowspan="3" align="left" valign="top"> |
| <code class="classname">cc_hash_table</code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mask_range_hashing</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_exponential_size_policy</code> |
| </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2 |
| </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_small.observations"></a> |
| Observations |
| </h6></div></div></div><p>See Observations::Mapping-Semantics |
| Considerations.</p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.multimap.text_insert_large"></a> |
| Text <code class="function">insert</code> with Small |
| Secondary-to-Primary Key Ratios |
| </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_large.info"></a> |
| Description |
| </h6></div></div></div><p>This test inserts a number of pairs into a container. The |
| first item of each pair is a string from an arbitrary text |
| [wickland96thirty], and |
| the second is a uniform integer. The container is a |
| "multimap" - it considers the first member of each pair as a |
| primary key, and the second member of each pair as a secondary |
| key. There |
| are 400 distinct primary keys, and the ratio of secondary keys |
| to primary keys ranges from 1 to 5.</p><p>The test measures the average insert-time as a function of |
| the number of values inserted. For this library's containers, |
| it inserts a primary key into the primary associative |
| container, then a secondary key into the secondary associative |
| container. For the native multimaps, it obtains a range using |
| <code class="classname">std::equal_range</code>, and inserts a value only if it was |
| not contained already.</p><p> |
| It uses the test file: |
| <code class="filename">performance/ext/pb_ds/multimap_text_insert_timing_large.cc</code> |
| </p><p>The test checks the insert-time scalability of different |
| "multimap" designs.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_large.results"></a> |
| Results |
| </h6></div></div></div><p>The graphic below show the results for "multimaps" which |
| use a tree-based container for primary keys. |
| </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_multimap_text_insert_large_s2p_tree.png" align="middle" /></div></div><p> |
| The abbreviated names in the legend of the graphic above are |
| instantiated with the types in the following table. |
| </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /><col align="left" class="c6" /><col align="left" class="c7" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="7" align="left"> |
| n_mmap |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::multimap</code> |
| </td><td colspan="6" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left"> |
| rb_tree_mmap_lu_mtf_set |
| </td></tr><tr><td rowspan="3" align="left" valign="top"> |
| <code class="classname">tree</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">rb_tree_tag</code> |
| </td><td colspan="4" align="left"> </td></tr><tr><td align="left"> |
| <code class="classname">Node_Update</code> |
| </td><td align="left"> |
| <code class="classname">null_node_update</code> |
| </td><td colspan="4" align="left"> </td></tr><tr><td align="left"> |
| <code class="classname">Mapped</code> |
| </td><td align="left"> |
| <code class="classname">list_update</code> |
| </td><td align="left"> |
| <code class="classname">Update_Policy</code> |
| </td><td align="left"> |
| <code class="classname">lu_move_to_front_policy</code> |
| </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left"> |
| rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set |
| </td></tr><tr><td rowspan="5" align="left" valign="top"> |
| <code class="classname">tree</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">rb_tree_tag</code> |
| </td><td colspan="4" align="left"> </td></tr><tr><td align="left"> |
| <code class="classname">Node_Update</code> |
| </td><td align="left"> |
| <code class="classname">null_node_update</code> |
| </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="3" align="left" valign="top"> |
| <code class="classname">Mapped</code> |
| </td><td rowspan="3" align="left" valign="top"> |
| <code class="classname">cc_hash_table</code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mask_range_hashing</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_exponential_size_policy</code> |
| </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2 |
| </td></tr></tbody></table></div><p>The graphic below show the results for "multimaps" which |
| use a hash-based container for primary keys. |
| </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_multimap_text_find_large_s2p_hash.png" align="middle" /></div></div><p> |
| The abbreviated names in the legend of the graphic above are |
| instantiated with the types in the following table. |
| </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /><col align="left" class="c6" /><col align="left" class="c7" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="7" align="left"> |
| n_hash_mmap |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::tr1::unordered_multimap</code> |
| </td><td colspan="6" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left"> |
| rb_tree_mmap_lu_mtf_set |
| </td></tr><tr><td rowspan="4" align="left" valign="top"> |
| <code class="classname"> |
| cc_hash_table |
| </code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mask_range_hashing</code> |
| </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_exponential_size_policy</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2 |
| </td><td colspan="2" align="left"> </td></tr><tr><td align="left"> |
| <code class="classname">Mapped</code> |
| </td><td align="left"> |
| <code class="classname">list_update</code> |
| </td><td align="left"> |
| <code class="classname">Update_Policy</code> |
| </td><td align="left"> |
| <code class="classname">lu_move_to_front_policy</code> |
| </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left"> |
| rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set |
| </td></tr><tr><td rowspan="6" align="left" valign="top"> |
| <code class="classname"> |
| cc_hash_table |
| </code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mask_range_hashing</code> |
| </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_exponential_size_policy</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2 |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="3" align="left" valign="top"> |
| <code class="classname">Mapped</code> |
| </td><td rowspan="3" align="left" valign="top"> |
| <code class="classname">cc_hash_table</code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mask_range_hashing</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_exponential_size_policy</code> |
| </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2 |
| </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_large.observations"></a> |
| Observations |
| </h6></div></div></div><p>See Observations::Mapping-Semantics |
| Considerations.</p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.multimap.text_insert_mem_small"></a> |
| Text <code class="function">insert</code> with Small |
| Secondary-to-Primary Key Ratios Memory Use |
| </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_mem_small.info"></a> |
| Description |
| </h6></div></div></div><p>This test inserts a number of pairs into a container. The |
| first item of each pair is a string from an arbitrary text |
| [wickland96thirty], and |
| the second is a uniform integer. The container is a |
| "multimap" - it considers the first member of each pair as a |
| primary key, and the second member of each pair as a secondary |
| key. There |
| are 100 distinct primary keys, and the ratio of secondary keys |
| to primary keys ranges to about 20.</p><p>The test measures the memory use as a function of the number |
| of values inserted.</p><p> |
| It uses the test file: |
| <code class="filename">performance/ext/pb_ds/multimap_text_insert_mem_usage_small.cc</code> |
| </p><p>The test checks the memory scalability of different |
| "multimap" designs.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_mem_small.results"></a> |
| Results |
| </h6></div></div></div><p>The graphic below show the results for "multimaps" which |
| use a tree-based container for primary keys. |
| </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_multimap_text_insert_mem_small_s2p_tree.png" align="middle" /></div></div><p> |
| The abbreviated names in the legend of the graphic above are |
| instantiated with the types in the following table. |
| </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /><col align="left" class="c6" /><col align="left" class="c7" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="7" align="left"> |
| n_mmap |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::multimap</code> |
| </td><td colspan="6" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left"> |
| rb_tree_mmap_lu_mtf_set |
| </td></tr><tr><td rowspan="3" align="left" valign="top"> |
| <code class="classname">tree</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">rb_tree_tag</code> |
| </td><td colspan="4" align="left"> </td></tr><tr><td align="left"> |
| <code class="classname">Node_Update</code> |
| </td><td align="left"> |
| <code class="classname">null_node_update</code> |
| </td><td colspan="4" align="left"> </td></tr><tr><td align="left"> |
| <code class="classname">Mapped</code> |
| </td><td align="left"> |
| <code class="classname">list_update</code> |
| </td><td align="left"> |
| <code class="classname">Update_Policy</code> |
| </td><td align="left"> |
| <code class="classname">lu_move_to_front_policy</code> |
| </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left"> |
| rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set |
| </td></tr><tr><td rowspan="5" align="left" valign="top"> |
| <code class="classname">tree</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">rb_tree_tag</code> |
| </td><td colspan="4" align="left"> </td></tr><tr><td align="left"> |
| <code class="classname">Node_Update</code> |
| </td><td align="left"> |
| <code class="classname">null_node_update</code> |
| </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="3" align="left" valign="top"> |
| <code class="classname">Mapped</code> |
| </td><td rowspan="3" align="left" valign="top"> |
| <code class="classname">cc_hash_table</code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mask_range_hashing</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_exponential_size_policy</code> |
| </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2 |
| </td></tr></tbody></table></div><p>The graphic below show the results for "multimaps" which |
| use a hash-based container for primary keys. |
| </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_multimap_text_find_large_s2p_hash.png" align="middle" /></div></div><p> |
| The abbreviated names in the legend of the graphic above are |
| instantiated with the types in the following table. |
| </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /><col align="left" class="c6" /><col align="left" class="c7" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="7" align="left"> |
| n_hash_mmap |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::tr1::unordered_multimap</code> |
| </td><td colspan="6" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left"> |
| rb_tree_mmap_lu_mtf_set |
| </td></tr><tr><td rowspan="4" align="left" valign="top"> |
| <code class="classname"> |
| cc_hash_table |
| </code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mask_range_hashing</code> |
| </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_exponential_size_policy</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2 |
| </td><td colspan="2" align="left"> </td></tr><tr><td align="left"> |
| <code class="classname">Mapped</code> |
| </td><td align="left"> |
| <code class="classname">list_update</code> |
| </td><td align="left"> |
| <code class="classname">Update_Policy</code> |
| </td><td align="left"> |
| <code class="classname">lu_move_to_front_policy</code> |
| </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left"> |
| rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set |
| </td></tr><tr><td rowspan="6" align="left" valign="top"> |
| <code class="classname"> |
| cc_hash_table |
| </code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mask_range_hashing</code> |
| </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_exponential_size_policy</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2 |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="3" align="left" valign="top"> |
| <code class="classname">Mapped</code> |
| </td><td rowspan="3" align="left" valign="top"> |
| <code class="classname">cc_hash_table</code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mask_range_hashing</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_exponential_size_policy</code> |
| </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2 |
| </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_mem_small.observations"></a> |
| Observations |
| </h6></div></div></div><p>See Observations::Mapping-Semantics |
| Considerations.</p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.multimap.text_insert_mem_large"></a> |
| Text <code class="function">insert</code> with Small |
| Secondary-to-Primary Key Ratios Memory Use |
| </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_mem_large.info"></a> |
| Description |
| </h6></div></div></div><p>This test inserts a number of pairs into a container. The |
| first item of each pair is a string from an arbitrary text |
| [wickland96thirty], and |
| the second is a uniform integer. The container is a |
| "multimap" - it considers the first member of each pair as a |
| primary key, and the second member of each pair as a secondary |
| key. There |
| are 100 distinct primary keys, and the ratio of secondary keys |
| to primary keys ranges to about 20.</p><p>The test measures the memory use as a function of the number |
| of values inserted.</p><p> |
| It uses the test file: |
| <code class="filename">performance/ext/pb_ds/multimap_text_insert_mem_usage_large.cc</code> |
| </p><p>The test checks the memory scalability of different |
| "multimap" designs.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_mem_large.results"></a> |
| Results |
| </h6></div></div></div><p>The graphic below show the results for "multimaps" which |
| use a tree-based container for primary keys. |
| </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_multimap_text_insert_mem_large_s2p_tree.png" align="middle" /></div></div><p> |
| The abbreviated names in the legend of the graphic above are |
| instantiated with the types in the following table. |
| </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /><col align="left" class="c6" /><col align="left" class="c7" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="7" align="left"> |
| n_mmap |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::multimap</code> |
| </td><td colspan="6" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left"> |
| rb_tree_mmap_lu_mtf_set |
| </td></tr><tr><td rowspan="3" align="left" valign="top"> |
| <code class="classname">tree</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">rb_tree_tag</code> |
| </td><td colspan="4" align="left"> </td></tr><tr><td align="left"> |
| <code class="classname">Node_Update</code> |
| </td><td align="left"> |
| <code class="classname">null_node_update</code> |
| </td><td colspan="4" align="left"> </td></tr><tr><td align="left"> |
| <code class="classname">Mapped</code> |
| </td><td align="left"> |
| <code class="classname">list_update</code> |
| </td><td align="left"> |
| <code class="classname">Update_Policy</code> |
| </td><td align="left"> |
| <code class="classname">lu_move_to_front_policy</code> |
| </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left"> |
| rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set |
| </td></tr><tr><td rowspan="5" align="left" valign="top"> |
| <code class="classname">tree</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">rb_tree_tag</code> |
| </td><td colspan="4" align="left"> </td></tr><tr><td align="left"> |
| <code class="classname">Node_Update</code> |
| </td><td align="left"> |
| <code class="classname">null_node_update</code> |
| </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="3" align="left" valign="top"> |
| <code class="classname">Mapped</code> |
| </td><td rowspan="3" align="left" valign="top"> |
| <code class="classname">cc_hash_table</code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mask_range_hashing</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_exponential_size_policy</code> |
| </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2 |
| </td></tr></tbody></table></div><p>The graphic below show the results for "multimaps" which |
| use a hash-based container for primary keys. |
| </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_multimap_text_find_large_s2p_hash.png" align="middle" /></div></div><p> |
| The abbreviated names in the legend of the graphic above are |
| instantiated with the types in the following table. |
| </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /><col align="left" class="c6" /><col align="left" class="c7" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="7" align="left"> |
| n_hash_mmap |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::tr1::unordered_multimap</code> |
| </td><td colspan="6" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left"> |
| rb_tree_mmap_lu_mtf_set |
| </td></tr><tr><td rowspan="4" align="left" valign="top"> |
| <code class="classname"> |
| cc_hash_table |
| </code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mask_range_hashing</code> |
| </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_exponential_size_policy</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2 |
| </td><td colspan="2" align="left"> </td></tr><tr><td align="left"> |
| <code class="classname">Mapped</code> |
| </td><td align="left"> |
| <code class="classname">list_update</code> |
| </td><td align="left"> |
| <code class="classname">Update_Policy</code> |
| </td><td align="left"> |
| <code class="classname">lu_move_to_front_policy</code> |
| </td><td colspan="2" align="left"> </td></tr><tr bgcolor="#B0B0B0"><td colspan="7" align="left"> |
| rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set |
| </td></tr><tr><td rowspan="6" align="left" valign="top"> |
| <code class="classname"> |
| cc_hash_table |
| </code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mask_range_hashing</code> |
| </td><td colspan="4" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_exponential_size_policy</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2 |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="3" align="left" valign="top"> |
| <code class="classname">Mapped</code> |
| </td><td rowspan="3" align="left" valign="top"> |
| <code class="classname">cc_hash_table</code> |
| </td><td align="left"> |
| <code class="classname">Comb_Hash_Fn</code> |
| </td><td align="left"> |
| <code class="classname">direct_mask_range_hashing</code> |
| </td><td colspan="2" align="left"> </td></tr><tr><td rowspan="2" align="left" valign="top"> |
| <code class="classname">Resize_Policy</code> |
| </td><td rowspan="2" align="left" valign="top"> |
| <code class="classname">hash_standard_resize_policy</code> |
| </td><td align="left"> |
| <code class="classname">Size_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_exponential_size_policy</code> |
| </td></tr><tr><td align="left" valign="top"> |
| <code class="classname">Trigger_Policy</code> |
| </td><td align="left"> |
| <code class="classname">hash_load_check_resize_trigger</code> with |
| α<sub>min</sub> = 1/8 and α<sub>max</sub> = 1/2 |
| </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_mem_large.observations"></a> |
| Observations |
| </h6></div></div></div><p>See Observations::Mapping-Semantics |
| Considerations.</p></div></div></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="performance.priority_queue"></a>Priority Queue</h4></div></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.priority_queue.text_push"></a> |
| Text <code class="function">push</code> |
| </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_push.info"></a> |
| Description |
| </h6></div></div></div><p>This test inserts a number of values with keys from an |
| arbitrary text ([ wickland96thirty ]) into |
| a container using <code class="function">push</code>. It measures the average time |
| for <code class="function">push</code> as a function of the number of values |
| pushed.</p><p> |
| It uses the test file: |
| <code class="filename">performance/ext/pb_ds/priority_queue_text_push_timing.cc</code> |
| </p><p>The test checks the effect of different underlying data |
| structures. |
| </p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_push.results"></a> |
| Results |
| </h6></div></div></div><p>The two graphics below show the results for the native |
| priority_queues and this library's priority_queues. |
| </p><p>The graphic immediately below shows the results for the |
| native priority_queue type instantiated with different underlying |
| container types versus several different versions of library's |
| priority_queues. |
| </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_priority_queue_text_push.png" align="middle" /></div></div><p> |
| The abbreviated names in the legend of the graphic above are |
| instantiated with the types in the following table. |
| </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| n_pq_vector |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Sequence</code> |
| </td><td align="left"> |
| <code class="classname">std::vector</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| n_pq_deque |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Sequence</code> |
| </td><td align="left"> |
| <code class="classname">std::deque</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| binary_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">binary_heap_tag</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| binomial_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">binomial_heap_tag</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| rc_binomial_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">rc_binomial_heap_tag</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| thin_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">thin_heap_tag</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| pairing_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">pairing_heap_tag</code> |
| </td></tr></tbody></table></div><p>The graphic below shows the results for the binary-heap |
| based native priority queues and this library's pairing-heap |
| priority_queue data structures. |
| </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_pairing_priority_queue_text_push.png" align="middle" /></div></div><p> |
| The abbreviated names in the legend of the graphic above are |
| instantiated with the types in the following table. |
| </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| n_pq_vector |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Sequence</code> |
| </td><td align="left"> |
| <code class="classname">std::vector</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| n_pq_deque |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Sequence</code> |
| </td><td align="left"> |
| <code class="classname">std::deque</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| thin_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">thin_heap_tag</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| pairing_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">pairing_heap_tag</code> |
| </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_push.observations"></a> |
| Observations |
| </h6></div></div></div><p>Pairing heaps (<code class="classname">priority_queue</code> with |
| <code class="classname">Tag</code> = <code class="classname">pairing_heap_tag</code>) |
| are the most suited for sequences of <code class="function">push</code> and |
| <code class="function">pop</code> operations of non-primitive types (e.g. |
| <code class="classname">std::string</code>s). (See Priority Queue |
| Text <code class="function">push</code> and <code class="function">pop</code> Timing Test.) They are |
| less constrained than binomial heaps, e.g., and since |
| they are node-based, they outperform binary heaps. (See |
| Priority |
| Queue Random Integer <code class="function">push</code> Timing Test for the case |
| of primitive types.)</p><p>The standard's priority queues do not seem to perform well in |
| this case: the <code class="classname">std::vector</code> implementation needs to |
| perform a logarithmic sequence of string operations for each |
| operation, and the deque implementation is possibly hampered by |
| its need to manipulate a relatively-complex type (deques |
| support a O(1) <code class="function">push_front</code>, even though it is |
| not used by <code class="classname">std::priority_queue</code>.)</p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.priority_queue.text_push_pop"></a> |
| Text <code class="function">push</code> and <code class="function">pop</code> |
| </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_push_pop.info"></a> |
| Description |
| </h6></div></div></div><p>This test inserts a number of values with keys from an |
| arbitrary text ([ wickland96thirty ]) into |
| a container using <code class="classname">push</code> , then removes them using |
| <code class="classname">pop</code> . It measures the average time for <code class="classname">push</code> |
| as a function of the number of values.</p><p> |
| It uses the test file: |
| <code class="filename">performance/ext/pb_ds/priority_queue_text_push_pop_timing.cc</code> |
| </p><p>The test checks the effect of different underlying data |
| structures. |
| </p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_push_pop.results"></a> |
| Results |
| </h6></div></div></div><p>The two graphics below show the results for the native |
| priority_queues and this library's priority_queues. |
| </p><p>The graphic immediately below shows the results for the |
| native priority_queue type instantiated with different underlying |
| container types versus several different versions of library's |
| priority_queues. |
| </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_priority_queue_text_push_pop.png" align="middle" /></div></div><p> |
| The abbreviated names in the legend of the graphic above are |
| instantiated with the types in the following table. |
| </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| n_pq_vector |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Sequence</code> |
| </td><td align="left"> |
| <code class="classname">std::vector</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| n_pq_deque |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Sequence</code> |
| </td><td align="left"> |
| <code class="classname">std::deque</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| binary_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">binary_heap_tag</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| binomial_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">binomial_heap_tag</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| rc_binomial_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">rc_binomial_heap_tag</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| thin_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">thin_heap_tag</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| pairing_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">pairing_heap_tag</code> |
| </td></tr></tbody></table></div><p>The graphic below shows the results for the native priority |
| queues and this library's pairing-heap priority_queue data |
| structures. |
| </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_pairing_priority_queue_text_push_pop.png" align="middle" /></div></div><p> |
| The abbreviated names in the legend of the graphic above are |
| instantiated with the types in the following table. |
| </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| n_pq_vector |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::priority_queue</code> adapting <code class="classname">std::vector</code> |
| </td><td align="left"> |
| <code class="classname">Sequence</code> |
| </td><td align="left"> |
| <code class="classname">std::vector</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| n_pq_deque |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Sequence</code> |
| </td><td align="left"> |
| <code class="classname">std::deque</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| pairing_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">pairing_heap_tag</code> |
| </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_push_pop.observations"></a> |
| Observations |
| </h6></div></div></div><p>These results are very similar to Priority Queue Text |
| <code class="function">push</code> Timing Test. As stated there, pairing heaps |
| (<code class="classname">priority_queue</code> with |
| <code class="classname">Tag</code> |
| = <code class="classname">pairing_heap_tag</code>) are most suited |
| for <code class="function">push</code> and <code class="function">pop</code> |
| sequences of non-primitive types such as strings. Observing these |
| two tests, one can note that a pairing heap outperforms the others |
| in terms of <code class="function">push</code> operations, but equals |
| binary heaps (<code class="classname">priority_queue</code> with |
| <code class="classname">Tag</code> |
| = <code class="classname">binary_heap_tag</code>) if the number |
| of <code class="function">push</code> and <code class="function">pop</code> |
| operations is equal. As the number of <code class="function">pop</code> |
| operations is at most equal to the number |
| of <code class="function">push</code> operations, pairing heaps are better |
| in this case. See Priority Queue Random |
| Integer <code class="function">push</code> and <code class="function">pop</code> |
| Timing Test for a case which is different.</p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.priority_queue.int_push"></a> |
| Integer <code class="function">push</code> |
| </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.int_push.info"></a> |
| Description |
| </h6></div></div></div><p>This test inserts a number of values with integer keys |
| into a container using <code class="function">push</code>. It |
| measures the average time for <code class="function">push</code> as a |
| function of the number of values.</p><p> |
| It uses the test file: |
| <code class="filename">performance/ext/pb_ds/priority_queue_random_int_push_timing.cc</code> |
| </p><p>The test checks the effect of different underlying data |
| structures. |
| </p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.int_push.results"></a> |
| Results |
| </h6></div></div></div><p>The two graphics below show the results for the native |
| priority_queues and this library's priority_queues. |
| </p><p>The graphic immediately below shows the results for the |
| native priority_queue type instantiated with different underlying |
| container types versus several different versions of library's |
| priority_queues. |
| </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_priority_queue_int_push.png" align="middle" /></div></div><p> |
| The abbreviated names in the legend of the graphic above are |
| instantiated with the types in the following table. |
| </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| n_pq_vector |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Sequence</code> |
| </td><td align="left"> |
| <code class="classname">std::vector</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| n_pq_deque |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Sequence</code> |
| </td><td align="left"> |
| <code class="classname">std::deque</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| binary_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">binary_heap_tag</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| binomial_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">binomial_heap_tag</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| rc_binomial_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">rc_binomial_heap_tag</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| thin_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">thin_heap_tag</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| pairing_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">pairing_heap_tag</code> |
| </td></tr></tbody></table></div><p>The graphic below shows the results for the binary-heap |
| based native priority queues and this library's |
| priority_queue data structures. |
| </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_binary_priority_queue_int_push.png" align="middle" /></div></div><p> |
| The abbreviated names in the legend of the graphic above are |
| instantiated with the types in the following table. |
| </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| n_pq_vector |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::priority_queue</code> adapting <code class="classname">std::vector</code> |
| </td><td align="left"> |
| <code class="classname">Sequence</code> |
| </td><td align="left"> |
| <code class="classname">std::vector</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| n_pq_deque |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Sequence</code> |
| </td><td align="left"> |
| <code class="classname">std::deque</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| binary_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">binary_heap_tag</code> |
| </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.int_push.observations"></a> |
| Observations |
| </h6></div></div></div><p>Binary heaps are the most suited for sequences of |
| <code class="function">push</code> and <code class="function">pop</code> operations of primitive types |
| (e.g. <span class="type">int</span>s). They are less constrained |
| than any other type, and since it is very efficient to store |
| such types in arrays, they outperform even pairing heaps. (See |
| Priority |
| Queue Text <code class="function">push</code> Timing Test for the case of |
| non-primitive types.)</p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.priority_queue.int_push_pop"></a> |
| Integer <code class="function">push</code> |
| </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.int_push_pop.info"></a> |
| Description |
| </h6></div></div></div><p>This test inserts a number of values with integer keys |
| into a container using <code class="function">push</code> , then removes them |
| using <code class="function">pop</code> . It measures the average time for |
| <code class="function">push</code> and <code class="function">pop</code> as a function |
| of the number of values.</p><p> |
| It uses the test file: |
| <code class="filename">performance/ext/pb_ds/priority_queue_random_int_push_pop_timing.cc</code> |
| </p><p>The test checks the effect of different underlying data |
| structures. |
| </p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.int_push_pop.results"></a> |
| Results |
| </h6></div></div></div><p>The graphic immediately below shows the results for the |
| native priority_queue type instantiated with different underlying |
| container types versus several different versions of library's |
| priority_queues. |
| </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_priority_queue_int_push_pop.png" align="middle" /></div></div><p> |
| The abbreviated names in the legend of the graphic above are |
| instantiated with the types in the following table. |
| </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| n_pq_vector |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Sequence</code> |
| </td><td align="left"> |
| <code class="classname">std::vector</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| n_pq_deque |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Sequence</code> |
| </td><td align="left"> |
| <code class="classname">std::deque</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| binary_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">binary_heap_tag</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| binomial_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">binomial_heap_tag</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| rc_binomial_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">rc_binomial_heap_tag</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| thin_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">thin_heap_tag</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| pairing_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">pairing_heap_tag</code> |
| </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.int_push_pop.observations"></a> |
| Observations |
| </h6></div></div></div><p>Binary heaps are the most suited for sequences of |
| <code class="function">push</code> and <code class="function">pop</code> operations of primitive types |
| (e.g. <span class="type">int</span>s). This is explained in |
| Priority |
| Queue Random Int <code class="function">push</code> Timing Test. (See Priority Queue |
| Text <code class="function">push</code> Timing Test for the case of primitive |
| types.)</p><p>At first glance it seems that the standard's vector-based |
| priority queue is approximately on par with this |
| library's corresponding priority queue. There are two |
| differences however:</p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>The standard's priority queue does not downsize the underlying |
| vector (or deque) as the priority queue becomes smaller |
| (see Priority Queue |
| Text <code class="function">pop</code> Memory Use Test). It is therefore |
| gaining some speed at the expense of space.</p></li><li class="listitem"><p>From Priority Queue Random |
| Integer <code class="function">push</code> and <code class="function">pop</code> |
| Timing Test, it seems that the standard's priority queue is |
| slower in terms of <code class="function">push</code> operations. Since |
| the number of |
| <code class="function">pop</code> operations is at most that of <code class="function">push</code> |
| operations, the test here is the "best" for the standard's |
| priority queue.</p></li></ol></div></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.priority_queue.text_pop"></a> |
| Text <code class="function">pop</code> Memory Use |
| </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_pop.info"></a> |
| Description |
| </h6></div></div></div><p>This test inserts a number of values with keys from an |
| arbitrary text ([ wickland96thirty ]) into |
| a container, then pops them until only one is left in the |
| container. It measures the memory use as a function of the |
| number of values pushed to the container.</p><p> |
| It uses the test file: |
| <code class="filename">performance/ext/pb_ds/priority_queue_text_pop_mem_usage.cc</code> |
| </p><p>The test checks the effect of different underlying data |
| structures. |
| </p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_pop.results"></a> |
| Results |
| </h6></div></div></div><p>The graphic immediately below shows the results for the |
| native priority_queue type instantiated with different underlying |
| container types versus several different versions of library's |
| priority_queues. |
| </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_priority_queue_text_pop_mem.png" align="middle" /></div></div><p> |
| The abbreviated names in the legend of the graphic above are |
| instantiated with the types in the following table. |
| </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| n_pq_vector |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Sequence</code> |
| </td><td align="left"> |
| <code class="classname">std::vector</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| n_pq_deque |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Sequence</code> |
| </td><td align="left"> |
| <code class="classname">std::deque</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| binary_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">binary_heap_tag</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| binomial_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">binomial_heap_tag</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| rc_binomial_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">rc_binomial_heap_tag</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| thin_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">thin_heap_tag</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| pairing_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">pairing_heap_tag</code> |
| </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_pop.observations"></a> |
| Observations |
| </h6></div></div></div><p>The priority queue implementations (excluding the standard's) use |
| memory proportionally to the number of values they hold: |
| node-based implementations (e.g., a pairing heap) do so |
| naturally; this library's binary heap de-allocates memory when |
| a certain lower threshold is exceeded.</p><p>Note from Priority Queue Text <code class="function">push</code> |
| and <code class="function">pop</code> Timing Test and Priority Queue |
| Random Integer <code class="function">push</code> |
| and <code class="function">pop</code> Timing Test that this does not |
| impede performance compared to the standard's priority |
| queues.</p><p>See Hash-Based Erase |
| Memory Use Test for a similar phenomenon regarding priority |
| queues.</p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.priority_queue.text_join"></a> |
| Text <code class="function">join</code> |
| </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_join.info"></a> |
| Description |
| </h6></div></div></div><p>This test inserts a number of values with keys from an |
| arbitrary text ([ wickland96thirty ]) into |
| two containers, then merges the containers. It uses |
| <code class="function">join</code> for this library's priority queues; for |
| the standard's priority queues, it successively pops values from |
| one container and pushes them into the other. The test measures |
| the average time as a function of the number of values.</p><p> |
| It uses the test file: |
| <code class="filename">performance/ext/pb_ds/priority_queue_text_join_timing.cc</code> |
| </p><p>The test checks the effect of different underlying data |
| structures. |
| </p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_join.results"></a> |
| Results |
| </h6></div></div></div><p>The graphic immediately below shows the results for the |
| native priority_queue type instantiated with different underlying |
| container types versus several different versions of library's |
| priority_queues. |
| </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_priority_queue_text_join.png" align="middle" /></div></div><p> |
| The abbreviated names in the legend of the graphic above are |
| instantiated with the types in the following table. |
| </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| n_pq_vector |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Sequence</code> |
| </td><td align="left"> |
| <code class="classname">std::vector</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| n_pq_deque |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Sequence</code> |
| </td><td align="left"> |
| <code class="classname">std::deque</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| binary_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">binary_heap_tag</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| binomial_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">binomial_heap_tag</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| rc_binomial_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">rc_binomial_heap_tag</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| thin_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">thin_heap_tag</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| pairing_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">pairing_heap_tag</code> |
| </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_join.observations"></a> |
| Observations |
| </h6></div></div></div><p>In this test the node-based heaps perform <code class="function">join</code> in |
| either logarithmic or constant time. The binary heap requires |
| linear time, since the well-known heapify algorithm [clrs2001] is linear.</p><p>It would be possible to apply the heapify algorithm to the |
| standard containers, if they would support iteration (which they |
| don't). Barring iterators, it is still somehow possible to perform |
| linear-time merge on a <code class="classname">std::vector</code>-based |
| standard priority queue, using <code class="function">top()</code> |
| and <code class="function">size()</code> (since they are enough to expose |
| the underlying array), but this is impossible for |
| a <code class="classname">std::deque</code>-based standard priority queue. |
| Without heapify, the cost is super-linear.</p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.priority_queue.text_modify_up"></a> |
| Text <code class="function">modify</code> Up |
| </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_modify_up.info"></a> |
| Description |
| </h6></div></div></div><p>This test inserts a number of values with keys from an |
| arbitrary text ([ wickland96thirty ]) into |
| into a container then modifies each one "up" (i.e., it |
| makes it larger). It uses <code class="function">modify</code> for this library's |
| priority queues; for the standard's priority queues, it pops values |
| from a container until it reaches the value that should be |
| modified, then pushes values back in. It measures the average |
| time for <code class="function">modify</code> as a function of the number of |
| values.</p><p> |
| It uses the test file: |
| <code class="filename">performance/ext/pb_ds/priority_queue_text_modify_up_timing.cc</code> |
| </p><p>The test checks the effect of different underlying data |
| structures for graph algorithms settings. Note that making an |
| arbitrary value larger (in the sense of the priority queue's |
| comparison functor) corresponds to decrease-key in standard graph |
| algorithms [clrs2001]. |
| </p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_modify_up.results"></a> |
| Results |
| </h6></div></div></div><p>The two graphics below show the results for the native |
| priority_queues and this library's priority_queues. |
| </p><p>The graphic immediately below shows the results for the |
| native priority_queue type instantiated with different underlying |
| container types versus several different versions of library's |
| priority_queues. |
| </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_priority_queue_text_modify_up.png" align="middle" /></div></div><p> |
| The abbreviated names in the legend of the graphic above are |
| instantiated with the types in the following table. |
| </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| n_pq_vector |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Sequence</code> |
| </td><td align="left"> |
| <code class="classname">std::vector</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| n_pq_deque |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Sequence</code> |
| </td><td align="left"> |
| <code class="classname">std::deque</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| binary_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">binary_heap_tag</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| binomial_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">binomial_heap_tag</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| rc_binomial_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">rc_binomial_heap_tag</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| thin_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">thin_heap_tag</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| pairing_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">pairing_heap_tag</code> |
| </td></tr></tbody></table></div><p>The graphic below shows the results for the |
| native priority queues and this library's pairing and thin heap |
| priority_queue data structures. |
| </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_pairing_priority_queue_text_modify_up_thin.png" align="middle" /></div></div><p> |
| The abbreviated names in the legend of the graphic above are |
| instantiated with the types in the following table. |
| </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| thin_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">thin_heap_tag</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| pairing_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">pairing_heap_tag</code> |
| </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_modify_up.observations"></a> |
| Observations |
| </h6></div></div></div><p>As noted above, increasing an arbitrary value (in the sense of |
| the priority queue's comparison functor) is very common in |
| graph-related algorithms. In this case, a thin heap |
| (<code class="classname">priority_queue</code> with |
| <code class="classname">Tag</code> = <code class="classname">thin_heap_tag</code>) |
| outperforms a pairing heap (<code class="classname">priority_queue</code> with |
| <code class="classname">Tag</code> = <code class="classname">pairing_heap_tag</code>). |
| Conversely, Priority Queue Text |
| <code class="function">push</code> Timing Test, Priority Queue |
| Text <code class="function">push</code> and <code class="function">pop</code> Timing Test, Priority |
| Queue Random Integer <code class="function">push</code> Timing Test, and |
| Priority |
| Queue Random Integer <code class="function">push</code> and <code class="function">pop</code> Timing |
| Test show that the situation is reversed for other |
| operations. It is not clear when to prefer one of these two |
| different types.</p><p>In this test this library's binary heaps |
| effectively perform modify in linear time. As explained in |
| Priority Queue Design::Traits, given a valid point-type iterator, |
| a binary heap can perform |
| <code class="function">modify</code> logarithmically. The problem is that binary |
| heaps invalidate their find iterators with each modifying |
| operation, and so the only way to obtain a valid point-type |
| iterator is to iterate using a range-type iterator until |
| finding the appropriate value, then use the range-type iterator |
| for the <code class="function">modify</code> operation.</p><p>The explanation for the standard's priority queues' performance |
| is similar to that in Priority Queue Text |
| <code class="function">join</code> Timing Test.</p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="performance.priority_queue.text_modify_down"></a> |
| Text <code class="function">modify</code> Down |
| </h5></div></div></div><p></p><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_modify_down.info"></a> |
| Description |
| </h6></div></div></div><p>This test inserts a number of values with keys from an |
| arbitrary text ([ wickland96thirty ]) into |
| into a container then modifies each one "down" (i.e., it |
| makes it smaller). It uses <code class="function">modify</code> for this library's |
| priority queues; for the standard's priority queues, it pops values |
| from a container until it reaches the value that should be |
| modified, then pushes values back in. It measures the average |
| time for <code class="function">modify</code> as a function of the number of |
| values.</p><p> |
| It uses the test file: |
| <code class="filename">performance/ext/pb_ds/priority_queue_text_modify_down_timing.cc</code> |
| </p><p>The main purpose of this test is to contrast Priority Queue |
| Text <code class="classname">modify</code> Up Timing Test.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_modify_down.results"></a> |
| Results |
| </h6></div></div></div><p>The two graphics below show the results for the native |
| priority_queues and this library's priority_queues. |
| </p><p>The graphic immediately below shows the results for the |
| native priority_queue type instantiated with different underlying |
| container types versus several different versions of library's |
| priority_queues. |
| </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_priority_queue_text_modify_down.png" align="middle" /></div></div><p> |
| The abbreviated names in the legend of the graphic above are |
| instantiated with the types in the following table. |
| </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| n_pq_vector |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Sequence</code> |
| </td><td align="left"> |
| <code class="classname">std::vector</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| n_pq_deque |
| </td></tr><tr><td align="left"> |
| <code class="classname">std::priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Sequence</code> |
| </td><td align="left"> |
| <code class="classname">std::deque</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| binary_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">binary_heap_tag</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| binomial_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">binomial_heap_tag</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| rc_binomial_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">rc_binomial_heap_tag</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| thin_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">thin_heap_tag</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| pairing_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">pairing_heap_tag</code> |
| </td></tr></tbody></table></div><p>The graphic below shows the results for the |
| native priority queues and this library's pairing and thin heap |
| priority_queue data structures. |
| </p><div class="informalfigure"><div class="mediaobject" align="center"><img src="../images/pbds_pairing_priority_queue_text_modify_down_thin.png" align="middle" /></div></div><p> |
| The abbreviated names in the legend of the graphic above are |
| instantiated with the types in the following table. |
| </p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /></colgroup><thead><tr><th align="left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th align="left"><span class="emphasis"><em>Parameter</em></span></th><th align="left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| thin_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">thin_heap_tag</code> |
| </td></tr><tr bgcolor="#B0B0B0"><td colspan="3" align="left"> |
| pairing_heap |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| </td><td align="left"> |
| <code class="classname">Tag</code> |
| </td><td align="left"> |
| <code class="classname">pairing_heap_tag</code> |
| </td></tr></tbody></table></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_modify_down.observations"></a> |
| Observations |
| </h6></div></div></div><p>Most points in these results are similar to Priority Queue |
| Text <code class="function">modify</code> Up Timing Test.</p><p>It is interesting to note, however, that as opposed to that |
| test, a thin heap (<code class="classname">priority_queue</code> with |
| <code class="classname">Tag</code> = <code class="classname">thin_heap_tag</code>) is |
| outperformed by a pairing heap (<code class="classname">priority_queue</code> with |
| <code class="classname">Tag</code> = <code class="classname">pairing_heap_tag</code>). |
| In this case, both heaps essentially perform an <code class="function">erase</code> |
| operation followed by a <code class="function">push</code> operation. As the other |
| tests show, a pairing heap is usually far more efficient than a |
| thin heap, so this is not surprising.</p><p>Most algorithms that involve priority queues increase values |
| (in the sense of the priority queue's comparison functor), and |
| so Priority Queue |
| Text <code class="classname">modify</code> Up Timing Test - is more interesting |
| than this test.</p></div></div></div><div class="section"><div class="titlepage"><div><div><h4 class="title"><a id="pbds.test.performance.observations"></a>Observations</h4></div></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="observations.associative"></a>Associative</h5></div></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="observations.associative.underlying"></a> |
| Underlying Data-Structure Families |
| </h6></div></div></div><p>In general, hash-based containers have better timing performance |
| than containers based on different underlying-data structures. The |
| main reason to choose a tree-based or trie-based container is if a |
| byproduct of the tree-like structure is required: either |
| order-preservation, or the ability to utilize node invariants. If |
| memory-use is the major factor, an ordered-vector tree gives |
| optimal results (albeit with high modificiation costs), and a |
| list-based container gives reasonable results.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="observations.associative.hash"></a> |
| Hash-Based Containers |
| </h6></div></div></div><p>Hash-based containers are typically either collision |
| chaining or probing. Collision-chaining |
| containers are more flexible internally, and so offer better |
| timing performance. Probing containers, if used for simple |
| value-types, manage memory more efficiently (they perform far |
| fewer allocation-related calls). In general, therefore, a |
| collision-chaining table should be used. A probing container, |
| conversely, might be used efficiently for operations such as |
| eliminating duplicates in a sequence, or counting the number of |
| occurrences within a sequence. Probing containers might be more |
| useful also in multithreaded applications where each thread |
| manipulates a hash-based container: in the standard, allocators have |
| class-wise semantics (see [meyers96more] - Item 10); a |
| probing container might incur less contention in this case.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="observations.associative.hash_policies"></a> |
| Hash Policies |
| </h6></div></div></div><p>In hash-based containers, the range-hashing scheme seems to |
| affect performance more than other considerations. In most |
| settings, a mask-based scheme works well (or can be made to |
| work well). If the key-distribution can be estimated a-priori, |
| a simple hash function can produce nearly uniform hash-value |
| distribution. In many other cases (e.g., text hashing, |
| floating-point hashing), the hash function is powerful enough |
| to generate hash values with good uniformity properties |
| [knuth98sorting]; |
| a modulo-based scheme, taking into account all bits of the hash |
| value, appears to overlap the hash function in its effort.</p><p>The range-hashing scheme determines many of the other |
| policies. A mask-based scheme works |
| well with an exponential-size policy; for |
| probing-based containers, it goes well with a linear-probe |
| function.</p><p>An orthogonal consideration is the trigger policy. This |
| presents difficult tradeoffs. E.g., different load |
| factors in a load-check trigger policy yield a |
| space/amortized-cost tradeoff.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="observations.associative.branch"></a> |
| Branch-Based Containers |
| </h6></div></div></div><p>In general, there are several families of tree-based |
| underlying data structures: balanced node-based trees |
| (e.g., red-black or AVL trees), high-probability |
| balanced node-based trees (e.g., random treaps or |
| skip-lists), competitive node-based trees (e.g., splay |
| trees), vector-based "trees", and tries. (Additionally, there |
| are disk-residing or network-residing trees, such as B-Trees |
| and their numerous variants. An interface for this would have |
| to deal with the execution model and ACID guarantees; this is |
| out of the scope of this library.) Following are some |
| observations on their application to different settings.</p><p>Of the balanced node-based trees, this library includes a |
| red-black tree, as does standard (in |
| practice). This type of tree is the "workhorse" of tree-based |
| containers: it offers both reasonable modification and |
| reasonable lookup time. Unfortunately, this data structure |
| stores a huge amount of metadata. Each node must contain, |
| besides a value, three pointers and a boolean. This type might |
| be avoided if space is at a premium [austern00noset].</p><p>High-probability balanced node-based trees suffer the |
| drawbacks of deterministic balanced trees. Although they are |
| fascinating data structures, preliminary tests with them showed |
| their performance was worse than red-black trees. The library |
| does not contain any such trees, therefore.</p><p>Competitive node-based trees have two drawbacks. They are |
| usually somewhat unbalanced, and they perform a large number of |
| comparisons. Balanced trees perform one comparison per each |
| node they encounter on a search path; a splay tree performs two |
| comparisons. If the keys are complex objects, e.g., |
| <code class="classname">std::string</code>, this can increase the running time. |
| Conversely, such trees do well when there is much locality of |
| reference. It is difficult to determine in which case to prefer |
| such trees over balanced trees. This library includes a splay |
| tree.</p><p>Ordered-vector trees use very little space |
| [austern00noset]. |
| They do not have any other advantages (at least in this |
| implementation).</p><p>Large-fan-out PATRICIA tries have excellent lookup |
| performance, but they do so through maintaining, for each node, |
| a miniature "hash-table". Their space efficiency is low, and |
| their modification performance is bad. These tries might be |
| used for semi-static settings, where order preservation is |
| important. Alternatively, red-black trees cross-referenced with |
| hash tables can be used. [okasaki98mereable] |
| discusses small-fan-out PATRICIA tries for integers, but the |
| cited results seem to indicate that the amortized cost of |
| maintaining such trees is higher than that of balanced trees. |
| Moderate-fan-out trees might be useful for sequences where each |
| element has a limited number of choices, e.g., DNA |
| strings.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="observations.associative.mapping_semantics"></a> |
| Mapping-Semantics |
| </h6></div></div></div><p>Different mapping semantics were discussed in the introduction and design sections.Here |
| the focus will be on the case where a keys can be composed into |
| primary keys and secondary keys. (In the case where some keys |
| are completely identical, it is trivial that one should use an |
| associative container mapping values to size types.) In this |
| case there are (at least) five possibilities:</p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>Use an associative container that allows equivalent-key |
| values (such as <code class="classname">std::multimap</code>)</p></li><li class="listitem"><p>Use a unique-key value associative container that maps |
| each primary key to some complex associative container of |
| secondary keys, say a tree-based or hash-based container. |
| </p></li><li class="listitem"><p>Use a unique-key value associative container that maps |
| each primary key to some simple associative container of |
| secondary keys, say a list-based container.</p></li><li class="listitem"><p>Use a unique-key value associative container that maps |
| each primary key to some non-associative container |
| (e.g., <code class="classname">std::vector</code>)</p></li><li class="listitem"><p>Use a unique-key value associative container that takes |
| into account both primary and secondary keys.</p></li></ol></div><p>Stated simply: there is a simple answer for this. (Excluding |
| option 1, which should be avoided in all cases).</p><p>If the expected ratio of secondary keys to primary keys is |
| small, then 3 and 4 seem reasonable. Both types of secondary |
| containers are relatively lightweight (in terms of memory use |
| and construction time), and so creating an entire container |
| object for each primary key is not too expensive. Option 4 |
| might be preferable to option 3 if changing the secondary key |
| of some primary key is frequent - one cannot modify an |
| associative container's key, and the only possibility, |
| therefore, is erasing the secondary key and inserting another |
| one instead; a non-associative container, conversely, can |
| support in-place modification. The actual cost of erasing a |
| secondary key and inserting another one depends also on the |
| allocator used for secondary associative-containers (The tests |
| above used the standard allocator, but in practice one might |
| choose to use, e.g., [boost_pool]). Option 2 is |
| definitely an overkill in this case. Option 1 loses out either |
| immediately (when there is one secondary key per primary key) |
| or almost immediately after that. Option 5 has the same |
| drawbacks as option 2, but it has the additional drawback that |
| finding all values whose primary key is equivalent to some key, |
| might be linear in the total number of values stored (for |
| example, if using a hash-based container).</p><p>If the expected ratio of secondary keys to primary keys is |
| large, then the answer is more complicated. It depends on the |
| distribution of secondary keys to primary keys, the |
| distribution of accesses according to primary keys, and the |
| types of operations most frequent.</p><p>To be more precise, assume there are m primary keys, |
| primary key i is mapped to n<sub>i</sub> |
| secondary keys, and each primary key is mapped, on average, to |
| n secondary keys (i.e., |
| E(n<sub>i</sub>) = n).</p><p>Suppose one wants to find a specific pair of primary and |
| secondary keys. Using 1 with a tree based container |
| (<code class="classname">std::multimap</code>), the expected cost is |
| E(Θ(log(m) + n<sub>i</sub>)) = Θ(log(m) + |
| n); using 1 with a hash-based container |
| (<code class="classname">std::tr1::unordered_multimap</code>), the expected cost is |
| Θ(n). Using 2 with a primary hash-based container |
| and secondary hash-based containers, the expected cost is |
| O(1); using 2 with a primary tree-based container and |
| secondary tree-based containers, the expected cost is (using |
| the Jensen inequality [motwani95random]) |
| E(O(log(m) + log(n<sub>i</sub>)) = O(log(m)) + |
| E(O(log(n<sub>i</sub>)) = O(log(m)) + O(log(n)), |
| assuming that primary keys are accessed equiprobably. 3 and 4 |
| are similar to 1, but with lower constants. Using 5 with a |
| hash-based container, the expected cost is O(1); using 5 |
| with a tree based container, the cost is |
| E(Θ(log(mn))) = Θ(log(m) + |
| log(n)).</p><p>Suppose one needs the values whose primary key matches some |
| given key. Using 1 with a hash-based container, the expected |
| cost is Θ(n), but the values will not be ordered |
| by secondary keys (which may or may not be required); using 1 |
| with a tree-based container, the expected cost is |
| Θ(log(m) + n), but with high constants; again the |
| values will not be ordered by secondary keys. 2, 3, and 4 are |
| similar to 1, but typically with lower constants (and, |
| additionally, if one uses a tree-based container for secondary |
| keys, they will be ordered). Using 5 with a hash-based |
| container, the cost is Θ(mn).</p><p>Suppose one wants to assign to a primary key all secondary |
| keys assigned to a different primary key. Using 1 with a |
| hash-based container, the expected cost is Θ(n), |
| but with very high constants; using 1 with a tree-based |
| container, the cost is Θ(nlog(mn)). Using 2, 3, |
| and 4, the expected cost is Θ(n), but typically |
| with far lower costs than 1. 5 is similar to 1.</p></div></div><div class="section"><div class="titlepage"><div><div><h5 class="title"><a id="observations.priority_queue"></a>Priority_Queue</h5></div></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="observations.priority_queue.complexity"></a>Complexity</h6></div></div></div><p>The following table shows the complexities of the different |
| underlying data structures in terms of orders of growth. It is |
| interesting to note that this table implies something about the |
| constants of the operations as well (see Amortized <code class="function">push</code> |
| and <code class="function">pop</code> operations).</p><div class="informaltable"><table border="1"><colgroup><col align="left" class="c1" /><col align="left" class="c2" /><col align="left" class="c3" /><col align="left" class="c4" /><col align="left" class="c5" /><col align="left" class="c6" /></colgroup><thead><tr><th align="left"> </th><th align="left"><span class="emphasis"><em><code class="function">push</code></em></span></th><th align="left"><span class="emphasis"><em><code class="function">pop</code></em></span></th><th align="left"><span class="emphasis"><em><code class="function">modify</code></em></span></th><th align="left"><span class="emphasis"><em><code class="function">erase</code></em></span></th><th align="left"><span class="emphasis"><em><code class="function">join</code></em></span></th></tr></thead><tbody><tr><td align="left"> |
| <code class="classname">std::priority_queue</code> |
| </td><td align="left"> |
| Θ(n) worst |
| Θ(log(n)) amortized |
| </td><td align="left"> |
| Θ(log(n)) Worst |
| </td><td align="left"> |
| Θ(n log(n)) Worst |
| <sub>[std note 1]</sub> |
| </td><td align="left"> |
| Θ(n log(n)) |
| <sub>[std note 2]</sub> |
| </td><td align="left"> |
| Θ(n log(n)) |
| <sub>[std note 1]</sub> |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| <<code class="classname">Tag</code> = |
| <code class="classname">pairing_heap_tag</code>> |
| </td><td align="left"> |
| O(1) |
| </td><td align="left"> |
| Θ(n) worst |
| Θ(log(n)) amortized |
| </td><td align="left"> |
| Θ(n) worst |
| Θ(log(n)) amortized |
| </td><td align="left"> |
| Θ(n) worst |
| Θ(log(n)) amortized |
| </td><td align="left"> |
| O(1) |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| <<code class="classname">Tag</code> = |
| <code class="classname">binary_heap_tag</code>> |
| </td><td align="left"> |
| Θ(n) worst |
| Θ(log(n)) amortized |
| </td><td align="left"> |
| Θ(n) worst |
| Θ(log(n)) amortized |
| </td><td align="left"> |
| Θ(n) |
| </td><td align="left"> |
| Θ(n) |
| </td><td align="left"> |
| Θ(n) |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| <<code class="classname">Tag</code> = |
| <code class="classname">binomial_heap_tag</code>> |
| </td><td align="left"> |
| Θ(log(n)) worst |
| O(1) amortized |
| </td><td align="left"> |
| Θ(log(n)) |
| </td><td align="left"> |
| Θ(log(n)) |
| </td><td align="left"> |
| Θ(log(n)) |
| </td><td align="left"> |
| Θ(log(n)) |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code> |
| <<code class="classname">Tag</code> = |
| <code class="classname">rc_binomial_heap_tag</code>> |
| </td><td align="left"> |
| O(1) |
| </td><td align="left"> |
| Θ(log(n)) |
| </td><td align="left"> |
| Θ(log(n)) |
| </td><td align="left"> |
| Θ(log(n)) |
| </td><td align="left"> |
| Θ(log(n)) |
| </td></tr><tr><td align="left"> |
| <code class="classname">priority_queue</code><<code class="classname">Tag</code> = |
| <code class="classname">thin_heap_tag</code>> |
| </td><td align="left"> |
| O(1) |
| </td><td align="left"> |
| Θ(n) worst |
| Θ(log(n)) amortized |
| </td><td align="left"> |
| Θ(log(n)) worst |
| O(1) amortized, |
| or Θ(log(n)) amortized |
| <sub>[thin_heap_note]</sub> |
| </td><td align="left"> |
| Θ(n) worst |
| Θ(log(n)) amortized |
| </td><td align="left"> |
| Θ(n) |
| </td></tr></tbody></table></div><p>[std note 1] This |
| is not a property of the algorithm, but rather due to the fact |
| that the standard's priority queue implementation does not support |
| iterators (and consequently the ability to access a specific |
| value inside it). If the priority queue is adapting an |
| <code class="classname">std::vector</code>, then it is still possible to reduce this |
| to Θ(n) by adapting over the standard's adapter and |
| using the fact that <code class="function">top</code> returns a reference to the |
| first value; if, however, it is adapting an |
| <code class="classname">std::deque</code>, then this is impossible.</p><p>[std note 2] As |
| with [std note 1], this is not a |
| property of the algorithm, but rather the standard's implementation. |
| Again, if the priority queue is adapting an |
| <code class="classname">std::vector</code> then it is possible to reduce this to |
| Θ(n), but with a very high constant (one must call |
| <code class="function">std::make_heap</code> which is an expensive linear |
| operation); if the priority queue is adapting an |
| <code class="classname">std::deque</code>, then this is impossible.</p><p>[thin_heap_note] A thin heap has |
| Θ(log(n)) worst case <code class="function">modify</code> time |
| always, but the amortized time depends on the nature of the |
| operation: I) if the operation increases the key (in the sense |
| of the priority queue's comparison functor), then the amortized |
| time is O(1), but if II) it decreases it, then the |
| amortized time is the same as the worst case time. Note that |
| for most algorithms, I) is important and II) is not.</p></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="observations.priority_queue.amortized_ops"></a> |
| Amortized <code class="function">push</code> |
| and <code class="function">pop</code> operations |
| </h6></div></div></div><p>In many cases, a priority queue is needed primarily for |
| sequences of <code class="function">push</code> and <code class="function">pop</code> operations. All of |
| the underlying data structures have the same amortized |
| logarithmic complexity, but they differ in terms of |
| constants.</p><p>The table above shows that the different data structures are |
| "constrained" in some respects. In general, if a data structure |
| has lower worst-case complexity than another, then it will |
| perform slower in the amortized sense. Thus, for example a |
| redundant-counter binomial heap (<code class="classname">priority_queue</code> with |
| <code class="classname">Tag</code> = <code class="classname">rc_binomial_heap_tag</code>) |
| has lower worst-case <code class="function">push</code> performance than a binomial |
| heap (<code class="classname">priority_queue</code> |
| with <code class="classname">Tag</code> = <code class="classname">binomial_heap_tag</code>), |
| and so its amortized <code class="function">push</code> performance is slower in |
| terms of constants.</p><p>As the table shows, the "least constrained" underlying |
| data structures are binary heaps and pairing heaps. |
| Consequently, it is not surprising that they perform best in |
| terms of amortized constants.</p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>Pairing heaps seem to perform best for non-primitive |
| types (e.g., <code class="classname">std::string</code>s), as shown by |
| Priority |
| Queue Text <code class="function">push</code> Timing Test and Priority |
| Queue Text <code class="function">push</code> and <code class="function">pop</code> Timing |
| Test</p></li><li class="listitem"><p>binary heaps seem to perform best for primitive types |
| (e.g., <span class="type">int</span>s), as shown by Priority |
| Queue Random Integer <code class="function">push</code> Timing Test and |
| Priority |
| Queue Random Integer <code class="function">push</code> and <code class="function">pop</code> Timing |
| Test.</p></li></ol></div></div><div class="section"><div class="titlepage"><div><div><h6 class="title"><a id="observations.priority_queue.graphs"></a> |
| Graph Algorithms |
| </h6></div></div></div><p>In some graph algorithms, a decrease-key operation is |
| required [clrs2001]; |
| this operation is identical to <code class="function">modify</code> if a value is |
| increased (in the sense of the priority queue's comparison |
| functor). The table above and Priority Queue |
| Text <code class="function">modify</code> Up Timing Test show that a thin heap |
| (<code class="classname">priority_queue</code> with |
| <code class="classname">Tag</code> = <code class="classname">thin_heap_tag</code>) |
| outperforms a pairing heap (<code class="classname">priority_queue</code> with |
| <code class="classname">Tag</code> = <code class="classname">Tag</code> = <code class="classname">pairing_heap_tag</code>), |
| but the rest of the tests show otherwise.</p><p>This makes it difficult to decide which implementation to use in |
| this case. Dijkstra's shortest-path algorithm, for example, requires |
| Θ(n) <code class="function">push</code> and <code class="function">pop</code> operations |
| (in the number of vertices), but O(n<sup>2</sup>) |
| <code class="function">modify</code> operations, which can be in practice Θ(n) |
| as well. It is difficult to find an a-priori characterization of |
| graphs in which the actual number of <code class="function">modify</code> |
| operations will dwarf the number of <code class="function">push</code> and |
| <code class="function">pop</code> operations.</p></div></div></div></div></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="policy_data_structures_design.html">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="policy_data_structures.html">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="policy_data_structures_ack.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Design </td><td width="20%" align="center"><a accesskey="h" href="../index.html">Home</a></td><td width="40%" align="right" valign="top"> Acknowledgments</td></tr></table></div></body></html> |