"Multimap" Text Insert Timing Test with Small 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 400 distinct primary keys, and the ratio of secondary keys to primary keys ranges from 1 to 5.
The test measures the average insert-time as a function of the number of values inserted. For pb_ds's containers, it inserts a primary key into the primary associative container, then a secondary key into the secondary associative container. For the native multimaps, it obtains a range usingstd::equal_range, and inserts a value only if it was not contained already.
(The test was executed with multimap_text_insert_timing_test thirty_years_among_the_dead_preproc.txt 400 1 1 6)
Purpose
The test checks the insert-time scalability of different "multimap" designs (see Motivation::Associative Containers::Alternative to Multiple Equivalent Keys).
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