This is the mail archive of the
mailing list for the GCC project.
Proposal for adding splay_tree_find (to find elements without updating the nodes).
- From: vax mzn <hiraditya at msn dot com>
- To: "gcc at gcc dot gnu dot org" <gcc at gcc dot gnu dot org>
- Date: Mon, 9 Mar 2015 18:59:10 +0000
- Subject: Proposal for adding splay_tree_find (to find elements without updating the nodes).
- Authentication-results: sourceware.org; auth=none
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.
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.