This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

RE: Proposal for adding splay_tree_find (to find elements without updating the nodes).



----------------------------------------
> From: stevenb.gcc@gmail.com
> Date: Mon, 9 Mar 2015 23:59:52 +0100
> Subject: Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
> To: hiraditya@msn.com
> CC: gcc@gcc.gnu.org
>
> On Mon, Mar 9, 2015 at 7:59 PM, vax mzn wrote:
>> w.r.t, https://gcc.gnu.org/wiki/Speedup_areas where we want to improve the performance of splay trees.
>>
>> The function `splay_tree_node splay_tree_lookup (splay_tree, splay_tree_key);'
>> updates the nodes every time a lookup is done.
>>
>> IIUC, There are places where we call this function in a loop i.e., we lookup different elements every time.
>> e.g.,
>> In this exaple we are looking for a different `t' in each iteration.
>
>
> If that's really true, then a splay tree is a horrible choice of data
> structure. The splay tree will simply degenerate to a linked list. The
> right thing to do would be, not to "break" one of the key features of
> splay trees (i.e. the latest lookup is always on top), but to use
> another data structure.
>
> Ciao!
> Steven

So I have this patch which replaces splay_tree_lookup with a new function splay_tree_find at some places.
I hope this is helpful.

commit 64f203f36661efd95958474f31b588a134dedb41
Author: Aditya <hiraditya@msn.com>
Date:   Mon Mar 9 22:47:04 2015 -0500

    add splay_tree_find for finding elements without updating the tree

diff --git a/gcc/gimplify.c b/gcc/gimplify.c
index d822913..1053eee 100644
--- a/gcc/gimplify.c
+++ b/gcc/gimplify.c
@@ -1093,7 +1093,7 @@ gimplify_bind_expr (tree *expr_p, gimple_seq *pre_p)
          /* Mark variable as local.  */
          if (ctx && !DECL_EXTERNAL (t)
              && (! DECL_SEEN_IN_BIND_EXPR_P (t)
-                 || splay_tree_lookup (ctx->variables,
+          || splay_tree_find (ctx->variables,
                                        (splay_tree_key) t) == NULL))
            {
              if (ctx->region_type == ORT_SIMD
@@ -5529,7 +5529,7 @@ omp_firstprivatize_variable (struct gimplify_omp_ctx *ctx, tree decl)
 
   do
     {
-      n = splay_tree_lookup (ctx->variables, (splay_tree_key)decl);
+      n = splay_tree_find (ctx->variables, (splay_tree_key)decl);
       if (n != NULL)
        {
          if (n->value & GOVD_SHARED)
@@ -6428,7 +6428,7 @@ gimplify_adjust_omp_clauses_1 (splay_tree_node n, void *data)
          while (ctx != NULL)
            {
              splay_tree_node on
-               = splay_tree_lookup (ctx->variables, (splay_tree_key) decl);
+        = splay_tree_find (ctx->variables, (splay_tree_key) decl);
              if (on && (on->value & (GOVD_FIRSTPRIVATE | GOVD_LASTPRIVATE
                                      | GOVD_PRIVATE | GOVD_REDUCTION
                                      | GOVD_LINEAR | GOVD_MAP)) != 0)
@@ -6529,7 +6529,7 @@ gimplify_adjust_omp_clauses (gimple_seq *pre_p, tree *list_p)
        case OMP_CLAUSE_FIRSTPRIVATE:
        case OMP_CLAUSE_LINEAR:
          decl = OMP_CLAUSE_DECL (c);
-         n = splay_tree_lookup (ctx->variables, (splay_tree_key) decl);
+      n = splay_tree_find (ctx->variables, (splay_tree_key) decl);
          remove = !(n->value & GOVD_SEEN);
          if (! remove)
            {
@@ -6551,7 +6551,7 @@ gimplify_adjust_omp_clauses (gimple_seq *pre_p, tree *list_p)
                  if (ctx->outer_context->combined_loop
                      && !OMP_CLAUSE_LINEAR_NO_COPYIN (c))
                    {
-                     n = splay_tree_lookup (ctx->outer_context->variables,
+              n = splay_tree_find (ctx->outer_context->variables,
                                             (splay_tree_key) decl);
                      if (n == NULL
                          || (n->value & GOVD_DATA_SHARE_CLASS) == 0)
@@ -6578,7 +6578,7 @@ gimplify_adjust_omp_clauses (gimple_seq *pre_p, tree *list_p)
          /* Make sure OMP_CLAUSE_LASTPRIVATE_FIRSTPRIVATE is set to
             accurately reflect the presence of a FIRSTPRIVATE clause.  */
          decl = OMP_CLAUSE_DECL (c);
-         n = splay_tree_lookup (ctx->variables, (splay_tree_key) decl);
+      n = splay_tree_find (ctx->variables, (splay_tree_key) decl);
          OMP_CLAUSE_LASTPRIVATE_FIRSTPRIVATE (c)
            = (n->value & GOVD_FIRSTPRIVATE) != 0;
          break;
@@ -6587,7 +6587,7 @@ gimplify_adjust_omp_clauses (gimple_seq *pre_p, tree *list_p)
          decl = OMP_CLAUSE_DECL (c);
          if (!is_global_var (decl))
            {
-             n = splay_tree_lookup (ctx->variables, (splay_tree_key) decl);
+          n = splay_tree_find (ctx->variables, (splay_tree_key) decl);
              remove = n == NULL || !(n->value & GOVD_SEEN);
              if (!remove && TREE_CODE (TREE_TYPE (decl)) == POINTER_TYPE)
                {
@@ -6600,7 +6600,7 @@ gimplify_adjust_omp_clauses (gimple_seq *pre_p, tree *list_p)
                    for (octx = ctx->outer_context; octx;
                         octx = octx->outer_context)
                      {
-                       n = splay_tree_lookup (octx->variables,
+            n = splay_tree_find (octx->variables,
                                               (splay_tree_key) decl);
                        if (n == NULL)
                          continue;
@@ -6619,7 +6619,7 @@ gimplify_adjust_omp_clauses (gimple_seq *pre_p, tree *list_p)
            }
          else if (TREE_CODE (TREE_TYPE (decl)) == ARRAY_TYPE)
            {
-             n = splay_tree_lookup (ctx->variables, (splay_tree_key) decl);
+          n = splay_tree_find (ctx->variables, (splay_tree_key) decl);
              if (n != NULL && (n->value & GOVD_DATA_SHARE_CLASS) != 0)
                remove = true;
            }
@@ -6629,7 +6629,7 @@ gimplify_adjust_omp_clauses (gimple_seq *pre_p, tree *list_p)
          decl = OMP_CLAUSE_DECL (c);
          if (!DECL_P (decl))
            break;
-         n = splay_tree_lookup (ctx->variables, (splay_tree_key) decl);
+      n = splay_tree_find (ctx->variables, (splay_tree_key) decl);
          if (ctx->region_type == ORT_TARGET && !(n->value & GOVD_SEEN))
            remove = true;
          else if (DECL_SIZE (decl)
diff --git a/gcc/tree-dump.c b/gcc/tree-dump.c
index 620b391..f942f14 100644
--- a/gcc/tree-dump.c
+++ b/gcc/tree-dump.c
@@ -113,7 +113,7 @@ queue_and_dump_index (dump_info_p di, const char *field, const_tree t, int flags
     return;
 
   /* See if we've already queued or dumped this node.  */
-  n = splay_tree_lookup (di->nodes, (splay_tree_key) t);
+  n = splay_tree_find (di->nodes, (splay_tree_key) t);
   if (n)
     index = ((dump_node_info_p) n->value)->index;
   else
diff --git a/include/splay-tree.h b/include/splay-tree.h
index ec48a1f..a73a2cf 100644
--- a/include/splay-tree.h
+++ b/include/splay-tree.h
@@ -141,6 +141,7 @@ extern splay_tree_node splay_tree_insert (splay_tree,
                                          splay_tree_key,
                                          splay_tree_value);
 extern void splay_tree_remove  (splay_tree, splay_tree_key);
+extern splay_tree_node splay_tree_find (splay_tree sp, splay_tree_key key);
 extern splay_tree_node splay_tree_lookup (splay_tree, splay_tree_key);
 extern splay_tree_node splay_tree_predecessor (splay_tree, splay_tree_key);
 extern splay_tree_node splay_tree_successor (splay_tree, splay_tree_key);
diff --git a/libiberty/splay-tree.c b/libiberty/splay-tree.c
index 12bfa8b..7cdf5d5 100644
--- a/libiberty/splay-tree.c
+++ b/libiberty/splay-tree.c
@@ -198,6 +198,38 @@ splay_tree_splay (splay_tree sp, splay_tree_key key)
   } while (1);
 }
 
+/* Simple binary tree search without any sort of update. This is useful when
+   we do not care about locality. e.g., searching nodes in an loop */
+
+splay_tree_node
+splay_tree_find (splay_tree sp, splay_tree_key key)
+{
+  if (sp->root == 0)
+    return;
+
+  int cmp;
+  splay_tree_node n, c;
+  c = sp->root;
+
+  do {
+
+    n = c;
+    cmp = (*sp->comp) (key, n->key);
+
+    /* Found.  */
+    if (cmp == 0)
+      return n;
+
+    /* Left or right?  If no child, then we're done.  */
+    if (cmp < 0)
+      c = n->left;
+    else
+      c = n->right;
+    if (!c)
+      return 0;
+  } while (1);
+}
+
 /* Call FN, passing it the DATA, for every node below NODE, all of
    which are from SP, following an in-order traversal.  If FN every
    returns a non-zero value, the iteration ceases immediately, and the

 		 	   		  

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]