This is the mail archive of the 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 <> wrote:
> On Mon, Mar 9, 2015 at 7:59 PM, vax mzn wrote:
>> w.r.t, 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.


> Ciao!
> Steven

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