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).


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
>  		 	   		  


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