From 554fd8c5195424bdbcabf5de30fdc183aba391bd Mon Sep 17 00:00:00 2001 From: upstream source tree Date: Sun, 15 Mar 2015 20:14:05 -0400 Subject: obtained gcc-4.6.4.tar.bz2 from upstream website; verified gcc-4.6.4.tar.bz2.sig; imported gcc-4.6.4 source tree from verified upstream tarball. downloading a git-generated archive based on the 'upstream' tag should provide you with a source tree that is binary identical to the one extracted from the above tarball. if you have obtained the source via the command 'git clone', however, do note that line-endings of files in your working directory might differ from line-endings of the respective files in the upstream repository. --- .../pb_ds/tree_text_lor_find_find_timing_test.html | 126 +++++++++++++++++++++ 1 file changed, 126 insertions(+) create mode 100644 libstdc++-v3/doc/html/ext/pb_ds/tree_text_lor_find_find_timing_test.html (limited to 'libstdc++-v3/doc/html/ext/pb_ds/tree_text_lor_find_find_timing_test.html') 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 000000000..c577a56db --- /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.

+
+ + -- cgit v1.2.3