diff options
Diffstat (limited to 'libstdc++-v3/doc/html/manual/policy_based_data_structures_test.html')
| -rw-r--r-- | libstdc++-v3/doc/html/manual/policy_based_data_structures_test.html | 3813 |
1 files changed, 3813 insertions, 0 deletions
diff --git a/libstdc++-v3/doc/html/manual/policy_based_data_structures_test.html b/libstdc++-v3/doc/html/manual/policy_based_data_structures_test.html new file mode 100644 index 00000000000..ee89d191709 --- /dev/null +++ b/libstdc++-v3/doc/html/manual/policy_based_data_structures_test.html @@ -0,0 +1,3813 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd"> +<html xmlns="http://www.w3.org/1999/xhtml"><head><title>Testing</title><meta name="generator" content="DocBook XSL-NS Stylesheets V1.76.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_biblio.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 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 align="right"> <a accesskey="n" href="policy_data_structures_biblio.html">Next</a></td></tr></table><hr/></div><div class="section" title="Testing"><div class="titlepage"><div><div><h2 class="title"><a id="pbds.test"/>Testing</h2></div></div></div><div class="section" title="Regression"><div class="titlepage"><div><div><h3 class="title"><a id="pbds.test.regression"/>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" title="Performance"><div class="titlepage"><div><div><h3 class="title"><a id="pbds.test.performance"/>Performance</h3></div></div></div><div class="section" title="Hash-Based"><div class="titlepage"><div><div><h4 class="title"><a id="performance.hash"/>Hash-Based</h4></div></div></div><p/><div class="section" title="Text find"><div class="titlepage"><div><div><h5 class="title"><a id="performance.hash.text_find"/> + Text <code class="function">find</code> + </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="hash.text_find.info"/> + 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" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="hash.text_find.results"/> + 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" style="text-align: center"><img src="../images/pbds_hash_text_find.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="5" style="text-align: left"> + n_hash_map_ncah + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::tr1::unordered_map</code> + </td><td style="text-align: left"> + <code class="classname">cache_hash_code</code> + </td><td style="text-align: left"> + <code class="constant">false</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="5" style="text-align: left"> + cc_hash_mod_prime_1div1_nsth_map + </td></tr><tr><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">cc_hash_table</code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mod_range_hashing</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_prime_size_policy</code> + </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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 style="background-color: #B0B0B0"><td colspan="5" style="text-align: left"> + cc_hash_mask_exp_1div2_sth_map + </td></tr><tr><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname"> + cc_hash_table + </code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mask_range_hashing</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_exponential_size_policy</code> + </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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 style="background-color: #B0B0B0"><td colspan="5" style="text-align: left"> + cc_hash_mask_exp_1div1_nsth_map + </td></tr><tr><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">cc_hash_table</code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mask_range_hashing</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_exponential_size_policy</code> + </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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 style="background-color: #B0B0B0"><td colspan="5" style="text-align: left"> + cc_hash_mask_exp_1div2_nsth_map + </td></tr><tr><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">cc_hash_table</code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mask_range_hashing</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_exponential_size_policy</code> + </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="hash.text_find.observations"/> + 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" title="Integer find"><div class="titlepage"><div><div><h5 class="title"><a id="performance.hash.int_find"/> + Integer <code class="function">find</code> + </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="hash.int_find.info"/> + 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" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="hash.int_find.results"/> + 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" style="text-align: center"><img src="../images/pbds_cc_hash_int_find.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="5" style="text-align: left"> + n_hash_map_ncah + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::tr1::unordered_map</code> + </td><td style="text-align: left"> + <code class="classname">cache_hash_code</code> + </td><td style="text-align: left"> + <code class="constant">false</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="5" style="text-align: left"> + cc_hash_mod_prime_1div1_nsth_map + </td></tr><tr><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">cc_hash_table</code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mod_range_hashing</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_prime_size_policy</code> + </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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 style="background-color: #B0B0B0"><td colspan="5" style="text-align: left"> + cc_hash_mod_prime_1div2_nsth_map + </td></tr><tr><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname"> + cc_hash_table + </code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mod_range_hashing</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_prime_size_policy</code> + </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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 style="background-color: #B0B0B0"><td colspan="5" style="text-align: left"> + cc_hash_mask_exp_1div1_nsth_map + </td></tr><tr><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">cc_hash_table</code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mask_range_hashing</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_exponential_size_policy</code> + </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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 style="background-color: #B0B0B0"><td colspan="5" style="text-align: left"> + cc_hash_mask_exp_1div2_nsth_map + </td></tr><tr><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">cc_hash_table</code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mask_range_hashing</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_exponential_size_policy</code> + </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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" style="text-align: center"><img src="../images/pbds_gp_hash_int_find.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="5" style="text-align: left"> + n_hash_map_ncah + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::tr1::unordered_map</code> + </td><td style="text-align: left"> + <code class="classname">cache_hash_code</code> + </td><td style="text-align: left"> + <code class="constant">false</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="5" style="text-align: left"> + gp_hash_mod_quadp_prime_1div2_nsth_map + </td></tr><tr><td rowspan="4" style="text-align: left" valign="top"> + <code class="classname">gp_hash_table</code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mod_range_hashing</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td style="text-align: left"> + <code class="classname">Probe_Fn</code> + </td><td style="text-align: left"> + <code class="classname">quadratic_probe_fn</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_prime_size_policy</code> + </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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 style="background-color: #B0B0B0"><td colspan="5" style="text-align: left"> + gp_hash_mask_linp_exp_1div2_nsth_map + </td></tr><tr><td rowspan="4" style="text-align: left" valign="top"> + <code class="classname"> + gp_hash_table + </code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mask_range_hashing</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td style="text-align: left"> + <code class="classname">Probe_Fn</code> + </td><td style="text-align: left"> + <code class="classname">linear_probe_fn</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_exponential_size_policy</code> + </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="hash.int_find.observations"/> + 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" title="Integer Subscript find"><div class="titlepage"><div><div><h5 class="title"><a id="performance.hash.int_subscript_find"/> + Integer Subscript <code class="function">find</code> + </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="hash.int_subscript_find.info"/> + 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" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="hash.int_subscript_find.results"/> + 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" style="text-align: center"><img src="../images/pbds_cc_hash_int_subscript_find.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="5" style="text-align: left"> + n_hash_map_ncah + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::tr1::unordered_map</code> + </td><td style="text-align: left"> + <code class="classname">cache_hash_code</code> + </td><td style="text-align: left"> + <code class="constant">false</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="5" style="text-align: left"> + cc_hash_mod_prime_1div1_nsth_map + </td></tr><tr><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">cc_hash_table</code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mod_range_hashing</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_prime_size_policy</code> + </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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 style="background-color: #B0B0B0"><td colspan="5" style="text-align: left"> + cc_hash_mod_prime_1div2_nsth_map + </td></tr><tr><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">cc_hash_table</code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mod_range_hashing</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_prime_size_policy</code> + </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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 style="background-color: #B0B0B0"><td colspan="5" style="text-align: left"> + cc_hash_mask_exp_1div1_nsth_map + </td></tr><tr><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">cc_hash_table</code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mask_range_hashing</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_exponential_size_policy</code> + </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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 style="background-color: #B0B0B0"><td colspan="5" style="text-align: left"> + cc_hash_mask_exp_1div2_nsth_map + </td></tr><tr><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">cc_hash_table</code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mask_range_hashing</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_exponential_size_policy</code> + </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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" style="text-align: center"><img src="../images/pbds_gp_hash_int_subscript_find.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="5" style="text-align: left"> + n_hash_map_ncah + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::tr1::unordered_map</code> + </td><td style="text-align: left"> + <code class="classname">cache_hash_code</code> + </td><td style="text-align: left"> + <code class="constant">false</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="5" style="text-align: left"> + gp_hash_mod_quadp_prime_1div2_nsth_map + </td></tr><tr><td rowspan="4" style="text-align: left" valign="top"> + <code class="classname">gp_hash_table</code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mod_range_hashing</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td style="text-align: left"> + <code class="classname">Probe_Fn</code> + </td><td style="text-align: left"> + <code class="classname">quadratic_probe_fn</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_prime_size_policy</code> + </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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 style="background-color: #B0B0B0"><td colspan="5" style="text-align: left"> + gp_hash_mask_linp_exp_1div2_nsth_map + </td></tr><tr><td rowspan="4" style="text-align: left" valign="top"> + <code class="classname"> + gp_hash_table + </code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mask_range_hashing</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td style="text-align: left"> + <code class="classname">Probe_Fn</code> + </td><td style="text-align: left"> + <code class="classname">linear_probe_fn</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_exponential_size_policy</code> + </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="hash.int_subscript_find.observations"/> + 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" title="Integer Subscript insert"><div class="titlepage"><div><div><h5 class="title"><a id="performance.hash.int_subscript_insert"/> + Integer Subscript <code class="function">insert</code> + </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="hash.int_subscript_insert.info"/> + 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" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="hash.int_subscript_insert.results"/> + 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" style="text-align: center"><img src="../images/pbds_cc_hash_int_subscript_insert.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="5" style="text-align: left"> + n_hash_map_ncah + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::tr1::unordered_map</code> + </td><td style="text-align: left"> + <code class="classname">cache_hash_code</code> + </td><td style="text-align: left"> + <code class="constant">false</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="5" style="text-align: left"> + cc_hash_mod_prime_1div1_nsth_map + </td></tr><tr><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">cc_hash_table</code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mod_range_hashing</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_prime_size_policy</code> + </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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 style="background-color: #B0B0B0"><td colspan="5" style="text-align: left"> + cc_hash_mod_prime_1div2_nsth_map + </td></tr><tr><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">cc_hash_table</code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mod_range_hashing</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_prime_size_policy</code> + </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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 style="background-color: #B0B0B0"><td colspan="5" style="text-align: left"> + cc_hash_mask_exp_1div1_nsth_map + </td></tr><tr><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">cc_hash_table</code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mask_range_hashing</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_exponential_size_policy</code> + </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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 style="background-color: #B0B0B0"><td colspan="5" style="text-align: left"> + cc_hash_mask_exp_1div2_nsth_map + </td></tr><tr><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">cc_hash_table</code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mask_range_hashing</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_exponential_size_policy</code> + </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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" style="text-align: center"><img src="../images/pbds_gp_hash_int_subscript_insert.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="5" style="text-align: left"> + n_hash_map_ncah + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::tr1::unordered_map</code> + </td><td style="text-align: left"> + <code class="classname">cache_hash_code</code> + </td><td style="text-align: left"> + <code class="constant">false</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="5" style="text-align: left"> + gp_hash_mod_quadp_prime_1div2_nsth_map + </td></tr><tr><td rowspan="4" style="text-align: left" valign="top"> + <code class="classname">gp_hash_table</code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mod_range_hashing</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td style="text-align: left"> + <code class="classname">Probe_Fn</code> + </td><td style="text-align: left"> + <code class="classname">quadratic_probe_fn</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_prime_size_policy</code> + </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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 style="background-color: #B0B0B0"><td colspan="5" style="text-align: left"> + gp_hash_mask_linp_exp_1div2_nsth_map + </td></tr><tr><td rowspan="4" style="text-align: left" valign="top"> + <code class="classname"> + gp_hash_table + </code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mask_range_hashing</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td style="text-align: left"> + <code class="classname">Probe_Fn</code> + </td><td style="text-align: left"> + <code class="classname">linear_probe_fn</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_exponential_size_policy</code> + </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="hash.int_subscript_insert.observations"/> + 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"><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" title="Integer find with Skewed-Distribution"><div class="titlepage"><div><div><h5 class="title"><a id="performance.hash.zlob_int_find"/> + Integer <code class="function">find</code> with Skewed-Distribution + </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="hash.zlob_int_find.info"/> + 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" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="hash.zlob_int_find.results"/> + 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" style="text-align: center"><img src="../images/pbds_hash_zlob_int_find.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="5" style="text-align: left"> + n_hash_map_ncah + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::tr1::unordered_map</code> + </td><td style="text-align: left"> + <code class="classname">cache_hash_code</code> + </td><td style="text-align: left"> + <code class="constant">false</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="5" style="text-align: left"> + cc_hash_mod_prime_1div1_nsth_map + </td></tr><tr><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">cc_hash_table</code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mod_range_hashing</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_prime_size_policy</code> + </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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 style="background-color: #B0B0B0"><td colspan="5" style="text-align: left"> + cc_hash_mask_exp_1div1_nsth_map + </td></tr><tr><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname"> + cc_hash_table + </code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mask_range_hashing</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_exponential_size_policy</code> + </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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 style="background-color: #B0B0B0"><td colspan="5" style="text-align: left"> + gp_hash_mod_quadp_prime_1div2_nsth_map + </td></tr><tr><td rowspan="4" style="text-align: left" valign="top"> + <code class="classname">gp_hash_table</code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mod_range_hashing</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td style="text-align: left"> + <code class="classname">Probe_Fn</code> + </td><td style="text-align: left"> + <code class="classname">quadratic_probe_fn</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_prime_size_policy</code> + </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="hash.zlob_int_find.observations"/> + 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" title="Erase Memory Use"><div class="titlepage"><div><div><h5 class="title"><a id="performance.hash.erase_mem"/> + Erase Memory Use + </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="hash.erase_mem.info"/> + 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" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="hash.erase_mem.results"/> + 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" style="text-align: center"><img src="../images/pbds_hash_int_erase_mem.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="5" style="text-align: left"> + n_hash_map_ncah + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::tr1::unordered_map</code> + </td><td style="text-align: left"> + <code class="classname">cache_hash_code</code> + </td><td style="text-align: left"> + <code class="constant">false</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="5" style="text-align: left"> + cc_hash_mod_prime_1div1_nsth_map + </td></tr><tr><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">cc_hash_table</code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mod_range_hashing</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_prime_size_policy</code> + </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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 style="background-color: #B0B0B0"><td colspan="5" style="text-align: left"> + cc_hash_mask_exp_1div2_nsth_map + </td></tr><tr><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname"> + cc_hash_table + </code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mask_range_hashing</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_exponential_size_policy</code> + </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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 style="background-color: #B0B0B0"><td colspan="5" style="text-align: left"> + gp_hash_mask_linp_exp_1div2_nsth_set + </td></tr><tr><td rowspan="4" style="text-align: left" valign="top"> + <code class="classname">gp_hash_table</code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mask_range_hashing</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td style="text-align: left"> + <code class="classname">Probe_Fn</code> + </td><td style="text-align: left"> + <code class="classname">linear_probe_fn</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_exponential_size_policy</code> + </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="hash.erase_mem.observations"/> + 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" title="Branch-Based"><div class="titlepage"><div><div><h4 class="title"><a id="performance.branch"/>Branch-Based</h4></div></div></div><p/><div class="section" title="Text insert"><div class="titlepage"><div><div><h5 class="title"><a id="performance.branch.text_insert"/> + Text <code class="function">insert</code> + </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="branch.text_insert.info"/> + 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" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="branch.text_insert.results"/> + 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" style="text-align: center"><img src="../images/pbds_tree_text_insert_node.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + n_map + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::map</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + splay_tree_map + </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">tree</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">splay_tree_tag</code> + </td></tr><tr><td style="text-align: left"> + <code class="classname">Node_update</code> + </td><td style="text-align: left"> + <code class="classname">null_node_update</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + rb_tree_map + </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">tree</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">rb_tree_tag</code> + </td></tr><tr><td style="text-align: left"> + <code class="classname">Node_update</code> + </td><td style="text-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" style="text-align: center"><img src="../images/pbds_tree_text_insert_vector.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + n_map + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::map</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + ov_tree_map + </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">tree</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">ov_tree_tag</code> + </td></tr><tr><td style="text-align: left"> + <code class="classname">Node_update</code> + </td><td style="text-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" style="text-align: center"><img src="../images/pbds_tree_text_insert_trie.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + n_map + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::map</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + pat_trie_map + </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">tree</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">pat_trie_tag</code> + </td></tr><tr><td style="text-align: left"> + <code class="classname">Node_update</code> + </td><td style="text-align: left"> + <code class="classname">null_node_update</code> + </td></tr></tbody></table></div></div><div class="section" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="branch.text_insert.observations"/> + 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" title="Text find"><div class="titlepage"><div><div><h5 class="title"><a id="performance.branch.text_find"/> + Text <code class="function">find</code> + </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="branch.text_find.info"/> + 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" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="branch.text_find.results"/> + 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" style="text-align: center"><img src="../images/pbds_tree_text_find.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + n_map + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::map</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + splay_tree_map + </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">tree</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">splay_tree_tag</code> + </td></tr><tr><td style="text-align: left"> + <code class="classname">Node_Update</code> + </td><td style="text-align: left"> + <code class="classname">null_node_update</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + rb_tree_map + </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">tree</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">rb_tree_tag</code> + </td></tr><tr><td style="text-align: left"> + <code class="classname">Node_Update</code> + </td><td style="text-align: left"> + <code class="classname">null_node_update</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + ov_tree_map + </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">tree</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">ov_tree_tag</code> + </td></tr><tr><td style="text-align: left"> + <code class="classname">Node_Update</code> + </td><td style="text-align: left"> + <code class="classname">null_node_update</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + pat_trie_map + </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">tree</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">pat_trie_tag</code> + </td></tr><tr><td style="text-align: left"> + <code class="classname">Node_Update</code> + </td><td style="text-align: left"> + <code class="classname">null_node_update</code> + </td></tr></tbody></table></div></div><div class="section" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="branch.text_find.observations"/> + 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"><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" title="Text find with Locality-of-Reference"><div class="titlepage"><div><div><h5 class="title"><a id="performance.branch.text_lor_find"/> + Text <code class="function">find</code> with Locality-of-Reference + </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="branch.text_lor_find.info"/> + 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" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="branch.text_lor_find.results"/> + 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" style="text-align: center"><img src="../images/pbds_tree_text_lor_find.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + n_map + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::map</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + splay_tree_map + </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">tree</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">splay_tree_tag</code> + </td></tr><tr><td style="text-align: left"> + <code class="classname">Node_Update</code> + </td><td style="text-align: left"> + <code class="classname">null_node_update</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + rb_tree_map + </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">tree</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">rb_tree_tag</code> + </td></tr><tr><td style="text-align: left"> + <code class="classname">Node_Update</code> + </td><td style="text-align: left"> + <code class="classname">null_node_update</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + ov_tree_map + </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">tree</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">ov_tree_tag</code> + </td></tr><tr><td style="text-align: left"> + <code class="classname">Node_Update</code> + </td><td style="text-align: left"> + <code class="classname">null_node_update</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + pat_trie_map + </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">tree</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">pat_trie_tag</code> + </td></tr><tr><td style="text-align: left"> + <code class="classname">Node_Update</code> + </td><td style="text-align: left"> + <code class="classname">null_node_update</code> + </td></tr></tbody></table></div></div><div class="section" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="branch.text_lor_find.observations"/> + 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" title="split and join"><div class="titlepage"><div><div><h5 class="title"><a id="performance.branch.split_join"/> + <code class="function">split</code> and <code class="function">join</code> + </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="branch.split_join.info"/> + 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" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="branch.split_join.results"/> + 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" style="text-align: center"><img src="../images/pbds_tree_split_join.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + n_set + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::set</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + splay_tree_set + </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">tree</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">splay_tree_tag</code> + </td></tr><tr><td style="text-align: left"> + <code class="classname">Node_Update</code> + </td><td style="text-align: left"> + <code class="classname">null_node_update</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + rb_tree_set + </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">tree</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">rb_tree_tag</code> + </td></tr><tr><td style="text-align: left"> + <code class="classname">Node_Update</code> + </td><td style="text-align: left"> + <code class="classname">null_node_update</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + ov_tree_set + </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">tree</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">ov_tree_tag</code> + </td></tr><tr><td style="text-align: left"> + <code class="classname">Node_Update</code> + </td><td style="text-align: left"> + <code class="classname">null_node_update</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + pat_trie_map + </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">tree</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">pat_trie_tag</code> + </td></tr><tr><td style="text-align: left"> + <code class="classname">Node_Update</code> + </td><td style="text-align: left"> + <code class="classname">null_node_update</code> + </td></tr></tbody></table></div></div><div class="section" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="branch.split_join.observations"/> + 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" title="Order-Statistics"><div class="titlepage"><div><div><h5 class="title"><a id="performance.branch.order_statistics"/> + Order-Statistics + </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="branch.order_statistics.info"/> + 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" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="branch.order_statistics.results"/> + 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" style="text-align: center"><img src="../images/pbds_tree_order_statistics.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + n_set + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::set</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + splay_tree_ost_set + </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">tree</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">splay_tree_tag</code> + </td></tr><tr><td style="text-align: left"> + <code class="classname">Node_Update</code> + </td><td style="text-align: left"> + <code class="classname">tree_order_statistics_node_update</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + rb_tree_ost_set + </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">tree</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">rb_tree_tag</code> + </td></tr><tr><td style="text-align: left"> + <code class="classname">Node_Update</code> + </td><td style="text-align: left"> + <code class="classname">tree_order_statistics_node_update</code> + </td></tr></tbody></table></div></div><div class="section" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="branch.order_statistics.observations"/> + 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" title="Multimap"><div class="titlepage"><div><div><h4 class="title"><a id="performance.multimap"/>Multimap</h4></div></div></div><p/><div class="section" title="Text find with Small Secondary-to-Primary Key Ratios"><div class="titlepage"><div><div><h5 class="title"><a id="performance.multimap.text_find_small"/> + Text <code class="function">find</code> with Small Secondary-to-Primary Key Ratios + </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_find_small.info"/> + 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" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_find_small.results"/> + 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" style="text-align: center"><img src="../images/pbds_multimap_text_find_small_s2p_tree.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/><col style="text-align: left" class="c6"/><col style="text-align: left" class="c7"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left"> + n_mmap + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::multimap</code> + </td><td colspan="6" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left"> + rb_tree_mmap_lu_mtf_set + </td></tr><tr><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">tree</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">rb_tree_tag</code> + </td><td colspan="4" style="text-align: left"> </td></tr><tr><td style="text-align: left"> + <code class="classname">Node_Update</code> + </td><td style="text-align: left"> + <code class="classname">null_node_update</code> + </td><td colspan="4" style="text-align: left"> </td></tr><tr><td style="text-align: left"> + <code class="classname">Mapped</code> + </td><td style="text-align: left"> + <code class="classname">list_update</code> + </td><td style="text-align: left"> + <code class="classname">Update_Policy</code> + </td><td style="text-align: left"> + <code class="classname">lu_move_to_front_policy</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left"> + rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set + </td></tr><tr><td rowspan="5" style="text-align: left" valign="top"> + <code class="classname">tree</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">rb_tree_tag</code> + </td><td colspan="4" style="text-align: left"> </td></tr><tr><td style="text-align: left"> + <code class="classname">Node_Update</code> + </td><td style="text-align: left"> + <code class="classname">null_node_update</code> + </td><td colspan="4" style="text-align: left"> </td></tr><tr><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">Mapped</code> + </td><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">cc_hash_table</code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mask_range_hashing</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_exponential_size_policy</code> + </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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" style="text-align: center"><img src="../images/pbds_multimap_text_find_small_s2p_hash.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/><col style="text-align: left" class="c6"/><col style="text-align: left" class="c7"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left"> + n_hash_mmap + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::tr1::unordered_multimap</code> + </td><td colspan="6" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left"> + rb_tree_mmap_lu_mtf_set + </td></tr><tr><td rowspan="4" style="text-align: left" valign="top"> + <code class="classname"> + cc_hash_table + </code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mask_range_hashing</code> + </td><td colspan="4" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_exponential_size_policy</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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" style="text-align: left"> </td></tr><tr><td style="text-align: left"> + <code class="classname">Mapped</code> + </td><td style="text-align: left"> + <code class="classname">list_update</code> + </td><td style="text-align: left"> + <code class="classname">Update_Policy</code> + </td><td style="text-align: left"> + <code class="classname">lu_move_to_front_policy</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left"> + rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set + </td></tr><tr><td rowspan="6" style="text-align: left" valign="top"> + <code class="classname"> + cc_hash_table + </code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mask_range_hashing</code> + </td><td colspan="4" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_exponential_size_policy</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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" style="text-align: left"> </td></tr><tr><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">Mapped</code> + </td><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">cc_hash_table</code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mask_range_hashing</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_exponential_size_policy</code> + </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_find_small.observations"/> + Observations + </h6></div></div></div><p>See Observations::Mapping-Semantics + Considerations.</p></div></div><div class="section" title="Text find with Large Secondary-to-Primary Key Ratios"><div class="titlepage"><div><div><h5 class="title"><a id="performance.multimap.text_find_large"/> + Text <code class="function">find</code> with Large Secondary-to-Primary Key Ratios + </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_find_large.info"/> + 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" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_find_large.results"/> + 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" style="text-align: center"><img src="../images/pbds_multimap_text_find_large_s2p_tree.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/><col style="text-align: left" class="c6"/><col style="text-align: left" class="c7"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left"> + n_mmap + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::multimap</code> + </td><td colspan="6" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left"> + rb_tree_mmap_lu_mtf_set + </td></tr><tr><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">tree</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">rb_tree_tag</code> + </td><td colspan="4" style="text-align: left"> </td></tr><tr><td style="text-align: left"> + <code class="classname">Node_Update</code> + </td><td style="text-align: left"> + <code class="classname">null_node_update</code> + </td><td colspan="4" style="text-align: left"> </td></tr><tr><td style="text-align: left"> + <code class="classname">Mapped</code> + </td><td style="text-align: left"> + <code class="classname">list_update</code> + </td><td style="text-align: left"> + <code class="classname">Update_Policy</code> + </td><td style="text-align: left"> + <code class="classname">lu_move_to_front_policy</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left"> + rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set + </td></tr><tr><td rowspan="5" style="text-align: left" valign="top"> + <code class="classname">tree</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">rb_tree_tag</code> + </td><td colspan="4" style="text-align: left"> </td></tr><tr><td style="text-align: left"> + <code class="classname">Node_Update</code> + </td><td style="text-align: left"> + <code class="classname">null_node_update</code> + </td><td colspan="4" style="text-align: left"> </td></tr><tr><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">Mapped</code> + </td><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">cc_hash_table</code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mask_range_hashing</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_exponential_size_policy</code> + </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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" style="text-align: center"><img src="../images/pbds_multimap_text_find_large_s2p_hash.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/><col style="text-align: left" class="c6"/><col style="text-align: left" class="c7"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left"> + n_hash_mmap + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::tr1::unordered_multimap</code> + </td><td colspan="6" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left"> + rb_tree_mmap_lu_mtf_set + </td></tr><tr><td rowspan="4" style="text-align: left" valign="top"> + <code class="classname"> + cc_hash_table + </code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mask_range_hashing</code> + </td><td colspan="4" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_exponential_size_policy</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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" style="text-align: left"> </td></tr><tr><td style="text-align: left"> + <code class="classname">Mapped</code> + </td><td style="text-align: left"> + <code class="classname">list_update</code> + </td><td style="text-align: left"> + <code class="classname">Update_Policy</code> + </td><td style="text-align: left"> + <code class="classname">lu_move_to_front_policy</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left"> + rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set + </td></tr><tr><td rowspan="6" style="text-align: left" valign="top"> + <code class="classname"> + cc_hash_table + </code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mask_range_hashing</code> + </td><td colspan="4" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_exponential_size_policy</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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" style="text-align: left"> </td></tr><tr><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">Mapped</code> + </td><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">cc_hash_table</code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mask_range_hashing</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_exponential_size_policy</code> + </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_find_large.observations"/> + Observations + </h6></div></div></div><p>See Observations::Mapping-Semantics + Considerations.</p></div></div><div class="section" title="Text insert with Small Secondary-to-Primary Key Ratios"><div class="titlepage"><div><div><h5 class="title"><a id="performance.multimap.text_insert_small"/> + Text <code class="function">insert</code> with Small + Secondary-to-Primary Key Ratios + </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_small.info"/> + 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" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_small.results"/> + 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" style="text-align: center"><img src="../images/pbds_multimap_text_insert_small_s2p_tree.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/><col style="text-align: left" class="c6"/><col style="text-align: left" class="c7"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left"> + n_mmap + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::multimap</code> + </td><td colspan="6" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left"> + rb_tree_mmap_lu_mtf_set + </td></tr><tr><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">tree</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">rb_tree_tag</code> + </td><td colspan="4" style="text-align: left"> </td></tr><tr><td style="text-align: left"> + <code class="classname">Node_Update</code> + </td><td style="text-align: left"> + <code class="classname">null_node_update</code> + </td><td colspan="4" style="text-align: left"> </td></tr><tr><td style="text-align: left"> + <code class="classname">Mapped</code> + </td><td style="text-align: left"> + <code class="classname">list_update</code> + </td><td style="text-align: left"> + <code class="classname">Update_Policy</code> + </td><td style="text-align: left"> + <code class="classname">lu_move_to_front_policy</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left"> + rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set + </td></tr><tr><td rowspan="5" style="text-align: left" valign="top"> + <code class="classname">tree</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">rb_tree_tag</code> + </td><td colspan="4" style="text-align: left"> </td></tr><tr><td style="text-align: left"> + <code class="classname">Node_Update</code> + </td><td style="text-align: left"> + <code class="classname">null_node_update</code> + </td><td colspan="4" style="text-align: left"> </td></tr><tr><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">Mapped</code> + </td><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">cc_hash_table</code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mask_range_hashing</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_exponential_size_policy</code> + </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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" style="text-align: center"><img src="../images/pbds_multimap_text_find_small_s2p_hash.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/><col style="text-align: left" class="c6"/><col style="text-align: left" class="c7"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left"> + n_hash_mmap + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::tr1::unordered_multimap</code> + </td><td colspan="6" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left"> + rb_tree_mmap_lu_mtf_set + </td></tr><tr><td rowspan="4" style="text-align: left" valign="top"> + <code class="classname"> + cc_hash_table + </code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mask_range_hashing</code> + </td><td colspan="4" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_exponential_size_policy</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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" style="text-align: left"> </td></tr><tr><td style="text-align: left"> + <code class="classname">Mapped</code> + </td><td style="text-align: left"> + <code class="classname">list_update</code> + </td><td style="text-align: left"> + <code class="classname">Update_Policy</code> + </td><td style="text-align: left"> + <code class="classname">lu_move_to_front_policy</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left"> + rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set + </td></tr><tr><td rowspan="6" style="text-align: left" valign="top"> + <code class="classname"> + cc_hash_table + </code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mask_range_hashing</code> + </td><td colspan="4" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_exponential_size_policy</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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" style="text-align: left"> </td></tr><tr><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">Mapped</code> + </td><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">cc_hash_table</code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mask_range_hashing</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_exponential_size_policy</code> + </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_small.observations"/> + Observations + </h6></div></div></div><p>See Observations::Mapping-Semantics + Considerations.</p></div></div><div class="section" title="Text insert with Small Secondary-to-Primary Key Ratios"><div class="titlepage"><div><div><h5 class="title"><a id="performance.multimap.text_insert_large"/> + Text <code class="function">insert</code> with Small + Secondary-to-Primary Key Ratios + </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_large.info"/> + 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" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_large.results"/> + 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" style="text-align: center"><img src="../images/pbds_multimap_text_insert_large_s2p_tree.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/><col style="text-align: left" class="c6"/><col style="text-align: left" class="c7"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left"> + n_mmap + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::multimap</code> + </td><td colspan="6" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left"> + rb_tree_mmap_lu_mtf_set + </td></tr><tr><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">tree</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">rb_tree_tag</code> + </td><td colspan="4" style="text-align: left"> </td></tr><tr><td style="text-align: left"> + <code class="classname">Node_Update</code> + </td><td style="text-align: left"> + <code class="classname">null_node_update</code> + </td><td colspan="4" style="text-align: left"> </td></tr><tr><td style="text-align: left"> + <code class="classname">Mapped</code> + </td><td style="text-align: left"> + <code class="classname">list_update</code> + </td><td style="text-align: left"> + <code class="classname">Update_Policy</code> + </td><td style="text-align: left"> + <code class="classname">lu_move_to_front_policy</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left"> + rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set + </td></tr><tr><td rowspan="5" style="text-align: left" valign="top"> + <code class="classname">tree</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">rb_tree_tag</code> + </td><td colspan="4" style="text-align: left"> </td></tr><tr><td style="text-align: left"> + <code class="classname">Node_Update</code> + </td><td style="text-align: left"> + <code class="classname">null_node_update</code> + </td><td colspan="4" style="text-align: left"> </td></tr><tr><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">Mapped</code> + </td><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">cc_hash_table</code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mask_range_hashing</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_exponential_size_policy</code> + </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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" style="text-align: center"><img src="../images/pbds_multimap_text_find_large_s2p_hash.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/><col style="text-align: left" class="c6"/><col style="text-align: left" class="c7"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left"> + n_hash_mmap + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::tr1::unordered_multimap</code> + </td><td colspan="6" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left"> + rb_tree_mmap_lu_mtf_set + </td></tr><tr><td rowspan="4" style="text-align: left" valign="top"> + <code class="classname"> + cc_hash_table + </code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mask_range_hashing</code> + </td><td colspan="4" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_exponential_size_policy</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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" style="text-align: left"> </td></tr><tr><td style="text-align: left"> + <code class="classname">Mapped</code> + </td><td style="text-align: left"> + <code class="classname">list_update</code> + </td><td style="text-align: left"> + <code class="classname">Update_Policy</code> + </td><td style="text-align: left"> + <code class="classname">lu_move_to_front_policy</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left"> + rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set + </td></tr><tr><td rowspan="6" style="text-align: left" valign="top"> + <code class="classname"> + cc_hash_table + </code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mask_range_hashing</code> + </td><td colspan="4" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_exponential_size_policy</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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" style="text-align: left"> </td></tr><tr><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">Mapped</code> + </td><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">cc_hash_table</code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mask_range_hashing</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_exponential_size_policy</code> + </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_large.observations"/> + Observations + </h6></div></div></div><p>See Observations::Mapping-Semantics + Considerations.</p></div></div><div class="section" title="Text insert with Small Secondary-to-Primary Key Ratios Memory Use"><div class="titlepage"><div><div><h5 class="title"><a id="performance.multimap.text_insert_mem_small"/> + Text <code class="function">insert</code> with Small + Secondary-to-Primary Key Ratios Memory Use + </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_mem_small.info"/> + 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" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_mem_small.results"/> + 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" style="text-align: center"><img src="../images/pbds_multimap_text_insert_mem_small_s2p_tree.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/><col style="text-align: left" class="c6"/><col style="text-align: left" class="c7"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left"> + n_mmap + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::multimap</code> + </td><td colspan="6" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left"> + rb_tree_mmap_lu_mtf_set + </td></tr><tr><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">tree</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">rb_tree_tag</code> + </td><td colspan="4" style="text-align: left"> </td></tr><tr><td style="text-align: left"> + <code class="classname">Node_Update</code> + </td><td style="text-align: left"> + <code class="classname">null_node_update</code> + </td><td colspan="4" style="text-align: left"> </td></tr><tr><td style="text-align: left"> + <code class="classname">Mapped</code> + </td><td style="text-align: left"> + <code class="classname">list_update</code> + </td><td style="text-align: left"> + <code class="classname">Update_Policy</code> + </td><td style="text-align: left"> + <code class="classname">lu_move_to_front_policy</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left"> + rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set + </td></tr><tr><td rowspan="5" style="text-align: left" valign="top"> + <code class="classname">tree</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">rb_tree_tag</code> + </td><td colspan="4" style="text-align: left"> </td></tr><tr><td style="text-align: left"> + <code class="classname">Node_Update</code> + </td><td style="text-align: left"> + <code class="classname">null_node_update</code> + </td><td colspan="4" style="text-align: left"> </td></tr><tr><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">Mapped</code> + </td><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">cc_hash_table</code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mask_range_hashing</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_exponential_size_policy</code> + </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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" style="text-align: center"><img src="../images/pbds_multimap_text_find_large_s2p_hash.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/><col style="text-align: left" class="c6"/><col style="text-align: left" class="c7"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left"> + n_hash_mmap + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::tr1::unordered_multimap</code> + </td><td colspan="6" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left"> + rb_tree_mmap_lu_mtf_set + </td></tr><tr><td rowspan="4" style="text-align: left" valign="top"> + <code class="classname"> + cc_hash_table + </code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mask_range_hashing</code> + </td><td colspan="4" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_exponential_size_policy</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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" style="text-align: left"> </td></tr><tr><td style="text-align: left"> + <code class="classname">Mapped</code> + </td><td style="text-align: left"> + <code class="classname">list_update</code> + </td><td style="text-align: left"> + <code class="classname">Update_Policy</code> + </td><td style="text-align: left"> + <code class="classname">lu_move_to_front_policy</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left"> + rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set + </td></tr><tr><td rowspan="6" style="text-align: left" valign="top"> + <code class="classname"> + cc_hash_table + </code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mask_range_hashing</code> + </td><td colspan="4" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_exponential_size_policy</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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" style="text-align: left"> </td></tr><tr><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">Mapped</code> + </td><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">cc_hash_table</code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mask_range_hashing</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_exponential_size_policy</code> + </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_mem_small.observations"/> + Observations + </h6></div></div></div><p>See Observations::Mapping-Semantics + Considerations.</p></div></div><div class="section" title="Text insert with Small Secondary-to-Primary Key Ratios Memory Use"><div class="titlepage"><div><div><h5 class="title"><a id="performance.multimap.text_insert_mem_large"/> + Text <code class="function">insert</code> with Small + Secondary-to-Primary Key Ratios Memory Use + </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_mem_large.info"/> + 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" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_mem_large.results"/> + 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" style="text-align: center"><img src="../images/pbds_multimap_text_insert_mem_large_s2p_tree.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/><col style="text-align: left" class="c6"/><col style="text-align: left" class="c7"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left"> + n_mmap + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::multimap</code> + </td><td colspan="6" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left"> + rb_tree_mmap_lu_mtf_set + </td></tr><tr><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">tree</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">rb_tree_tag</code> + </td><td colspan="4" style="text-align: left"> </td></tr><tr><td style="text-align: left"> + <code class="classname">Node_Update</code> + </td><td style="text-align: left"> + <code class="classname">null_node_update</code> + </td><td colspan="4" style="text-align: left"> </td></tr><tr><td style="text-align: left"> + <code class="classname">Mapped</code> + </td><td style="text-align: left"> + <code class="classname">list_update</code> + </td><td style="text-align: left"> + <code class="classname">Update_Policy</code> + </td><td style="text-align: left"> + <code class="classname">lu_move_to_front_policy</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left"> + rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set + </td></tr><tr><td rowspan="5" style="text-align: left" valign="top"> + <code class="classname">tree</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">rb_tree_tag</code> + </td><td colspan="4" style="text-align: left"> </td></tr><tr><td style="text-align: left"> + <code class="classname">Node_Update</code> + </td><td style="text-align: left"> + <code class="classname">null_node_update</code> + </td><td colspan="4" style="text-align: left"> </td></tr><tr><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">Mapped</code> + </td><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">cc_hash_table</code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mask_range_hashing</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_exponential_size_policy</code> + </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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" style="text-align: center"><img src="../images/pbds_multimap_text_find_large_s2p_hash.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/><col style="text-align: left" class="c6"/><col style="text-align: left" class="c7"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left"> + n_hash_mmap + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::tr1::unordered_multimap</code> + </td><td colspan="6" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left"> + rb_tree_mmap_lu_mtf_set + </td></tr><tr><td rowspan="4" style="text-align: left" valign="top"> + <code class="classname"> + cc_hash_table + </code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mask_range_hashing</code> + </td><td colspan="4" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_exponential_size_policy</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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" style="text-align: left"> </td></tr><tr><td style="text-align: left"> + <code class="classname">Mapped</code> + </td><td style="text-align: left"> + <code class="classname">list_update</code> + </td><td style="text-align: left"> + <code class="classname">Update_Policy</code> + </td><td style="text-align: left"> + <code class="classname">lu_move_to_front_policy</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr style="background-color: #B0B0B0"><td colspan="7" style="text-align: left"> + rb_tree_mmap_cc_hash_mask_exp_1div2_nsth_set + </td></tr><tr><td rowspan="6" style="text-align: left" valign="top"> + <code class="classname"> + cc_hash_table + </code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mask_range_hashing</code> + </td><td colspan="4" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_exponential_size_policy</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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" style="text-align: left"> </td></tr><tr><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">Mapped</code> + </td><td rowspan="3" style="text-align: left" valign="top"> + <code class="classname">cc_hash_table</code> + </td><td style="text-align: left"> + <code class="classname">Comb_Hash_Fn</code> + </td><td style="text-align: left"> + <code class="classname">direct_mask_range_hashing</code> + </td><td colspan="2" style="text-align: left"> </td></tr><tr><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">Resize_Policy</code> + </td><td rowspan="2" style="text-align: left" valign="top"> + <code class="classname">hash_standard_resize_policy</code> + </td><td style="text-align: left"> + <code class="classname">Size_Policy</code> + </td><td style="text-align: left"> + <code class="classname">hash_exponential_size_policy</code> + </td></tr><tr><td style="text-align: left" valign="top"> + <code class="classname">Trigger_Policy</code> + </td><td style="text-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" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="multimap.text_insert_mem_large.observations"/> + Observations + </h6></div></div></div><p>See Observations::Mapping-Semantics + Considerations.</p></div></div></div><div class="section" title="Priority Queue"><div class="titlepage"><div><div><h4 class="title"><a id="performance.priority_queue"/>Priority Queue</h4></div></div></div><div class="section" title="Text push"><div class="titlepage"><div><div><h5 class="title"><a id="performance.priority_queue.text_push"/> + Text <code class="function">push</code> + </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_push.info"/> + 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" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_push.results"/> + 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" style="text-align: center"><img src="../images/pbds_priority_queue_text_push.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + n_pq_vector + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Sequence</code> + </td><td style="text-align: left"> + <code class="classname">std::vector</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + n_pq_deque + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Sequence</code> + </td><td style="text-align: left"> + <code class="classname">std::deque</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + binary_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">binary_heap_tag</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + binomial_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">binomial_heap_tag</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + rc_binomial_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">rc_binomial_heap_tag</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + thin_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">thin_heap_tag</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + pairing_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-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" style="text-align: center"><img src="../images/pbds_pairing_priority_queue_text_push.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + n_pq_vector + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Sequence</code> + </td><td style="text-align: left"> + <code class="classname">std::vector</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + n_pq_deque + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Sequence</code> + </td><td style="text-align: left"> + <code class="classname">std::deque</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + thin_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">thin_heap_tag</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + pairing_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">pairing_heap_tag</code> + </td></tr></tbody></table></div></div><div class="section" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_push.observations"/> + 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" title="Text push and pop"><div class="titlepage"><div><div><h5 class="title"><a id="performance.priority_queue.text_push_pop"/> + Text <code class="function">push</code> and <code class="function">pop</code> + </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_push_pop.info"/> + 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" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_push_pop.results"/> + 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" style="text-align: center"><img src="../images/pbds_priority_queue_text_push_pop.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + n_pq_vector + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Sequence</code> + </td><td style="text-align: left"> + <code class="classname">std::vector</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + n_pq_deque + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Sequence</code> + </td><td style="text-align: left"> + <code class="classname">std::deque</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + binary_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">binary_heap_tag</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + binomial_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">binomial_heap_tag</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + rc_binomial_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">rc_binomial_heap_tag</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + thin_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">thin_heap_tag</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + pairing_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-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" style="text-align: center"><img src="../images/pbds_pairing_priority_queue_text_push_pop.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + n_pq_vector + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::priority_queue</code> adapting <code class="classname">std::vector</code> + </td><td style="text-align: left"> + <code class="classname">Sequence</code> + </td><td style="text-align: left"> + <code class="classname">std::vector</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + n_pq_deque + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Sequence</code> + </td><td style="text-align: left"> + <code class="classname">std::deque</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + pairing_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">pairing_heap_tag</code> + </td></tr></tbody></table></div></div><div class="section" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_push_pop.observations"/> + 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" title="Integer push"><div class="titlepage"><div><div><h5 class="title"><a id="performance.priority_queue.int_push"/> + Integer <code class="function">push</code> + </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.int_push.info"/> + 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" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.int_push.results"/> + 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" style="text-align: center"><img src="../images/pbds_priority_queue_int_push.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + n_pq_vector + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Sequence</code> + </td><td style="text-align: left"> + <code class="classname">std::vector</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + n_pq_deque + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Sequence</code> + </td><td style="text-align: left"> + <code class="classname">std::deque</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + binary_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">binary_heap_tag</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + binomial_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">binomial_heap_tag</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + rc_binomial_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">rc_binomial_heap_tag</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + thin_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">thin_heap_tag</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + pairing_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-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" style="text-align: center"><img src="../images/pbds_binary_priority_queue_int_push.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + n_pq_vector + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::priority_queue</code> adapting <code class="classname">std::vector</code> + </td><td style="text-align: left"> + <code class="classname">Sequence</code> + </td><td style="text-align: left"> + <code class="classname">std::vector</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + n_pq_deque + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Sequence</code> + </td><td style="text-align: left"> + <code class="classname">std::deque</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + binary_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">binary_heap_tag</code> + </td></tr></tbody></table></div></div><div class="section" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.int_push.observations"/> + 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" title="Integer push"><div class="titlepage"><div><div><h5 class="title"><a id="performance.priority_queue.int_push_pop"/> + Integer <code class="function">push</code> + </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.int_push_pop.info"/> + 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" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.int_push_pop.results"/> + 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" style="text-align: center"><img src="../images/pbds_priority_queue_int_push_pop.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + n_pq_vector + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Sequence</code> + </td><td style="text-align: left"> + <code class="classname">std::vector</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + n_pq_deque + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Sequence</code> + </td><td style="text-align: left"> + <code class="classname">std::deque</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + binary_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">binary_heap_tag</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + binomial_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">binomial_heap_tag</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + rc_binomial_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">rc_binomial_heap_tag</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + thin_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">thin_heap_tag</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + pairing_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">pairing_heap_tag</code> + </td></tr></tbody></table></div></div><div class="section" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.int_push_pop.observations"/> + 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"><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" title="Text pop Memory Use"><div class="titlepage"><div><div><h5 class="title"><a id="performance.priority_queue.text_pop"/> + Text <code class="function">pop</code> Memory Use + </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_pop.info"/> + 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" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_pop.results"/> + 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" style="text-align: center"><img src="../images/pbds_priority_queue_text_pop_mem.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + n_pq_vector + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Sequence</code> + </td><td style="text-align: left"> + <code class="classname">std::vector</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + n_pq_deque + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Sequence</code> + </td><td style="text-align: left"> + <code class="classname">std::deque</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + binary_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">binary_heap_tag</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + binomial_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">binomial_heap_tag</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + rc_binomial_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">rc_binomial_heap_tag</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + thin_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">thin_heap_tag</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + pairing_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">pairing_heap_tag</code> + </td></tr></tbody></table></div></div><div class="section" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_pop.observations"/> + 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" title="Text join"><div class="titlepage"><div><div><h5 class="title"><a id="performance.priority_queue.text_join"/> + Text <code class="function">join</code> + </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_join.info"/> + 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" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_join.results"/> + 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" style="text-align: center"><img src="../images/pbds_priority_queue_text_join.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + n_pq_vector + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Sequence</code> + </td><td style="text-align: left"> + <code class="classname">std::vector</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + n_pq_deque + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Sequence</code> + </td><td style="text-align: left"> + <code class="classname">std::deque</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + binary_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">binary_heap_tag</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + binomial_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">binomial_heap_tag</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + rc_binomial_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">rc_binomial_heap_tag</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + thin_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">thin_heap_tag</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + pairing_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">pairing_heap_tag</code> + </td></tr></tbody></table></div></div><div class="section" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_join.observations"/> + 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" title="Text modify Up"><div class="titlepage"><div><div><h5 class="title"><a id="performance.priority_queue.text_modify_up"/> + Text <code class="function">modify</code> Up + </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_modify_up.info"/> + 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" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_modify_up.results"/> + 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" style="text-align: center"><img src="../images/pbds_priority_queue_text_modify_up.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + n_pq_vector + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Sequence</code> + </td><td style="text-align: left"> + <code class="classname">std::vector</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + n_pq_deque + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Sequence</code> + </td><td style="text-align: left"> + <code class="classname">std::deque</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + binary_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">binary_heap_tag</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + binomial_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">binomial_heap_tag</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + rc_binomial_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">rc_binomial_heap_tag</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + thin_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">thin_heap_tag</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + pairing_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-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" style="text-align: center"><img src="../images/pbds_pairing_priority_queue_text_modify_up_thin.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + thin_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">thin_heap_tag</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + pairing_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">pairing_heap_tag</code> + </td></tr></tbody></table></div></div><div class="section" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_modify_up.observations"/> + 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" title="Text modify Down"><div class="titlepage"><div><div><h5 class="title"><a id="performance.priority_queue.text_modify_down"/> + Text <code class="function">modify</code> Down + </h5></div></div></div><p/><div class="section" title="Description"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_modify_down.info"/> + 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" title="Results"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_modify_down.results"/> + 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" style="text-align: center"><img src="../images/pbds_priority_queue_text_modify_down.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + n_pq_vector + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Sequence</code> + </td><td style="text-align: left"> + <code class="classname">std::vector</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + n_pq_deque + </td></tr><tr><td style="text-align: left"> + <code class="classname">std::priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Sequence</code> + </td><td style="text-align: left"> + <code class="classname">std::deque</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + binary_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">binary_heap_tag</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + binomial_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">binomial_heap_tag</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + rc_binomial_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">rc_binomial_heap_tag</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + thin_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">thin_heap_tag</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + pairing_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-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" style="text-align: center"><img src="../images/pbds_pairing_priority_queue_text_modify_down_thin.png" style="text-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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/></colgroup><thead><tr><th style="text-align: left"><span class="emphasis"><em>Name/Instantiating Type</em></span></th><th style="text-align: left"><span class="emphasis"><em>Parameter</em></span></th><th style="text-align: left"><span class="emphasis"><em>Details</em></span></th></tr></thead><tbody><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + thin_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">thin_heap_tag</code> + </td></tr><tr style="background-color: #B0B0B0"><td colspan="3" style="text-align: left"> + pairing_heap + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + </td><td style="text-align: left"> + <code class="classname">Tag</code> + </td><td style="text-align: left"> + <code class="classname">pairing_heap_tag</code> + </td></tr></tbody></table></div></div><div class="section" title="Observations"><div class="titlepage"><div><div><h6 class="title"><a id="priority_queue.text_modify_down.observations"/> + 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" title="Observations"><div class="titlepage"><div><div><h4 class="title"><a id="pbds.test.performance.observations"/>Observations</h4></div></div></div><div class="section" title="Associative"><div class="titlepage"><div><div><h5 class="title"><a id="observations.associative"/>Associative</h5></div></div></div><div class="section" title="Underlying Data-Structure Families"><div class="titlepage"><div><div><h6 class="title"><a id="observations.associative.underlying"/> + 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" title="Hash-Based Containers"><div class="titlepage"><div><div><h6 class="title"><a id="observations.associative.hash"/> + 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" title="Hash Policies"><div class="titlepage"><div><div><h6 class="title"><a id="observations.associative.hash_policies"/> + 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" title="Branch-Based Containers"><div class="titlepage"><div><div><h6 class="title"><a id="observations.associative.branch"/> + 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" title="Mapping-Semantics"><div class="titlepage"><div><div><h6 class="title"><a id="observations.associative.mapping_semantics"/> + 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"><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" title="Priority_Queue"><div class="titlepage"><div><div><h5 class="title"><a id="observations.priority_queue"/>Priority_Queue</h5></div></div></div><div class="section" title="Complexity"><div class="titlepage"><div><div><h6 class="title"><a id="observations.priority_queue.complexity"/>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 style="text-align: left" class="c1"/><col style="text-align: left" class="c2"/><col style="text-align: left" class="c3"/><col style="text-align: left" class="c4"/><col style="text-align: left" class="c5"/><col style="text-align: left" class="c6"/></colgroup><thead><tr><th style="text-align: left"> </th><th style="text-align: left"><span class="emphasis"><em><code class="function">push</code></em></span></th><th style="text-align: left"><span class="emphasis"><em><code class="function">pop</code></em></span></th><th style="text-align: left"><span class="emphasis"><em><code class="function">modify</code></em></span></th><th style="text-align: left"><span class="emphasis"><em><code class="function">erase</code></em></span></th><th style="text-align: left"><span class="emphasis"><em><code class="function">join</code></em></span></th></tr></thead><tbody><tr><td style="text-align: left"> + <code class="classname">std::priority_queue</code> + </td><td style="text-align: left"> + Θ(n) worst + Θ(log(n)) amortized + </td><td style="text-align: left"> + Θ(log(n)) Worst + </td><td style="text-align: left"> + Θ(n log(n)) Worst + <sub>[std note 1]</sub> + </td><td style="text-align: left"> + Θ(n log(n)) + <sub>[std note 2]</sub> + </td><td style="text-align: left"> + Θ(n log(n)) + <sub>[std note 1]</sub> + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + <<code class="classname">Tag</code> = + <code class="classname">pairing_heap_tag</code>> + </td><td style="text-align: left"> + O(1) + </td><td style="text-align: left"> + Θ(n) worst + Θ(log(n)) amortized + </td><td style="text-align: left"> + Θ(n) worst + Θ(log(n)) amortized + </td><td style="text-align: left"> + Θ(n) worst + Θ(log(n)) amortized + </td><td style="text-align: left"> + O(1) + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + <<code class="classname">Tag</code> = + <code class="classname">binary_heap_tag</code>> + </td><td style="text-align: left"> + Θ(n) worst + Θ(log(n)) amortized + </td><td style="text-align: left"> + Θ(n) worst + Θ(log(n)) amortized + </td><td style="text-align: left"> + Θ(n) + </td><td style="text-align: left"> + Θ(n) + </td><td style="text-align: left"> + Θ(n) + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + <<code class="classname">Tag</code> = + <code class="classname">binomial_heap_tag</code>> + </td><td style="text-align: left"> + Θ(log(n)) worst + O(1) amortized + </td><td style="text-align: left"> + Θ(log(n)) + </td><td style="text-align: left"> + Θ(log(n)) + </td><td style="text-align: left"> + Θ(log(n)) + </td><td style="text-align: left"> + Θ(log(n)) + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code> + <<code class="classname">Tag</code> = + <code class="classname">rc_binomial_heap_tag</code>> + </td><td style="text-align: left"> + O(1) + </td><td style="text-align: left"> + Θ(log(n)) + </td><td style="text-align: left"> + Θ(log(n)) + </td><td style="text-align: left"> + Θ(log(n)) + </td><td style="text-align: left"> + Θ(log(n)) + </td></tr><tr><td style="text-align: left"> + <code class="classname">priority_queue</code><<code class="classname">Tag</code> = + <code class="classname">thin_heap_tag</code>> + </td><td style="text-align: left"> + O(1) + </td><td style="text-align: left"> + Θ(n) worst + Θ(log(n)) amortized + </td><td style="text-align: left"> + Θ(log(n)) worst + O(1) amortized, + or Θ(log(n)) amortized + <sub>[thin_heap_note]</sub> + </td><td style="text-align: left"> + Θ(n) worst + Θ(log(n)) amortized + </td><td style="text-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" title="Amortized push and pop operations"><div class="titlepage"><div><div><h6 class="title"><a id="observations.priority_queue.amortized_ops"/> + 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"><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" title="Graph Algorithms"><div class="titlepage"><div><div><h6 class="title"><a id="observations.priority_queue.graphs"/> + 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 align="left"><a accesskey="p" href="policy_data_structures_design.html">Prev</a> </td><td align="center"><a accesskey="u" href="policy_data_structures.html">Up</a></td><td align="right"> <a accesskey="n" href="policy_data_structures_biblio.html">Next</a></td></tr><tr><td align="left" valign="top">Design </td><td align="center"><a accesskey="h" href="../index.html">Home</a></td><td align="right" valign="top"> Acknowledgments</td></tr></table></div></body></html> |