"Multimap" Text Insert Timing Test with Large Average Secondary-Key to Primary-Key Ratio (original) (raw)
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 400 1 6 6)
Purpose
The test checks the insert-time scalability of different "multimap" designs (see Motivation::Associative Containers::Mapping Semantics).
Results
Figures NTG, NTM, andNTL show the results for "multimaps" which use a tree-based container for primary keys, in g++, msvc++, andlocal, 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.
NTL: Native and primary tree-based multimap types insert timing test - local
NHL: Native and primary hash-based multimap types insert timing test - local