"Multimap" Text Find 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 average find-time as a function of the number of values inserted. For pb_ds's containers, it finds the secondary key from a container obtained from finding a primary key. For the native multimaps, it searches a range obtained using std::equal_range on a primary key.
(The test was executed with multimap_text_find_timing_test thirty_years_among_the_dead_preproc.txt 100 3 4 4)
Purpose
The test checks the find-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 find timing test - local
NHL: Native and primary hash-based multimap types find timing test - local