On Mon, Mar 09, 2015 at 06:59:10PM +0000, 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.
So, this makes sense, but I've always wondered if it wouldn't make more sense to just use the red black tree in libstdc++ (or does it have a splay tree of its own too?) Trev > e.g., > In this exaple we are looking for a different `t' in each iteration. > > gcc/gimplify.c:1096: splay_tree_lookup (ctx->variables, (splay_tree_key) t) > == NULL) > > Here, we change the tree itself `ctx' > gcc/gimplify.c:5532: n = splay_tree_lookup (ctx->variables, > (splay_tree_key)decl); > > > I think we don't need to update the tree in these cases at least. > > > -Aditya >
