Tree-Based Locality-of-Reference Text find Find Timing Test

Description

This test inserts a number of values with keys from an arbitrary text ([ wickland96thirty ]) into a container, then performs a series of finds using find . It is different than Tree-Based and Trie-Based Text find Find Timing Test in the sequence of finds it performs: this test performs multiple find s on the same key before moving on to the next key. It measures the average time for find as a function of the number of values inserted.

(The test was executed with tree_text_lor_find_timing_test thirty_years_among_the_dead_preproc.txt 200 200 2100)

Purpose

The test checks the effect of different underlying data structures in a locality-of-reference setting.

Results

Figures NTG, NTM, and NTL show the results for the native and pb_ds tree-based types in g++, msvc++ and local, respectively.

no image
NTG: Native and tree-based locality-of-reference text find timing test using find - g++

In the above figure, the names in the legends have the following meaning:

  1. ov_tree_map- tree with Tag = ov_tree_tag , and Node_Update = null_tree_node_update
  2. rb_tree_map- tree with Tag = rb_tree_tag , and Node_Update = null_tree_node_update
  3. n_map- std::map
  4. splay_tree_map- tree with Tag = splay_tree_tag , and Node_Update = null_tree_node_update
no image
NTM: Native and tree-based locality-of-reference text find timing test using find - msvc++

In the above figure, the names in the legends have the following meaning:

  1. ov_tree_map- tree with Tag = ov_tree_tag , and Node_Update = null_tree_node_update
  2. rb_tree_map- tree with Tag = rb_tree_tag , and Node_Update = null_tree_node_update
  3. n_map- std::map
  4. splay_tree_map- tree with Tag = splay_tree_tag , and Node_Update = null_tree_node_update
no image
NTL: Native and tree-based locality-of-reference text find timing test using find - local

Observations

For this setting, an ordered-vector tree ( tree with Tag = ov_tree_tag ), a red-black tree ( tree with Tag = rb_tree_tag ), and the native red-black tree all share approximately the same performance.

A splay tree ( tree with Tag = splay_tree_tag ) does much better, since each (successful) find "bubbles" the corresponding node to the root of the tree.

Observations::Tree-Like-Based Container Types summarizes some observations on tree-based and trie-based containers.