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 9, 2015 at 11:59 PM, Steven Bosscher <stevenb.gcc@gmail.com> wrote:
> On Mon, Mar 9, 2015 at 7:59 PM, 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.
>> e.g.,
>> In this exaple we are looking for a different `t' in each iteration.
>
>
> If that's really true, then a splay tree is a horrible choice of data
> structure. The splay tree will simply degenerate to a linked list. The
> right thing to do would be, not to "break" one of the key features of
> splay trees (i.e. the latest lookup is always on top), but to use
> another data structure.

I agree with Steven here and wanted to say the same.  If you don't
benefit from splay trees LRU scheme then use a different data structure.

Richard.

> Ciao!
> Steven


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