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: Aditya K <hiraditya at msn dot com>
- To: "gcc at gcc dot gnu dot org" <gcc at gcc dot gnu dot org>
- Date: Mon, 9 Mar 2015 21:02:00 +0000
- 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>,<20150309192419 dot GA4286 at tsaunders-iceball dot corp dot tor1 dot mozilla dot com>
> Date: Mon, 9 Mar 2015 15:26:26 -0400
> From: email@example.com
> To: firstname.lastname@example.org
> Subject: 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?)
Red-black trees do have better cost of balancing, although at a cost of higher complexity.
I'm not sure if using red-black trees would improve the performance because I don't have any data to back.
>> 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.