On Sun, 9 Jul 2006, Roger Sayle wrote:
Interesting. Richard Guenther's post for the above change, which was
based upon a previous proposal by Brian Makin, suggested that this
patch reduced the compile-time of his tramp3d benchmark by 1%.
http://gcc.gnu.org/ml/gcc-patches/2005-11/msg00294.html
I realized that 3 orders of magnitude of diference wasn't a very realistic
benchmark. So I reviewed it. I found that I forgot some profiling code
that was biasing the result of the revision 106584, and that the pice
of splay tree usage used to perform the benchmark wasn't so representative
of the whole bootstrap. So the previous benchmark wasn't accurate at all.
That said, I rebuild a benchmark this time with full traces of splay tree
usage during tramp3d (380mb) compilation and gcc bootstraping(1gb).
And I did the benchmarking again. This time with the original code, with
the revision 106584 code and with the proposed by Brian Makin (with a
few changes). Thus I have been able to reproduce the speed improvement
with the Richard Guenther's patch.
I also noticed that the code sent by Brian Makin is slightly better than
Revision 106584 and that not pushes down the root node more than 2 levels,
which can prevent that some rare cases perform bad.
bootstrap
Original
real 61.630s
user 61.010s
sys 0.620s
Revision 106584
real 59.660s
user 59.000s
sys 0.660s
New
real 58.910s
user 58.240s
sys 0.670s
tramp3d
Original
real 26.680s
user 26.350s
sys 0.340s
Revision 106584
real 26.010s
user 25.660s
sys 0.340s
New
real 25.700s
user 25.340s
sys 0.360s
ian
--- splay-tree.c 2006-07-11 15:36:50.000000000 +0200
+++ splay-tree.nrn.c 2006-07-11 15:46:54.000000000 +0200
@@ -38,10 +38,6 @@ Boston, MA 02110-1301, USA. */
#include "splay-tree.h"
static void splay_tree_delete_helper (splay_tree, splay_tree_node);
-static inline void rotate_left (splay_tree_node *,
- splay_tree_node, splay_tree_node);
-static inline void rotate_right (splay_tree_node *,
- splay_tree_node, splay_tree_node);
static void splay_tree_splay (splay_tree, splay_tree_key);
static int splay_tree_foreach_helper (splay_tree, splay_tree_node,
splay_tree_foreach_fn, void*);
@@ -106,95 +102,103 @@ splay_tree_delete_helper (splay_tree sp,
#undef VDEL
}
-/* Rotate the edge joining the left child N with its parent P. PP is the
- grandparents pointer to P. */
+/* Splay SP around KEY.
+ This works alot like spliting a BST except if you traverse
+ left left or right right you first rotate the root before splitting
+ then move down a node. */
-static inline void
-rotate_left (splay_tree_node *pp, splay_tree_node p, splay_tree_node n)
+static void
+splay_tree_splay (splay_tree sp, splay_tree_key key)
{
- splay_tree_node tmp;
- tmp = n->right;
- n->right = p;
- p->left = tmp;
- *pp = n;
-}
+ if (sp->root == 0)
+ return;
-/* Rotate the edge joining the right child N with its parent P. PP is the
- grandparents pointer to P. */
+ /* temp_tree.left is all the nodes less than key while
+ temp_tree.right is all the nodes greater than key */
+ struct splay_tree_node_s temp_tree;
+
+ /* these are the points we will add new nodes to the respective trees */
+ splay_tree_node left_ptr;
+ splay_tree_node right_ptr;
-static inline void
-rotate_right (splay_tree_node *pp, splay_tree_node p, splay_tree_node n)
-{
- splay_tree_node tmp;
- tmp = n->left;
- n->left = p;
- p->right = tmp;
- *pp = n;
-}
+ /* current node we are splitting the tree at */
+ splay_tree_node current_node;
-/* Bottom up splay of key. */
+ splay_tree_node tmp_node;
+ int comparison;
-static void
-splay_tree_splay (splay_tree sp, splay_tree_key key)
-{
- if (sp->root == 0)
+ temp_tree.left = temp_tree.right = 0;
+ left_ptr = right_ptr = &temp_tree;
+
+ current_node = sp->root;
+ comparison = (*sp->comp) (key, current_node->key);
+
+ /* no splaying need */
+ if (comparison == 0)
return;
- do {
- int cmp1, cmp2;
- splay_tree_node n, c;
-
- n = sp->root;
- cmp1 = (*sp->comp) (key, n->key);
-
- /* Found. */
- if (cmp1 == 0)
- return;
-
- /* Left or right? If no child, then we're done. */
- if (cmp1 < 0)
- c = n->left;
- else
- c = n->right;
- if (!c)
- return;
-
- /* Next one left or right? If found or no child, we're done
- after one rotation. */
- cmp2 = (*sp->comp) (key, c->key);
- if (cmp2 == 0
- || (cmp2 < 0 && !c->left)
- || (cmp2 > 0 && !c->right))
- {
- if (cmp1 < 0)
- rotate_left (&sp->root, n, c);
- else
- rotate_right (&sp->root, n, c);
- return;
- }
-
- /* Now we have the four cases of double-rotation. */
- if (cmp1 < 0 && cmp2 < 0)
- {
- rotate_left (&n->left, c, c->left);
- rotate_left (&sp->root, n, n->left);
- }
- else if (cmp1 > 0 && cmp2 > 0)
- {
- rotate_right (&n->right, c, c->right);
- rotate_right (&sp->root, n, n->right);
- }
- else if (cmp1 < 0 && cmp2 > 0)
- {
- rotate_right (&n->left, c, c->right);
- rotate_left (&sp->root, n, n->left);
- }
- else if (cmp1 > 0 && cmp2 < 0)
- {
- rotate_left (&n->right, c, c->left);
- rotate_right (&sp->root, n, n->right);
- }
- } while (1);
+ /* while we haven't found the node */
+ do
+ {
+ /* left */
+ if (comparison < 0)
+ {
+ if (!current_node->left)
+ break;
+
+ comparison = (*sp->comp) (key, current_node->left->key);
+ /* left left */
+ if (comparison < 0)
+ {
+ tmp_node = current_node->left;
+ current_node->left = tmp_node->right;
+ tmp_node->right = current_node;
+ current_node = tmp_node;
+
+ if (!current_node->left)
+ break;
+
+ comparison = (*sp->comp) (key, current_node->left->key);
+ }
+
+ right_ptr->left = current_node;
+ right_ptr = current_node;
+ current_node = current_node->left;
+ }
+ /* right */
+ else
+ {
+ if (!current_node->right)
+ break;
+
+ comparison = (*sp->comp) (key, current_node->right->key);
+ /* right right */
+ if (comparison > 0)
+ {
+ tmp_node = current_node->right;
+ current_node->right = tmp_node->left;
+ tmp_node->left = current_node;
+ current_node = tmp_node;
+
+ if (!current_node->right)
+ break;
+
+ comparison = (*sp->comp) (key, current_node->right->key);
+ }
+
+ left_ptr->right = current_node;
+ left_ptr = current_node;
+ current_node = current_node->right;
+ }
+ }
+ while (comparison != 0);
+
+ left_ptr->right = current_node->left;
+ right_ptr->left = current_node->right;
+ current_node->left = temp_tree.right;
+ current_node->right = temp_tree.left;
+
+ sp->root = current_node;
}
/* Call FN, passing it the DATA, for every node below NODE, all of
