On Mon, Mar 9, 2015 at 11:59 PM, Steven Bosscher <stevenb....@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
