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

[Aditya K <hiraditya at msn dot com>]

----------------------------------------
> Date: Mon, 9 Mar 2015 15:26:26 -0400
> From: tbsaunde@tbsaunde.org
> To: gcc@gcc.gnu.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?)
>
> Trev
>

 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.

 -Aditya

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