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

Ciao!
Steven


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