This is the mail archive of the
mailing list for the GCC project.
Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
- From: Trevor Saunders <tbsaunde at tbsaunde dot org>
- To: gcc at gcc dot gnu dot org
- Date: Mon, 9 Mar 2015 15:26:26 -0400
- Subject: Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
- Authentication-results: sourceware.org; auth=none
- References: <BLU179-W40C136025D7BD569ABEE24B61B0 at phx dot gbl>
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?)
> 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.