"Multimap" Text Memory Use Test with Large 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. 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 200 2100 100)

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: NHG 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. n_mmap- std::multimap
  2. 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
  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. n_hash_mmap- stdext::hash_multimap
  2. 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
  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.