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: Richard Biener <richard dot guenther at gmail dot com>
- To: Steven Bosscher <stevenb dot gcc at gmail dot com>
- Cc: vax mzn <hiraditya at msn dot com>, "gcc at gcc dot gnu dot org" <gcc at gcc dot gnu dot org>
- Date: Tue, 10 Mar 2015 11:20:07 +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> <CABu31nMN2KajAC4LO=RBrmxG9gHapMJmWbBC=8i_i9RyieZ5pA at mail dot gmail dot com>
On Mon, Mar 9, 2015 at 11:59 PM, Steven Bosscher <firstname.lastname@example.org> 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.
>> 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.