This is the mail archive of the
mailing list for the GCC project.
Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
- From: Steven Bosscher <stevenb dot gcc at gmail dot com>
- To: vax mzn <hiraditya at msn dot com>
- Cc: "gcc at gcc dot gnu dot org" <gcc at gcc dot gnu dot org>
- Date: Mon, 9 Mar 2015 23:59:52 +0100
- Subject: Re: Proposal for adding splay_tree_find (to find elements without updating the nodes).
- Authentication-results: sourceware.org; auth=none
- References: <BLU179-W40C136025D7BD569ABEE24B61B0 at phx dot gbl>
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.
> 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.