1 <section xmlns="http://docbook.org/ns/docbook" version="5.0"
2 xml:id="pbds.test" xreflabel="Test">
3 <info><title>Testing</title></info>
4 <?dbhtml filename="policy_based_data_structures_test.html"?>
6 <!-- S01 regression -->
7 <section xml:id="pbds.test.regression">
8 <info><title>Regression</title></info>
10 <para>The library contains a single comprehensive regression test.
11 For a given container type in this library, the test creates
12 an object of the container type and an object of the
13 corresponding standard type (e.g., <classname>std::set</classname>). It
14 then performs a random sequence of methods with random
15 arguments (e.g., inserts, erases, and so forth) on both
16 objects. At each operation, the test checks the return value of
17 the method, and optionally both compares this library's
18 object with the standard's object as well as performing other
19 consistency checks on this library's object (e.g.,
20 order preservation, when applicable, or node invariants, when
23 <para>Additionally, the test integrally checks exception safety
24 and resource leaks. This is done as follows. A special
25 allocator type, written for the purpose of the test, both
26 randomly throws an exceptions when allocations are performed,
27 and tracks allocations and de-allocations. The exceptions thrown
28 at allocations simulate memory-allocation failures; the
29 tracking mechanism checks for memory-related bugs (e.g.,
30 resource leaks and multiple de-allocations). Both
31 this library's containers and the containers' value-types are
32 configured to use this allocator.</para>
34 <para>For granularity, the test is split into the
35 several sources, each checking only some containers.</para>
37 <para>For more details, consult the files in
38 <filename>testsuite/ext/pb_ds/regression</filename>.</para>
41 <!-- S02 performance -->
42 <section xml:id="pbds.test.performance">
43 <info><title>Performance</title></info>
45 <section xml:id="performance.hash">
46 <info><title>Hash-Based</title></info>
49 <!-- 01 <a href="hash_text_find_find_timing_test"> -->
50 <section xml:id="performance.hash.text_find">
52 Text <function>find</function>
56 <section xml:id="hash.text_find.info">
62 This test inserts a number of values with keys from an
64 linkend="biblio.wickland96thirty"/>) into a container,
65 then performs a series of finds using
66 <function>find</function> . It measures the average
67 time for <function>find</function> as a function of
68 the number of values inserted.</para>
70 It uses the test file:
72 performance/ext/pb_ds/text_find_timing_test.cc
77 And uses the data file:
79 filethirty_years_among_the_dead_preproc.txt
83 <para>The test checks the effect of different range-hashing
84 functions, trigger policies, and cache-hashing policies.
89 <section xml:id="hash.text_find.results">
94 <para>The graphic below show the results for the native
95 and collision-chaining hash types the the function
96 applied being a text find timing test using
97 <function>find</function>.
100 <!-- results graphic -->
104 <imagedata align="center" format="PDF" scale="75"
105 fileref="../images/pbds_text_find_timing_test_hash_local.pdf"/>
108 <imagedata align="center" format="PNG" scale="100"
109 fileref="/mnt/share/src/gcc.svn-trunk/libstdc++-v3/doc/xml/images/pbds_text_find_timing_test_hash_local.png"/>
115 The abbreviated names in the legend of the graphic above are
116 instantiated with the types in the following table.
120 <informaltable frame="all">
122 <tgroup cols="5" align="left" colsep="1" rowsep="1">
123 <colspec colname="c1"/>
124 <colspec colname="c2"/>
125 <colspec colname="c3"/>
126 <colspec colname="c4"/>
127 <colspec colname="c5"/>
130 <entry><emphasis>Name/Instantiating Type</emphasis></entry>
131 <entry><emphasis>Parameter</emphasis></entry>
132 <entry><emphasis>Details</emphasis></entry>
133 <entry><emphasis>Parameter</emphasis></entry>
134 <entry><emphasis>Details</emphasis></entry>
142 <?dbhtml bgcolor="#B0B0B0" ?>
143 <entry namest="c1" nameend="c5">
150 <classname>std::tr1::unordered_map</classname>
153 <classname>cache_hash_code</classname>
156 <constant>false</constant>
158 <entry namest="c4" nameend="c5"></entry>
163 <?dbhtml bgcolor="#B0B0B0" ?>
164 <entry namest="c1" nameend="c5">
165 cc_hash_mod_prime_nea_lc_1div8_1div1_nsth_map
170 <entry morerows="2" valign="top">
171 <classname>cc_hash_table</classname>
174 <classname>Comb_Hash_Fn</classname>
177 <classname>direct_mod_range_hashing</classname>
179 <entry namest="c4" nameend="c5"></entry>
183 <entry morerows="1" valign="top">
184 <classname>Resize_Policy</classname>
186 <entry morerows="1" valign="top">
187 <classname>hash_standard_resize_policy</classname>
190 <classname>Size_Policy</classname>
193 <classname>hash_prime_size_policy</classname>
199 <classname>Trigger_Policy</classname>
202 <classname>hash_load_check_resize_trigger</classname> with
203 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/1
209 <?dbhtml bgcolor="#B0B0B0" ?>
210 <entry namest="c1" nameend="c5">
211 cc_hash_mask_exp_nea_lc_1div8_1div2_sth_map
216 <entry morerows="2" valign="top">
222 <classname>Comb_Hash_Fn</classname>
225 <classname>direct_mask_range_hashing</classname>
227 <entry namest="c4" nameend="c5"></entry>
231 <entry morerows="1" valign="top">
232 <classname>Resize_Policy</classname>
234 <entry morerows="1" valign="top">
235 <classname>hash_standard_resize_policy</classname>
238 <classname>Size_Policy</classname>
241 <classname>hash_exponential_size_policy</classname>
247 <classname>Trigger_Policy</classname>
250 <classname>hash_load_check_resize_trigger</classname> with
251 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2
257 <?dbhtml bgcolor="#B0B0B0" ?>
258 <entry namest="c1" nameend="c5">
259 cc_hash_mask_exp_nea_lc_1div8_1div1_nsth_map
264 <entry morerows="2" valign="top">
265 <classname>cc_hash_table</classname>
268 <classname>Comb_Hash_Fn</classname>
271 <classname>direct_mask_range_hashing</classname>
273 <entry namest="c4" nameend="c5"></entry>
277 <entry morerows="1" valign="top">
278 <classname>Resize_Policy</classname>
280 <entry morerows="1" valign="top">
281 <classname>hash_standard_resize_policy</classname>
284 <classname>Size_Policy</classname>
287 <classname>hash_exponential_size_policy</classname>
293 <classname>Trigger_Policy</classname>
296 <classname>hash_load_check_resize_trigger</classname> with
297 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/1
303 <?dbhtml bgcolor="#B0B0B0" ?>
304 <entry namest="c1" nameend="c5">
305 cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_map
309 <entry morerows="2" valign="top">
310 <classname>cc_hash_table</classname>
313 <classname>Comb_Hash_Fn</classname>
316 <classname>direct_mask_range_hashing</classname>
318 <entry namest="c4" nameend="c5"></entry>
322 <entry morerows="1" valign="top">
323 <classname>Resize_Policy</classname>
325 <entry morerows="1" valign="top">
326 <classname>hash_standard_resize_policy</classname>
329 <classname>Size_Policy</classname>
332 <classname>hash_exponential_size_policy</classname>
338 <classname>Trigger_Policy</classname>
341 <classname>hash_load_check_resize_trigger</classname> with
342 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2
352 <section xml:id="hash.text_find.observations">
357 <para>In this setting, the range-hashing scheme affects performance
358 more than other policies. As the results show, containers using
359 mod-based range-hashing (including the native hash-based container,
360 which is currently hard-wired to this scheme) have lower performance
361 than those using mask-based range-hashing. A modulo-based
362 range-hashing scheme's main benefit is that it takes into account
363 all hash-value bits. Standard string hash-functions are designed to
364 create hash values that are nearly-uniform as is (<xref
365 linkend="biblio.knuth98sorting"/>).</para>
367 <para>Trigger policies, i.e. the load-checks constants, affect
368 performance to a lesser extent.</para>
370 <para>Perhaps surprisingly, storing the hash value alongside each
371 entry affects performance only marginally, at least in this
372 library's implementation. (Unfortunately, it was not possible to run
373 the tests with <classname>std::tr1::unordered_map</classname> 's
374 <classname>cache_hash_code = true</classname> , as it appeared to
381 <!-- 02 <a href="hash_int_find_timing_test"> -->
382 <section xml:id="performance.hash.int_find">
384 Integer <function>find</function>
388 <section xml:id="hash.int_find.info">
393 <para>This test inserts a number of values with uniform
394 integer keys into a container, then performs a series of finds
395 using <function>find</function>. It measures the average time
396 for <function>find</function> as a function of the number of values
400 It uses the test file:
402 performance/ext/pb_ds/random_int_find_timing.cc
406 <para>The test checks the effect of different underlying
408 range-hashing functions, and trigger policies.</para>
412 <section xml:id="hash.int_find.results">
418 There are two sets of results for this type, one for
419 collision-chaining hashes, and one for general-probe hashes.
422 <para>The first graphic below shows the results for the native and
423 collision-chaining hash types. The function applied being a random
424 integer timing test using <function>find</function>.
427 <!-- results graphic 01 -->
431 <imagedata align="center" format="PDF" scale="75"
432 fileref="../images/pbds_cc_hash_random_int_find_timing_test_local.pdf"/>
435 <imagedata align="center" format="PNG" scale="100"
436 fileref="/mnt/share/src/gcc.svn-trunk/libstdc++-v3/doc/xml/images/pbds_cc_hash_random_int_find_timing_test_local.png"/>
442 The abbreviated names in the legend of the graphic above are
443 instantiated with the types in the following table.
447 <informaltable frame="all">
449 <tgroup cols="5" align="left" colsep="1" rowsep="1">
450 <colspec colname="c1"/>
451 <colspec colname="c2"/>
452 <colspec colname="c3"/>
453 <colspec colname="c4"/>
454 <colspec colname="c5"/>
457 <entry><emphasis>Name/Instantiating Type</emphasis></entry>
458 <entry><emphasis>Parameter</emphasis></entry>
459 <entry><emphasis>Details</emphasis></entry>
460 <entry><emphasis>Parameter</emphasis></entry>
461 <entry><emphasis>Details</emphasis></entry>
469 <?dbhtml bgcolor="#B0B0B0" ?>
470 <entry namest="c1" nameend="c5">
477 <classname>std::tr1::unordered_map</classname>
480 <classname>cache_hash_code</classname>
483 <constant>false</constant>
485 <entry namest="c4" nameend="c5"></entry>
490 <?dbhtml bgcolor="#B0B0B0" ?>
491 <entry namest="c1" nameend="c5">
492 cc_hash_mod_prime_nea_lc_1div8_1div1_nsth_map
497 <entry morerows="2" valign="top">
498 <classname>cc_hash_table</classname>
501 <classname>Comb_Hash_Fn</classname>
504 <classname>direct_mod_range_hashing</classname>
506 <entry namest="c4" nameend="c5"></entry>
510 <entry morerows="1" valign="top">
511 <classname>Resize_Policy</classname>
513 <entry morerows="1" valign="top">
514 <classname>hash_standard_resize_policy</classname>
517 <classname>Size_Policy</classname>
520 <classname>hash_prime_size_policy</classname>
526 <classname>Trigger_Policy</classname>
529 <classname>hash_load_check_resize_trigger</classname> with
530 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/1
536 <?dbhtml bgcolor="#B0B0B0" ?>
537 <entry namest="c1" nameend="c5">
538 cc_hash_mod_prime_nea_lc_1div8_1div2_nsth_map
543 <entry morerows="2" valign="top">
549 <classname>Comb_Hash_Fn</classname>
552 <classname>direct_mod_range_hashing</classname>
554 <entry namest="c4" nameend="c5"></entry>
558 <entry morerows="1" valign="top">
559 <classname>Resize_Policy</classname>
561 <entry morerows="1" valign="top">
562 <classname>hash_standard_resize_policy</classname>
565 <classname>Size_Policy</classname>
568 <classname>hash_prime_size_policy</classname>
574 <classname>Trigger_Policy</classname>
577 <classname>hash_load_check_resize_trigger</classname> with
578 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2
584 <?dbhtml bgcolor="#B0B0B0" ?>
585 <entry namest="c1" nameend="c5">
586 cc_hash_mask_exp_nea_lc_1div8_1div1_nsth_map
591 <entry morerows="2" valign="top">
592 <classname>cc_hash_table</classname>
595 <classname>Comb_Hash_Fn</classname>
598 <classname>direct_mask_range_hashing</classname>
600 <entry namest="c4" nameend="c5"></entry>
604 <entry morerows="1" valign="top">
605 <classname>Resize_Policy</classname>
607 <entry morerows="1" valign="top">
608 <classname>hash_standard_resize_policy</classname>
611 <classname>Size_Policy</classname>
614 <classname>hash_exponential_size_policy</classname>
620 <classname>Trigger_Policy</classname>
623 <classname>hash_load_check_resize_trigger</classname> with
624 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/1
630 <?dbhtml bgcolor="#B0B0B0" ?>
631 <entry namest="c1" nameend="c5">
632 cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_map
636 <entry morerows="2" valign="top">
637 <classname>cc_hash_table</classname>
640 <classname>Comb_Hash_Fn</classname>
643 <classname>direct_mask_range_hashing</classname>
645 <entry namest="c4" nameend="c5"></entry>
649 <entry morerows="1" valign="top">
650 <classname>Resize_Policy</classname>
652 <entry morerows="1" valign="top">
653 <classname>hash_standard_resize_policy</classname>
656 <classname>Size_Policy</classname>
659 <classname>hash_exponential_size_policy</classname>
665 <classname>Trigger_Policy</classname>
668 <classname>hash_load_check_resize_trigger</classname> with
669 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2
683 <para>And the second graphic shows the results for the native and
684 general-probe hash types. The function applied being a random
685 integer timing test using <function>find</function>.
688 <!-- results graphic 02 -->
692 <imagedata align="center" format="PDF" scale="75"
693 fileref="../images/pbds_gp_hash_random_int_find_timing_test_local.pdf"/>
696 <imagedata align="center" format="PNG" scale="100"
697 fileref="/mnt/share/src/gcc.svn-trunk/libstdc++-v3/doc/xml/images/pbds_gp_hash_random_int_find_timing_test_local.png"/>
703 The abbreviated names in the legend of the graphic above are
704 instantiated with the types in the following table.
708 <informaltable frame="all">
710 <tgroup cols="5" align="left" colsep="1" rowsep="1">
711 <colspec colname="c1"/>
712 <colspec colname="c2"/>
713 <colspec colname="c3"/>
714 <colspec colname="c4"/>
715 <colspec colname="c5"/>
718 <entry><emphasis>Name/Instantiating Type</emphasis></entry>
719 <entry><emphasis>Parameter</emphasis></entry>
720 <entry><emphasis>Details</emphasis></entry>
721 <entry><emphasis>Parameter</emphasis></entry>
722 <entry><emphasis>Details</emphasis></entry>
730 <?dbhtml bgcolor="#B0B0B0" ?>
731 <entry namest="c1" nameend="c5">
738 <classname>std::tr1::unordered_map</classname>
741 <classname>cache_hash_code</classname>
744 <constant>false</constant>
746 <entry namest="c4" nameend="c5"></entry>
751 <?dbhtml bgcolor="#B0B0B0" ?>
752 <entry namest="c1" nameend="c5">
753 gp_hash_mod_quadp_prime_nea_lc_1div8_1div2_nsth_map
758 <entry morerows="3" valign="top">
759 <classname>gp_hash_table</classname>
762 <classname>Comb_Hash_Fn</classname>
765 <classname>direct_mod_range_hashing</classname>
767 <entry namest="c4" nameend="c5"></entry>
772 <classname>Probe_Fn</classname>
775 <classname>quadratic_probe_fn</classname>
777 <entry namest="c4" nameend="c5"></entry>
781 <entry morerows="1" valign="top">
782 <classname>Resize_Policy</classname>
784 <entry morerows="1" valign="top">
785 <classname>hash_standard_resize_policy</classname>
788 <classname>Size_Policy</classname>
791 <classname>hash_prime_size_policy</classname>
797 <classname>Trigger_Policy</classname>
800 <classname>hash_load_check_resize_trigger</classname> with
801 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2
807 <?dbhtml bgcolor="#B0B0B0" ?>
808 <entry namest="c1" nameend="c5">
809 gp_hash_mask_linp_exp_nea_lc_1div8_1div2_nsth_map
814 <entry morerows="3" valign="top">
820 <classname>Comb_Hash_Fn</classname>
823 <classname>direct_mask_range_hashing</classname>
825 <entry namest="c4" nameend="c5"></entry>
830 <classname>Probe_Fn</classname>
833 <classname>linear_probe_fn</classname>
835 <entry namest="c4" nameend="c5"></entry>
839 <entry morerows="1" valign="top">
840 <classname>Resize_Policy</classname>
842 <entry morerows="1" valign="top">
843 <classname>hash_standard_resize_policy</classname>
846 <classname>Size_Policy</classname>
849 <classname>hash_exponential_size_policy</classname>
855 <classname>Trigger_Policy</classname>
858 <classname>hash_load_check_resize_trigger</classname> with
859 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2
869 <section xml:id="hash.int_find.observations">
874 <para>In this setting, the choice of underlying hash-table affects
875 performance most, then the range-hashing scheme and, only finally,
876 other policies.</para>
878 <para>When comparing probing and chaining containers, it is
879 apparent that the probing containers are less efficient than the
880 collision-chaining containers (
881 <classname>std::tr1::unordered_map</classname> uses
882 collision-chaining) in this case.</para>
884 <para>Hash-Based Integer Subscript Insert Timing Test shows
885 a different case, where the situation is reversed;
888 <para>Within each type of hash-table, the range-hashing scheme
889 affects performance more than other policies; Hash-Based Text
890 <function>find</function> Find Timing Test also shows this. In the
891 above graphics should be noted that
892 <classname>std::tr1::unordered_map</classname> are hard-wired
893 currently to mod-based schemes.
900 <!-- 03 <a href="hash_int_subscript_find_test"> -->
901 <section xml:id="performance.hash.int_subscript_find">
903 Integer Subscript <function>find</function>
907 <section xml:id="hash.int_subscript_find.info">
912 <para>This test inserts a number of values with uniform
913 integer keys into a container, then performs a series of finds
914 using <function>operator[]</function>. It measures the average time
915 for <function>operator[]</function> as a function of the number of
916 values inserted.</para>
919 It uses the test file:
921 performance/ext/pb_ds/random_int_subscript_find_timing.cc
925 <para>The test checks the effect of different underlying
926 hash-tables, range-hashing functions, and trigger policies.</para>
931 <section xml:id="hash.int_subscript_find.results">
937 There are two sets of results for this type, one for
938 collision-chaining hashes, and one for general-probe hashes.
941 <para>The first graphic below shows the results for the native
942 and collision-chaining hash types, using as the function
943 applied an integer subscript timing test with
944 <function>find</function>.
947 <!-- results graphic -->
951 <imagedata align="center" format="PDF" scale="75"
952 fileref="../images/pbds_cc_hash_random_int_subscript_timing_test_find_local.pdf"/>
955 <imagedata align="center" format="PNG" scale="100"
956 fileref="/mnt/share/src/gcc.svn-trunk/libstdc++-v3/doc/xml/images/pbds_cc_hash_random_int_subscript_timing_test_find_local.png"/>
962 The abbreviated names in the legend of the graphic above are
963 instantiated with the types in the following table.
966 <informaltable frame="all">
968 <tgroup cols="5" align="left" colsep="1" rowsep="1">
969 <colspec colname="c1"/>
970 <colspec colname="c2"/>
971 <colspec colname="c3"/>
972 <colspec colname="c4"/>
973 <colspec colname="c5"/>
976 <entry><emphasis>Name/Instantiating Type</emphasis></entry>
977 <entry><emphasis>Parameter</emphasis></entry>
978 <entry><emphasis>Details</emphasis></entry>
979 <entry><emphasis>Parameter</emphasis></entry>
980 <entry><emphasis>Details</emphasis></entry>
988 <?dbhtml bgcolor="#B0B0B0" ?>
989 <entry namest="c1" nameend="c5">
996 <classname>std::tr1::unordered_map</classname>
999 <classname>cache_hash_code</classname>
1002 <constant>false</constant>
1004 <entry namest="c4" nameend="c5"></entry>
1009 <?dbhtml bgcolor="#B0B0B0" ?>
1010 <entry namest="c1" nameend="c5">
1011 cc_hash_mod_prime_nea_lc_1div8_1div1_nsth_map
1016 <entry morerows="2" valign="top">
1017 <classname>cc_hash_table</classname>
1020 <classname>Comb_Hash_Fn</classname>
1023 <classname>direct_mod_range_hashing</classname>
1025 <entry namest="c4" nameend="c5"></entry>
1029 <entry morerows="1" valign="top">
1030 <classname>Resize_Policy</classname>
1032 <entry morerows="1" valign="top">
1033 <classname>hash_standard_resize_policy</classname>
1036 <classname>Size_Policy</classname>
1039 <classname>hash_prime_size_policy</classname>
1044 <entry valign="top">
1045 <classname>Trigger_Policy</classname>
1048 <classname>hash_load_check_resize_trigger</classname> with
1049 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/1
1055 <?dbhtml bgcolor="#B0B0B0" ?>
1056 <entry namest="c1" nameend="c5">
1057 cc_hash_mod_prime_nea_lc_1div8_1div2_nsth_map
1062 <entry morerows="2" valign="top">
1063 <classname>cc_hash_table</classname>
1066 <classname>Comb_Hash_Fn</classname>
1069 <classname>direct_mod_range_hashing</classname>
1071 <entry namest="c4" nameend="c5"></entry>
1075 <entry morerows="1" valign="top">
1076 <classname>Resize_Policy</classname>
1078 <entry morerows="1" valign="top">
1079 <classname>hash_standard_resize_policy</classname>
1082 <classname>Size_Policy</classname>
1085 <classname>hash_prime_size_policy</classname>
1090 <entry valign="top">
1091 <classname>Trigger_Policy</classname>
1094 <classname>hash_load_check_resize_trigger</classname> with
1095 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2
1101 <?dbhtml bgcolor="#B0B0B0" ?>
1102 <entry namest="c1" nameend="c5">
1103 cc_hash_mask_exp_nea_lc_1div8_1div1_nsth_map
1108 <entry morerows="2" valign="top">
1109 <classname>cc_hash_table</classname>
1112 <classname>Comb_Hash_Fn</classname>
1115 <classname>direct_mask_range_hashing</classname>
1117 <entry namest="c4" nameend="c5"></entry>
1121 <entry morerows="1" valign="top">
1122 <classname>Resize_Policy</classname>
1124 <entry morerows="1" valign="top">
1125 <classname>hash_standard_resize_policy</classname>
1128 <classname>Size_Policy</classname>
1131 <classname>hash_exponential_size_policy</classname>
1136 <entry valign="top">
1137 <classname>Trigger_Policy</classname>
1140 <classname>hash_load_check_resize_trigger</classname> with
1141 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/1
1147 <?dbhtml bgcolor="#B0B0B0" ?>
1148 <entry namest="c1" nameend="c5">
1149 cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_map
1153 <entry morerows="2" valign="top">
1154 <classname>cc_hash_table</classname>
1157 <classname>Comb_Hash_Fn</classname>
1160 <classname>direct_mask_range_hashing</classname>
1162 <entry namest="c4" nameend="c5"></entry>
1166 <entry morerows="1" valign="top">
1167 <classname>Resize_Policy</classname>
1169 <entry morerows="1" valign="top">
1170 <classname>hash_standard_resize_policy</classname>
1173 <classname>Size_Policy</classname>
1176 <classname>hash_exponential_size_policy</classname>
1181 <entry valign="top">
1182 <classname>Trigger_Policy</classname>
1185 <classname>hash_load_check_resize_trigger</classname> with
1186 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2
1201 <para>And the second graphic shows the results for the native and
1202 general-probe hash types. The function applied being a random
1203 integer timing test using <function>find</function>.
1206 <!-- results graphic 02 -->
1210 <imagedata align="center" format="PDF" scale="75"
1211 fileref="../images/pbds_gp_hash_random_int_subscript_timing_test_find_local.pdf"/>
1214 <imagedata align="center" format="PNG" scale="100"
1215 fileref="/mnt/share/src/gcc.svn-trunk/libstdc++-v3/doc/xml/images/pbds_gp_hash_random_int_subscript_timing_test_find_local.png"/>
1221 The abbreviated names in the legend of the graphic above are
1222 instantiated with the types in the following table.
1226 <informaltable frame="all">
1228 <tgroup cols="5" align="left" colsep="1" rowsep="1">
1229 <colspec colname="c1"/>
1230 <colspec colname="c2"/>
1231 <colspec colname="c3"/>
1232 <colspec colname="c4"/>
1233 <colspec colname="c5"/>
1236 <entry><emphasis>Name/Instantiating Type</emphasis></entry>
1237 <entry><emphasis>Parameter</emphasis></entry>
1238 <entry><emphasis>Details</emphasis></entry>
1239 <entry><emphasis>Parameter</emphasis></entry>
1240 <entry><emphasis>Details</emphasis></entry>
1248 <?dbhtml bgcolor="#B0B0B0" ?>
1249 <entry namest="c1" nameend="c5">
1256 <classname>std::tr1::unordered_map</classname>
1259 <classname>cache_hash_code</classname>
1262 <constant>false</constant>
1264 <entry namest="c4" nameend="c5"></entry>
1269 <?dbhtml bgcolor="#B0B0B0" ?>
1270 <entry namest="c1" nameend="c5">
1271 gp_hash_mod_quadp_prime_nea_lc_1div8_1div2_nsth_map
1276 <entry morerows="3" valign="top">
1277 <classname>gp_hash_table</classname>
1280 <classname>Comb_Hash_Fn</classname>
1283 <classname>direct_mod_range_hashing</classname>
1285 <entry namest="c4" nameend="c5"></entry>
1290 <classname>Probe_Fn</classname>
1293 <classname>quadratic_probe_fn</classname>
1295 <entry namest="c4" nameend="c5"></entry>
1299 <entry morerows="1" valign="top">
1300 <classname>Resize_Policy</classname>
1302 <entry morerows="1" valign="top">
1303 <classname>hash_standard_resize_policy</classname>
1306 <classname>Size_Policy</classname>
1309 <classname>hash_prime_size_policy</classname>
1314 <entry valign="top">
1315 <classname>Trigger_Policy</classname>
1318 <classname>hash_load_check_resize_trigger</classname> with
1319 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2
1325 <?dbhtml bgcolor="#B0B0B0" ?>
1326 <entry namest="c1" nameend="c5">
1327 gp_hash_mask_linp_exp_nea_lc_1div8_1div2_nsth_map
1332 <entry morerows="3" valign="top">
1338 <classname>Comb_Hash_Fn</classname>
1341 <classname>direct_mask_range_hashing</classname>
1343 <entry namest="c4" nameend="c5"></entry>
1348 <classname>Probe_Fn</classname>
1351 <classname>linear_probe_fn</classname>
1353 <entry namest="c4" nameend="c5"></entry>
1357 <entry morerows="1" valign="top">
1358 <classname>Resize_Policy</classname>
1360 <entry morerows="1" valign="top">
1361 <classname>hash_standard_resize_policy</classname>
1364 <classname>Size_Policy</classname>
1367 <classname>hash_exponential_size_policy</classname>
1372 <entry valign="top">
1373 <classname>Trigger_Policy</classname>
1376 <classname>hash_load_check_resize_trigger</classname> with
1377 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2
1388 <section xml:id="hash.int_subscript_find.observations">
1392 <para>This test shows similar results to Hash-Based
1393 Integer <classname>find</classname> Find Timing test.</para>
1399 <!-- 04 <a href="hash_random_int_subscript_insert_timing_test"> -->
1400 <section xml:id="performance.hash.int_subscript_insert">
1402 Integer Subscript <function>insert</function>
1406 <section xml:id="hash.int_subscript_insert.info">
1411 <para>This test inserts a number of values with uniform i.i.d.
1412 integer keys into a container, using
1413 <function>operator[]</function>. It measures the average time for
1414 <function>operator[]</function> as a function of the number of
1415 values inserted.</para>
1418 It uses the test file:
1420 performance/ext/pb_ds/random_int_subscript_insert_timing.cc
1424 <para>The test checks the effect of different underlying
1430 <section xml:id="hash.int_subscript_insert.results">
1436 There are two sets of results for this type, one for
1437 collision-chaining hashes, and one for general-probe hashes.
1440 <para>The first graphic below shows the results for the native
1441 and collision-chaining hash types, using as the function
1442 applied an integer subscript timing test with
1443 <function>insert</function>.
1446 <!-- results graphic -->
1450 <imagedata align="center" format="PDF" scale="75"
1451 fileref="../images/pbds_cc_hash_random_int_subscript_timing_test_insert_local.pdf"/>
1454 <imagedata align="center" format="PNG" scale="100"
1455 fileref="/mnt/share/src/gcc.svn-trunk/libstdc++-v3/doc/xml/images/pbds_cc_hash_random_int_subscript_timing_test_insert_local.png"/>
1461 The abbreviated names in the legend of the graphic above are
1462 instantiated with the types in the following table.
1465 <informaltable frame="all">
1467 <tgroup cols="5" align="left" colsep="1" rowsep="1">
1468 <colspec colname="c1"/>
1469 <colspec colname="c2"/>
1470 <colspec colname="c3"/>
1471 <colspec colname="c4"/>
1472 <colspec colname="c5"/>
1475 <entry><emphasis>Name/Instantiating Type</emphasis></entry>
1476 <entry><emphasis>Parameter</emphasis></entry>
1477 <entry><emphasis>Details</emphasis></entry>
1478 <entry><emphasis>Parameter</emphasis></entry>
1479 <entry><emphasis>Details</emphasis></entry>
1487 <?dbhtml bgcolor="#B0B0B0" ?>
1488 <entry namest="c1" nameend="c5">
1495 <classname>std::tr1::unordered_map</classname>
1498 <classname>cache_hash_code</classname>
1501 <constant>false</constant>
1503 <entry namest="c4" nameend="c5"></entry>
1508 <?dbhtml bgcolor="#B0B0B0" ?>
1509 <entry namest="c1" nameend="c5">
1510 cc_hash_mod_prime_nea_lc_1div8_1div1_nsth_map
1515 <entry morerows="2" valign="top">
1516 <classname>cc_hash_table</classname>
1519 <classname>Comb_Hash_Fn</classname>
1522 <classname>direct_mod_range_hashing</classname>
1524 <entry namest="c4" nameend="c5"></entry>
1528 <entry morerows="1" valign="top">
1529 <classname>Resize_Policy</classname>
1531 <entry morerows="1" valign="top">
1532 <classname>hash_standard_resize_policy</classname>
1535 <classname>Size_Policy</classname>
1538 <classname>hash_prime_size_policy</classname>
1543 <entry valign="top">
1544 <classname>Trigger_Policy</classname>
1547 <classname>hash_load_check_resize_trigger</classname> with
1548 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/1
1554 <?dbhtml bgcolor="#B0B0B0" ?>
1555 <entry namest="c1" nameend="c5">
1556 cc_hash_mod_prime_nea_lc_1div8_1div2_nsth_map
1561 <entry morerows="2" valign="top">
1562 <classname>cc_hash_table</classname>
1565 <classname>Comb_Hash_Fn</classname>
1568 <classname>direct_mod_range_hashing</classname>
1570 <entry namest="c4" nameend="c5"></entry>
1574 <entry morerows="1" valign="top">
1575 <classname>Resize_Policy</classname>
1577 <entry morerows="1" valign="top">
1578 <classname>hash_standard_resize_policy</classname>
1581 <classname>Size_Policy</classname>
1584 <classname>hash_prime_size_policy</classname>
1589 <entry valign="top">
1590 <classname>Trigger_Policy</classname>
1593 <classname>hash_load_check_resize_trigger</classname> with
1594 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2
1600 <?dbhtml bgcolor="#B0B0B0" ?>
1601 <entry namest="c1" nameend="c5">
1602 cc_hash_mask_exp_nea_lc_1div8_1div1_nsth_map
1607 <entry morerows="2" valign="top">
1608 <classname>cc_hash_table</classname>
1611 <classname>Comb_Hash_Fn</classname>
1614 <classname>direct_mask_range_hashing</classname>
1616 <entry namest="c4" nameend="c5"></entry>
1620 <entry morerows="1" valign="top">
1621 <classname>Resize_Policy</classname>
1623 <entry morerows="1" valign="top">
1624 <classname>hash_standard_resize_policy</classname>
1627 <classname>Size_Policy</classname>
1630 <classname>hash_exponential_size_policy</classname>
1635 <entry valign="top">
1636 <classname>Trigger_Policy</classname>
1639 <classname>hash_load_check_resize_trigger</classname> with
1640 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/1
1646 <?dbhtml bgcolor="#B0B0B0" ?>
1647 <entry namest="c1" nameend="c5">
1648 cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_map
1652 <entry morerows="2" valign="top">
1653 <classname>cc_hash_table</classname>
1656 <classname>Comb_Hash_Fn</classname>
1659 <classname>direct_mask_range_hashing</classname>
1661 <entry namest="c4" nameend="c5"></entry>
1665 <entry morerows="1" valign="top">
1666 <classname>Resize_Policy</classname>
1668 <entry morerows="1" valign="top">
1669 <classname>hash_standard_resize_policy</classname>
1672 <classname>Size_Policy</classname>
1675 <classname>hash_exponential_size_policy</classname>
1680 <entry valign="top">
1681 <classname>Trigger_Policy</classname>
1684 <classname>hash_load_check_resize_trigger</classname> with
1685 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2
1700 <para>And the second graphic shows the results for the native and
1701 general-probe hash types. The function applied being a random
1702 integer timing test using <function>find</function>.
1705 <!-- results graphic 02 -->
1709 <imagedata align="center" format="PDF" scale="75"
1710 fileref="../images/pbds_gp_hash_random_int_subscript_timing_test_insert_local.pdf"/>
1713 <imagedata align="center" format="PNG" scale="100"
1714 fileref="/mnt/share/src/gcc.svn-trunk/libstdc++-v3/doc/xml/images/pbds_gp_hash_random_int_subscript_timing_test_insert_local.png"/>
1720 The abbreviated names in the legend of the graphic above are
1721 instantiated with the types in the following table.
1725 <informaltable frame="all">
1727 <tgroup cols="5" align="left" colsep="1" rowsep="1">
1728 <colspec colname="c1"/>
1729 <colspec colname="c2"/>
1730 <colspec colname="c3"/>
1731 <colspec colname="c4"/>
1732 <colspec colname="c5"/>
1735 <entry><emphasis>Name/Instantiating Type</emphasis></entry>
1736 <entry><emphasis>Parameter</emphasis></entry>
1737 <entry><emphasis>Details</emphasis></entry>
1738 <entry><emphasis>Parameter</emphasis></entry>
1739 <entry><emphasis>Details</emphasis></entry>
1747 <?dbhtml bgcolor="#B0B0B0" ?>
1748 <entry namest="c1" nameend="c5">
1755 <classname>std::tr1::unordered_map</classname>
1758 <classname>cache_hash_code</classname>
1761 <constant>false</constant>
1763 <entry namest="c4" nameend="c5"></entry>
1768 <?dbhtml bgcolor="#B0B0B0" ?>
1769 <entry namest="c1" nameend="c5">
1770 gp_hash_mod_quadp_prime_nea_lc_1div8_1div2_nsth_map
1775 <entry morerows="3" valign="top">
1776 <classname>gp_hash_table</classname>
1779 <classname>Comb_Hash_Fn</classname>
1782 <classname>direct_mod_range_hashing</classname>
1784 <entry namest="c4" nameend="c5"></entry>
1789 <classname>Probe_Fn</classname>
1792 <classname>quadratic_probe_fn</classname>
1794 <entry namest="c4" nameend="c5"></entry>
1798 <entry morerows="1" valign="top">
1799 <classname>Resize_Policy</classname>
1801 <entry morerows="1" valign="top">
1802 <classname>hash_standard_resize_policy</classname>
1805 <classname>Size_Policy</classname>
1808 <classname>hash_prime_size_policy</classname>
1813 <entry valign="top">
1814 <classname>Trigger_Policy</classname>
1817 <classname>hash_load_check_resize_trigger</classname> with
1818 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2
1824 <?dbhtml bgcolor="#B0B0B0" ?>
1825 <entry namest="c1" nameend="c5">
1826 gp_hash_mask_linp_exp_nea_lc_1div8_1div2_nsth_map
1831 <entry morerows="3" valign="top">
1837 <classname>Comb_Hash_Fn</classname>
1840 <classname>direct_mask_range_hashing</classname>
1842 <entry namest="c4" nameend="c5"></entry>
1847 <classname>Probe_Fn</classname>
1850 <classname>linear_probe_fn</classname>
1852 <entry namest="c4" nameend="c5"></entry>
1856 <entry morerows="1" valign="top">
1857 <classname>Resize_Policy</classname>
1859 <entry morerows="1" valign="top">
1860 <classname>hash_standard_resize_policy</classname>
1863 <classname>Size_Policy</classname>
1866 <classname>hash_exponential_size_policy</classname>
1871 <entry valign="top">
1872 <classname>Trigger_Policy</classname>
1875 <classname>hash_load_check_resize_trigger</classname> with
1876 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2
1887 <section xml:id="hash.int_subscript_insert.observations">
1892 <para>In this setting, as in Hash-Based Text
1893 <function>find</function> Find Timing test and Hash-Based
1894 Integer <function>find</function> Find Timing test , the choice
1895 of underlying hash-table underlying hash-table affects performance
1896 most, then the range-hashing scheme, and
1897 finally any other policies.</para>
1898 <para>There are some differences, however:</para>
1900 <listitem><para>In this setting, probing tables function sometimes more
1901 efficiently than collision-chaining tables.
1902 This is explained shortly.</para></listitem>
1903 <listitem><para>The performance graphs have a "saw-tooth" shape. The
1904 average insert time rises and falls. As values are inserted
1905 into the container, the load factor grows larger. Eventually,
1906 a resize occurs. The reallocations and rehashing are
1907 relatively expensive. After this, the load factor is smaller
1908 than before.</para></listitem>
1911 <para>Collision-chaining containers use indirection for greater
1912 flexibility; probing containers store values contiguously, in
1913 an array (see Figure Motivation::Different
1914 underlying data structures A and B, respectively). It
1915 follows that for simple data types, probing containers access
1916 their allocator less frequently than collision-chaining
1917 containers, (although they still have less efficient probing
1918 sequences). This explains why some probing containers fare
1919 better than collision-chaining containers in this case.</para>
1922 Within each type of hash-table, the range-hashing scheme affects
1923 performance more than other policies. This is similar to the
1924 situation in Hash-Based Text
1925 <function>find</function> Find Timing Test and Hash-Based
1926 Integer <function>find</function> Find Timing Test.
1927 Unsurprisingly, however, containers with lower α<subscript>max</subscript> perform worse in this case,
1928 since more re-hashes are performed.</para>
1935 <!-- 05 <a href="hash_zlob_random_int_find_find_timing_test"> -->
1937 <!-- 05 <a href="hash_zlob_random_int_find_find_timing_test"> -->
1938 <section xml:id="performance.hash.zlob_int_find">
1940 Integer <function>find</function> with Skewed-Distribution
1944 <section xml:id="hash.zlob_int_find.info">
1949 <para>This test inserts a number of values with a markedly
1950 non-uniform integer keys into a container, then performs
1951 a series of finds using <function>find</function>. It measures the average
1952 time for <function>find</function> as a function of the number of values in
1953 the containers. The keys are generated as follows. First, a
1954 uniform integer is created. Then it is then shifted left 8 bits.</para>
1957 It uses the test file:
1959 performance/ext/pb_ds/hash_zlob_random_int_find_timing.cc
1963 <para>The test checks the effect of different range-hashing
1964 functions and trigger policies.</para>
1969 <section xml:id="hash.zlob_int_find.results">
1974 <para>The graphic below show the results for the native, collision-chaining, and general-probing hash types.
1977 <!-- results graphic -->
1981 <imagedata align="center" format="PDF" scale="75"
1982 fileref="../images/pbds_hash_zlob_random_int_find_timing_test_local.pdf"/>
1985 <imagedata align="center" format="PNG" scale="100"
1986 fileref="/mnt/share/src/gcc.svn-trunk/libstdc++-v3/doc/xml/images/pbds_hash_zlob_random_int_find_timing_test_local.png"/>
1992 The abbreviated names in the legend of the graphic above are
1993 instantiated with the types in the following table.
1997 <informaltable frame="all">
1999 <tgroup cols="5" align="left" colsep="1" rowsep="1">
2000 <colspec colname="c1"/>
2001 <colspec colname="c2"/>
2002 <colspec colname="c3"/>
2003 <colspec colname="c4"/>
2004 <colspec colname="c5"/>
2007 <entry><emphasis>Name/Instantiating Type</emphasis></entry>
2008 <entry><emphasis>Parameter</emphasis></entry>
2009 <entry><emphasis>Details</emphasis></entry>
2010 <entry><emphasis>Parameter</emphasis></entry>
2011 <entry><emphasis>Details</emphasis></entry>
2019 <?dbhtml bgcolor="#B0B0B0" ?>
2020 <entry namest="c1" nameend="c5">
2027 <classname>std::tr1::unordered_map</classname>
2030 <classname>cache_hash_code</classname>
2033 <constant>false</constant>
2035 <entry namest="c4" nameend="c5"></entry>
2040 <?dbhtml bgcolor="#B0B0B0" ?>
2041 <entry namest="c1" nameend="c5">
2042 cc_hash_mod_prime_nea_lc_1div8_1div1_nsth_map
2047 <entry morerows="2" valign="top">
2048 <classname>cc_hash_table</classname>
2051 <classname>Comb_Hash_Fn</classname>
2054 <classname>direct_mod_range_hashing</classname>
2056 <entry namest="c4" nameend="c5"></entry>
2060 <entry morerows="1" valign="top">
2061 <classname>Resize_Policy</classname>
2063 <entry morerows="1" valign="top">
2064 <classname>hash_standard_resize_policy</classname>
2067 <classname>Size_Policy</classname>
2070 <classname>hash_prime_size_policy</classname>
2075 <entry valign="top">
2076 <classname>Trigger_Policy</classname>
2079 <classname>hash_load_check_resize_trigger</classname> with
2080 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/1
2086 <?dbhtml bgcolor="#B0B0B0" ?>
2087 <entry namest="c1" nameend="c5">
2088 cc_hash_mask_exp_nea_lc_1div8_1div1_nsth_map
2093 <entry morerows="2" valign="top">
2099 <classname>Comb_Hash_Fn</classname>
2102 <classname>direct_mask_range_hashing</classname>
2104 <entry namest="c4" nameend="c5"></entry>
2108 <entry morerows="1" valign="top">
2109 <classname>Resize_Policy</classname>
2111 <entry morerows="1" valign="top">
2112 <classname>hash_standard_resize_policy</classname>
2115 <classname>Size_Policy</classname>
2118 <classname>hash_exponential_size_policy</classname>
2123 <entry valign="top">
2124 <classname>Trigger_Policy</classname>
2127 <classname>hash_load_check_resize_trigger</classname> with
2128 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/1
2134 <?dbhtml bgcolor="#B0B0B0" ?>
2135 <entry namest="c1" nameend="c5">
2136 gp_hash_mod_quadp_prime_nea_lc_1div8_1div2_nsth_map
2141 <entry morerows="3" valign="top">
2142 <classname>gp_hash_table</classname>
2145 <classname>Comb_Hash_Fn</classname>
2148 <classname>direct_mod_range_hashing</classname>
2150 <entry namest="c4" nameend="c5"></entry>
2155 <classname>Probe_Fn</classname>
2158 <classname>quadratic_probe_fn</classname>
2160 <entry namest="c4" nameend="c5"></entry>
2164 <entry morerows="1" valign="top">
2165 <classname>Resize_Policy</classname>
2167 <entry morerows="1" valign="top">
2168 <classname>hash_standard_resize_policy</classname>
2171 <classname>Size_Policy</classname>
2174 <classname>hash_prime_size_policy</classname>
2179 <entry valign="top">
2180 <classname>Trigger_Policy</classname>
2183 <classname>hash_load_check_resize_trigger</classname> with
2184 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2
2195 <section xml:id="hash.zlob_int_find.observations">
2200 <para>In this setting, the distribution of keys is so skewed that
2201 the underlying hash-table type affects performance marginally.
2202 (This is in contrast with Hash-Based Text
2203 <function>find</function> Find Timing Test, Hash-Based
2204 Integer <function>find</function> Find Timing Test, Hash-Based
2205 Integer Subscript Find Timing Test and Hash-Based
2206 Integer Subscript Insert Timing Test.)</para>
2208 <para>The range-hashing scheme affects performance dramatically. A
2209 mask-based range-hashing scheme effectively maps all values
2210 into the same bucket. Access degenerates into a search within
2211 an unordered linked-list. In the graphic above, it should be noted that
2212 <classname>std::tr1::unordered_map</classname> is hard-wired currently to mod-based and mask-based schemes,
2213 respectively.</para>
2215 <para>When observing the settings of this test, it is apparent
2216 that the keys' distribution is far from natural. One might ask
2217 if the test is not contrived to show that, in some cases,
2218 mod-based range hashing does better than mask-based range
2219 hashing. This is, in fact just the case. A
2220 more natural case in which mod-based range hashing is better was not encountered.
2221 Thus the inescapable conclusion: real-life key distributions are handled better
2222 with an appropriate hash function and a mask-based
2223 range-hashing function. (<filename>pb_ds/example/hash_shift_mask.cc</filename>
2224 shows an example of handling this a-priori known skewed
2225 distribution with a mask-based range-hashing function). If hash
2226 performance is bad, a χ<superscript>2</superscript> test can be used
2227 to check how to transform it into a more uniform
2228 distribution.</para>
2229 <para>For this reason, this library's default range-hashing
2230 function is mask-based.</para>
2237 <!-- 06 <a href="hash_random_int_erase_mem_usage_test"> -->
2239 <!-- 06 <a href="hash_random_int_erase_mem_usage_test"> -->
2240 <section xml:id="performance.hash.erase_mem">
2246 <section xml:id="hash.erase_mem.info">
2251 <para>This test inserts a number of uniform integer keys
2252 into a container, then erases all keys except one. It measures
2253 the final size of the container.</para>
2256 It uses the test file:
2258 performance/ext/pb_ds/hash_random_int_erase_mem_usage.cc
2263 <para>The test checks how containers adjust internally as their
2264 logical size decreases.</para>
2268 <section xml:id="hash.erase_mem.results">
2273 <para>The graphic below show the results for the native, collision-chaining, and general-probing hash types.
2276 <!-- results graphic -->
2280 <imagedata align="center" format="PDF" scale="75"
2281 fileref="../images/pbds_hash_random_int_erase_mem_usage_test_local.pdf"/>
2284 <imagedata align="center" format="PNG" scale="100"
2285 fileref="/mnt/share/src/gcc.svn-trunk/libstdc++-v3/doc/xml/images/pbds_hash_random_int_erase_mem_usage_test_local.png"/>
2291 The abbreviated names in the legend of the graphic above are
2292 instantiated with the types in the following table.
2296 <informaltable frame="all">
2298 <tgroup cols="5" align="left" colsep="1" rowsep="1">
2299 <colspec colname="c1"/>
2300 <colspec colname="c2"/>
2301 <colspec colname="c3"/>
2302 <colspec colname="c4"/>
2303 <colspec colname="c5"/>
2306 <entry><emphasis>Name/Instantiating Type</emphasis></entry>
2307 <entry><emphasis>Parameter</emphasis></entry>
2308 <entry><emphasis>Details</emphasis></entry>
2309 <entry><emphasis>Parameter</emphasis></entry>
2310 <entry><emphasis>Details</emphasis></entry>
2318 <?dbhtml bgcolor="#B0B0B0" ?>
2319 <entry namest="c1" nameend="c5">
2326 <classname>std::tr1::unordered_map</classname>
2329 <classname>cache_hash_code</classname>
2332 <constant>false</constant>
2334 <entry namest="c4" nameend="c5"></entry>
2339 <?dbhtml bgcolor="#B0B0B0" ?>
2340 <entry namest="c1" nameend="c5">
2341 cc_hash_mod_prime_nea_lc_1div8_1div1_nsth_map
2346 <entry morerows="2" valign="top">
2347 <classname>cc_hash_table</classname>
2350 <classname>Comb_Hash_Fn</classname>
2353 <classname>direct_mod_range_hashing</classname>
2355 <entry namest="c4" nameend="c5"></entry>
2359 <entry morerows="1" valign="top">
2360 <classname>Resize_Policy</classname>
2362 <entry morerows="1" valign="top">
2363 <classname>hash_standard_resize_policy</classname>
2366 <classname>Size_Policy</classname>
2369 <classname>hash_prime_size_policy</classname>
2374 <entry valign="top">
2375 <classname>Trigger_Policy</classname>
2378 <classname>hash_load_check_resize_trigger</classname> with
2379 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/1
2385 <?dbhtml bgcolor="#B0B0B0" ?>
2386 <entry namest="c1" nameend="c5">
2387 cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_map
2392 <entry morerows="2" valign="top">
2398 <classname>Comb_Hash_Fn</classname>
2401 <classname>direct_mask_range_hashing</classname>
2403 <entry namest="c4" nameend="c5"></entry>
2407 <entry morerows="1" valign="top">
2408 <classname>Resize_Policy</classname>
2410 <entry morerows="1" valign="top">
2411 <classname>hash_standard_resize_policy</classname>
2414 <classname>Size_Policy</classname>
2417 <classname>hash_exponential_size_policy</classname>
2422 <entry valign="top">
2423 <classname>Trigger_Policy</classname>
2426 <classname>hash_load_check_resize_trigger</classname> with
2427 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2
2433 <?dbhtml bgcolor="#B0B0B0" ?>
2434 <entry namest="c1" nameend="c5">
2435 gp_hash_mask_linp_exp_nea_lc_1div8_1div2_nsth_set
2440 <entry morerows="3" valign="top">
2441 <classname>gp_hash_table</classname>
2444 <classname>Comb_Hash_Fn</classname>
2447 <classname>direct_mask_range_hashing</classname>
2449 <entry namest="c4" nameend="c5"></entry>
2454 <classname>Probe_Fn</classname>
2457 <classname>linear_probe_fn</classname>
2459 <entry namest="c4" nameend="c5"></entry>
2463 <entry morerows="1" valign="top">
2464 <classname>Resize_Policy</classname>
2466 <entry morerows="1" valign="top">
2467 <classname>hash_standard_resize_policy</classname>
2470 <classname>Size_Policy</classname>
2473 <classname>hash_exponential_size_policy</classname>
2478 <entry valign="top">
2479 <classname>Trigger_Policy</classname>
2482 <classname>hash_load_check_resize_trigger</classname> with
2483 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2
2494 <section xml:id="hash.erase_mem.observations">
2498 <para>The standard's hash-based containers act very differently than trees in
2499 this respect. When erasing numerous keys from an standard
2500 associative-container, the resulting memory user varies greatly
2501 depending on whether the container is tree-based or hash-based.
2502 This is a fundamental consequence of the standard's interface for
2503 associative containers, and it is not due to a specific
2504 implementation.</para>
2511 <section xml:id="performance.branch">
2512 <info><title>Branch-Based</title></info>
2515 <!-- 01 <a href="tree_text_insert_timing_test"> -->
2516 <section xml:id="performance.branch.text_insert">
2518 Text <function>insert</function>
2522 <section xml:id="branch.text_insert.info">
2528 <para>This test inserts a number of values with keys from an arbitrary
2529 text ([ wickland96thirty ]) into a container
2530 using <function>insert</function> . It measures the average time
2531 for <function>insert</function> as a function of the number of
2532 values inserted.</para>
2534 <para>The test checks the effect of different underlying
2535 data structures.</para>
2538 It uses the test file:
2540 performance/ext/pb_ds/tree_text_insert_timing.cc
2547 <section xml:id="branch.text_insert.results">
2552 <para>The three graphics below show the results for the native
2553 tree and this library's node-based trees, the native tree and
2554 this library's vector-based trees, and the native tree
2555 and this library's PATRICIA-trie, respectively.
2558 <para>The graphic immediately below shows the results for the
2559 native tree type and several node-based tree types.
2562 <!-- results graphic -->
2566 <imagedata align="center" format="PDF" scale="75"
2567 fileref="../images/pbds_tree_text_insert_timing_test_node_tree_local.pdf"/>
2570 <imagedata align="center" format="PNG" scale="100"
2571 fileref="/mnt/share/src/gcc.svn-trunk/libstdc++-v3/doc/xml/images/pbds_tree_text_insert_timing_test_node_tree_local.png"/>
2577 The abbreviated names in the legend of the graphic above are
2578 instantiated with the types in the following table.
2582 <informaltable frame="all">
2583 <tgroup cols="3" align="left" colsep="1" rowsep="1">
2584 <colspec colname="c1"/>
2585 <colspec colname="c2"/>
2586 <colspec colname="c3"/>
2589 <entry><emphasis>Name/Instantiating Type</emphasis></entry>
2590 <entry><emphasis>Parameter</emphasis></entry>
2591 <entry><emphasis>Details</emphasis></entry>
2599 <?dbhtml bgcolor="#B0B0B0" ?>
2600 <entry namest="c1" nameend="c3">
2607 <classname>std::map</classname>
2609 <entry namest="c2" nameend="c3"></entry>
2614 <?dbhtml bgcolor="#B0B0B0" ?>
2615 <entry namest="c1" nameend="c3">
2621 <entry morerows="1" valign="top">
2622 <classname>tree</classname>
2625 <classname>Tag</classname>
2628 <classname>splay_tree_tag</classname>
2634 <classname>Node_update</classname>
2637 <classname>null_node_update</classname>
2644 <?dbhtml bgcolor="#B0B0B0" ?>
2645 <entry namest="c1" nameend="c3">
2651 <entry morerows="1" valign="top">
2652 <classname>tree</classname>
2655 <classname>Tag</classname>
2658 <classname>rb_tree_tag</classname>
2664 <classname>Node_update</classname>
2667 <classname>null_node_update</classname>
2677 <para>The graphic below shows the results for the
2678 native tree type and a vector-based tree type.
2681 <!-- results graphic -->
2685 <imagedata align="center" format="PDF" scale="75"
2686 fileref="../images/pbds_tree_text_insert_timing_test_vector_tree_local.pdf"/>
2689 <imagedata align="center" format="PNG" scale="100"
2690 fileref="/mnt/share/src/gcc.svn-trunk/libstdc++-v3/doc/xml/images/pbds_tree_text_insert_timing_test_vector_tree_local.png"/>
2696 The abbreviated names in the legend of the graphic above are
2697 instantiated with the types in the following table.
2701 <informaltable frame="all">
2703 <tgroup cols="3" align="left" colsep="1" rowsep="1">
2704 <colspec colname="c1"/>
2705 <colspec colname="c2"/>
2706 <colspec colname="c3"/>
2709 <entry><emphasis>Name/Instantiating Type</emphasis></entry>
2710 <entry><emphasis>Parameter</emphasis></entry>
2711 <entry><emphasis>Details</emphasis></entry>
2719 <?dbhtml bgcolor="#B0B0B0" ?>
2720 <entry namest="c1" nameend="c3">
2727 <classname>std::map</classname>
2729 <entry namest="c2" nameend="c3"></entry>
2734 <?dbhtml bgcolor="#B0B0B0" ?>
2735 <entry namest="c1" nameend="c3">
2741 <entry morerows="1" valign="top">
2742 <classname>tree</classname>
2745 <classname>Tag</classname>
2748 <classname>ov_tree_tag</classname>
2754 <classname>Node_update</classname>
2757 <classname>null_node_update</classname>
2769 <para>The graphic below shows the results for the
2770 native tree type and a PATRICIA trie type.
2773 <!-- results graphic -->
2777 <imagedata align="center" format="PDF" scale="75"
2778 fileref="../images/pbds_tree_text_insert_timing_test_pat_trie_local.pdf"/>
2781 <imagedata align="center" format="PNG" scale="100"
2782 fileref="/mnt/share/src/gcc.svn-trunk/libstdc++-v3/doc/xml/images/pbds_tree_text_insert_timing_test_pat_trie_local.png"/>
2788 The abbreviated names in the legend of the graphic above are
2789 instantiated with the types in the following table.
2793 <informaltable frame="all">
2795 <tgroup cols="3" align="left" colsep="1" rowsep="1">
2796 <colspec colname="c1"/>
2797 <colspec colname="c2"/>
2798 <colspec colname="c3"/>
2801 <entry><emphasis>Name/Instantiating Type</emphasis></entry>
2802 <entry><emphasis>Parameter</emphasis></entry>
2803 <entry><emphasis>Details</emphasis></entry>
2811 <?dbhtml bgcolor="#B0B0B0" ?>
2812 <entry namest="c1" nameend="c3">
2819 <classname>std::map</classname>
2821 <entry namest="c2" nameend="c3"></entry>
2826 <?dbhtml bgcolor="#B0B0B0" ?>
2827 <entry namest="c1" nameend="c3">
2833 <entry morerows="1" valign="top">
2834 <classname>tree</classname>
2837 <classname>Tag</classname>
2840 <classname>pat_trie_tag</classname>
2846 <classname>Node_update</classname>
2849 <classname>null_node_update</classname>
2860 <section xml:id="branch.text_insert.observations">
2865 <para>Observing the first graphic implies that for this setting, a splay tree
2866 (<classname>tree</classname> with <classname>Tag
2867 </classname> = <classname>splay_tree_tag</classname>) does not do
2868 well. See also the Branch-Based
2869 Text <function>find</function> Find Timing Test. The two
2870 red-black trees perform better.</para>
2872 <para>Observing the second graphic, an ordered-vector tree
2873 (<classname>tree</classname> with <classname>Tag
2874 </classname> = <classname>ov_tree_tag</classname>) performs
2875 abysmally. Inserting into this type of tree has linear complexity
2876 [ austern00noset].</para>
2878 <para>Observing the third and last graphic, A PATRICIA trie
2879 (<classname>trie</classname> with <classname>Tag
2880 </classname> = <classname>pat_trie_tag</classname>) has abysmal
2881 performance, as well. This is not that surprising, since a
2882 large-fan-out PATRICIA trie works like a hash table with
2883 collisions resolved by a sub-trie. Each time a collision is
2884 encountered, a new "hash-table" is built A large fan-out PATRICIA
2885 trie, however, doe does well in look-ups (see Branch-Based
2886 Text <function>find</function> Find Timing Test). It may be
2887 beneficial in semi-static settings.</para>
2893 <!-- 02 <a href="tree_text_find_find_timing_test"> -->
2894 <section xml:id="performance.branch.text_find">
2896 Text <function>find</function>
2900 <section xml:id="branch.text_find.info">
2906 <para>This test inserts a number of values with keys from an
2907 arbitrary text ([wickland96thirty]) into
2908 a container, then performs a series of finds using
2909 <function>find</function>. It measures the average time
2910 for <function>find</function> as a function of the number of
2911 values inserted.</para>
2914 It uses the test file:
2916 performance/ext/pb_ds/text_find_timing.cc
2921 <para>The test checks the effect of different underlying
2922 data structures.</para>
2926 <section xml:id="branch.text_find.results">
2931 <para>The graphic immediately below shows the results for the
2932 native tree type and several other tree types.
2935 <!-- results graphic -->
2939 <imagedata align="center" format="PDF" scale="75"
2940 fileref="../images/pbds_text_find_timing_test_tree_like_local.pdf"/>
2943 <imagedata align="center" format="PNG" scale="100"
2944 fileref="/mnt/share/src/gcc.svn-trunk/libstdc++-v3/doc/xml/images/pbds_text_find_timing_test_tree_like_local.png"/>
2950 The abbreviated names in the legend of the graphic above are
2951 instantiated with the types in the following table.
2955 <informaltable frame="all">
2957 <tgroup cols="3" align="left" colsep="1" rowsep="1">
2958 <colspec colname="c1"/>
2959 <colspec colname="c2"/>
2960 <colspec colname="c3"/>
2963 <entry><emphasis>Name/Instantiating Type</emphasis></entry>
2964 <entry><emphasis>Parameter</emphasis></entry>
2965 <entry><emphasis>Details</emphasis></entry>
2973 <?dbhtml bgcolor="#B0B0B0" ?>
2974 <entry namest="c1" nameend="c3">
2981 <classname>std::map</classname>
2983 <entry namest="c2" nameend="c3"></entry>
2988 <?dbhtml bgcolor="#B0B0B0" ?>
2989 <entry namest="c1" nameend="c3">
2995 <entry morerows="1" valign="top">
2996 <classname>tree</classname>
2999 <classname>Tag</classname>
3002 <classname>splay_tree_tag</classname>
3008 <classname>Node_Update</classname>
3011 <classname>null_node_update</classname>
3018 <?dbhtml bgcolor="#B0B0B0" ?>
3019 <entry namest="c1" nameend="c3">
3025 <entry morerows="1" valign="top">
3026 <classname>tree</classname>
3029 <classname>Tag</classname>
3032 <classname>rb_tree_tag</classname>
3038 <classname>Node_Update</classname>
3041 <classname>null_node_update</classname>
3048 <?dbhtml bgcolor="#B0B0B0" ?>
3049 <entry namest="c1" nameend="c3">
3055 <entry morerows="1" valign="top">
3056 <classname>tree</classname>
3059 <classname>Tag</classname>
3062 <classname>ov_tree_tag</classname>
3068 <classname>Node_Update</classname>
3071 <classname>null_node_update</classname>
3078 <?dbhtml bgcolor="#B0B0B0" ?>
3079 <entry namest="c1" nameend="c3">
3085 <entry morerows="1" valign="top">
3086 <classname>tree</classname>
3089 <classname>Tag</classname>
3092 <classname>pat_trie_tag</classname>
3098 <classname>Node_Update</classname>
3101 <classname>null_node_update</classname>
3111 <section xml:id="branch.text_find.observations">
3116 <para>For this setting, a splay tree (<classname>tree</classname>
3118 </classname> = <classname>splay_tree_tag</classname>) does not do
3119 well. This is possibly due to two reasons:</para>
3122 <listitem><para>A splay tree is not guaranteed to be balanced [motwani95random]. If a
3123 splay tree contains n nodes, its average root-leaf
3124 path can be m >> log(n).</para></listitem>
3125 <listitem><para>Assume a specific root-leaf search path has length
3126 m, and the search-target node has distance m'
3127 from the root. A red-black tree will require m + 1
3128 comparisons to find the required node; a splay tree will
3129 require 2 m' comparisons. A splay tree, consequently,
3130 can perform many more comparisons than a red-black tree.</para></listitem>
3132 <para>An ordered-vector tree (<classname>tree</classname>
3133 with <classname>Tag</classname> = <classname>ov_tree_tag</classname>), a red-black
3134 tree (<classname>tree</classname>
3135 with <classname>Tag</classname> = <classname>rb_tree_tag</classname>), and the
3136 native red-black tree all share approximately the same
3138 <para>An ordered-vector tree is slightly slower than red-black
3139 trees, since it requires, in order to find a key, more math
3140 operations than they do. Conversely, an ordered-vector tree
3141 requires far lower space than the others. ([austern00noset], however,
3142 seems to have an implementation that is also faster than a
3143 red-black tree).</para>
3144 <para>A PATRICIA trie (<classname>trie</classname>
3145 with <classname>Tag</classname> = <classname>pat_trie_tag</classname>) has good
3146 look-up performance, due to its large fan-out in this case. In
3147 this setting, a PATRICIA trie has look-up performance comparable
3148 to a hash table (see Hash-Based Text
3149 <classname>find</classname> Timing Test), but it is order
3150 preserving. This is not that surprising, since a large-fan-out
3151 PATRICIA trie works like a hash table with collisions resolved
3152 by a sub-trie. A large-fan-out PATRICIA trie does not do well on
3153 modifications (see Tree-Based and Trie-Based
3154 Text Insert Timing Test). Therefore, it is possibly beneficial in
3155 semi-static settings.</para>
3160 <!-- 03 <a href="tree_text_lor_find_find_timing_test"> -->
3161 <section xml:id="performance.branch.text_lor_find">
3164 Text <function>find</function> with Locality-of-Reference
3168 <section xml:id="branch.text_lor_find.info">
3175 <para>This test inserts a number of values with keys from an
3176 arbitrary text ([ wickland96thirty ]) into
3177 a container, then performs a series of finds using
3178 <function>find</function>. It is different than Tree-Based and
3179 Trie-Based Text <function>find</function> Find Timing Test in the
3180 sequence of finds it performs: this test performs multiple
3181 <function>find</function>s on the same key before moving on to the next
3182 key. It measures the average time for <function>find</function> as a
3183 function of the number of values inserted.</para>
3187 It uses the test file:
3189 performance/ext/pb_ds/tree_text_lor_find_timing.cc
3193 <para>The test checks the effect of different underlying
3194 data structures in a locality-of-reference setting.</para>
3198 <section xml:id="branch.text_lor_find.results">
3203 <para>The graphic immediately below shows the results for the
3204 native tree type and several other tree types.
3207 <!-- results graphic -->
3211 <imagedata align="center" format="PDF" scale="75"
3212 fileref="../images/pbds_tree_text_lor_find_timing_test_local.pdf"/>
3215 <imagedata align="center" format="PNG" scale="100"
3216 fileref="/mnt/share/src/gcc.svn-trunk/libstdc++-v3/doc/xml/images/pbds_tree_text_lor_find_timing_test_local.png"/>
3222 The abbreviated names in the legend of the graphic above are
3223 instantiated with the types in the following table.
3227 <informaltable frame="all">
3229 <tgroup cols="3" align="left" colsep="1" rowsep="1">
3230 <colspec colname="c1"/>
3231 <colspec colname="c2"/>
3232 <colspec colname="c3"/>
3235 <entry><emphasis>Name/Instantiating Type</emphasis></entry>
3236 <entry><emphasis>Parameter</emphasis></entry>
3237 <entry><emphasis>Details</emphasis></entry>
3245 <?dbhtml bgcolor="#B0B0B0" ?>
3246 <entry namest="c1" nameend="c3">
3253 <classname>std::map</classname>
3255 <entry namest="c2" nameend="c3"></entry>
3260 <?dbhtml bgcolor="#B0B0B0" ?>
3261 <entry namest="c1" nameend="c3">
3267 <entry morerows="1" valign="top">
3268 <classname>tree</classname>
3271 <classname>Tag</classname>
3274 <classname>splay_tree_tag</classname>
3280 <classname>Node_Update</classname>
3283 <classname>null_node_update</classname>
3290 <?dbhtml bgcolor="#B0B0B0" ?>
3291 <entry namest="c1" nameend="c3">
3297 <entry morerows="1" valign="top">
3298 <classname>tree</classname>
3301 <classname>Tag</classname>
3304 <classname>rb_tree_tag</classname>
3310 <classname>Node_Update</classname>
3313 <classname>null_node_update</classname>
3320 <?dbhtml bgcolor="#B0B0B0" ?>
3321 <entry namest="c1" nameend="c3">
3327 <entry morerows="1" valign="top">
3328 <classname>tree</classname>
3331 <classname>Tag</classname>
3334 <classname>ov_tree_tag</classname>
3340 <classname>Node_Update</classname>
3343 <classname>null_node_update</classname>
3350 <?dbhtml bgcolor="#B0B0B0" ?>
3351 <entry namest="c1" nameend="c3">
3357 <entry morerows="1" valign="top">
3358 <classname>tree</classname>
3361 <classname>Tag</classname>
3364 <classname>pat_trie_tag</classname>
3370 <classname>Node_Update</classname>
3373 <classname>null_node_update</classname>
3383 <section xml:id="branch.text_lor_find.observations">
3388 <para>For this setting, an ordered-vector tree
3389 (<classname>tree</classname> with <classname>Tag</classname>
3390 = <classname>ov_tree_tag</classname>), a red-black tree
3391 (<classname>tree</classname> with <classname>Tag</classname>
3392 = <classname>rb_tree_tag</classname>), and the native red-black
3393 tree all share approximately the same performance.</para>
3394 <para>A splay tree (<classname>tree</classname>
3395 with <classname>Tag</classname> = <classname>splay_tree_tag</classname>) does
3396 much better, since each (successful) find "bubbles" the
3397 corresponding node to the root of the tree.</para>
3402 <!-- 04 <a href="tree_split_join_timing_test"> -->
3403 <section xml:id="performance.branch.split_join">
3406 <function>split</function> and <function>join</function>
3410 <section xml:id="branch.split_join.info">
3416 <para>This test a container, inserts into a number of values, splits
3417 the container at the median, and joins the two containers. (If the
3418 containers are one of this library's trees,
3419 it splits and joins with the <function>split</function> and
3420 <function>join</function> method; otherwise, it uses the <function>erase</function> and
3421 <function>insert</function> methods.) It measures the time for splitting
3422 and joining the containers as a function of the number of
3423 values inserted.</para>
3426 It uses the test file:
3428 performance/ext/pb_ds/tree_split_join_timing.cc
3433 <para>The test checks the performance difference of <function>join</function>
3434 as opposed to a sequence of <function>insert</function> operations; by
3435 implication, this test checks the most efficient way to erase a
3436 sub-sequence from a tree-like-based container, since this can
3437 always be performed by a small sequence of splits and joins.
3441 <section xml:id="branch.split_join.results">
3446 <para>The graphic immediately below shows the results for the
3447 native tree type and several other tree types.
3450 <!-- results graphic -->
3454 <imagedata align="center" format="PDF" scale="75"
3455 fileref="../images/pbds_tree_split_join_timing_test_local.pdf"/>
3458 <imagedata align="center" format="PNG" scale="100"
3459 fileref="/mnt/share/src/gcc.svn-trunk/libstdc++-v3/doc/xml/images/pbds_tree_split_join_timing_test_local.png"/>
3465 The abbreviated names in the legend of the graphic above are
3466 instantiated with the types in the following table.
3470 <informaltable frame="all">
3472 <tgroup cols="3" align="left" colsep="1" rowsep="1">
3473 <colspec colname="c1"/>
3474 <colspec colname="c2"/>
3475 <colspec colname="c3"/>
3478 <entry><emphasis>Name/Instantiating Type</emphasis></entry>
3479 <entry><emphasis>Parameter</emphasis></entry>
3480 <entry><emphasis>Details</emphasis></entry>
3488 <?dbhtml bgcolor="#B0B0B0" ?>
3489 <entry namest="c1" nameend="c3">
3496 <classname>std::set</classname>
3498 <entry namest="c2" nameend="c3"></entry>
3503 <?dbhtml bgcolor="#B0B0B0" ?>
3504 <entry namest="c1" nameend="c3">
3510 <entry morerows="1" valign="top">
3511 <classname>tree</classname>
3514 <classname>Tag</classname>
3517 <classname>splay_tree_tag</classname>
3523 <classname>Node_Update</classname>
3526 <classname>null_node_update</classname>
3533 <?dbhtml bgcolor="#B0B0B0" ?>
3534 <entry namest="c1" nameend="c3">
3540 <entry morerows="1" valign="top">
3541 <classname>tree</classname>
3544 <classname>Tag</classname>
3547 <classname>rb_tree_tag</classname>
3553 <classname>Node_Update</classname>
3556 <classname>null_node_update</classname>
3563 <?dbhtml bgcolor="#B0B0B0" ?>
3564 <entry namest="c1" nameend="c3">
3570 <entry morerows="1" valign="top">
3571 <classname>tree</classname>
3574 <classname>Tag</classname>
3577 <classname>ov_tree_tag</classname>
3583 <classname>Node_Update</classname>
3586 <classname>null_node_update</classname>
3593 <?dbhtml bgcolor="#B0B0B0" ?>
3594 <entry namest="c1" nameend="c3">
3600 <entry morerows="1" valign="top">
3601 <classname>tree</classname>
3604 <classname>Tag</classname>
3607 <classname>pat_trie_tag</classname>
3613 <classname>Node_Update</classname>
3616 <classname>null_node_update</classname>
3626 <section xml:id="branch.split_join.observations">
3631 <para>In this test, the native red-black trees must be split and
3632 joined externally, through a sequence of <function>erase</function> and
3633 <function>insert</function> operations. This is clearly
3634 super-linear, and it is not that surprising that the cost is
3636 <para>This library's tree-based containers use in this test the
3637 <function>split</function> and <function>join</function> methods,
3638 which have lower complexity: the <function>join</function> method
3639 of a splay tree (<classname>tree</classname>
3640 with <classname>Tag </classname>
3641 = <classname>splay_tree_tag</classname>) is quadratic in the
3642 length of the longest root-leaf path, and linear in the total
3643 number of elements; the <function>join</function> method of a
3644 red-black tree (<classname>tree</classname>
3645 with <classname>Tag </classname>
3646 = <classname>rb_tree_tag</classname>) or an ordered-vector tree
3647 (<classname>tree</classname> with <classname>Tag </classname>
3648 = <classname>ov_tree_tag</classname>) is linear in the number of
3651 <para>Asides from orders of growth, this library's trees access their
3652 allocator very little in these operations, and some of them do not
3653 access it at all. This leads to lower constants in their
3654 complexity, and, for some containers, to exception-free splits and
3655 joins (which can be determined
3656 via <classname>container_traits</classname>).</para>
3658 <para>It is important to note that <function>split</function> and
3659 <function>join</function> are not esoteric methods - they are the most
3660 efficient means of erasing a contiguous range of values from a
3661 tree based container.</para>
3665 <!-- 05 <a href="tree_order_statistics_timing_test"> -->
3666 <section xml:id="performance.branch.order_statistics">
3673 <section xml:id="branch.order_statistics.info">
3678 <para>This test creates a container, inserts random integers into the
3679 the container, and then checks the order-statistics of the
3680 container's values. (If the container is one of this
3681 library's trees, it does this with
3682 the <function>order_of_key</function> method of
3683 <classname>tree_order_statistics_node_update</classname>
3684 ; otherwise, it uses the <function>find</function> method and
3685 <function>std::distance</function>.) It measures the average
3686 time for such queries as a function of the number of values
3690 It uses the test file:
3692 performance/ext/pb_ds/tree_order_statistics_timing.cc
3696 <para>The test checks the performance difference of policies based
3697 on node-invariant as opposed to a external functions.</para>
3701 <section xml:id="branch.order_statistics.results">
3706 <para>The graphic immediately below shows the results for the
3707 native tree type and several other tree types.
3710 <!-- results graphic -->
3714 <imagedata align="center" format="PDF" scale="75"
3715 fileref="../images/pbds_tree_order_statistics_timing_test_local.pdf"/>
3718 <imagedata align="center" format="PNG" scale="100"
3719 fileref="/mnt/share/src/gcc.svn-trunk/libstdc++-v3/doc/xml/images/pbds_tree_order_statistics_timing_test_local.png"/>
3725 The abbreviated names in the legend of the graphic above are
3726 instantiated with the types in the following table.
3730 <informaltable frame="all">
3732 <tgroup cols="3" align="left" colsep="1" rowsep="1">
3733 <colspec colname="c1"/>
3734 <colspec colname="c2"/>
3735 <colspec colname="c3"/>
3738 <entry><emphasis>Name/Instantiating Type</emphasis></entry>
3739 <entry><emphasis>Parameter</emphasis></entry>
3740 <entry><emphasis>Details</emphasis></entry>
3748 <?dbhtml bgcolor="#B0B0B0" ?>
3749 <entry namest="c1" nameend="c3">
3756 <classname>std::set</classname>
3758 <entry namest="c2" nameend="c3"></entry>
3763 <?dbhtml bgcolor="#B0B0B0" ?>
3764 <entry namest="c1" nameend="c3">
3770 <entry morerows="1" valign="top">
3771 <classname>tree</classname>
3774 <classname>Tag</classname>
3777 <classname>splay_tree_tag</classname>
3783 <classname>Node_Update</classname>
3786 <classname>tree_order_statistics_node_update</classname>
3793 <?dbhtml bgcolor="#B0B0B0" ?>
3794 <entry namest="c1" nameend="c3">
3800 <entry morerows="1" valign="top">
3801 <classname>tree</classname>
3804 <classname>Tag</classname>
3807 <classname>rb_tree_tag</classname>
3813 <classname>Node_Update</classname>
3816 <classname>tree_order_statistics_node_update</classname>
3827 <section xml:id="branch.order_statistics.observations">
3831 <para>In this test, the native red-black tree can support
3832 order-statistics queries only externally, by performing a
3833 <classname>find</classname> (alternatively, <classname>lower_bound</classname> or
3834 <classname>upper_bound</classname> ) and then using <classname>std::distance</classname> .
3835 This is clearly linear, and it is not that surprising that the
3836 cost is high.</para>
3837 <para>This library's tree-based containers use in this test the
3838 <classname>order_of_key</classname> method of <classname>tree_order_statistics_node_update</classname>.
3839 This method has only linear complexity in the length of the
3840 root-node path. Unfortunately, the average path of a splay tree
3841 (<classname>tree</classname>
3842 with <classname>Tag =</classname> <classname>splay_tree_tag</classname> ) can
3843 be higher than logarithmic; the longest path of a red-black
3844 tree (<classname>tree</classname>
3845 with <classname>Tag =</classname> <classname>rb_tree_tag</classname> ) is
3846 logarithmic in the number of elements. Consequently, the splay
3847 tree has worse performance than the red-black tree.</para>
3851 </section> <!-- branch -->
3853 <section xml:id="performance.multimap">
3854 <info><title>Multimap</title></info>
3858 <!-- 01 <a href="multimap_text_find_timing_test_small"> -->
3859 <section xml:id="performance.multimap.text_find_small">
3861 Text <function>find</function> with Small Secondary-to-Primary Key Ratios
3865 <section xml:id="multimap.text_find_small.info">
3870 <para>This test inserts a number of pairs into a container. The
3871 first item of each pair is a string from an arbitrary text
3872 [wickland96thirty], and
3873 the second is a uniform i.i.d.integer. The container is a
3874 "multimap" - it considers the first member of each pair as a
3875 primary key, and the second member of each pair as a secondary
3876 key (see Motivation::Associative
3877 Containers::Alternative to Multiple Equivalent Keys). There
3878 are 400 distinct primary keys, and the ratio of secondary keys
3879 to primary keys ranges from 1 to 5.</para>
3880 <para>The test measures the average find-time as a function of the
3881 number of values inserted. For this library's containers, it
3882 finds the secondary key from a container obtained from finding
3883 a primary key. For the native multimaps, it searches a range
3884 obtained using <classname>std::equal_range</classname> on a primary key.</para>
3887 It uses the test file:
3889 performance/ext/pb_ds/multimap_text_find_timing_small.cc
3893 <para>The test checks the find-time scalability of different
3894 "multimap" designs.</para>
3898 <section xml:id="multimap.text_find_small.results">
3903 <para>The graphic below show the results for "multimaps" which
3904 use a tree-based container for primary keys.
3907 <!-- results graphic -->
3911 <imagedata align="center" format="PNG" scale="100"
3912 fileref="/mnt/share/src/gcc.svn-trunk/libstdc++-v3/doc/xml/images/pbds_multimap_text_find_timing_test_small_s2p_tree_local.png"/>
3915 <imagedata align="center" format="PDF" scale="33"
3916 fileref="../images/pbds_multimap_text_find_timing_test_small_s2p_tree_local.pdf"/>
3922 The abbreviated names in the legend of the graphic above are
3923 instantiated with the types in the following table.
3927 <informaltable frame="all">
3929 <tgroup cols="7" align="left" colsep="1" rowsep="1">
3930 <colspec colname="c1"/>
3931 <colspec colname="c2"/>
3932 <colspec colname="c3"/>
3933 <colspec colname="c4"/>
3934 <colspec colname="c5"/>
3935 <colspec colname="c6"/>
3936 <colspec colname="c7"/>
3939 <entry><emphasis>Name/Instantiating Type</emphasis></entry>
3940 <entry><emphasis>Parameter</emphasis></entry>
3941 <entry><emphasis>Details</emphasis></entry>
3942 <entry><emphasis>Parameter</emphasis></entry>
3943 <entry><emphasis>Details</emphasis></entry>
3944 <entry><emphasis>Parameter</emphasis></entry>
3945 <entry><emphasis>Details</emphasis></entry>
3953 <?dbhtml bgcolor="#B0B0B0" ?>
3954 <entry namest="c1" nameend="c7">
3961 <classname>std::multimap</classname>
3963 <entry namest="c2" nameend="c7"></entry>
3966 <!-- multimap 01 -->
3968 <?dbhtml bgcolor="#B0B0B0" ?>
3969 <entry namest="c1" nameend="c7">
3970 rb_tree_mmap_lu_mtf_set
3975 <entry morerows="2" valign="top">
3976 <classname>tree</classname>
3979 <classname>Tag</classname>
3982 <classname>rb_tree_tag</classname>
3984 <entry namest="c4" nameend="c7"></entry>
3989 <classname>Node_Update</classname>
3992 <classname>null_node_update</classname>
3994 <entry namest="c4" nameend="c7"></entry>
3998 <classname>Mapped</classname>
4001 <classname>list_update</classname>
4004 <classname>Update_Policy</classname>
4007 <classname>lu_move_to_front_policy</classname>
4009 <entry namest="c6" nameend="c7"></entry>
4012 <!-- multimap 02 -->
4014 <?dbhtml bgcolor="#B0B0B0" ?>
4015 <entry namest="c1" nameend="c7">
4016 rb_tree_mmap_cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_set
4021 <entry morerows="4" valign="top">
4022 <classname>tree</classname>
4025 <classname>Tag</classname>
4028 <classname>rb_tree_tag</classname>
4030 <entry namest="c4" nameend="c7"></entry>
4035 <classname>Node_Update</classname>
4038 <classname>null_node_update</classname>
4040 <entry namest="c4" nameend="c7"></entry>
4044 <entry morerows="2" valign="top">
4045 <classname>Mapped</classname>
4047 <entry morerows="2" valign="top">
4048 <classname>cc_hash_table</classname>
4051 <classname>Comb_Hash_Fn</classname>
4054 <classname>direct_mask_range_hashing</classname>
4056 <entry namest="c6" nameend="c7"></entry>
4060 <entry morerows="1" valign="top">
4061 <classname>Resize_Policy</classname>
4063 <entry morerows="1" valign="top">
4064 <classname>hash_standard_resize_policy</classname>
4067 <classname>Size_Policy</classname>
4070 <classname>hash_exponential_size_policy</classname>
4075 <entry valign="top">
4076 <classname>Trigger_Policy</classname>
4079 <classname>hash_load_check_resize_trigger</classname> with
4080 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2
4089 <para>The graphic below show the results for "multimaps" which
4090 use a hash-based container for primary keys.
4093 <!-- results graphic -->
4097 <imagedata align="center" format="PNG" scale="100"
4098 fileref="/mnt/share/src/gcc.svn-trunk/libstdc++-v3/doc/xml/images/pbds_multimap_text_find_timing_test_small_s2p_hash_local.png"/>
4101 <imagedata align="center" format="PDF" scale="33"
4102 fileref="../images/pbds_multimap_text_find_timing_test_small_s2p_hash_local.pdf"/>
4108 The abbreviated names in the legend of the graphic above are
4109 instantiated with the types in the following table.
4112 <informaltable frame="all">
4114 <tgroup cols="7" align="left" colsep="1" rowsep="1">
4115 <colspec colname="c1"/>
4116 <colspec colname="c2"/>
4117 <colspec colname="c3"/>
4118 <colspec colname="c4"/>
4119 <colspec colname="c5"/>
4120 <colspec colname="c6"/>
4121 <colspec colname="c7"/>
4124 <entry><emphasis>Name/Instantiating Type</emphasis></entry>
4125 <entry><emphasis>Parameter</emphasis></entry>
4126 <entry><emphasis>Details</emphasis></entry>
4127 <entry><emphasis>Parameter</emphasis></entry>
4128 <entry><emphasis>Details</emphasis></entry>
4129 <entry><emphasis>Parameter</emphasis></entry>
4130 <entry><emphasis>Details</emphasis></entry>
4138 <?dbhtml bgcolor="#B0B0B0" ?>
4139 <entry namest="c1" nameend="c7">
4146 <classname>std::tr1::unordered_multimap</classname>
4148 <entry namest="c2" nameend="c7"></entry>
4151 <!-- multimap 01 -->
4153 <?dbhtml bgcolor="#B0B0B0" ?>
4154 <entry namest="c1" nameend="c7">
4155 rb_tree_mmap_lu_mtf_set
4160 <entry morerows="3" valign="top">
4166 <classname>Comb_Hash_Fn</classname>
4169 <classname>direct_mask_range_hashing</classname>
4171 <entry namest="c4" nameend="c7"></entry>
4174 <entry morerows="1" valign="top">
4175 <classname>Resize_Policy</classname>
4177 <entry morerows="1" valign="top">
4178 <classname>hash_standard_resize_policy</classname>
4181 <classname>Size_Policy</classname>
4184 <classname>hash_exponential_size_policy</classname>
4186 <entry namest="c6" nameend="c7"></entry>
4190 <entry valign="top">
4191 <classname>Trigger_Policy</classname>
4194 <classname>hash_load_check_resize_trigger</classname> with
4195 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2
4197 <entry namest="c6" nameend="c7"></entry>
4202 <classname>Mapped</classname>
4205 <classname>list_update</classname>
4208 <classname>Update_Policy</classname>
4211 <classname>lu_move_to_front_policy</classname>
4213 <entry namest="c6" nameend="c7"></entry>
4216 <!-- multimap 02 -->
4218 <?dbhtml bgcolor="#B0B0B0" ?>
4219 <entry namest="c1" nameend="c7">
4220 rb_tree_mmap_cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_set
4225 <entry morerows="5" valign="top">
4231 <classname>Comb_Hash_Fn</classname>
4234 <classname>direct_mask_range_hashing</classname>
4236 <entry namest="c4" nameend="c7"></entry>
4239 <entry morerows="1" valign="top">
4240 <classname>Resize_Policy</classname>
4242 <entry morerows="1" valign="top">
4243 <classname>hash_standard_resize_policy</classname>
4246 <classname>Size_Policy</classname>
4249 <classname>hash_exponential_size_policy</classname>
4251 <entry namest="c6" nameend="c7"></entry>
4255 <entry valign="top">
4256 <classname>Trigger_Policy</classname>
4259 <classname>hash_load_check_resize_trigger</classname> with
4260 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2
4262 <entry namest="c6" nameend="c7"></entry>
4266 <entry morerows="2" valign="top">
4267 <classname>Mapped</classname>
4269 <entry morerows="2" valign="top">
4270 <classname>cc_hash_table</classname>
4273 <classname>Comb_Hash_Fn</classname>
4276 <classname>direct_mask_range_hashing</classname>
4278 <entry namest="c6" nameend="c7"></entry>
4282 <entry morerows="1" valign="top">
4283 <classname>Resize_Policy</classname>
4285 <entry morerows="1" valign="top">
4286 <classname>hash_standard_resize_policy</classname>
4289 <classname>Size_Policy</classname>
4292 <classname>hash_exponential_size_policy</classname>
4297 <entry valign="top">
4298 <classname>Trigger_Policy</classname>
4301 <classname>hash_load_check_resize_trigger</classname> with
4302 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2
4312 <section xml:id="multimap.text_find_small.observations">
4317 <para>See Observations::Mapping-Semantics
4318 Considerations.</para>
4324 <!-- 02 <a href="multimap_text_find_timing_test_large"> -->
4325 <section xml:id="performance.multimap.text_find_large">
4327 Text <function>find</function> with Large Secondary-to-Primary Key Ratios
4331 <section xml:id="multimap.text_find_large.info">
4336 <para>This test inserts a number of pairs into a container. The
4337 first item of each pair is a string from an arbitrary text
4338 [wickland96thirty], and
4339 the second is a uniform integer. The container is a
4340 "multimap" - it considers the first member of each pair as a
4341 primary key, and the second member of each pair as a secondary
4343 are 400 distinct primary keys, and the ratio of secondary keys
4344 to primary keys ranges from 1 to 5.</para>
4345 <para>The test measures the average find-time as a function of the
4346 number of values inserted. For this library's containers, it
4347 finds the secondary key from a container obtained from finding
4348 a primary key. For the native multimaps, it searches a range
4349 obtained using <classname>std::equal_range</classname> on a primary key.</para>
4352 It uses the test file:
4354 performance/ext/pb_ds/multimap_text_find_timing_large.cc
4358 <para>The test checks the find-time scalability of different
4359 "multimap" designs.</para>
4363 <section xml:id="multimap.text_find_large.results">
4368 <para>The graphic below show the results for "multimaps" which
4369 use a tree-based container for primary keys.
4372 <!-- results graphic -->
4376 <imagedata align="center" format="PNG" scale="100"
4377 fileref="/mnt/share/src/gcc.svn-trunk/libstdc++-v3/doc/xml/images/pbds_multimap_text_find_timing_test_large_s2p_tree_local.png"/>
4380 <imagedata align="center" format="PDF" scale="33"
4381 fileref="../images/pbds_multimap_text_find_timing_test_large_s2p_tree_local.pdf"/>
4387 The abbreviated names in the legend of the graphic above are
4388 instantiated with the types in the following table.
4392 <informaltable frame="all">
4394 <tgroup cols="7" align="left" colsep="1" rowsep="1">
4395 <colspec colname="c1"/>
4396 <colspec colname="c2"/>
4397 <colspec colname="c3"/>
4398 <colspec colname="c4"/>
4399 <colspec colname="c5"/>
4400 <colspec colname="c6"/>
4401 <colspec colname="c7"/>
4404 <entry><emphasis>Name/Instantiating Type</emphasis></entry>
4405 <entry><emphasis>Parameter</emphasis></entry>
4406 <entry><emphasis>Details</emphasis></entry>
4407 <entry><emphasis>Parameter</emphasis></entry>
4408 <entry><emphasis>Details</emphasis></entry>
4409 <entry><emphasis>Parameter</emphasis></entry>
4410 <entry><emphasis>Details</emphasis></entry>
4418 <?dbhtml bgcolor="#B0B0B0" ?>
4419 <entry namest="c1" nameend="c7">
4426 <classname>std::multimap</classname>
4428 <entry namest="c2" nameend="c7"></entry>
4431 <!-- multimap 01 -->
4433 <?dbhtml bgcolor="#B0B0B0" ?>
4434 <entry namest="c1" nameend="c7">
4435 rb_tree_mmap_lu_mtf_set
4440 <entry morerows="2" valign="top">
4441 <classname>tree</classname>
4444 <classname>Tag</classname>
4447 <classname>rb_tree_tag</classname>
4449 <entry namest="c4" nameend="c7"></entry>
4454 <classname>Node_Update</classname>
4457 <classname>null_node_update</classname>
4459 <entry namest="c4" nameend="c7"></entry>
4463 <classname>Mapped</classname>
4466 <classname>list_update</classname>
4469 <classname>Update_Policy</classname>
4472 <classname>lu_move_to_front_policy</classname>
4474 <entry namest="c6" nameend="c7"></entry>
4477 <!-- multimap 02 -->
4479 <?dbhtml bgcolor="#B0B0B0" ?>
4480 <entry namest="c1" nameend="c7">
4481 rb_tree_mmap_cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_set
4486 <entry morerows="4" valign="top">
4487 <classname>tree</classname>
4490 <classname>Tag</classname>
4493 <classname>rb_tree_tag</classname>
4495 <entry namest="c4" nameend="c7"></entry>
4500 <classname>Node_Update</classname>
4503 <classname>null_node_update</classname>
4505 <entry namest="c4" nameend="c7"></entry>
4509 <entry morerows="2" valign="top">
4510 <classname>Mapped</classname>
4512 <entry morerows="2" valign="top">
4513 <classname>cc_hash_table</classname>
4516 <classname>Comb_Hash_Fn</classname>
4519 <classname>direct_mask_range_hashing</classname>
4521 <entry namest="c6" nameend="c7"></entry>
4525 <entry morerows="1" valign="top">
4526 <classname>Resize_Policy</classname>
4528 <entry morerows="1" valign="top">
4529 <classname>hash_standard_resize_policy</classname>
4532 <classname>Size_Policy</classname>
4535 <classname>hash_exponential_size_policy</classname>
4540 <entry valign="top">
4541 <classname>Trigger_Policy</classname>
4544 <classname>hash_load_check_resize_trigger</classname> with
4545 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2
4554 <para>The graphic below show the results for "multimaps" which
4555 use a hash-based container for primary keys.
4558 <!-- results graphic -->
4562 <imagedata align="center" format="PNG" scale="100"
4563 fileref="/mnt/share/src/gcc.svn-trunk/libstdc++-v3/doc/xml/images/pbds_multimap_text_find_timing_test_large_s2p_hash_local.png"/>
4566 <imagedata align="center" format="PDF" scale="33"
4567 fileref="../images/pbds_multimap_text_find_timing_test_large_s2p_hash_local.pdf"/>
4573 The abbreviated names in the legend of the graphic above are
4574 instantiated with the types in the following table.
4577 <informaltable frame="all">
4579 <tgroup cols="7" align="left" colsep="1" rowsep="1">
4580 <colspec colname="c1"/>
4581 <colspec colname="c2"/>
4582 <colspec colname="c3"/>
4583 <colspec colname="c4"/>
4584 <colspec colname="c5"/>
4585 <colspec colname="c6"/>
4586 <colspec colname="c7"/>
4589 <entry><emphasis>Name/Instantiating Type</emphasis></entry>
4590 <entry><emphasis>Parameter</emphasis></entry>
4591 <entry><emphasis>Details</emphasis></entry>
4592 <entry><emphasis>Parameter</emphasis></entry>
4593 <entry><emphasis>Details</emphasis></entry>
4594 <entry><emphasis>Parameter</emphasis></entry>
4595 <entry><emphasis>Details</emphasis></entry>
4603 <?dbhtml bgcolor="#B0B0B0" ?>
4604 <entry namest="c1" nameend="c7">
4611 <classname>std::tr1::unordered_multimap</classname>
4613 <entry namest="c2" nameend="c7"></entry>
4616 <!-- multimap 01 -->
4618 <?dbhtml bgcolor="#B0B0B0" ?>
4619 <entry namest="c1" nameend="c7">
4620 rb_tree_mmap_lu_mtf_set
4625 <entry morerows="3" valign="top">
4631 <classname>Comb_Hash_Fn</classname>
4634 <classname>direct_mask_range_hashing</classname>
4636 <entry namest="c4" nameend="c7"></entry>
4639 <entry morerows="1" valign="top">
4640 <classname>Resize_Policy</classname>
4642 <entry morerows="1" valign="top">
4643 <classname>hash_standard_resize_policy</classname>
4646 <classname>Size_Policy</classname>
4649 <classname>hash_exponential_size_policy</classname>
4651 <entry namest="c6" nameend="c7"></entry>
4655 <entry valign="top">
4656 <classname>Trigger_Policy</classname>
4659 <classname>hash_load_check_resize_trigger</classname> with
4660 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2
4662 <entry namest="c6" nameend="c7"></entry>
4667 <classname>Mapped</classname>
4670 <classname>list_update</classname>
4673 <classname>Update_Policy</classname>
4676 <classname>lu_move_to_front_policy</classname>
4678 <entry namest="c6" nameend="c7"></entry>
4681 <!-- multimap 02 -->
4683 <?dbhtml bgcolor="#B0B0B0" ?>
4684 <entry namest="c1" nameend="c7">
4685 rb_tree_mmap_cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_set
4690 <entry morerows="5" valign="top">
4696 <classname>Comb_Hash_Fn</classname>
4699 <classname>direct_mask_range_hashing</classname>
4701 <entry namest="c4" nameend="c7"></entry>
4704 <entry morerows="1" valign="top">
4705 <classname>Resize_Policy</classname>
4707 <entry morerows="1" valign="top">
4708 <classname>hash_standard_resize_policy</classname>
4711 <classname>Size_Policy</classname>
4714 <classname>hash_exponential_size_policy</classname>
4716 <entry namest="c6" nameend="c7"></entry>
4720 <entry valign="top">
4721 <classname>Trigger_Policy</classname>
4724 <classname>hash_load_check_resize_trigger</classname> with
4725 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2
4727 <entry namest="c6" nameend="c7"></entry>
4731 <entry morerows="2" valign="top">
4732 <classname>Mapped</classname>
4734 <entry morerows="2" valign="top">
4735 <classname>cc_hash_table</classname>
4738 <classname>Comb_Hash_Fn</classname>
4741 <classname>direct_mask_range_hashing</classname>
4743 <entry namest="c6" nameend="c7"></entry>
4747 <entry morerows="1" valign="top">
4748 <classname>Resize_Policy</classname>
4750 <entry morerows="1" valign="top">
4751 <classname>hash_standard_resize_policy</classname>
4754 <classname>Size_Policy</classname>
4757 <classname>hash_exponential_size_policy</classname>
4762 <entry valign="top">
4763 <classname>Trigger_Policy</classname>
4766 <classname>hash_load_check_resize_trigger</classname> with
4767 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2
4777 <section xml:id="multimap.text_find_large.observations">
4782 <para>See Observations::Mapping-Semantics
4783 Considerations.</para>
4790 <!-- 03 <a href="multimap_text_insert_timing_test_small"> -->
4791 <section xml:id="performance.multimap.text_insert_small">
4793 Text <function>insert</function> with Small
4794 Secondary-to-Primary Key Ratios
4798 <section xml:id="multimap.text_insert_small.info">
4803 <para>This test inserts a number of pairs into a container. The
4804 first item of each pair is a string from an arbitrary text
4805 [wickland96thirty], and
4806 the second is a uniform integer. The container is a
4807 "multimap" - it considers the first member of each pair as a
4808 primary key, and the second member of each pair as a secondary
4810 are 400 distinct primary keys, and the ratio of secondary keys
4811 to primary keys ranges from 1 to 5.</para>
4812 <para>The test measures the average insert-time as a function of
4813 the number of values inserted. For this library's containers,
4814 it inserts a primary key into the primary associative
4815 container, then a secondary key into the secondary associative
4816 container. For the native multimaps, it obtains a range using
4817 <classname>std::equal_range</classname>, and inserts a value only if it was
4818 not contained already.</para>
4821 It uses the test file:
4823 performance/ext/pb_ds/multimap_text_insert_timing_small.cc
4827 <para>The test checks the insert-time scalability of different
4828 "multimap" designs.</para>
4832 <section xml:id="multimap.text_insert_small.results">
4837 <para>The graphic below show the results for "multimaps" which
4838 use a tree-based container for primary keys.
4841 <!-- results graphic -->
4845 <imagedata align="center" format="PNG" scale="100"
4846 fileref="/mnt/share/src/gcc.svn-trunk/libstdc++-v3/doc/xml/images/pbds_multimap_text_insert_timing_test_small_s2p_tree_local.png"/>
4849 <imagedata align="center" format="PDF" scale="33"
4850 fileref="../images/pbds_multimap_text_insert_timing_test_small_s2p_tree_local.pdf"/>
4856 The abbreviated names in the legend of the graphic above are
4857 instantiated with the types in the following table.
4861 <informaltable frame="all">
4863 <tgroup cols="7" align="left" colsep="1" rowsep="1">
4864 <colspec colname="c1"/>
4865 <colspec colname="c2"/>
4866 <colspec colname="c3"/>
4867 <colspec colname="c4"/>
4868 <colspec colname="c5"/>
4869 <colspec colname="c6"/>
4870 <colspec colname="c7"/>
4873 <entry><emphasis>Name/Instantiating Type</emphasis></entry>
4874 <entry><emphasis>Parameter</emphasis></entry>
4875 <entry><emphasis>Details</emphasis></entry>
4876 <entry><emphasis>Parameter</emphasis></entry>
4877 <entry><emphasis>Details</emphasis></entry>
4878 <entry><emphasis>Parameter</emphasis></entry>
4879 <entry><emphasis>Details</emphasis></entry>
4887 <?dbhtml bgcolor="#B0B0B0" ?>
4888 <entry namest="c1" nameend="c7">
4895 <classname>std::multimap</classname>
4897 <entry namest="c2" nameend="c7"></entry>
4900 <!-- multimap 01 -->
4902 <?dbhtml bgcolor="#B0B0B0" ?>
4903 <entry namest="c1" nameend="c7">
4904 rb_tree_mmap_lu_mtf_set
4909 <entry morerows="2" valign="top">
4910 <classname>tree</classname>
4913 <classname>Tag</classname>
4916 <classname>rb_tree_tag</classname>
4918 <entry namest="c4" nameend="c7"></entry>
4923 <classname>Node_Update</classname>
4926 <classname>null_node_update</classname>
4928 <entry namest="c4" nameend="c7"></entry>
4932 <classname>Mapped</classname>
4935 <classname>list_update</classname>
4938 <classname>Update_Policy</classname>
4941 <classname>lu_move_to_front_policy</classname>
4943 <entry namest="c6" nameend="c7"></entry>
4946 <!-- multimap 02 -->
4948 <?dbhtml bgcolor="#B0B0B0" ?>
4949 <entry namest="c1" nameend="c7">
4950 rb_tree_mmap_cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_set
4955 <entry morerows="4" valign="top">
4956 <classname>tree</classname>
4959 <classname>Tag</classname>
4962 <classname>rb_tree_tag</classname>
4964 <entry namest="c4" nameend="c7"></entry>
4969 <classname>Node_Update</classname>
4972 <classname>null_node_update</classname>
4974 <entry namest="c4" nameend="c7"></entry>
4978 <entry morerows="2" valign="top">
4979 <classname>Mapped</classname>
4981 <entry morerows="2" valign="top">
4982 <classname>cc_hash_table</classname>
4985 <classname>Comb_Hash_Fn</classname>
4988 <classname>direct_mask_range_hashing</classname>
4990 <entry namest="c6" nameend="c7"></entry>
4994 <entry morerows="1" valign="top">
4995 <classname>Resize_Policy</classname>
4997 <entry morerows="1" valign="top">
4998 <classname>hash_standard_resize_policy</classname>
5001 <classname>Size_Policy</classname>
5004 <classname>hash_exponential_size_policy</classname>
5009 <entry valign="top">
5010 <classname>Trigger_Policy</classname>
5013 <classname>hash_load_check_resize_trigger</classname> with
5014 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2
5023 <para>The graphic below show the results for "multimaps" which
5024 use a hash-based container for primary keys.
5027 <!-- results graphic -->
5031 <imagedata align="center" format="PNG" scale="100"
5032 fileref="/mnt/share/src/gcc.svn-trunk/libstdc++-v3/doc/xml/images/pbds_multimap_text_find_timing_test_small_s2p_hash_local.png"/>
5035 <imagedata align="center" format="PDF" scale="33"
5036 fileref="../images/pbds_multimap_text_find_timing_test_small_s2p_hash_local.pdf"/>
5042 The abbreviated names in the legend of the graphic above are
5043 instantiated with the types in the following table.
5046 <informaltable frame="all">
5048 <tgroup cols="7" align="left" colsep="1" rowsep="1">
5049 <colspec colname="c1"/>
5050 <colspec colname="c2"/>
5051 <colspec colname="c3"/>
5052 <colspec colname="c4"/>
5053 <colspec colname="c5"/>
5054 <colspec colname="c6"/>
5055 <colspec colname="c7"/>
5058 <entry><emphasis>Name/Instantiating Type</emphasis></entry>
5059 <entry><emphasis>Parameter</emphasis></entry>
5060 <entry><emphasis>Details</emphasis></entry>
5061 <entry><emphasis>Parameter</emphasis></entry>
5062 <entry><emphasis>Details</emphasis></entry>
5063 <entry><emphasis>Parameter</emphasis></entry>
5064 <entry><emphasis>Details</emphasis></entry>
5072 <?dbhtml bgcolor="#B0B0B0" ?>
5073 <entry namest="c1" nameend="c7">
5080 <classname>std::tr1::unordered_multimap</classname>
5082 <entry namest="c2" nameend="c7"></entry>
5085 <!-- multimap 01 -->
5087 <?dbhtml bgcolor="#B0B0B0" ?>
5088 <entry namest="c1" nameend="c7">
5089 rb_tree_mmap_lu_mtf_set
5094 <entry morerows="3" valign="top">
5100 <classname>Comb_Hash_Fn</classname>
5103 <classname>direct_mask_range_hashing</classname>
5105 <entry namest="c4" nameend="c7"></entry>
5108 <entry morerows="1" valign="top">
5109 <classname>Resize_Policy</classname>
5111 <entry morerows="1" valign="top">
5112 <classname>hash_standard_resize_policy</classname>
5115 <classname>Size_Policy</classname>
5118 <classname>hash_exponential_size_policy</classname>
5120 <entry namest="c6" nameend="c7"></entry>
5124 <entry valign="top">
5125 <classname>Trigger_Policy</classname>
5128 <classname>hash_load_check_resize_trigger</classname> with
5129 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2
5131 <entry namest="c6" nameend="c7"></entry>
5136 <classname>Mapped</classname>
5139 <classname>list_update</classname>
5142 <classname>Update_Policy</classname>
5145 <classname>lu_move_to_front_policy</classname>
5147 <entry namest="c6" nameend="c7"></entry>
5150 <!-- multimap 02 -->
5152 <?dbhtml bgcolor="#B0B0B0" ?>
5153 <entry namest="c1" nameend="c7">
5154 rb_tree_mmap_cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_set
5159 <entry morerows="5" valign="top">
5165 <classname>Comb_Hash_Fn</classname>
5168 <classname>direct_mask_range_hashing</classname>
5170 <entry namest="c4" nameend="c7"></entry>
5173 <entry morerows="1" valign="top">
5174 <classname>Resize_Policy</classname>
5176 <entry morerows="1" valign="top">
5177 <classname>hash_standard_resize_policy</classname>
5180 <classname>Size_Policy</classname>
5183 <classname>hash_exponential_size_policy</classname>
5185 <entry namest="c6" nameend="c7"></entry>
5189 <entry valign="top">
5190 <classname>Trigger_Policy</classname>
5193 <classname>hash_load_check_resize_trigger</classname> with
5194 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2
5196 <entry namest="c6" nameend="c7"></entry>
5200 <entry morerows="2" valign="top">
5201 <classname>Mapped</classname>
5203 <entry morerows="2" valign="top">
5204 <classname>cc_hash_table</classname>
5207 <classname>Comb_Hash_Fn</classname>
5210 <classname>direct_mask_range_hashing</classname>
5212 <entry namest="c6" nameend="c7"></entry>
5216 <entry morerows="1" valign="top">
5217 <classname>Resize_Policy</classname>
5219 <entry morerows="1" valign="top">
5220 <classname>hash_standard_resize_policy</classname>
5223 <classname>Size_Policy</classname>
5226 <classname>hash_exponential_size_policy</classname>
5231 <entry valign="top">
5232 <classname>Trigger_Policy</classname>
5235 <classname>hash_load_check_resize_trigger</classname> with
5236 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2
5246 <section xml:id="multimap.text_insert_small.observations">
5251 <para>See Observations::Mapping-Semantics
5252 Considerations.</para>
5259 <!-- 04 <a href="multimap_text_insert_timing_test_large"> -->
5260 <section xml:id="performance.multimap.text_insert_large">
5262 Text <function>insert</function> with Small
5263 Secondary-to-Primary Key Ratios
5267 <section xml:id="multimap.text_insert_large.info">
5272 <para>This test inserts a number of pairs into a container. The
5273 first item of each pair is a string from an arbitrary text
5274 [wickland96thirty], and
5275 the second is a uniform integer. The container is a
5276 "multimap" - it considers the first member of each pair as a
5277 primary key, and the second member of each pair as a secondary
5279 are 400 distinct primary keys, and the ratio of secondary keys
5280 to primary keys ranges from 1 to 5.</para>
5281 <para>The test measures the average insert-time as a function of
5282 the number of values inserted. For this library's containers,
5283 it inserts a primary key into the primary associative
5284 container, then a secondary key into the secondary associative
5285 container. For the native multimaps, it obtains a range using
5286 <classname>std::equal_range</classname>, and inserts a value only if it was
5287 not contained already.</para>
5290 It uses the test file:
5292 performance/ext/pb_ds/multimap_text_insert_timing_large.cc
5296 <para>The test checks the insert-time scalability of different
5297 "multimap" designs.</para>
5301 <section xml:id="multimap.text_insert_large.results">
5306 <para>The graphic below show the results for "multimaps" which
5307 use a tree-based container for primary keys.
5310 <!-- results graphic -->
5314 <imagedata align="center" format="PNG" scale="100"
5315 fileref="/mnt/share/src/gcc.svn-trunk/libstdc++-v3/doc/xml/images/pbds_multimap_text_insert_timing_test_large_s2p_tree_local.png"/>
5318 <imagedata align="center" format="PDF" scale="33"
5319 fileref="../images/pbds_multimap_text_insert_timing_test_large_s2p_tree_local.pdf"/>
5325 The abbreviated names in the legend of the graphic above are
5326 instantiated with the types in the following table.
5330 <informaltable frame="all">
5332 <tgroup cols="7" align="left" colsep="1" rowsep="1">
5333 <colspec colname="c1"/>
5334 <colspec colname="c2"/>
5335 <colspec colname="c3"/>
5336 <colspec colname="c4"/>
5337 <colspec colname="c5"/>
5338 <colspec colname="c6"/>
5339 <colspec colname="c7"/>
5342 <entry><emphasis>Name/Instantiating Type</emphasis></entry>
5343 <entry><emphasis>Parameter</emphasis></entry>
5344 <entry><emphasis>Details</emphasis></entry>
5345 <entry><emphasis>Parameter</emphasis></entry>
5346 <entry><emphasis>Details</emphasis></entry>
5347 <entry><emphasis>Parameter</emphasis></entry>
5348 <entry><emphasis>Details</emphasis></entry>
5356 <?dbhtml bgcolor="#B0B0B0" ?>
5357 <entry namest="c1" nameend="c7">
5364 <classname>std::multimap</classname>
5366 <entry namest="c2" nameend="c7"></entry>
5369 <!-- multimap 01 -->
5371 <?dbhtml bgcolor="#B0B0B0" ?>
5372 <entry namest="c1" nameend="c7">
5373 rb_tree_mmap_lu_mtf_set
5378 <entry morerows="2" valign="top">
5379 <classname>tree</classname>
5382 <classname>Tag</classname>
5385 <classname>rb_tree_tag</classname>
5387 <entry namest="c4" nameend="c7"></entry>
5392 <classname>Node_Update</classname>
5395 <classname>null_node_update</classname>
5397 <entry namest="c4" nameend="c7"></entry>
5401 <classname>Mapped</classname>
5404 <classname>list_update</classname>
5407 <classname>Update_Policy</classname>
5410 <classname>lu_move_to_front_policy</classname>
5412 <entry namest="c6" nameend="c7"></entry>
5415 <!-- multimap 02 -->
5417 <?dbhtml bgcolor="#B0B0B0" ?>
5418 <entry namest="c1" nameend="c7">
5419 rb_tree_mmap_cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_set
5424 <entry morerows="4" valign="top">
5425 <classname>tree</classname>
5428 <classname>Tag</classname>
5431 <classname>rb_tree_tag</classname>
5433 <entry namest="c4" nameend="c7"></entry>
5438 <classname>Node_Update</classname>
5441 <classname>null_node_update</classname>
5443 <entry namest="c4" nameend="c7"></entry>
5447 <entry morerows="2" valign="top">
5448 <classname>Mapped</classname>
5450 <entry morerows="2" valign="top">
5451 <classname>cc_hash_table</classname>
5454 <classname>Comb_Hash_Fn</classname>
5457 <classname>direct_mask_range_hashing</classname>
5459 <entry namest="c6" nameend="c7"></entry>
5463 <entry morerows="1" valign="top">
5464 <classname>Resize_Policy</classname>
5466 <entry morerows="1" valign="top">
5467 <classname>hash_standard_resize_policy</classname>
5470 <classname>Size_Policy</classname>
5473 <classname>hash_exponential_size_policy</classname>
5478 <entry valign="top">
5479 <classname>Trigger_Policy</classname>
5482 <classname>hash_load_check_resize_trigger</classname> with
5483 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2
5492 <para>The graphic below show the results for "multimaps" which
5493 use a hash-based container for primary keys.
5496 <!-- results graphic -->
5500 <imagedata align="center" format="PNG" scale="100"
5501 fileref="/mnt/share/src/gcc.svn-trunk/libstdc++-v3/doc/xml/images/pbds_multimap_text_find_timing_test_large_s2p_hash_local.png"/>
5504 <imagedata align="center" format="PDF" scale="33"
5505 fileref="../images/pbds_multimap_text_find_timing_test_large_s2p_hash_local.pdf"/>
5511 The abbreviated names in the legend of the graphic above are
5512 instantiated with the types in the following table.
5515 <informaltable frame="all">
5517 <tgroup cols="7" align="left" colsep="1" rowsep="1">
5518 <colspec colname="c1"/>
5519 <colspec colname="c2"/>
5520 <colspec colname="c3"/>
5521 <colspec colname="c4"/>
5522 <colspec colname="c5"/>
5523 <colspec colname="c6"/>
5524 <colspec colname="c7"/>
5527 <entry><emphasis>Name/Instantiating Type</emphasis></entry>
5528 <entry><emphasis>Parameter</emphasis></entry>
5529 <entry><emphasis>Details</emphasis></entry>
5530 <entry><emphasis>Parameter</emphasis></entry>
5531 <entry><emphasis>Details</emphasis></entry>
5532 <entry><emphasis>Parameter</emphasis></entry>
5533 <entry><emphasis>Details</emphasis></entry>
5541 <?dbhtml bgcolor="#B0B0B0" ?>
5542 <entry namest="c1" nameend="c7">
5549 <classname>std::tr1::unordered_multimap</classname>
5551 <entry namest="c2" nameend="c7"></entry>
5554 <!-- multimap 01 -->
5556 <?dbhtml bgcolor="#B0B0B0" ?>
5557 <entry namest="c1" nameend="c7">
5558 rb_tree_mmap_lu_mtf_set
5563 <entry morerows="3" valign="top">
5569 <classname>Comb_Hash_Fn</classname>
5572 <classname>direct_mask_range_hashing</classname>
5574 <entry namest="c4" nameend="c7"></entry>
5577 <entry morerows="1" valign="top">
5578 <classname>Resize_Policy</classname>
5580 <entry morerows="1" valign="top">
5581 <classname>hash_standard_resize_policy</classname>
5584 <classname>Size_Policy</classname>
5587 <classname>hash_exponential_size_policy</classname>
5589 <entry namest="c6" nameend="c7"></entry>
5593 <entry valign="top">
5594 <classname>Trigger_Policy</classname>
5597 <classname>hash_load_check_resize_trigger</classname> with
5598 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2
5600 <entry namest="c6" nameend="c7"></entry>
5605 <classname>Mapped</classname>
5608 <classname>list_update</classname>
5611 <classname>Update_Policy</classname>
5614 <classname>lu_move_to_front_policy</classname>
5616 <entry namest="c6" nameend="c7"></entry>
5619 <!-- multimap 02 -->
5621 <?dbhtml bgcolor="#B0B0B0" ?>
5622 <entry namest="c1" nameend="c7">
5623 rb_tree_mmap_cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_set
5628 <entry morerows="5" valign="top">
5634 <classname>Comb_Hash_Fn</classname>
5637 <classname>direct_mask_range_hashing</classname>
5639 <entry namest="c4" nameend="c7"></entry>
5642 <entry morerows="1" valign="top">
5643 <classname>Resize_Policy</classname>
5645 <entry morerows="1" valign="top">
5646 <classname>hash_standard_resize_policy</classname>
5649 <classname>Size_Policy</classname>
5652 <classname>hash_exponential_size_policy</classname>
5654 <entry namest="c6" nameend="c7"></entry>
5658 <entry valign="top">
5659 <classname>Trigger_Policy</classname>
5662 <classname>hash_load_check_resize_trigger</classname> with
5663 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2
5665 <entry namest="c6" nameend="c7"></entry>
5669 <entry morerows="2" valign="top">
5670 <classname>Mapped</classname>
5672 <entry morerows="2" valign="top">
5673 <classname>cc_hash_table</classname>
5676 <classname>Comb_Hash_Fn</classname>
5679 <classname>direct_mask_range_hashing</classname>
5681 <entry namest="c6" nameend="c7"></entry>
5685 <entry morerows="1" valign="top">
5686 <classname>Resize_Policy</classname>
5688 <entry morerows="1" valign="top">
5689 <classname>hash_standard_resize_policy</classname>
5692 <classname>Size_Policy</classname>
5695 <classname>hash_exponential_size_policy</classname>
5700 <entry valign="top">
5701 <classname>Trigger_Policy</classname>
5704 <classname>hash_load_check_resize_trigger</classname> with
5705 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2
5715 <section xml:id="multimap.text_insert_large.observations">
5720 <para>See Observations::Mapping-Semantics
5721 Considerations.</para>
5728 <!-- 05 <a href="multimap_text_insert_mem_usage_test_small"> -->
5729 <section xml:id="performance.multimap.text_insert_mem_small">
5731 Text <function>insert</function> with Small
5732 Secondary-to-Primary Key Ratios Memory Use
5736 <section xml:id="multimap.text_insert_mem_small.info">
5740 <para>This test inserts a number of pairs into a container. The
5741 first item of each pair is a string from an arbitrary text
5742 [wickland96thirty], and
5743 the second is a uniform integer. The container is a
5744 "multimap" - it considers the first member of each pair as a
5745 primary key, and the second member of each pair as a secondary
5747 are 100 distinct primary keys, and the ratio of secondary keys
5748 to primary keys ranges to about 20.</para>
5749 <para>The test measures the memory use as a function of the number
5750 of values inserted.</para>
5753 It uses the test file:
5755 performance/ext/pb_ds/multimap_text_insert_mem_usage_small.cc
5759 <para>The test checks the memory scalability of different
5760 "multimap" designs.</para>
5764 <section xml:id="multimap.text_insert_mem_small.results">
5769 <para>The graphic below show the results for "multimaps" which
5770 use a tree-based container for primary keys.
5773 <!-- results graphic -->
5777 <imagedata align="center" format="PNG" scale="100"
5778 fileref="/mnt/share/src/gcc.svn-trunk/libstdc++-v3/doc/xml/images/pbds_multimap_text_insert_mem_usage_test_small_s2p_tree_local.png"/>
5781 <imagedata align="center" format="PDF" scale="33"
5782 fileref="../images/pbds_multimap_text_insert_mem_usage_test_small_s2p_tree_local.pdf"/>
5788 The abbreviated names in the legend of the graphic above are
5789 instantiated with the types in the following table.
5793 <informaltable frame="all">
5795 <tgroup cols="7" align="left" colsep="1" rowsep="1">
5796 <colspec colname="c1"/>
5797 <colspec colname="c2"/>
5798 <colspec colname="c3"/>
5799 <colspec colname="c4"/>
5800 <colspec colname="c5"/>
5801 <colspec colname="c6"/>
5802 <colspec colname="c7"/>
5805 <entry><emphasis>Name/Instantiating Type</emphasis></entry>
5806 <entry><emphasis>Parameter</emphasis></entry>
5807 <entry><emphasis>Details</emphasis></entry>
5808 <entry><emphasis>Parameter</emphasis></entry>
5809 <entry><emphasis>Details</emphasis></entry>
5810 <entry><emphasis>Parameter</emphasis></entry>
5811 <entry><emphasis>Details</emphasis></entry>
5819 <?dbhtml bgcolor="#B0B0B0" ?>
5820 <entry namest="c1" nameend="c7">
5827 <classname>std::multimap</classname>
5829 <entry namest="c2" nameend="c7"></entry>
5832 <!-- multimap 01 -->
5834 <?dbhtml bgcolor="#B0B0B0" ?>
5835 <entry namest="c1" nameend="c7">
5836 rb_tree_mmap_lu_mtf_set
5841 <entry morerows="2" valign="top">
5842 <classname>tree</classname>
5845 <classname>Tag</classname>
5848 <classname>rb_tree_tag</classname>
5850 <entry namest="c4" nameend="c7"></entry>
5855 <classname>Node_Update</classname>
5858 <classname>null_node_update</classname>
5860 <entry namest="c4" nameend="c7"></entry>
5864 <classname>Mapped</classname>
5867 <classname>list_update</classname>
5870 <classname>Update_Policy</classname>
5873 <classname>lu_move_to_front_policy</classname>
5875 <entry namest="c6" nameend="c7"></entry>
5878 <!-- multimap 02 -->
5880 <?dbhtml bgcolor="#B0B0B0" ?>
5881 <entry namest="c1" nameend="c7">
5882 rb_tree_mmap_cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_set
5887 <entry morerows="4" valign="top">
5888 <classname>tree</classname>
5891 <classname>Tag</classname>
5894 <classname>rb_tree_tag</classname>
5896 <entry namest="c4" nameend="c7"></entry>
5901 <classname>Node_Update</classname>
5904 <classname>null_node_update</classname>
5906 <entry namest="c4" nameend="c7"></entry>
5910 <entry morerows="2" valign="top">
5911 <classname>Mapped</classname>
5913 <entry morerows="2" valign="top">
5914 <classname>cc_hash_table</classname>
5917 <classname>Comb_Hash_Fn</classname>
5920 <classname>direct_mask_range_hashing</classname>
5922 <entry namest="c6" nameend="c7"></entry>
5926 <entry morerows="1" valign="top">
5927 <classname>Resize_Policy</classname>
5929 <entry morerows="1" valign="top">
5930 <classname>hash_standard_resize_policy</classname>
5933 <classname>Size_Policy</classname>
5936 <classname>hash_exponential_size_policy</classname>
5941 <entry valign="top">
5942 <classname>Trigger_Policy</classname>
5945 <classname>hash_load_check_resize_trigger</classname> with
5946 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2
5955 <para>The graphic below show the results for "multimaps" which
5956 use a hash-based container for primary keys.
5959 <!-- results graphic -->
5963 <imagedata align="center" format="PNG" scale="100"
5964 fileref="/mnt/share/src/gcc.svn-trunk/libstdc++-v3/doc/xml/images/pbds_multimap_text_find_timing_test_large_s2p_hash_local.png"/>
5967 <imagedata align="center" format="PDF" scale="33"
5968 fileref="../images/pbds_multimap_text_find_timing_test_large_s2p_hash_local.pdf"/>
5974 The abbreviated names in the legend of the graphic above are
5975 instantiated with the types in the following table.
5978 <informaltable frame="all">
5980 <tgroup cols="7" align="left" colsep="1" rowsep="1">
5981 <colspec colname="c1"/>
5982 <colspec colname="c2"/>
5983 <colspec colname="c3"/>
5984 <colspec colname="c4"/>
5985 <colspec colname="c5"/>
5986 <colspec colname="c6"/>
5987 <colspec colname="c7"/>
5990 <entry><emphasis>Name/Instantiating Type</emphasis></entry>
5991 <entry><emphasis>Parameter</emphasis></entry>
5992 <entry><emphasis>Details</emphasis></entry>
5993 <entry><emphasis>Parameter</emphasis></entry>
5994 <entry><emphasis>Details</emphasis></entry>
5995 <entry><emphasis>Parameter</emphasis></entry>
5996 <entry><emphasis>Details</emphasis></entry>
6004 <?dbhtml bgcolor="#B0B0B0" ?>
6005 <entry namest="c1" nameend="c7">
6012 <classname>std::tr1::unordered_multimap</classname>
6014 <entry namest="c2" nameend="c7"></entry>
6017 <!-- multimap 01 -->
6019 <?dbhtml bgcolor="#B0B0B0" ?>
6020 <entry namest="c1" nameend="c7">
6021 rb_tree_mmap_lu_mtf_set
6026 <entry morerows="3" valign="top">
6032 <classname>Comb_Hash_Fn</classname>
6035 <classname>direct_mask_range_hashing</classname>
6037 <entry namest="c4" nameend="c7"></entry>
6040 <entry morerows="1" valign="top">
6041 <classname>Resize_Policy</classname>
6043 <entry morerows="1" valign="top">
6044 <classname>hash_standard_resize_policy</classname>
6047 <classname>Size_Policy</classname>
6050 <classname>hash_exponential_size_policy</classname>
6052 <entry namest="c6" nameend="c7"></entry>
6056 <entry valign="top">
6057 <classname>Trigger_Policy</classname>
6060 <classname>hash_load_check_resize_trigger</classname> with
6061 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2
6063 <entry namest="c6" nameend="c7"></entry>
6068 <classname>Mapped</classname>
6071 <classname>list_update</classname>
6074 <classname>Update_Policy</classname>
6077 <classname>lu_move_to_front_policy</classname>
6079 <entry namest="c6" nameend="c7"></entry>
6082 <!-- multimap 02 -->
6084 <?dbhtml bgcolor="#B0B0B0" ?>
6085 <entry namest="c1" nameend="c7">
6086 rb_tree_mmap_cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_set
6091 <entry morerows="5" valign="top">
6097 <classname>Comb_Hash_Fn</classname>
6100 <classname>direct_mask_range_hashing</classname>
6102 <entry namest="c4" nameend="c7"></entry>
6105 <entry morerows="1" valign="top">
6106 <classname>Resize_Policy</classname>
6108 <entry morerows="1" valign="top">
6109 <classname>hash_standard_resize_policy</classname>
6112 <classname>Size_Policy</classname>
6115 <classname>hash_exponential_size_policy</classname>
6117 <entry namest="c6" nameend="c7"></entry>
6121 <entry valign="top">
6122 <classname>Trigger_Policy</classname>
6125 <classname>hash_load_check_resize_trigger</classname> with
6126 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2
6128 <entry namest="c6" nameend="c7"></entry>
6132 <entry morerows="2" valign="top">
6133 <classname>Mapped</classname>
6135 <entry morerows="2" valign="top">
6136 <classname>cc_hash_table</classname>
6139 <classname>Comb_Hash_Fn</classname>
6142 <classname>direct_mask_range_hashing</classname>
6144 <entry namest="c6" nameend="c7"></entry>
6148 <entry morerows="1" valign="top">
6149 <classname>Resize_Policy</classname>
6151 <entry morerows="1" valign="top">
6152 <classname>hash_standard_resize_policy</classname>
6155 <classname>Size_Policy</classname>
6158 <classname>hash_exponential_size_policy</classname>
6163 <entry valign="top">
6164 <classname>Trigger_Policy</classname>
6167 <classname>hash_load_check_resize_trigger</classname> with
6168 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2
6178 <section xml:id="multimap.text_insert_mem_small.observations">
6183 <para>See Observations::Mapping-Semantics
6184 Considerations.</para>
6190 <!-- 06 <a href="multimap_text_insert_mem_usage_test_large"> -->
6191 <section xml:id="performance.multimap.text_insert_mem_large">
6193 Text <function>insert</function> with Small
6194 Secondary-to-Primary Key Ratios Memory Use
6198 <section xml:id="multimap.text_insert_mem_large.info">
6202 <para>This test inserts a number of pairs into a container. The
6203 first item of each pair is a string from an arbitrary text
6204 [wickland96thirty], and
6205 the second is a uniform integer. The container is a
6206 "multimap" - it considers the first member of each pair as a
6207 primary key, and the second member of each pair as a secondary
6209 are 100 distinct primary keys, and the ratio of secondary keys
6210 to primary keys ranges to about 20.</para>
6211 <para>The test measures the memory use as a function of the number
6212 of values inserted.</para>
6215 It uses the test file:
6217 performance/ext/pb_ds/multimap_text_insert_mem_usage_large.cc
6221 <para>The test checks the memory scalability of different
6222 "multimap" designs.</para>
6226 <section xml:id="multimap.text_insert_mem_large.results">
6231 <para>The graphic below show the results for "multimaps" which
6232 use a tree-based container for primary keys.
6235 <!-- results graphic -->
6239 <imagedata align="center" format="PNG" scale="100"
6240 fileref="/mnt/share/src/gcc.svn-trunk/libstdc++-v3/doc/xml/images/pbds_multimap_text_insert_mem_usage_test_large_s2p_tree_local.png"/>
6243 <imagedata align="center" format="PDF" scale="33"
6244 fileref="../images/pbds_multimap_text_insert_mem_usage_test_large_s2p_tree_local.pdf"/>
6250 The abbreviated names in the legend of the graphic above are
6251 instantiated with the types in the following table.
6255 <informaltable frame="all">
6257 <tgroup cols="7" align="left" colsep="1" rowsep="1">
6258 <colspec colname="c1"/>
6259 <colspec colname="c2"/>
6260 <colspec colname="c3"/>
6261 <colspec colname="c4"/>
6262 <colspec colname="c5"/>
6263 <colspec colname="c6"/>
6264 <colspec colname="c7"/>
6267 <entry><emphasis>Name/Instantiating Type</emphasis></entry>
6268 <entry><emphasis>Parameter</emphasis></entry>
6269 <entry><emphasis>Details</emphasis></entry>
6270 <entry><emphasis>Parameter</emphasis></entry>
6271 <entry><emphasis>Details</emphasis></entry>
6272 <entry><emphasis>Parameter</emphasis></entry>
6273 <entry><emphasis>Details</emphasis></entry>
6281 <?dbhtml bgcolor="#B0B0B0" ?>
6282 <entry namest="c1" nameend="c7">
6289 <classname>std::multimap</classname>
6291 <entry namest="c2" nameend="c7"></entry>
6294 <!-- multimap 01 -->
6296 <?dbhtml bgcolor="#B0B0B0" ?>
6297 <entry namest="c1" nameend="c7">
6298 rb_tree_mmap_lu_mtf_set
6303 <entry morerows="2" valign="top">
6304 <classname>tree</classname>
6307 <classname>Tag</classname>
6310 <classname>rb_tree_tag</classname>
6312 <entry namest="c4" nameend="c7"></entry>
6317 <classname>Node_Update</classname>
6320 <classname>null_node_update</classname>
6322 <entry namest="c4" nameend="c7"></entry>
6326 <classname>Mapped</classname>
6329 <classname>list_update</classname>
6332 <classname>Update_Policy</classname>
6335 <classname>lu_move_to_front_policy</classname>
6337 <entry namest="c6" nameend="c7"></entry>
6340 <!-- multimap 02 -->
6342 <?dbhtml bgcolor="#B0B0B0" ?>
6343 <entry namest="c1" nameend="c7">
6344 rb_tree_mmap_cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_set
6349 <entry morerows="4" valign="top">
6350 <classname>tree</classname>
6353 <classname>Tag</classname>
6356 <classname>rb_tree_tag</classname>
6358 <entry namest="c4" nameend="c7"></entry>
6363 <classname>Node_Update</classname>
6366 <classname>null_node_update</classname>
6368 <entry namest="c4" nameend="c7"></entry>
6372 <entry morerows="2" valign="top">
6373 <classname>Mapped</classname>
6375 <entry morerows="2" valign="top">
6376 <classname>cc_hash_table</classname>
6379 <classname>Comb_Hash_Fn</classname>
6382 <classname>direct_mask_range_hashing</classname>
6384 <entry namest="c6" nameend="c7"></entry>
6388 <entry morerows="1" valign="top">
6389 <classname>Resize_Policy</classname>
6391 <entry morerows="1" valign="top">
6392 <classname>hash_standard_resize_policy</classname>
6395 <classname>Size_Policy</classname>
6398 <classname>hash_exponential_size_policy</classname>
6403 <entry valign="top">
6404 <classname>Trigger_Policy</classname>
6407 <classname>hash_load_check_resize_trigger</classname> with
6408 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2
6417 <para>The graphic below show the results for "multimaps" which
6418 use a hash-based container for primary keys.
6421 <!-- results graphic -->
6425 <imagedata align="center" format="PNG" scale="100"
6426 fileref="/mnt/share/src/gcc.svn-trunk/libstdc++-v3/doc/xml/images/pbds_multimap_text_find_timing_test_large_s2p_hash_local.png"/>
6429 <imagedata align="center" format="PDF" scale="33"
6430 fileref="../images/pbds_multimap_text_find_timing_test_large_s2p_hash_local.pdf"/>
6436 The abbreviated names in the legend of the graphic above are
6437 instantiated with the types in the following table.
6440 <informaltable frame="all">
6442 <tgroup cols="7" align="left" colsep="1" rowsep="1">
6443 <colspec colname="c1"/>
6444 <colspec colname="c2"/>
6445 <colspec colname="c3"/>
6446 <colspec colname="c4"/>
6447 <colspec colname="c5"/>
6448 <colspec colname="c6"/>
6449 <colspec colname="c7"/>
6452 <entry><emphasis>Name/Instantiating Type</emphasis></entry>
6453 <entry><emphasis>Parameter</emphasis></entry>
6454 <entry><emphasis>Details</emphasis></entry>
6455 <entry><emphasis>Parameter</emphasis></entry>
6456 <entry><emphasis>Details</emphasis></entry>
6457 <entry><emphasis>Parameter</emphasis></entry>
6458 <entry><emphasis>Details</emphasis></entry>
6466 <?dbhtml bgcolor="#B0B0B0" ?>
6467 <entry namest="c1" nameend="c7">
6474 <classname>std::tr1::unordered_multimap</classname>
6476 <entry namest="c2" nameend="c7"></entry>
6479 <!-- multimap 01 -->
6481 <?dbhtml bgcolor="#B0B0B0" ?>
6482 <entry namest="c1" nameend="c7">
6483 rb_tree_mmap_lu_mtf_set
6488 <entry morerows="3" valign="top">
6494 <classname>Comb_Hash_Fn</classname>
6497 <classname>direct_mask_range_hashing</classname>
6499 <entry namest="c4" nameend="c7"></entry>
6502 <entry morerows="1" valign="top">
6503 <classname>Resize_Policy</classname>
6505 <entry morerows="1" valign="top">
6506 <classname>hash_standard_resize_policy</classname>
6509 <classname>Size_Policy</classname>
6512 <classname>hash_exponential_size_policy</classname>
6514 <entry namest="c6" nameend="c7"></entry>
6518 <entry valign="top">
6519 <classname>Trigger_Policy</classname>
6522 <classname>hash_load_check_resize_trigger</classname> with
6523 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2
6525 <entry namest="c6" nameend="c7"></entry>
6530 <classname>Mapped</classname>
6533 <classname>list_update</classname>
6536 <classname>Update_Policy</classname>
6539 <classname>lu_move_to_front_policy</classname>
6541 <entry namest="c6" nameend="c7"></entry>
6544 <!-- multimap 02 -->
6546 <?dbhtml bgcolor="#B0B0B0" ?>
6547 <entry namest="c1" nameend="c7">
6548 rb_tree_mmap_cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_set
6553 <entry morerows="5" valign="top">
6559 <classname>Comb_Hash_Fn</classname>
6562 <classname>direct_mask_range_hashing</classname>
6564 <entry namest="c4" nameend="c7"></entry>
6567 <entry morerows="1" valign="top">
6568 <classname>Resize_Policy</classname>
6570 <entry morerows="1" valign="top">
6571 <classname>hash_standard_resize_policy</classname>
6574 <classname>Size_Policy</classname>
6577 <classname>hash_exponential_size_policy</classname>
6579 <entry namest="c6" nameend="c7"></entry>
6583 <entry valign="top">
6584 <classname>Trigger_Policy</classname>
6587 <classname>hash_load_check_resize_trigger</classname> with
6588 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2
6590 <entry namest="c6" nameend="c7"></entry>
6594 <entry morerows="2" valign="top">
6595 <classname>Mapped</classname>
6597 <entry morerows="2" valign="top">
6598 <classname>cc_hash_table</classname>
6601 <classname>Comb_Hash_Fn</classname>
6604 <classname>direct_mask_range_hashing</classname>
6606 <entry namest="c6" nameend="c7"></entry>
6610 <entry morerows="1" valign="top">
6611 <classname>Resize_Policy</classname>
6613 <entry morerows="1" valign="top">
6614 <classname>hash_standard_resize_policy</classname>
6617 <classname>Size_Policy</classname>
6620 <classname>hash_exponential_size_policy</classname>
6625 <entry valign="top">
6626 <classname>Trigger_Policy</classname>
6629 <classname>hash_load_check_resize_trigger</classname> with
6630 α<subscript>min</subscript> = 1/8 and α<subscript>max</subscript> = 1/2
6640 <section xml:id="multimap.text_insert_mem_large.observations">
6645 <para>See Observations::Mapping-Semantics
6646 Considerations.</para>
6652 </section> <!-- multimap -->
6654 <section xml:id="performance.priority_queue">
6655 <info><title>Priority Queue</title></info>
6657 <!-- 01 <a href="priority_queue_text_push_timing_test"> -->
6658 <section xml:id="performance.priority_queue.text_push">
6660 Text <function>push</function>
6664 <section xml:id="priority_queue.text_push.info">
6670 <para>This test inserts a number of values with keys from an
6671 arbitrary text ([ wickland96thirty ]) into
6672 a container using <function>push</function>. It measures the average time
6673 for <function>push</function> as a function of the number of values
6677 It uses the test file:
6679 performance/ext/pb_ds/priority_queue_text_push_timing.cc
6683 <para>The test checks the effect of different underlying data
6689 <section xml:id="priority_queue.text_push.results">
6694 <para>The two graphics below show the results for the native
6695 priority_queues and this library's priority_queues.
6698 <para>The graphic immediately below shows the results for the
6699 native priority_queue type instantiated with different underlying
6700 container types versus several different versions of library's
6704 <!-- results graphic -->
6708 <imagedata align="center" format="PDF" scale="75"
6709 fileref="../images/pbds_priority_queue_text_push_timing_test_local.pdf"/>
6712 <imagedata align="center" format="PNG" scale="100"
6713 fileref="/mnt/share/src/gcc.svn-trunk/libstdc++-v3/doc/xml/images/pbds_priority_queue_text_push_timing_test_local.png"/>
6719 The abbreviated names in the legend of the graphic above are
6720 instantiated with the types in the following table.
6724 <informaltable frame="all">
6726 <tgroup cols="3" align="left" colsep="1" rowsep="1">
6727 <colspec colname="c1"/>
6728 <colspec colname="c2"/>
6729 <colspec colname="c3"/>
6732 <entry><emphasis>Name/Instantiating Type</emphasis></entry>
6733 <entry><emphasis>Parameter</emphasis></entry>
6734 <entry><emphasis>Details</emphasis></entry>
6742 <?dbhtml bgcolor="#B0B0B0" ?>
6743 <entry namest="c1" nameend="c3">
6750 <classname>std::priority_queue</classname>
6753 <classname>Sequence</classname>
6756 <classname>std::vector</classname>
6762 <?dbhtml bgcolor="#B0B0B0" ?>
6763 <entry namest="c1" nameend="c3">
6770 <classname>std::priority_queue</classname>
6773 <classname>Sequence</classname>
6776 <classname>std::deque</classname>
6780 <!-- priority_queue 01 -->
6782 <?dbhtml bgcolor="#B0B0B0" ?>
6783 <entry namest="c1" nameend="c3">
6790 <classname>priority_queue</classname>
6793 <classname>Tag</classname>
6796 <classname>binary_heap_tag</classname>
6800 <!-- priority_queue 02 -->
6802 <?dbhtml bgcolor="#B0B0B0" ?>
6803 <entry namest="c1" nameend="c3">
6810 <classname>priority_queue</classname>
6813 <classname>Tag</classname>
6816 <classname>binomial_heap_tag</classname>
6820 <!-- priority_queue 03 -->
6822 <?dbhtml bgcolor="#B0B0B0" ?>
6823 <entry namest="c1" nameend="c3">
6830 <classname>priority_queue</classname>
6833 <classname>Tag</classname>
6836 <classname>rc_binomial_heap_tag</classname>
6840 <!-- priority_queue 04 -->
6842 <?dbhtml bgcolor="#B0B0B0" ?>
6843 <entry namest="c1" nameend="c3">
6850 <classname>priority_queue</classname>
6853 <classname>Tag</classname>
6856 <classname>thin_heap_tag</classname>
6861 <!-- priority_queue 05 -->
6863 <?dbhtml bgcolor="#B0B0B0" ?>
6864 <entry namest="c1" nameend="c3">
6871 <classname>priority_queue</classname>
6874 <classname>Tag</classname>
6877 <classname>pairing_heap_tag</classname>
6887 <para>The graphic below shows the results for the binary-heap
6888 based native priority queues and this library's pairing-heap
6889 priority_queue data structures.
6892 <!-- results graphic -->
6896 <imagedata align="center" format="PDF" scale="75"
6897 fileref="../images/pbds_pairing_priority_queue_text_push_timing_test_local.pdf"/>
6900 <imagedata align="center" format="PNG" scale="100"
6901 fileref="/mnt/share/src/gcc.svn-trunk/libstdc++-v3/doc/xml//images/pbds_pairing_priority_queue_text_push_timing_test_local.png"/>
6907 The abbreviated names in the legend of the graphic above are
6908 instantiated with the types in the following table.
6912 <informaltable frame="all">
6914 <tgroup cols="3" align="left" colsep="1" rowsep="1">
6915 <colspec colname="c1"/>
6916 <colspec colname="c2"/>
6917 <colspec colname="c3"/>
6920 <entry><emphasis>Name/Instantiating Type</emphasis></entry>
6921 <entry><emphasis>Parameter</emphasis></entry>
6922 <entry><emphasis>Details</emphasis></entry>
6929 <?dbhtml bgcolor="#B0B0B0" ?>
6930 <entry namest="c1" nameend="c3">
6937 <classname>std::priority_queue</classname>
6940 <classname>Sequence</classname>
6943 <classname>std::vector</classname>
6949 <?dbhtml bgcolor="#B0B0B0" ?>
6950 <entry namest="c1" nameend="c3">
6957 <classname>std::priority_queue</classname>
6960 <classname>Sequence</classname>
6963 <classname>std::deque</classname>
6968 <!-- priority_queue 01 -->
6970 <?dbhtml bgcolor="#B0B0B0" ?>
6971 <entry namest="c1" nameend="c3">
6978 <classname>priority_queue</classname>
6981 <classname>Tag</classname>
6984 <classname>thin_heap_tag</classname>
6989 <!-- priority_queue 02 -->
6991 <?dbhtml bgcolor="#B0B0B0" ?>
6992 <entry namest="c1" nameend="c3">
6999 <classname>priority_queue</classname>
7002 <classname>Tag</classname>
7005 <classname>pairing_heap_tag</classname>
7016 <section xml:id="priority_queue.text_push.observations">
7021 <para>Pairing heaps (<classname>priority_queue</classname> with
7022 <classname>Tag</classname> = <classname>pairing_heap_tag</classname>)
7023 are the most suited for sequences of <function>push</function> and
7024 <function>pop</function> operations of non-primitive types (e.g.
7025 <classname>std::string</classname>s). (See Priority Queue
7026 Text <function>push</function> and <function>pop</function> Timing Test.) They are
7027 less constrained than binomial heaps, e.g., and since
7028 they are node-based, they outperform binary heaps. (See
7030 Queue Random Integer <function>push</function> Timing Test for the case
7031 of primitive types.)</para>
7033 <para>The standard's priority queues do not seem to perform well in
7034 this case: the <classname>std::vector</classname> implementation needs to
7035 perform a logarithmic sequence of string operations for each
7036 operation, and the deque implementation is possibly hampered by
7037 its need to manipulate a relatively-complex type (deques
7038 support a O(1) <function>push_front</function>, even though it is
7039 not used by <classname>std::priority_queue</classname>.)</para>
7044 <!-- 02 <a href="priority_queue_text_push_pop_timing_test"> -->
7045 <section xml:id="performance.priority_queue.text_push_pop">
7047 Text <function>push</function> and <function>pop</function>
7051 <section xml:id="priority_queue.text_push_pop.info">
7056 <para>This test inserts a number of values with keys from an
7057 arbitrary text ([ wickland96thirty ]) into
7058 a container using <classname>push</classname> , then removes them using
7059 <classname>pop</classname> . It measures the average time for <classname>push</classname>
7060 as a function of the number of values.</para>
7064 It uses the test file:
7066 performance/ext/pb_ds/priority_queue_text_push_pop_timing.cc
7070 <para>The test checks the effect of different underlying data
7076 <section xml:id="priority_queue.text_push_pop.results">
7081 <para>The two graphics below show the results for the native
7082 priority_queues and this library's priority_queues.
7085 <para>The graphic immediately below shows the results for the
7086 native priority_queue type instantiated with different underlying
7087 container types versus several different versions of library's
7091 <!-- results graphic -->
7095 <imagedata align="center" format="PDF" scale="75"
7096 fileref="../images/pbds_priority_queue_text_push_pop_timing_test_local.pdf"/>
7099 <imagedata align="center" format="PNG" scale="100"
7100 fileref="/mnt/share/src/gcc.svn-trunk/libstdc++-v3/doc/xml/images/pbds_priority_queue_text_push_pop_timing_test_local.png"/>
7106 The abbreviated names in the legend of the graphic above are
7107 instantiated with the types in the following table.
7111 <informaltable frame="all">
7113 <tgroup cols="3" align="left" colsep="1" rowsep="1">
7114 <colspec colname="c1"/>
7115 <colspec colname="c2"/>
7116 <colspec colname="c3"/>
7119 <entry><emphasis>Name/Instantiating Type</emphasis></entry>
7120 <entry><emphasis>Parameter</emphasis></entry>
7121 <entry><emphasis>Details</emphasis></entry>
7129 <?dbhtml bgcolor="#B0B0B0" ?>
7130 <entry namest="c1" nameend="c3">
7137 <classname>std::priority_queue</classname>
7140 <classname>Sequence</classname>
7143 <classname>std::vector</classname>
7149 <?dbhtml bgcolor="#B0B0B0" ?>
7150 <entry namest="c1" nameend="c3">
7157 <classname>std::priority_queue</classname>
7160 <classname>Sequence</classname>
7163 <classname>std::deque</classname>
7168 <!-- priority_queue 01 -->
7170 <?dbhtml bgcolor="#B0B0B0" ?>
7171 <entry namest="c1" nameend="c3">
7178 <classname>priority_queue</classname>
7181 <classname>Tag</classname>
7184 <classname>binary_heap_tag</classname>
7188 <!-- priority_queue 02 -->
7190 <?dbhtml bgcolor="#B0B0B0" ?>
7191 <entry namest="c1" nameend="c3">
7198 <classname>priority_queue</classname>
7201 <classname>Tag</classname>
7204 <classname>binomial_heap_tag</classname>
7208 <!-- priority_queue 03 -->
7210 <?dbhtml bgcolor="#B0B0B0" ?>
7211 <entry namest="c1" nameend="c3">
7218 <classname>priority_queue</classname>
7221 <classname>Tag</classname>
7224 <classname>rc_binomial_heap_tag</classname>
7228 <!-- priority_queue 04 -->
7230 <?dbhtml bgcolor="#B0B0B0" ?>
7231 <entry namest="c1" nameend="c3">
7238 <classname>priority_queue</classname>
7241 <classname>Tag</classname>
7244 <classname>thin_heap_tag</classname>
7248 <!-- priority_queue 05 -->
7250 <?dbhtml bgcolor="#B0B0B0" ?>
7251 <entry namest="c1" nameend="c3">
7258 <classname>priority_queue</classname>
7261 <classname>Tag</classname>
7264 <classname>pairing_heap_tag</classname>
7274 <para>The graphic below shows the results for the native priority
7275 queues and this library's pairing-heap priority_queue data
7279 <!-- results graphic -->
7283 <imagedata align="center" format="PDF" scale="75"
7284 fileref="../images/pbds_pairing_priority_queue_text_push_pop_timing_test_local.pdf"/>
7287 <imagedata align="center" format="PNG" scale="100"
7288 fileref="/mnt/share/src/gcc.svn-trunk/libstdc++-v3/doc/xml//images/pbds_pairing_priority_queue_text_push_pop_timing_test_local.png"/>
7294 The abbreviated names in the legend of the graphic above are
7295 instantiated with the types in the following table.
7299 <informaltable frame="all">
7301 <tgroup cols="3" align="left" colsep="1" rowsep="1">
7302 <colspec colname="c1"/>
7303 <colspec colname="c2"/>
7304 <colspec colname="c3"/>
7307 <entry><emphasis>Name/Instantiating Type</emphasis></entry>
7308 <entry><emphasis>Parameter</emphasis></entry>
7309 <entry><emphasis>Details</emphasis></entry>
7317 <?dbhtml bgcolor="#B0B0B0" ?>
7318 <entry namest="c1" nameend="c3">
7325 <classname>std::priority_queue</classname> adapting <classname>std::vector</classname>
7328 <classname>Sequence</classname>
7331 <classname>std::vector</classname>
7338 <?dbhtml bgcolor="#B0B0B0" ?>
7339 <entry namest="c1" nameend="c3">
7346 <classname>std::priority_queue</classname>
7349 <classname>Sequence</classname>
7352 <classname>std::deque</classname>
7357 <!-- priority_queue 01 -->
7359 <?dbhtml bgcolor="#B0B0B0" ?>
7360 <entry namest="c1" nameend="c3">
7367 <classname>priority_queue</classname>
7370 <classname>Tag</classname>
7373 <classname>pairing_heap_tag</classname>
7384 <section xml:id="priority_queue.text_push_pop.observations">
7389 <para>These results are very similar to Priority Queue Text
7390 <function>push</function> Timing Test. As stated there, pairing heaps
7391 (<classname>priority_queue</classname> with
7392 <classname>Tag</classname>
7393 = <classname>pairing_heap_tag</classname>) are most suited
7394 for <function>push</function> and <function>pop</function>
7395 sequences of non-primitive types such as strings. Observing these
7396 two tests, one can note that a pairing heap outperforms the others
7397 in terms of <function>push</function> operations, but equals
7398 binary heaps (<classname>priority_queue</classname> with
7399 <classname>Tag</classname>
7400 = <classname>binary_heap_tag</classname>) if the number
7401 of <function>push</function> and <function>pop</function>
7402 operations is equal. As the number of <function>pop</function>
7403 operations is at most equal to the number
7404 of <function>push</function> operations, pairing heaps are better
7405 in this case. See Priority Queue Random
7406 Integer <function>push</function> and <function>pop</function>
7407 Timing Test for a case which is different.</para>
7413 <!-- 03 <a href="priority_queue_random_int_push_timing_test"> -->
7414 <section xml:id="performance.priority_queue.int_push">
7416 Integer <function>push</function>
7420 <section xml:id="priority_queue.int_push.info">
7425 <para>This test inserts a number of values with integer keys
7426 into a container using <function>push</function>. It
7427 measures the average time for <function>push</function> as a
7428 function of the number of values.</para>
7431 It uses the test file:
7433 performance/ext/pb_ds/priority_queue_random_int_push_timing.cc
7437 <para>The test checks the effect of different underlying data
7443 <section xml:id="priority_queue.int_push.results">
7448 <para>The two graphics below show the results for the native
7449 priority_queues and this library's priority_queues.
7452 <para>The graphic immediately below shows the results for the
7453 native priority_queue type instantiated with different underlying
7454 container types versus several different versions of library's
7458 <!-- results graphic -->
7462 <imagedata align="center" format="PDF" scale="75"
7463 fileref="../images/pbds_priority_queue_random_int_push_timing_test_local.pdf"/>
7466 <imagedata align="center" format="PNG" scale="100"
7467 fileref="/mnt/share/src/gcc.svn-trunk/libstdc++-v3/doc/xml/images/pbds_priority_queue_random_int_push_timing_test_local.png"/>
7473 The abbreviated names in the legend of the graphic above are
7474 instantiated with the types in the following table.
7478 <informaltable frame="all">
7480 <tgroup cols="3" align="left" colsep="1" rowsep="1">
7481 <colspec colname="c1"/>
7482 <colspec colname="c2"/>
7483 <colspec colname="c3"/>
7486 <entry><emphasis>Name/Instantiating Type</emphasis></entry>
7487 <entry><emphasis>Parameter</emphasis></entry>
7488 <entry><emphasis>Details</emphasis></entry>
7496 <?dbhtml bgcolor="#B0B0B0" ?>
7497 <entry namest="c1" nameend="c3">
7504 <classname>std::priority_queue</classname>
7507 <classname>Sequence</classname>
7510 <classname>std::vector</classname>
7516 <?dbhtml bgcolor="#B0B0B0" ?>
7517 <entry namest="c1" nameend="c3">
7524 <classname>std::priority_queue</classname>
7527 <classname>Sequence</classname>
7530 <classname>std::deque</classname>
7535 <!-- priority_queue 01 -->
7537 <?dbhtml bgcolor="#B0B0B0" ?>
7538 <entry namest="c1" nameend="c3">
7545 <classname>priority_queue</classname>
7548 <classname>Tag</classname>
7551 <classname>binary_heap_tag</classname>
7555 <!-- priority_queue 02 -->
7557 <?dbhtml bgcolor="#B0B0B0" ?>
7558 <entry namest="c1" nameend="c3">
7565 <classname>priority_queue</classname>
7568 <classname>Tag</classname>
7571 <classname>binomial_heap_tag</classname>
7575 <!-- priority_queue 03 -->
7577 <?dbhtml bgcolor="#B0B0B0" ?>
7578 <entry namest="c1" nameend="c3">
7585 <classname>priority_queue</classname>
7588 <classname>Tag</classname>
7591 <classname>rc_binomial_heap_tag</classname>
7595 <!-- priority_queue 04 -->
7597 <?dbhtml bgcolor="#B0B0B0" ?>
7598 <entry namest="c1" nameend="c3">
7605 <classname>priority_queue</classname>
7608 <classname>Tag</classname>
7611 <classname>thin_heap_tag</classname>
7615 <!-- priority_queue 05 -->
7617 <?dbhtml bgcolor="#B0B0B0" ?>
7618 <entry namest="c1" nameend="c3">
7625 <classname>priority_queue</classname>
7628 <classname>Tag</classname>
7631 <classname>pairing_heap_tag</classname>
7641 <para>The graphic below shows the results for the binary-heap
7642 based native priority queues and this library's
7643 priority_queue data structures.
7646 <!-- results graphic -->
7650 <imagedata align="center" format="PDF" scale="75"
7651 fileref="../images/pbds_binary_priority_queue_random_int_push_timing_test_local.pdf"/>
7654 <imagedata align="center" format="PNG" scale="100"
7655 fileref="/mnt/share/src/gcc.svn-trunk/libstdc++-v3/doc/xml//images/pbds_binary_priority_queue_random_int_push_timing_test_local.png"/>
7661 The abbreviated names in the legend of the graphic above are
7662 instantiated with the types in the following table.
7666 <informaltable frame="all">
7668 <tgroup cols="3" align="left" colsep="1" rowsep="1">
7669 <colspec colname="c1"/>
7670 <colspec colname="c2"/>
7671 <colspec colname="c3"/>
7674 <entry><emphasis>Name/Instantiating Type</emphasis></entry>
7675 <entry><emphasis>Parameter</emphasis></entry>
7676 <entry><emphasis>Details</emphasis></entry>
7684 <?dbhtml bgcolor="#B0B0B0" ?>
7685 <entry namest="c1" nameend="c3">
7692 <classname>std::priority_queue</classname> adapting <classname>std::vector</classname>
7695 <classname>Sequence</classname>
7698 <classname>std::vector</classname>
7705 <?dbhtml bgcolor="#B0B0B0" ?>
7706 <entry namest="c1" nameend="c3">
7713 <classname>std::priority_queue</classname>
7716 <classname>Sequence</classname>
7719 <classname>std::deque</classname>
7724 <!-- priority_queue 01 -->
7726 <?dbhtml bgcolor="#B0B0B0" ?>
7727 <entry namest="c1" nameend="c3">
7734 <classname>priority_queue</classname>
7737 <classname>Tag</classname>
7740 <classname>binary_heap_tag</classname>
7751 <section xml:id="priority_queue.int_push.observations">
7757 <para>Binary heaps are the most suited for sequences of
7758 <function>push</function> and <function>pop</function> operations of primitive types
7759 (e.g. <type>int</type>s). They are less constrained
7760 than any other type, and since it is very efficient to store
7761 such types in arrays, they outperform even pairing heaps. (See
7763 Queue Text <function>push</function> Timing Test for the case of
7764 non-primitive types.)</para>
7768 <!-- 04 "priority_queue_random_int_push_pop_timing_test" -->
7769 <section xml:id="performance.priority_queue.int_push_pop">
7771 Integer <function>push</function>
7775 <section xml:id="priority_queue.int_push_pop.info">
7780 <para>This test inserts a number of values with integer keys
7781 into a container using <function>push</function> , then removes them
7782 using <function>pop</function> . It measures the average time for
7783 <function>push</function> and <function>pop</function> as a function
7784 of the number of values.</para>
7787 It uses the test file:
7789 performance/ext/pb_ds/priority_queue_random_int_push_pop_timing.cc
7793 <para>The test checks the effect of different underlying data
7799 <section xml:id="priority_queue.int_push_pop.results">
7804 <para>The graphic immediately below shows the results for the
7805 native priority_queue type instantiated with different underlying
7806 container types versus several different versions of library's
7810 <!-- results graphic -->
7814 <imagedata align="center" format="PDF" scale="75"
7815 fileref="../images/pbds_priority_queue_random_int_push_pop_timing_test_local.pdf"/>
7818 <imagedata align="center" format="PNG" scale="100"
7819 fileref="/mnt/share/src/gcc.svn-trunk/libstdc++-v3/doc/xml/images/pbds_priority_queue_random_int_push_pop_timing_test_local.png"/>
7825 The abbreviated names in the legend of the graphic above are
7826 instantiated with the types in the following table.
7830 <informaltable frame="all">
7832 <tgroup cols="3" align="left" colsep="1" rowsep="1">
7833 <colspec colname="c1"/>
7834 <colspec colname="c2"/>
7835 <colspec colname="c3"/>
7838 <entry><emphasis>Name/Instantiating Type</emphasis></entry>
7839 <entry><emphasis>Parameter</emphasis></entry>
7840 <entry><emphasis>Details</emphasis></entry>
7848 <?dbhtml bgcolor="#B0B0B0" ?>
7849 <entry namest="c1" nameend="c3">
7856 <classname>std::priority_queue</classname>
7859 <classname>Sequence</classname>
7862 <classname>std::vector</classname>
7868 <?dbhtml bgcolor="#B0B0B0" ?>
7869 <entry namest="c1" nameend="c3">
7876 <classname>std::priority_queue</classname>
7879 <classname>Sequence</classname>
7882 <classname>std::deque</classname>
7887 <!-- priority_queue 01 -->
7889 <?dbhtml bgcolor="#B0B0B0" ?>
7890 <entry namest="c1" nameend="c3">
7897 <classname>priority_queue</classname>
7900 <classname>Tag</classname>
7903 <classname>binary_heap_tag</classname>
7907 <!-- priority_queue 02 -->
7909 <?dbhtml bgcolor="#B0B0B0" ?>
7910 <entry namest="c1" nameend="c3">
7917 <classname>priority_queue</classname>
7920 <classname>Tag</classname>
7923 <classname>binomial_heap_tag</classname>
7927 <!-- priority_queue 03 -->
7929 <?dbhtml bgcolor="#B0B0B0" ?>
7930 <entry namest="c1" nameend="c3">
7937 <classname>priority_queue</classname>
7940 <classname>Tag</classname>
7943 <classname>rc_binomial_heap_tag</classname>
7947 <!-- priority_queue 04 -->
7949 <?dbhtml bgcolor="#B0B0B0" ?>
7950 <entry namest="c1" nameend="c3">
7957 <classname>priority_queue</classname>
7960 <classname>Tag</classname>
7963 <classname>thin_heap_tag</classname>
7967 <!-- priority_queue 05 -->
7969 <?dbhtml bgcolor="#B0B0B0" ?>
7970 <entry namest="c1" nameend="c3">
7977 <classname>priority_queue</classname>
7980 <classname>Tag</classname>
7983 <classname>pairing_heap_tag</classname>
7995 <section xml:id="priority_queue.int_push_pop.observations">
8000 <para>Binary heaps are the most suited for sequences of
8001 <function>push</function> and <function>pop</function> operations of primitive types
8002 (e.g. <type>int</type>s). This is explained in
8004 Queue Random Int <function>push</function> Timing Test. (See Priority Queue
8005 Text <function>push</function> Timing Test for the case of primitive
8008 <para>At first glance it seems that the standard's vector-based
8009 priority queue is approximately on par with this
8010 library's corresponding priority queue. There are two
8011 differences however:</para>
8013 <listitem><para>The standard's priority queue does not downsize the underlying
8014 vector (or deque) as the priority queue becomes smaller
8016 Text <function>pop</function> Memory Use Test). It is therefore
8017 gaining some speed at the expense of space.</para></listitem>
8018 <listitem><para>From Priority Queue Random
8019 Integer <function>push</function> and <function>pop</function>
8020 Timing Test, it seems that the standard's priority queue is
8021 slower in terms of <function>push</function> operations. Since
8023 <function>pop</function> operations is at most that of <function>push</function>
8024 operations, the test here is the "best" for the standard's
8025 priority queue.</para></listitem>
8033 <!-- 05 <a href="priority_queue_text_pop_mem_usage_test"> -->
8034 <section xml:id="performance.priority_queue.text_pop">
8036 Text <function>pop</function> Memory Use
8040 <section xml:id="priority_queue.text_pop.info">
8046 <para>This test inserts a number of values with keys from an
8047 arbitrary text ([ wickland96thirty ]) into
8048 a container, then pops them until only one is left in the
8049 container. It measures the memory use as a function of the
8050 number of values pushed to the container.</para>
8052 It uses the test file:
8054 performance/ext/pb_ds/priority_queue_text_pop_mem_usage.cc
8058 <para>The test checks the effect of different underlying data
8064 <section xml:id="priority_queue.text_pop.results">
8069 <para>The graphic immediately below shows the results for the
8070 native priority_queue type instantiated with different underlying
8071 container types versus several different versions of library's
8075 <!-- results graphic -->
8079 <imagedata align="center" format="PDF" scale="75"
8080 fileref="../images/pbds_priority_queue_text_pop_mem_usage_test_local.pdf"/>
8083 <imagedata align="center" format="PNG" scale="100"
8084 fileref="/mnt/share/src/gcc.svn-trunk/libstdc++-v3/doc/xml/images/pbds_priority_queue_text_pop_mem_usage_test_local.png"/>
8090 The abbreviated names in the legend of the graphic above are
8091 instantiated with the types in the following table.
8095 <informaltable frame="all">
8097 <tgroup cols="3" align="left" colsep="1" rowsep="1">
8098 <colspec colname="c1"/>
8099 <colspec colname="c2"/>
8100 <colspec colname="c3"/>
8103 <entry><emphasis>Name/Instantiating Type</emphasis></entry>
8104 <entry><emphasis>Parameter</emphasis></entry>
8105 <entry><emphasis>Details</emphasis></entry>
8113 <?dbhtml bgcolor="#B0B0B0" ?>
8114 <entry namest="c1" nameend="c3">
8121 <classname>std::priority_queue</classname>
8124 <classname>Sequence</classname>
8127 <classname>std::vector</classname>
8133 <?dbhtml bgcolor="#B0B0B0" ?>
8134 <entry namest="c1" nameend="c3">
8141 <classname>std::priority_queue</classname>
8144 <classname>Sequence</classname>
8147 <classname>std::deque</classname>
8152 <!-- priority_queue 01 -->
8154 <?dbhtml bgcolor="#B0B0B0" ?>
8155 <entry namest="c1" nameend="c3">
8162 <classname>priority_queue</classname>
8165 <classname>Tag</classname>
8168 <classname>binary_heap_tag</classname>
8172 <!-- priority_queue 02 -->
8174 <?dbhtml bgcolor="#B0B0B0" ?>
8175 <entry namest="c1" nameend="c3">
8182 <classname>priority_queue</classname>
8185 <classname>Tag</classname>
8188 <classname>binomial_heap_tag</classname>
8192 <!-- priority_queue 03 -->
8194 <?dbhtml bgcolor="#B0B0B0" ?>
8195 <entry namest="c1" nameend="c3">
8202 <classname>priority_queue</classname>
8205 <classname>Tag</classname>
8208 <classname>rc_binomial_heap_tag</classname>
8212 <!-- priority_queue 04 -->
8214 <?dbhtml bgcolor="#B0B0B0" ?>
8215 <entry namest="c1" nameend="c3">
8222 <classname>priority_queue</classname>
8225 <classname>Tag</classname>
8228 <classname>thin_heap_tag</classname>
8232 <!-- priority_queue 05 -->
8234 <?dbhtml bgcolor="#B0B0B0" ?>
8235 <entry namest="c1" nameend="c3">
8242 <classname>priority_queue</classname>
8245 <classname>Tag</classname>
8248 <classname>pairing_heap_tag</classname>
8260 <section xml:id="priority_queue.text_pop.observations">
8266 <para>The priority queue implementations (excluding the standard's) use
8267 memory proportionally to the number of values they hold:
8268 node-based implementations (e.g., a pairing heap) do so
8269 naturally; this library's binary heap de-allocates memory when
8270 a certain lower threshold is exceeded.</para>
8272 <para>Note from Priority Queue Text <function>push</function>
8273 and <function>pop</function> Timing Test and Priority Queue
8274 Random Integer <function>push</function>
8275 and <function>pop</function> Timing Test that this does not
8276 impede performance compared to the standard's priority
8278 <para>See Hash-Based Erase
8279 Memory Use Test for a similar phenomenon regarding priority
8284 <!-- 06 <a href="priority_queue_text_join_timing_test"> -->
8285 <section xml:id="performance.priority_queue.text_join">
8287 Text <function>join</function>
8291 <section xml:id="priority_queue.text_join.info">
8296 <para>This test inserts a number of values with keys from an
8297 arbitrary text ([ wickland96thirty ]) into
8298 two containers, then merges the containers. It uses
8299 <function>join</function> for this library's priority queues; for
8300 the standard's priority queues, it successively pops values from
8301 one container and pushes them into the other. The test measures
8302 the average time as a function of the number of values.</para>
8304 It uses the test file:
8306 performance/ext/pb_ds/priority_queue_text_join_timing.cc
8310 <para>The test checks the effect of different underlying data
8316 <section xml:id="priority_queue.text_join.results">
8321 <para>The graphic immediately below shows the results for the
8322 native priority_queue type instantiated with different underlying
8323 container types versus several different versions of library's
8327 <!-- results graphic -->
8331 <imagedata align="center" format="PDF" scale="75"
8332 fileref="../images/pbds_priority_queue_text_join_timing_test_local.pdf"/>
8335 <imagedata align="center" format="PNG" scale="100"
8336 fileref="/mnt/share/src/gcc.svn-trunk/libstdc++-v3/doc/xml/images/pbds_priority_queue_text_join_timing_test_local.png"/>
8342 The abbreviated names in the legend of the graphic above are
8343 instantiated with the types in the following table.
8347 <informaltable frame="all">
8349 <tgroup cols="3" align="left" colsep="1" rowsep="1">
8350 <colspec colname="c1"/>
8351 <colspec colname="c2"/>
8352 <colspec colname="c3"/>
8355 <entry><emphasis>Name/Instantiating Type</emphasis></entry>
8356 <entry><emphasis>Parameter</emphasis></entry>
8357 <entry><emphasis>Details</emphasis></entry>
8365 <?dbhtml bgcolor="#B0B0B0" ?>
8366 <entry namest="c1" nameend="c3">
8373 <classname>std::priority_queue</classname>
8376 <classname>Sequence</classname>
8379 <classname>std::vector</classname>
8385 <?dbhtml bgcolor="#B0B0B0" ?>
8386 <entry namest="c1" nameend="c3">
8393 <classname>std::priority_queue</classname>
8396 <classname>Sequence</classname>
8399 <classname>std::deque</classname>
8404 <!-- priority_queue 01 -->
8406 <?dbhtml bgcolor="#B0B0B0" ?>
8407 <entry namest="c1" nameend="c3">
8414 <classname>priority_queue</classname>
8417 <classname>Tag</classname>
8420 <classname>binary_heap_tag</classname>
8424 <!-- priority_queue 02 -->
8426 <?dbhtml bgcolor="#B0B0B0" ?>
8427 <entry namest="c1" nameend="c3">
8434 <classname>priority_queue</classname>
8437 <classname>Tag</classname>
8440 <classname>binomial_heap_tag</classname>
8444 <!-- priority_queue 03 -->
8446 <?dbhtml bgcolor="#B0B0B0" ?>
8447 <entry namest="c1" nameend="c3">
8454 <classname>priority_queue</classname>
8457 <classname>Tag</classname>
8460 <classname>rc_binomial_heap_tag</classname>
8464 <!-- priority_queue 04 -->
8466 <?dbhtml bgcolor="#B0B0B0" ?>
8467 <entry namest="c1" nameend="c3">
8474 <classname>priority_queue</classname>
8477 <classname>Tag</classname>
8480 <classname>thin_heap_tag</classname>
8484 <!-- priority_queue 05 -->
8486 <?dbhtml bgcolor="#B0B0B0" ?>
8487 <entry namest="c1" nameend="c3">
8494 <classname>priority_queue</classname>
8497 <classname>Tag</classname>
8500 <classname>pairing_heap_tag</classname>
8512 <section xml:id="priority_queue.text_join.observations">
8517 <para>In this test the node-based heaps perform <function>join</function> in
8518 either logarithmic or constant time. The binary heap requires
8519 linear time, since the well-known heapify algorithm [clrs2001] is linear.</para>
8520 <para>It would be possible to apply the heapify algorithm to the
8521 standard containers, if they would support iteration (which they
8522 don't). Barring iterators, it is still somehow possible to perform
8523 linear-time merge on a <classname>std::vector</classname>-based
8524 standard priority queue, using <function>top()</function>
8525 and <function>size()</function> (since they are enough to expose
8526 the underlying array), but this is impossible for
8527 a <classname>std::deque</classname>-based standard priority queue.
8528 Without heapify, the cost is super-linear.</para>
8533 <!-- 07 <a href="priority_queue_text_push_timing_test"> -->
8534 <section xml:id="performance.priority_queue.text_modify_up">
8536 Text <function>modify</function> Up
8540 <section xml:id="priority_queue.text_modify_up.info">
8545 <para>This test inserts a number of values with keys from an
8546 arbitrary text ([ wickland96thirty ]) into
8547 into a container then modifies each one "up" (i.e., it
8548 makes it larger). It uses <function>modify</function> for this library's
8549 priority queues; for the standard's priority queues, it pops values
8550 from a container until it reaches the value that should be
8551 modified, then pushes values back in. It measures the average
8552 time for <function>modify</function> as a function of the number of
8556 It uses the test file:
8558 performance/ext/pb_ds/priority_queue_text_modify_up_timing.cc
8562 <para>The test checks the effect of different underlying data
8563 structures for graph algorithms settings. Note that making an
8564 arbitrary value larger (in the sense of the priority queue's
8565 comparison functor) corresponds to decrease-key in standard graph
8566 algorithms [clrs2001].
8571 <section xml:id="priority_queue.text_modify_up.results">
8576 <para>The two graphics below show the results for the native
8577 priority_queues and this library's priority_queues.
8580 <para>The graphic immediately below shows the results for the
8581 native priority_queue type instantiated with different underlying
8582 container types versus several different versions of library's
8586 <!-- results graphic -->
8590 <imagedata align="center" format="PDF" scale="75"
8591 fileref="../images/pbds_priority_queue_text_modify_up_timing_test_local.pdf"/>
8594 <imagedata align="center" format="PNG" scale="100"
8595 fileref="/mnt/share/src/gcc.svn-trunk/libstdc++-v3/doc/xml/images/pbds_priority_queue_text_modify_up_timing_test_local.png"/>
8601 The abbreviated names in the legend of the graphic above are
8602 instantiated with the types in the following table.
8606 <informaltable frame="all">
8608 <tgroup cols="3" align="left" colsep="1" rowsep="1">
8609 <colspec colname="c1"/>
8610 <colspec colname="c2"/>
8611 <colspec colname="c3"/>
8614 <entry><emphasis>Name/Instantiating Type</emphasis></entry>
8615 <entry><emphasis>Parameter</emphasis></entry>
8616 <entry><emphasis>Details</emphasis></entry>
8624 <?dbhtml bgcolor="#B0B0B0" ?>
8625 <entry namest="c1" nameend="c3">
8632 <classname>std::priority_queue</classname>
8635 <classname>Sequence</classname>
8638 <classname>std::vector</classname>
8644 <?dbhtml bgcolor="#B0B0B0" ?>
8645 <entry namest="c1" nameend="c3">
8652 <classname>std::priority_queue</classname>
8655 <classname>Sequence</classname>
8658 <classname>std::deque</classname>
8662 <!-- priority_queue 01 -->
8664 <?dbhtml bgcolor="#B0B0B0" ?>
8665 <entry namest="c1" nameend="c3">
8672 <classname>priority_queue</classname>
8675 <classname>Tag</classname>
8678 <classname>binary_heap_tag</classname>
8682 <!-- priority_queue 02 -->
8684 <?dbhtml bgcolor="#B0B0B0" ?>
8685 <entry namest="c1" nameend="c3">
8692 <classname>priority_queue</classname>
8695 <classname>Tag</classname>
8698 <classname>binomial_heap_tag</classname>
8702 <!-- priority_queue 03 -->
8704 <?dbhtml bgcolor="#B0B0B0" ?>
8705 <entry namest="c1" nameend="c3">
8712 <classname>priority_queue</classname>
8715 <classname>Tag</classname>
8718 <classname>rc_binomial_heap_tag</classname>
8722 <!-- priority_queue 04 -->
8724 <?dbhtml bgcolor="#B0B0B0" ?>
8725 <entry namest="c1" nameend="c3">
8732 <classname>priority_queue</classname>
8735 <classname>Tag</classname>
8738 <classname>thin_heap_tag</classname>
8743 <!-- priority_queue 05 -->
8745 <?dbhtml bgcolor="#B0B0B0" ?>
8746 <entry namest="c1" nameend="c3">
8753 <classname>priority_queue</classname>
8756 <classname>Tag</classname>
8759 <classname>pairing_heap_tag</classname>
8769 <para>The graphic below shows the results for the
8770 native priority queues and this library's pairing and thin heap
8771 priority_queue data structures.
8774 <!-- results graphic -->
8778 <imagedata align="center" format="PDF" scale="75"
8779 fileref="../images/pbds_priority_queue_text_modify_up_timing_test_pairing_thin_local.pdf"/>
8782 <imagedata align="center" format="PNG" scale="100"
8783 fileref="/mnt/share/src/gcc.svn-trunk/libstdc++-v3/doc/xml//images/pbds_priority_queue_text_modify_up_timing_test_pairing_thin_local.png"/>
8789 The abbreviated names in the legend of the graphic above are
8790 instantiated with the types in the following table.
8794 <informaltable frame="all">
8796 <tgroup cols="3" align="left" colsep="1" rowsep="1">
8797 <colspec colname="c1"/>
8798 <colspec colname="c2"/>
8799 <colspec colname="c3"/>
8802 <entry><emphasis>Name/Instantiating Type</emphasis></entry>
8803 <entry><emphasis>Parameter</emphasis></entry>
8804 <entry><emphasis>Details</emphasis></entry>
8810 <!-- priority_queue 01 -->
8812 <?dbhtml bgcolor="#B0B0B0" ?>
8813 <entry namest="c1" nameend="c3">
8820 <classname>priority_queue</classname>
8823 <classname>Tag</classname>
8826 <classname>thin_heap_tag</classname>
8831 <!-- priority_queue 02 -->
8833 <?dbhtml bgcolor="#B0B0B0" ?>
8834 <entry namest="c1" nameend="c3">
8841 <classname>priority_queue</classname>
8844 <classname>Tag</classname>
8847 <classname>pairing_heap_tag</classname>
8858 <section xml:id="priority_queue.text_modify_up.observations">
8863 <para>As noted above, increasing an arbitrary value (in the sense of
8864 the priority queue's comparison functor) is very common in
8865 graph-related algorithms. In this case, a thin heap
8866 (<classname>priority_queue</classname> with
8867 <classname>Tag</classname> = <classname>thin_heap_tag</classname>)
8868 outperforms a pairing heap (<classname>priority_queue</classname> with
8869 <classname>Tag</classname> = <classname>pairing_heap_tag</classname>).
8870 Conversely, Priority Queue Text
8871 <function>push</function> Timing Test, Priority Queue
8872 Text <function>push</function> and <function>pop</function> Timing Test, Priority
8873 Queue Random Integer <function>push</function> Timing Test, and
8875 Queue Random Integer <function>push</function> and <function>pop</function> Timing
8876 Test show that the situation is reversed for other
8877 operations. It is not clear when to prefer one of these two
8878 different types.</para>
8880 <para>In this test this library's binary heaps
8881 effectively perform modify in linear time. As explained in
8882 Priority Queue Design::Traits, given a valid point-type iterator,
8883 a binary heap can perform
8884 <function>modify</function> logarithmically. The problem is that binary
8885 heaps invalidate their find iterators with each modifying
8886 operation, and so the only way to obtain a valid point-type
8887 iterator is to iterate using a range-type iterator until
8888 finding the appropriate value, then use the range-type iterator
8889 for the <function>modify</function> operation.</para>
8890 <para>The explanation for the standard's priority queues' performance
8891 is similar to that in Priority Queue Text
8892 <function>join</function> Timing Test.</para>
8898 <!-- 08 <a href="priority_queue_text_modify_down_timing_test"> -->
8900 <section xml:id="performance.priority_queue.text_modify_down">
8902 Text <function>modify</function> Down
8906 <section xml:id="priority_queue.text_modify_down.info">
8911 <para>This test inserts a number of values with keys from an
8912 arbitrary text ([ wickland96thirty ]) into
8913 into a container then modifies each one "down" (i.e., it
8914 makes it smaller). It uses <function>modify</function> for this library's
8915 priority queues; for the standard's priority queues, it pops values
8916 from a container until it reaches the value that should be
8917 modified, then pushes values back in. It measures the average
8918 time for <function>modify</function> as a function of the number of
8922 It uses the test file:
8924 performance/ext/pb_ds/priority_queue_text_modify_down_timing.cc
8928 <para>The main purpose of this test is to contrast Priority Queue
8929 Text <classname>modify</classname> Up Timing Test.</para>
8933 <section xml:id="priority_queue.text_modify_down.results">
8938 <para>The two graphics below show the results for the native
8939 priority_queues and this library's priority_queues.
8942 <para>The graphic immediately below shows the results for the
8943 native priority_queue type instantiated with different underlying
8944 container types versus several different versions of library's
8948 <!-- results graphic -->
8952 <imagedata align="center" format="PDF" scale="75"
8953 fileref="../images/pbds_priority_queue_text_modify_down_timing_test_local.pdf"/>
8956 <imagedata align="center" format="PNG" scale="100"
8957 fileref="/mnt/share/src/gcc.svn-trunk/libstdc++-v3/doc/xml/images/pbds_priority_queue_text_modify_down_timing_test_local.png"/>
8963 The abbreviated names in the legend of the graphic above are
8964 instantiated with the types in the following table.
8968 <informaltable frame="all">
8970 <tgroup cols="3" align="left" colsep="1" rowsep="1">
8971 <colspec colname="c1"/>
8972 <colspec colname="c2"/>
8973 <colspec colname="c3"/>
8976 <entry><emphasis>Name/Instantiating Type</emphasis></entry>
8977 <entry><emphasis>Parameter</emphasis></entry>
8978 <entry><emphasis>Details</emphasis></entry>
8986 <?dbhtml bgcolor="#B0B0B0" ?>
8987 <entry namest="c1" nameend="c3">
8994 <classname>std::priority_queue</classname>
8997 <classname>Sequence</classname>
9000 <classname>std::vector</classname>
9006 <?dbhtml bgcolor="#B0B0B0" ?>
9007 <entry namest="c1" nameend="c3">
9014 <classname>std::priority_queue</classname>
9017 <classname>Sequence</classname>
9020 <classname>std::deque</classname>
9024 <!-- priority_queue 01 -->
9026 <?dbhtml bgcolor="#B0B0B0" ?>
9027 <entry namest="c1" nameend="c3">
9034 <classname>priority_queue</classname>
9037 <classname>Tag</classname>
9040 <classname>binary_heap_tag</classname>
9044 <!-- priority_queue 02 -->
9046 <?dbhtml bgcolor="#B0B0B0" ?>
9047 <entry namest="c1" nameend="c3">
9054 <classname>priority_queue</classname>
9057 <classname>Tag</classname>
9060 <classname>binomial_heap_tag</classname>
9064 <!-- priority_queue 03 -->
9066 <?dbhtml bgcolor="#B0B0B0" ?>
9067 <entry namest="c1" nameend="c3">
9074 <classname>priority_queue</classname>
9077 <classname>Tag</classname>
9080 <classname>rc_binomial_heap_tag</classname>
9084 <!-- priority_queue 04 -->
9086 <?dbhtml bgcolor="#B0B0B0" ?>
9087 <entry namest="c1" nameend="c3">
9094 <classname>priority_queue</classname>
9097 <classname>Tag</classname>
9100 <classname>thin_heap_tag</classname>
9105 <!-- priority_queue 05 -->
9107 <?dbhtml bgcolor="#B0B0B0" ?>
9108 <entry namest="c1" nameend="c3">
9115 <classname>priority_queue</classname>
9118 <classname>Tag</classname>
9121 <classname>pairing_heap_tag</classname>
9131 <para>The graphic below shows the results for the
9132 native priority queues and this library's pairing and thin heap
9133 priority_queue data structures.
9136 <!-- results graphic -->
9140 <imagedata align="center" format="PDF" scale="75"
9141 fileref="../images/pbds_priority_queue_text_modify_down_timing_test_pairing_thin_local.pdf"/>
9144 <imagedata align="center" format="PNG" scale="100"
9145 fileref="/mnt/share/src/gcc.svn-trunk/libstdc++-v3/doc/xml//images/pbds_priority_queue_text_modify_down_timing_test_pairing_thin_local.png"/>
9151 The abbreviated names in the legend of the graphic above are
9152 instantiated with the types in the following table.
9156 <informaltable frame="all">
9158 <tgroup cols="3" align="left" colsep="1" rowsep="1">
9159 <colspec colname="c1"/>
9160 <colspec colname="c2"/>
9161 <colspec colname="c3"/>
9164 <entry><emphasis>Name/Instantiating Type</emphasis></entry>
9165 <entry><emphasis>Parameter</emphasis></entry>
9166 <entry><emphasis>Details</emphasis></entry>
9172 <!-- priority_queue 01 -->
9174 <?dbhtml bgcolor="#B0B0B0" ?>
9175 <entry namest="c1" nameend="c3">
9182 <classname>priority_queue</classname>
9185 <classname>Tag</classname>
9188 <classname>thin_heap_tag</classname>
9193 <!-- priority_queue 02 -->
9195 <?dbhtml bgcolor="#B0B0B0" ?>
9196 <entry namest="c1" nameend="c3">
9203 <classname>priority_queue</classname>
9206 <classname>Tag</classname>
9209 <classname>pairing_heap_tag</classname>
9220 <section xml:id="priority_queue.text_modify_down.observations">
9225 <para>Most points in these results are similar to Priority Queue
9226 Text <function>modify</function> Up Timing Test.</para>
9228 <para>It is interesting to note, however, that as opposed to that
9229 test, a thin heap (<classname>priority_queue</classname> with
9230 <classname>Tag</classname> = <classname>thin_heap_tag</classname>) is
9231 outperformed by a pairing heap (<classname>priority_queue</classname> with
9232 <classname>Tag</classname> = <classname>pairing_heap_tag</classname>).
9233 In this case, both heaps essentially perform an <function>erase</function>
9234 operation followed by a <function>push</function> operation. As the other
9235 tests show, a pairing heap is usually far more efficient than a
9236 thin heap, so this is not surprising.</para>
9237 <para>Most algorithms that involve priority queues increase values
9238 (in the sense of the priority queue's comparison functor), and
9240 Text <classname>modify</classname> Up Timing Test - is more interesting
9241 than this test.</para>
9246 </section> <!-- priority_queue -->
9248 <section xml:id="pbds.test.performance.observations">
9249 <info><title>Observations</title></info>
9251 <section xml:id="observations.associative">
9252 <info><title>Associative</title></info>
9254 <section xml:id="observations.associative.underlying">
9256 Underlying Data-Structure Families
9259 <para>In general, hash-based containers have better timing performance
9260 than containers based on different underlying-data structures. The
9261 main reason to choose a tree-based or trie-based container is if a
9262 byproduct of the tree-like structure is required: either
9263 order-preservation, or the ability to utilize node invariants. If
9264 memory-use is the major factor, an ordered-vector tree gives
9265 optimal results (albeit with high modificiation costs), and a
9266 list-based container gives reasonable results.</para>
9270 <section xml:id="observations.associative.hash">
9272 Hash-Based Containers
9275 <para>Hash-based containers are typically either collision
9276 chaining or probing. Collision-chaining
9277 containers are more flexible internally, and so offer better
9278 timing performance. Probing containers, if used for simple
9279 value-types, manage memory more efficiently (they perform far
9280 fewer allocation-related calls). In general, therefore, a
9281 collision-chaining table should be used. A probing container,
9282 conversely, might be used efficiently for operations such as
9283 eliminating duplicates in a sequence, or counting the number of
9284 occurrences within a sequence. Probing containers might be more
9285 useful also in multithreaded applications where each thread
9286 manipulates a hash-based container: in the standard, allocators have
9287 class-wise semantics (see [meyers96more] - Item 10); a
9288 probing container might incur less contention in this case.</para>
9291 <section xml:id="observations.associative.hash_policies">
9296 <para>In hash-based containers, the range-hashing scheme seems to
9297 affect performance more than other considerations. In most
9298 settings, a mask-based scheme works well (or can be made to
9299 work well). If the key-distribution can be estimated a-priori,
9300 a simple hash function can produce nearly uniform hash-value
9301 distribution. In many other cases (e.g., text hashing,
9302 floating-point hashing), the hash function is powerful enough
9303 to generate hash values with good uniformity properties
9305 a modulo-based scheme, taking into account all bits of the hash
9306 value, appears to overlap the hash function in its effort.</para>
9307 <para>The range-hashing scheme determines many of the other
9308 policies. A mask-based scheme works
9309 well with an exponential-size policy; for
9310 probing-based containers, it goes well with a linear-probe
9312 <para>An orthogonal consideration is the trigger policy. This
9313 presents difficult tradeoffs. E.g., different load
9314 factors in a load-check trigger policy yield a
9315 space/amortized-cost tradeoff.</para>
9318 <section xml:id="observations.associative.branch">
9320 Branch-Based Containers
9322 <para>In general, there are several families of tree-based
9323 underlying data structures: balanced node-based trees
9324 (e.g., red-black or AVL trees), high-probability
9325 balanced node-based trees (e.g., random treaps or
9326 skip-lists), competitive node-based trees (e.g., splay
9327 trees), vector-based "trees", and tries. (Additionally, there
9328 are disk-residing or network-residing trees, such as B-Trees
9329 and their numerous variants. An interface for this would have
9330 to deal with the execution model and ACID guarantees; this is
9331 out of the scope of this library.) Following are some
9332 observations on their application to different settings.</para>
9334 <para>Of the balanced node-based trees, this library includes a
9335 red-black tree, as does standard (in
9336 practice). This type of tree is the "workhorse" of tree-based
9337 containers: it offers both reasonable modification and
9338 reasonable lookup time. Unfortunately, this data structure
9339 stores a huge amount of metadata. Each node must contain,
9340 besides a value, three pointers and a boolean. This type might
9341 be avoided if space is at a premium [austern00noset].</para>
9342 <para>High-probability balanced node-based trees suffer the
9343 drawbacks of deterministic balanced trees. Although they are
9344 fascinating data structures, preliminary tests with them showed
9345 their performance was worse than red-black trees. The library
9346 does not contain any such trees, therefore.</para>
9347 <para>Competitive node-based trees have two drawbacks. They are
9348 usually somewhat unbalanced, and they perform a large number of
9349 comparisons. Balanced trees perform one comparison per each
9350 node they encounter on a search path; a splay tree performs two
9351 comparisons. If the keys are complex objects, e.g.,
9352 <classname>std::string</classname>, this can increase the running time.
9353 Conversely, such trees do well when there is much locality of
9354 reference. It is difficult to determine in which case to prefer
9355 such trees over balanced trees. This library includes a splay
9357 <para>Ordered-vector trees use very little space
9359 They do not have any other advantages (at least in this
9360 implementation).</para>
9361 <para>Large-fan-out PATRICIA tries have excellent lookup
9362 performance, but they do so through maintaining, for each node,
9363 a miniature "hash-table". Their space efficiency is low, and
9364 their modification performance is bad. These tries might be
9365 used for semi-static settings, where order preservation is
9366 important. Alternatively, red-black trees cross-referenced with
9367 hash tables can be used. [okasaki98mereable]
9368 discusses small-fan-out PATRICIA tries for integers, but the
9369 cited results seem to indicate that the amortized cost of
9370 maintaining such trees is higher than that of balanced trees.
9371 Moderate-fan-out trees might be useful for sequences where each
9372 element has a limited number of choices, e.g., DNA
9376 <section xml:id="observations.associative.mapping_semantics">
9380 <para>Different mapping semantics were discussed in the introduction and design sections.Here
9381 the focus will be on the case where a keys can be composed into
9382 primary keys and secondary keys. (In the case where some keys
9383 are completely identical, it is trivial that one should use an
9384 associative container mapping values to size types.) In this
9385 case there are (at least) five possibilities:</para>
9387 <listitem><para>Use an associative container that allows equivalent-key
9388 values (such as <classname>std::multimap</classname>)</para></listitem>
9389 <listitem><para>Use a unique-key value associative container that maps
9390 each primary key to some complex associative container of
9391 secondary keys, say a tree-based or hash-based container.
9393 <listitem><para>Use a unique-key value associative container that maps
9394 each primary key to some simple associative container of
9395 secondary keys, say a list-based container.</para></listitem>
9396 <listitem><para>Use a unique-key value associative container that maps
9397 each primary key to some non-associative container
9398 (e.g., <classname>std::vector</classname>)</para></listitem>
9399 <listitem><para>Use a unique-key value associative container that takes
9400 into account both primary and secondary keys.</para></listitem>
9402 <para>Stated simply: there is a simple answer for this. (Excluding
9403 option 1, which should be avoided in all cases).</para>
9404 <para>If the expected ratio of secondary keys to primary keys is
9405 small, then 3 and 4 seem reasonable. Both types of secondary
9406 containers are relatively lightweight (in terms of memory use
9407 and construction time), and so creating an entire container
9408 object for each primary key is not too expensive. Option 4
9409 might be preferable to option 3 if changing the secondary key
9410 of some primary key is frequent - one cannot modify an
9411 associative container's key, and the only possibility,
9412 therefore, is erasing the secondary key and inserting another
9413 one instead; a non-associative container, conversely, can
9414 support in-place modification. The actual cost of erasing a
9415 secondary key and inserting another one depends also on the
9416 allocator used for secondary associative-containers (The tests
9417 above used the standard allocator, but in practice one might
9418 choose to use, e.g., [boost_pool]). Option 2 is
9419 definitely an overkill in this case. Option 1 loses out either
9420 immediately (when there is one secondary key per primary key)
9421 or almost immediately after that. Option 5 has the same
9422 drawbacks as option 2, but it has the additional drawback that
9423 finding all values whose primary key is equivalent to some key,
9424 might be linear in the total number of values stored (for
9425 example, if using a hash-based container).</para>
9426 <para>If the expected ratio of secondary keys to primary keys is
9427 large, then the answer is more complicated. It depends on the
9428 distribution of secondary keys to primary keys, the
9429 distribution of accesses according to primary keys, and the
9430 types of operations most frequent.</para>
9431 <para>To be more precise, assume there are m primary keys,
9432 primary key i is mapped to n<subscript>i</subscript>
9433 secondary keys, and each primary key is mapped, on average, to
9434 n secondary keys (i.e.,
9435 E(n<subscript>i</subscript>) = n).</para>
9436 <para>Suppose one wants to find a specific pair of primary and
9437 secondary keys. Using 1 with a tree based container
9438 (<classname>std::multimap</classname>), the expected cost is
9439 E(Θ(log(m) + n<subscript>i</subscript>)) = Θ(log(m) +
9440 n); using 1 with a hash-based container
9441 (<classname>std::tr1::unordered_multimap</classname>), the expected cost is
9442 Θ(n). Using 2 with a primary hash-based container
9443 and secondary hash-based containers, the expected cost is
9444 O(1); using 2 with a primary tree-based container and
9445 secondary tree-based containers, the expected cost is (using
9446 the Jensen inequality [motwani95random])
9447 E(O(log(m) + log(n<subscript>i</subscript>)) = O(log(m)) +
9448 E(O(log(n<subscript>i</subscript>)) = O(log(m)) + O(log(n)),
9449 assuming that primary keys are accessed equiprobably. 3 and 4
9450 are similar to 1, but with lower constants. Using 5 with a
9451 hash-based container, the expected cost is O(1); using 5
9452 with a tree based container, the cost is
9453 E(Θ(log(mn))) = Θ(log(m) +
9455 <para>Suppose one needs the values whose primary key matches some
9456 given key. Using 1 with a hash-based container, the expected
9457 cost is Θ(n), but the values will not be ordered
9458 by secondary keys (which may or may not be required); using 1
9459 with a tree-based container, the expected cost is
9460 Θ(log(m) + n), but with high constants; again the
9461 values will not be ordered by secondary keys. 2, 3, and 4 are
9462 similar to 1, but typically with lower constants (and,
9463 additionally, if one uses a tree-based container for secondary
9464 keys, they will be ordered). Using 5 with a hash-based
9465 container, the cost is Θ(mn).</para>
9466 <para>Suppose one wants to assign to a primary key all secondary
9467 keys assigned to a different primary key. Using 1 with a
9468 hash-based container, the expected cost is Θ(n),
9469 but with very high constants; using 1 with a tree-based
9470 container, the cost is Θ(nlog(mn)). Using 2, 3,
9471 and 4, the expected cost is Θ(n), but typically
9472 with far lower costs than 1. 5 is similar to 1.</para>
9479 <section xml:id="observations.priority_queue">
9480 <info><title>Priority_Queue</title></info>
9482 <section xml:id="observations.priority_queue.complexity">
9483 <info><title>Complexity</title></info>
9485 <para>The following table shows the complexities of the different
9486 underlying data structures in terms of orders of growth. It is
9487 interesting to note that this table implies something about the
9488 constants of the operations as well (see Amortized <function>push</function>
9489 and <function>pop</function> operations).</para>
9491 <informaltable frame="all">
9493 <tgroup cols="6" align="left" colsep="1" rowsep="1">
9494 <colspec colname="c1"/>
9495 <colspec colname="c2"/>
9496 <colspec colname="c3"/>
9497 <colspec colname="c4"/>
9498 <colspec colname="c5"/>
9499 <colspec colname="c6"/>
9503 <entry><emphasis><function>push</function></emphasis></entry>
9504 <entry><emphasis><function>pop</function></emphasis></entry>
9505 <entry><emphasis><function>modify</function></emphasis></entry>
9506 <entry><emphasis><function>erase</function></emphasis></entry>
9507 <entry><emphasis><function>join</function></emphasis></entry>
9515 <classname>std::priority_queue</classname>
9526 <subscript>[std note 1]</subscript>
9530 <subscript>[std note 2]</subscript>
9534 <subscript>[std note 1]</subscript>
9539 <classname>priority_queue</classname>
9540 <<classname>Tag</classname> =
9541 <classname>pairing_heap_tag</classname>>
9564 <classname>priority_queue</classname>
9565 <<classname>Tag</classname> =
9566 <classname>binary_heap_tag</classname>>
9588 <classname>priority_queue</classname>
9589 <<classname>Tag</classname> =
9590 <classname>binomial_heap_tag</classname>>
9611 <classname>priority_queue</classname>
9612 <<classname>Tag</classname> =
9613 <classname>rc_binomial_heap_tag</classname>>
9633 <classname>priority_queue</classname><<classname>Tag</classname> =
9634 <classname>thin_heap_tag</classname>>
9646 or Θ(log(n)) amortized
9647 <subscript>[thin_heap_note]</subscript>
9662 <para>[std note 1] This
9663 is not a property of the algorithm, but rather due to the fact
9664 that the standard's priority queue implementation does not support
9665 iterators (and consequently the ability to access a specific
9666 value inside it). If the priority queue is adapting an
9667 <classname>std::vector</classname>, then it is still possible to reduce this
9668 to Θ(n) by adapting over the standard's adapter and
9669 using the fact that <function>top</function> returns a reference to the
9670 first value; if, however, it is adapting an
9671 <classname>std::deque</classname>, then this is impossible.</para>
9673 <para>[std note 2] As
9674 with [std note 1], this is not a
9675 property of the algorithm, but rather the standard's implementation.
9676 Again, if the priority queue is adapting an
9677 <classname>std::vector</classname> then it is possible to reduce this to
9678 Θ(n), but with a very high constant (one must call
9679 <function>std::make_heap</function> which is an expensive linear
9680 operation); if the priority queue is adapting an
9681 <classname>std::deque</classname>, then this is impossible.</para>
9683 <para>[thin_heap_note] A thin heap has
9684 Θ(log(n)) worst case <function>modify</function> time
9685 always, but the amortized time depends on the nature of the
9686 operation: I) if the operation increases the key (in the sense
9687 of the priority queue's comparison functor), then the amortized
9688 time is O(1), but if II) it decreases it, then the
9689 amortized time is the same as the worst case time. Note that
9690 for most algorithms, I) is important and II) is not.</para>
9694 <section xml:id="observations.priority_queue.amortized_ops">
9696 Amortized <function>push</function>
9697 and <function>pop</function> operations
9701 <para>In many cases, a priority queue is needed primarily for
9702 sequences of <function>push</function> and <function>pop</function> operations. All of
9703 the underlying data structures have the same amortized
9704 logarithmic complexity, but they differ in terms of
9706 <para>The table above shows that the different data structures are
9707 "constrained" in some respects. In general, if a data structure
9708 has lower worst-case complexity than another, then it will
9709 perform slower in the amortized sense. Thus, for example a
9710 redundant-counter binomial heap (<classname>priority_queue</classname> with
9711 <classname>Tag</classname> = <classname>rc_binomial_heap_tag</classname>)
9712 has lower worst-case <function>push</function> performance than a binomial
9713 heap (<classname>priority_queue</classname>
9714 with <classname>Tag</classname> = <classname>binomial_heap_tag</classname>),
9715 and so its amortized <function>push</function> performance is slower in
9716 terms of constants.</para>
9717 <para>As the table shows, the "least constrained" underlying
9718 data structures are binary heaps and pairing heaps.
9719 Consequently, it is not surprising that they perform best in
9720 terms of amortized constants.</para>
9722 <listitem><para>Pairing heaps seem to perform best for non-primitive
9723 types (e.g., <classname>std::string</classname>s), as shown by
9725 Queue Text <function>push</function> Timing Test and Priority
9726 Queue Text <function>push</function> and <function>pop</function> Timing
9727 Test</para></listitem>
9728 <listitem><para>binary heaps seem to perform best for primitive types
9729 (e.g., <type>int</type>s), as shown by Priority
9730 Queue Random Integer <function>push</function> Timing Test and
9732 Queue Random Integer <function>push</function> and <function>pop</function> Timing
9733 Test.</para></listitem>
9738 <section xml:id="observations.priority_queue.graphs">
9743 <para>In some graph algorithms, a decrease-key operation is
9744 required [clrs2001];
9745 this operation is identical to <function>modify</function> if a value is
9746 increased (in the sense of the priority queue's comparison
9747 functor). The table above and Priority Queue
9748 Text <function>modify</function> Up Timing Test show that a thin heap
9749 (<classname>priority_queue</classname> with
9750 <classname>Tag</classname> = <classname>thin_heap_tag</classname>)
9751 outperforms a pairing heap (<classname>priority_queue</classname> with
9752 <classname>Tag</classname> = <classname>Tag</classname> = <classname>pairing_heap_tag</classname>),
9753 but the rest of the tests show otherwise.</para>
9755 <para>This makes it difficult to decide which implementation to use in
9756 this case. Dijkstra's shortest-path algorithm, for example, requires
9757 Θ(n) <function>push</function> and <function>pop</function> operations
9758 (in the number of vertices), but O(n<superscript>2</superscript>)
9759 <function>modify</function> operations, which can be in practice Θ(n)
9760 as well. It is difficult to find an a-priori characterization of
9761 graphs in which the actual number of <function>modify</function>
9762 operations will dwarf the number of <function>push</function> and
9763 <function>pop</function> operations.</para>
9767 </section> <!-- priority_queue -->
9772 </section> <!-- performance -->