Tree-Based and Trie-Based Text Insert Timing Test

Description

This test inserts a number of values with keys from an arbitrary text ([ wickland96thirty ]) into a container using insert . It measures the average time for insert as a function of the number of values inserted.

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

Purpose

The test checks the effect of different underlying data structures.

Results

Figures NNTG, NVTG, and NPTG show the results for the native tree and pb_ds's node-based trees, the native tree and pb_ds's vector-based trees, and the native tree andpb_ds's PATRICIA-trie, respectively, in g++; Figures NNTM, NVTM, and NPTM show the same in msvc++; Figures NNTL, NVTL, and NPTL show the same in local.

no image
NNTG: Native tree and node-based trees text insert timing test using insert - g++

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

  1. splay_tree_map- tree with Tag = splay_tree_tag , and Node_Update = null_tree_node_update
  2. n_map- std::map
  3. rb_tree_map- tree with Tag = rb_tree_tag , and Node_Update = null_tree_node_update
no image
NVTG: Native tree and vector-based tree text insert timing test using insert - 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. n_map- std::map
no image
NPTG: Native tree and PATRICIA trie text insert timing test using insert - g++

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

  1. n_map- std::map
  2. pat_trie_map- trie with Tag = pat_trie_tag , and Node_Update = null_trie_node_update
no image
NNTM: Native tree and node-based trees text insert timing test using insert - msvc++

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

  1. splay_tree_map- tree with Tag = splay_tree_tag , and Node_Update = null_tree_node_update
  2. n_map- std::map
  3. rb_tree_map- tree with Tag = rb_tree_tag , and Node_Update = null_tree_node_update
no image
NVTM: Native tree and vector-based tree text insert timing test using insert - 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. n_map- std::map
no image
NPTM: Native tree and PATRICIA trie text insert timing test using insert - msvc++

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

  1. pat_trie_map- trie with Tag = pat_trie_tag , and Node_Update = null_trie_node_update
  2. n_map- std::map
no image
NNTL: Native tree and node-based trees text insert timing test using insert - local
no image
NVTL: Native tree and vector-based tree text insert timing test using insert - local
no image
NPTL: Native tree and PATRICIA trie text insert timing test using insert - local

Observations

Observing Figure NNTG , for this setting, a splay tree, ( tree with Tag = splay_tree_tag ) does not do well. This was covered in Tree-Based and Trie-Based Text find Find Timing Test . The two red-black trees perform better.

Observing Figure NVTG, an ordered-vector tree ( tree with Tag = ov_tree_tag) performs abysmally. Inserting into this type of tree has linear complexity [ austern00noset].

Observing Figure NPTG , A PATRICIA trie ( trie with Tag = pat_trie_tag ) has abysmal performance, as well. This is not that surprising, since a large-fan-out PATRICIA trie works like a hash table with collisions resolved by a sub-trie. Each time a collision is encountered, a new "hash-table" is built A large fan-out PATRICIA trie, however, doe does well in look-ups (see Tree-Based and Trie-Based Text find Find Timing Test ). It is possibly beneficial to semi-static settings, therefore.

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