[rfa] libiberty: splay tree performance improvement

["Frank Ch. Eigler" <fche at redhat dot com>]

Hi -

The following patch tweaks the logic of the libiberty splay-tree
routines in order to accelerate an access pattern that is common
in libmudflap.  Repeated searching for the neighbourhood of a key
value that is not in the tree causes repeated splaying (sort of
sorting) that just needlessly perturbs the tree.  This patch aims
to avoid a subsequent splay operation when one was just done with
the same key.

The changes give about a further 10% speedup on the pointer-happy 
libmudflap benchmark from last week, and a very slight speedup
with gcc optimizers running over various test cases.  Bootstrapped
on x86.

May I commit?

- FChE


Index: libiberty/ChangeLog
+2004-06-28  Frank Ch. Eigler  <fche@redhat.com>
+
+	Add splay key caching.
+	* splay-tree.c (splay_tree_splay): Avoid repeated splaying
+	tree with identical key.
+	(splay_tree_new_with_allocator): Clear cache.
+	(splay_tree_insert, splay_tree_remove): Ditto.

Index: include/ChangeLog
+2004-06-28  Frank Ch. Eigler  <fche@redhat.com>
+
+	* splay-tree.h (splay_tree_s): Add fields for splay key caching.
+

Index: libiberty/splay-tree.c
===================================================================
RCS file: /cvs/gcc/gcc/libiberty/splay-tree.c,v
retrieving revision 1.23
diff -u -p -r1.23 splay-tree.c
--- libiberty/splay-tree.c	7 May 2003 18:19:36 -0000	1.23
+++ libiberty/splay-tree.c	28 Jun 2004 19:56:08 -0000
@@ -195,8 +195,17 @@ splay_tree_splay (sp, key)
   if (sp->root == 0)
     return;
 
+  /* If we just splayed the tree with the same key, do nothing.  */
+  if (sp->last_splayed_key_p &&
+      (*sp->comp)(sp->last_splayed_key, key) == 0)
+    return;
+
   splay_tree_splay_helper (sp, key, &sp->root, 
 			   /*grandparent=*/0, /*parent=*/0); 
+
+  /* Cache this splay key. */
+  sp->last_splayed_key = key;
+  sp->last_splayed_key_p = 1;
 }
 
 /* Call FN, passing it the DATA, for every node below NODE, all of
@@ -286,6 +295,7 @@ splay_tree_new_with_allocator (compare_f
   sp->allocate = allocate_fn;
   sp->deallocate = deallocate_fn;
   sp->allocate_data = allocate_data;
+  sp->last_splayed_key_p = 0;
 
   return sp;
 }
@@ -313,6 +323,7 @@ splay_tree_insert (sp, key, value)
   int comparison = 0;
 
   splay_tree_splay (sp, key);
+  sp->last_splayed_key_p = 0;
 
   if (sp->root)
     comparison = (*sp->comp)(sp->root->key, key);
@@ -365,6 +376,7 @@ splay_tree_remove (sp, key)
      splay_tree_key key;
 {
   splay_tree_splay (sp, key);
+  sp->last_splayed_key_p = 0;
 
   if (sp->root && (*sp->comp) (sp->root->key, key) == 0)
     {


Index: include/splay-tree.h
===================================================================
RCS file: /cvs/gcc/gcc/include/splay-tree.h,v
retrieving revision 1.19
diff -u -p -r1.19 splay-tree.h
--- include/splay-tree.h	30 Mar 2004 19:23:16 -0000	1.19
+++ include/splay-tree.h	28 Jun 2004 19:56:09 -0000
@@ -97,6 +97,11 @@ struct splay_tree_s GTY(())
   /* The root of the tree.  */
   splay_tree_node GTY ((use_params)) root;
 
+  /* The last key value for which the tree has been splayed, but not
+     since modified.  */
+  splay_tree_key GTY ((use_param1)) last_splayed_key;
+  int last_splayed_key_p;
+
   /* The comparision function.  */
   splay_tree_compare_fn comp;