From 554fd8c5195424bdbcabf5de30fdc183aba391bd Mon Sep 17 00:00:00 2001 From: upstream source tree Date: Sun, 15 Mar 2015 20:14:05 -0400 Subject: obtained gcc-4.6.4.tar.bz2 from upstream website; verified gcc-4.6.4.tar.bz2.sig; imported gcc-4.6.4 source tree from verified upstream tarball. downloading a git-generated archive based on the 'upstream' tag should provide you with a source tree that is binary identical to the one extracted from the above tarball. if you have obtained the source via the command 'git clone', however, do note that line-endings of files in your working directory might differ from line-endings of the respective files in the upstream repository. --- .../multimap_text_insert_mem_usage_test_small.html | 212 +++++++++++++++++++++ 1 file changed, 212 insertions(+) create mode 100644 libstdc++-v3/doc/html/ext/pb_ds/multimap_text_insert_mem_usage_test_small.html (limited to 'libstdc++-v3/doc/html/ext/pb_ds/multimap_text_insert_mem_usage_test_small.html') diff --git a/libstdc++-v3/doc/html/ext/pb_ds/multimap_text_insert_mem_usage_test_small.html b/libstdc++-v3/doc/html/ext/pb_ds/multimap_text_insert_mem_usage_test_small.html new file mode 100644 index 000000000..462fce4ca --- /dev/null +++ b/libstdc++-v3/doc/html/ext/pb_ds/multimap_text_insert_mem_usage_test_small.html @@ -0,0 +1,212 @@ + + + + + +Hash-List "Multimap" Text Memory Use Test with Small + Average Secondary-Key to Primary-Key Ratio + + + +
+

"Multimap" Text Memory Use Test with Small Average + Secondary-Key to Primary-Key Ratio

+

Description

+

This test inserts a number of pairs into a container. The + first item of each pair is a string from an arbitrary text + [wickland96thirty], and + the second is a uniform i.i.d.integer. The container is a + "multimap" - it considers the first member of each pair as a + primary key, and the second member of each pair as a secondary + key (see Motivation::Associative + Containers::Alternative to Multiple Equivalent Keys). There + are 100 distinct primary keys, and the ratio of secondary keys + to primary keys ranges to about 20.

+

The test measures the memory use as a function of the number + of values inserted.

+

(The test was executed with multimap_text_insert_mem_usage_test + thirty_years_among_the_dead_preproc.txt 100 3 4 4)

+

Purpose

+

The test checks the memory scalability of different + "multimap" designs (see Motivation::Associative + Containers::Mapping Semantics).

+

Results

+

Figures NTG, NTM, and + NTL show the results for "multimaps" which + use a tree-based container for primary keys, in g++, msvc++, and + local, + respectively; Figures NHG, NHM, and NHL show the results for + "multimaps" which use a hash-based container for primary keys, + in g++, + msvc++, + and local, + respectively.

+
+
+
+
+
no image
NTG: Native and primary tree-based multimap types mem usage test - g++

In the above figure, the names in the legends have the following meaning:

+
    +
  1. +rb_tree_mmap_cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_set- +tree + with Tag = rb_tree_tag +, and Node_Update = null_tree_node_update +, mapping each key to cc_hash_table +with Comb_Hash_Fn = direct_mask_range_hashing +, and Resize_Policy = hash_standard_resize_policy + with Size_Policy = hash_exponential_size_policy +, and Trigger_Policy = hash_load_check_resize_trigger + with αmin = 1/8 and αmax = 1/2
    2. +
  2. +n_mmap- +std::multimap
    3. +
  3. +rb_tree_mmap_lu_mtf_set- +tree + with Tag = rb_tree_tag +, and Node_Update = null_tree_node_update +, mapping each key to list_update + with Update_Policy = move_to_front_lu_policy +
    4. +
+
+
+
+
+
+
+
+
+
+
no image
NTM: NHM Native and primary tree-based multimap types mem usage test - msvc++

In the above figure, the names in the legends have the following meaning:

+
    +
  1. +rb_tree_mmap_cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_set- +tree + with Tag = rb_tree_tag +, and Node_Update = null_tree_node_update +, mapping each key to cc_hash_table +with Comb_Hash_Fn = direct_mask_range_hashing +, and Resize_Policy = hash_standard_resize_policy + with Size_Policy = hash_exponential_size_policy +, and Trigger_Policy = hash_load_check_resize_trigger + with αmin = 1/8 and αmax = 1/2
    2. +
  2. +n_mmap- +std::multimap
    3. +
  3. +rb_tree_mmap_lu_mtf_set- +tree + with Tag = rb_tree_tag +, and Node_Update = null_tree_node_update +, mapping each key to list_update + with Update_Policy = move_to_front_lu_policy +
    4. +
+
+
+
+
+
+
+
+
+
+
no image
NTL: Native and primary tree-based multimap types mem usage test - local
+
+
+
+
+
+
+
+
+
no image
NHG: Native and primary hash-based multimap types mem usage test - g++

In the above figure, the names in the legends have the following meaning:

+
    +
  1. +cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_mmap_cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_set- +cc_hash_table +with Comb_Hash_Fn = direct_mask_range_hashing +, and Resize_Policy = hash_standard_resize_policy + with Size_Policy = hash_exponential_size_policy +, and Trigger_Policy = hash_load_check_resize_trigger + with αmin = 1/8 and αmax = 1/2, mapping each key to cc_hash_table +with Comb_Hash_Fn = direct_mask_range_hashing +, and Resize_Policy = hash_standard_resize_policy + with Size_Policy = hash_exponential_size_policy +, and Trigger_Policy = hash_load_check_resize_trigger + with αmin = 1/8 and αmax = 1/2
    2. +
  2. +n_hash_mmap- +__gnucxx::hash_multimap
    3. +
  3. +cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_mmap_lu_mtf_set- +cc_hash_table +with Comb_Hash_Fn = direct_mask_range_hashing +, and Resize_Policy = hash_standard_resize_policy + with Size_Policy = hash_exponential_size_policy +, and Trigger_Policy = hash_load_check_resize_trigger + with αmin = 1/8 and αmax = 1/2, mapping each key to list_update + with Update_Policy = move_to_front_lu_policy +
    4. +
+
+
+
+
+
+
+
+
+
+
no image
NHM: Native and primary hash-based multimap types mem usage test - msvc++

In the above figure, the names in the legends have the following meaning:

+
    +
  1. +cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_mmap_cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_set- +cc_hash_table +with Comb_Hash_Fn = direct_mask_range_hashing +, and Resize_Policy = hash_standard_resize_policy + with Size_Policy = hash_exponential_size_policy +, and Trigger_Policy = hash_load_check_resize_trigger + with αmin = 1/8 and αmax = 1/2, mapping each key to cc_hash_table +with Comb_Hash_Fn = direct_mask_range_hashing +, and Resize_Policy = hash_standard_resize_policy + with Size_Policy = hash_exponential_size_policy +, and Trigger_Policy = hash_load_check_resize_trigger + with αmin = 1/8 and αmax = 1/2
    2. +
  2. +n_hash_mmap- +stdext::hash_multimap
    3. +
  3. +cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_mmap_lu_mtf_set- +cc_hash_table +with Comb_Hash_Fn = direct_mask_range_hashing +, and Resize_Policy = hash_standard_resize_policy + with Size_Policy = hash_exponential_size_policy +, and Trigger_Policy = hash_load_check_resize_trigger + with αmin = 1/8 and αmax = 1/2, mapping each key to list_update + with Update_Policy = move_to_front_lu_policy +
    4. +
+
+
+
+
+
+
+
+
+
+
no image
NHL: Native and primary hash-based multimap types mem usage test - local
+
+
+
+
+

Observations

+

See Observations::Mapping-Semantics + Considerations.

+
+ + -- cgit v1.2.3