X-Git-Url: https://oss.titaniummirror.com/gitweb?a=blobdiff_plain;f=libstdc%2B%2B-v3%2Fdoc%2Fhtml%2Fext%2Fpb_ds%2Ftree_text_lor_find_find_timing_test.html;fp=libstdc%2B%2B-v3%2Fdoc%2Fhtml%2Fext%2Fpb_ds%2Ftree_text_lor_find_find_timing_test.html;h=c577a56dbcbcce477f3245ef2b8a0ab37a632298;hb=6fed43773c9b0ce596dca5686f37ac3fc0fa11c0;hp=0000000000000000000000000000000000000000;hpb=27b11d56b743098deb193d510b337ba22dc52e5c;p=msp430-gcc.git diff --git a/libstdc++-v3/doc/html/ext/pb_ds/tree_text_lor_find_find_timing_test.html b/libstdc++-v3/doc/html/ext/pb_ds/tree_text_lor_find_find_timing_test.html new file mode 100644 index 00000000..c577a56d --- /dev/null +++ b/libstdc++-v3/doc/html/ext/pb_ds/tree_text_lor_find_find_timing_test.html @@ -0,0 +1,126 @@ + + + + + +Tree Text Locality of Reference Find Timing Test + + + +
+

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. +
  2. +rb_tree_map- +tree + with Tag = rb_tree_tag +, and Node_Update = null_tree_node_update +
    3. +
  3. +n_map- +std::map
    4. +
  4. +splay_tree_map- +tree + with Tag = splay_tree_tag +, and Node_Update = null_tree_node_update +
    5. +
+
+
+
+
+
+
+
+
+
+
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. +
  2. +rb_tree_map- +tree + with Tag = rb_tree_tag +, and Node_Update = null_tree_node_update +
    3. +
  3. +n_map- +std::map
    4. +
  4. +splay_tree_map- +tree + with Tag = splay_tree_tag +, and Node_Update = null_tree_node_update +
    5. +
+
+
+
+
+
+
+
+
+
+
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.

+
+ +