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

[Trevor Saunders <tbsaunde at tbsaunde dot org>]

On Mon, Mar 09, 2015 at 06:59:10PM +0000, 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.

So, this makes sense, but I've always wondered if it wouldn't make more
sense to just use the red black tree in libstdc++ (or does it have a
splay tree of its own too?)

Trev

> e.g.,
> In this exaple we are looking for a different `t' in each iteration.
> 
> gcc/gimplify.c:1096: splay_tree_lookup (ctx->variables, (splay_tree_key) t) == NULL)
> 
> Here, we change the tree itself `ctx'
> gcc/gimplify.c:5532: n = splay_tree_lookup (ctx->variables, (splay_tree_key)decl);
> 
> 
> I think we don't need to update the tree in these cases at least.
> 
> 
> -Aditya
>