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. --- .../hash_random_int_find_find_timing_test.html | 247 +++++++++++++++++++++ 1 file changed, 247 insertions(+) create mode 100644 libstdc++-v3/doc/html/ext/pb_ds/hash_random_int_find_find_timing_test.html (limited to 'libstdc++-v3/doc/html/ext/pb_ds/hash_random_int_find_find_timing_test.html') diff --git a/libstdc++-v3/doc/html/ext/pb_ds/hash_random_int_find_find_timing_test.html b/libstdc++-v3/doc/html/ext/pb_ds/hash_random_int_find_find_timing_test.html new file mode 100644 index 000000000..b6066e7cf --- /dev/null +++ b/libstdc++-v3/doc/html/ext/pb_ds/hash_random_int_find_find_timing_test.html @@ -0,0 +1,247 @@ + + + + + +Hash Random Int Find Timing Test + + + +
+

Hash-Based Random-Integer find Find Timing + Test

+

Description

+

This test inserts a number of values with uniform i.i.d. + integer keys into a container, then performs a series of finds + using find. It measures the average time + forfind as a function of the number of values + inserted.

+

(The test was executed with random_int_find_timing_test + 200 200 2100)

+

Purpose

+

The test checks the effect of different underlying + hash-tables (see Design::Associative + Containers::Associative Containers::Hash-Based Containers), + range-hashing functions, and trigger policies (see Design::Associative + Containers::Hash-Based Containers::Hash Policies and + Design::Associative + Containers::Hash-Based Containers::Resize Policies).

+

Results

+

Figures NCCG, NCCM, + and NCCL show the results for the native + and collision-chaining types in g++, MSVC++, and + local, + respectively; Figures NGPG, NGPM, and NGPL show the results + for the native and probing types in g++, MSVC++, and + local + respectively.

+
+
+
+
+
no image
NCCG: Native and collision-chaining hash random int find timing test using find - g++

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

+
    +
  1. +n_hash_map_ncah- +std::tr1::unordered_map with cache_hash_code = false
    2. +
  2. +cc_hash_mod_prime_nea_lc_1div8_1div1_nsth_map- +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
    3. +
  3. +cc_hash_mod_prime_nea_lc_1div8_1div2_nsth_map- +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/2
    4. +
  4. +cc_hash_mask_exp_nea_lc_1div8_1div1_nsth_map- +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/1
    5. +
  5. +cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_map- +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
    6. +
+
+
+
+
+
+
+
+
+
+
no image
NCCM: Native and collision-chaining hash random int find timing test using find - msvc++

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

+
    +
  1. +cc_hash_mod_prime_nea_lc_1div8_1div1_nsth_map- +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
    2. +
  2. +cc_hash_mod_prime_nea_lc_1div8_1div2_nsth_map- +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/2
    3. +
  3. +n_hash_map_ncah- +stdext::hash_map
    4. +
  4. +cc_hash_mask_exp_nea_lc_1div8_1div1_nsth_map- +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/1
    5. +
  5. +cc_hash_mask_exp_nea_lc_1div8_1div2_nsth_map- +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
    6. +
+
+
+
+
+
+
+
+
+
+
no image
NCCL: Native and collision-chaining hash random int find timing test using find - local
+
+
+
+
+
+
+
+
+
no image
NGPG: Native and collision-chaining hash random int find timing test using find - g++

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

+
    +
  1. +gp_hash_mod_quadp_prime_nea_lc_1div8_1div2_nsth_map- +gp_hash_table + with Comb_Hash_Fn = direct_mod_range_hashing +, 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/2, and Probe_Fn = quadratic_probe_fn +
    2. +
  2. +n_hash_map_ncah- +std::tr1::unordered_map with cache_hash_code = false
    3. +
  3. +gp_hash_mask_linp_exp_nea_lc_1div8_1div2_nsth_map- +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 +
    4. +
+
+
+
+
+
+
+
+
+
+
no image
NGPM: Native and collision-chaining hash random int find timing test using find - msvc++

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

+
    +
  1. +gp_hash_mod_quadp_prime_nea_lc_1div8_1div2_nsth_map- +gp_hash_table + with Comb_Hash_Fn = direct_mod_range_hashing +, 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/2, and Probe_Fn = quadratic_probe_fn +
    2. +
  2. +n_hash_map_ncah- +stdext::hash_map
    3. +
  3. +gp_hash_mask_linp_exp_nea_lc_1div8_1div2_nsth_map- +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 +
    4. +
+
+
+
+
+
+
+
+
+
+
no image
NGPL: Native and collision-chaining hash random int find timing test using find - local
+
+
+
+
+

Observations

+

In this setting, the choice of underlying hash-table (see + Design::Associative + Containers::Hash-Based Containers ) affects performance + most, then the range-hashing scheme (See Design::Associative + Containers::Hash-Based Containers::Hash Policies ), and, + only finally, other policies.

+

When comparing Figures NCCG and NCCM to NGPG and NGPM , respectively, it is apparent that the + probing containers are less efficient than the + collision-chaining containers (both + std::tr1::unordered_map and stdext::hash_map + use collision-chaining) in this case.

+

( Hash-Based + Random-Integer Subscript Insert Timing Test shows a + different case, where the situation is reversed; Observations::Hash-Based + Container Types discusses some further considerations.)

+

Within each type of hash-table, the range-hashing scheme + affects performance more than other policies; Hash-Based + Text find Find Timing Test::Observations discusses + this. In Figures NCCG , NCCM , NGPG , and NGPM , it should be noted that + std::tr1::unordered_map and stdext::hash_map + are hard-wired currently to mod-based and mask-based schemes, + respectively.

+

Observations::Hash-Based + Container Types summarizes some observations on hash-based + containers; Observations::Hash-Based + Containers' Policies summarizes some observations on + hash-based containers' policies.

+
+ + -- cgit v1.2.3