X-Git-Url: https://oss.titaniummirror.com/gitweb?a=blobdiff_plain;f=libstdc%2B%2B-v3%2Fdoc%2Fhtml%2Fext%2Fpb_ds%2Fhash_random_int_erase_mem_usage_test.html;fp=libstdc%2B%2B-v3%2Fdoc%2Fhtml%2Fext%2Fpb_ds%2Fhash_random_int_erase_mem_usage_test.html;h=2867595b09154c145de72fce1b9270d6df56fdce;hb=6fed43773c9b0ce596dca5686f37ac3fc0fa11c0;hp=0000000000000000000000000000000000000000;hpb=27b11d56b743098deb193d510b337ba22dc52e5c;p=msp430-gcc.git diff --git a/libstdc++-v3/doc/html/ext/pb_ds/hash_random_int_erase_mem_usage_test.html b/libstdc++-v3/doc/html/ext/pb_ds/hash_random_int_erase_mem_usage_test.html new file mode 100644 index 00000000..2867595b --- /dev/null +++ b/libstdc++-v3/doc/html/ext/pb_ds/hash_random_int_erase_mem_usage_test.html @@ -0,0 +1,173 @@ + + + + + +Tree Text Locality of Reference Timing Test + + + +
+

Hash-Based Erase Memory-Use Test

+

Description

+

This test inserts a number of uniform i.i.d. integer keys + into a container, then erases all keys except one. It measures + the final size of the container.

+

(The test was executed with hash_random_int_erase_mem_usage.cc + 2000 2000 2100)

+

Purpose

+

The test checks how containers adjust internally as their + logical size decreases (see Motivation::Associative + Containers::Slightly Different Methods::Methods Related to + Erase).

+

Results

+

Figures NHG, NHM and + NHL show the results for the native and + collision-chaining types in g++, msvc++ and + local, + respectively.

+
+
+
+
+
no image
NHG: Native, collision-chaing, and probing, hash random int erase test - g++

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

+
    +
  1. +n_hash_set_ncah- +std::tr1::unordered_set with cache_hash_code = false
    2. +
  2. +gp_hash_mask_linp_exp_nea_lc_1div8_1div2_nsth_set- +gp_hash_table + with Comb_Hash_Fn = direct_mask_range_hashing +, 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, and Probe_Fn = linear_probe_fn +
    3. +
  3. +cc_hash_mod_prime_nea_lc_1div8_1div1_nsth_set- +cc_hash_table +with Comb_Hash_Fn = direct_mod_range_hashing +, and Resize_Policy = hash_standard_resize_policy + with Size_Policy = hash_prime_size_policy +, and Trigger_Policy = hash_load_check_resize_trigger + with αmin = 1/8 and αmax = 1/1
    4. +
  4. +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
    5. +
+
+
+
+
+
+
+
+
+
+
no image
NHM: Native, collision-chaing, and probing, hash random int erase test - msvc++

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

+
    +
  1. +n_hash_set_ncah- +stdext::hash_set
    2. +
  2. +gp_hash_mask_linp_exp_nea_lc_1div8_1div2_nsth_set- +gp_hash_table + with Comb_Hash_Fn = direct_mask_range_hashing +, 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, and Probe_Fn = linear_probe_fn +
    3. +
  3. +cc_hash_mod_prime_nea_lc_1div8_1div1_nsth_set- +cc_hash_table +with Comb_Hash_Fn = direct_mod_range_hashing +, and Resize_Policy = hash_standard_resize_policy + with Size_Policy = hash_prime_size_policy +, and Trigger_Policy = hash_load_check_resize_trigger + with αmin = 1/8 and αmax = 1/1
    4. +
  4. +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
    5. +
+
+
+
+
+
+
+
+
+
+
no image
NHM: Native, collision-chaing, and probing, hash random int erase test - msvc++

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

+
    +
  1. +n_hash_set_ncah- +stdext::hash_set
    2. +
  2. +gp_hash_mask_linp_exp_nea_lc_1div8_1div2_nsth_set- +gp_hash_table + with Comb_Hash_Fn = direct_mask_range_hashing +, 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, and Probe_Fn = linear_probe_fn +
    3. +
  3. +cc_hash_mod_prime_nea_lc_1div8_1div1_nsth_set- +cc_hash_table +with Comb_Hash_Fn = direct_mod_range_hashing +, and Resize_Policy = hash_standard_resize_policy + with Size_Policy = hash_prime_size_policy +, and Trigger_Policy = hash_load_check_resize_trigger + with αmin = 1/8 and αmax = 1/1
    4. +
  4. +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
    5. +
+
+
+
+
+
+
+
+
+
+
no image
NHL: Native, collision-chaing, and probing, hash random int erase test - local
+
+
+
+
+

Observations

+

STL hash-based containers act very differently than trees in + this respect. When erasing numerous keys from an STL + associative-container, the resulting memory user varies greatly + depending on whether the container is tree-based or hash-based. + As noted in Motivation::Choice of + Methods , this is a fundamental consequence of the STL's + associative containers' interface, it is not due to a specific + implementation.

+

(See Priority Queue + Text pop Memory Use Test for a similar phenomenon + regarding priority queues.)

+
+ +