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