"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. n_mmap- std::multimap
  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
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. n_mmap- std::multimap
  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
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. n_hash_mmap- __gnucxx::hash_multimap
  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
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. n_hash_mmap- stdext::hash_multimap
  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
no image
NHL: Native and primary hash-based multimap types mem usage test - local

Observations

See Observations::Mapping-Semantics Considerations.