----------------------------------------
> Date: Mon, 9 Mar 2015 15:26:26 -0400
> From: tbsau...@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
>>
