On 05/17/2015 06:23 PM, Aditya K wrote:
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.
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.
I have pasted the patch which removes splay_tree with hash_map. Another patch
(attached) removes splay_tree with std::map.
Please review the patches.
Thanks,
-Aditya
gcc/ChangeLog:
2015-05-17 hiraditya hiradi...@msn.com
Remove splay_tree from gimplify.c
* gimplify.c (struct gimplify_omp_ctx): Replaced splay_tree with
hash_map
(splay_tree_compare_decl_uid): Likewise
(new_omp_context): Likewise
(delete_omp_context): Likewise
(gimplify_bind_expr): Likewise
(omp_firstprivatize_variable): Likewise
(omp_add_variable): Likewise
(omp_notice_threadprivate_variable): Likewise
(omp_notice_variable): Likewise
(omp_is_private): Likewise
(omp_check_private): Likewise
(gimplify_adjust_omp_clauses_1): Likewise
(gimplify_adjust_omp_clauses): Likewise
(gimplify_omp_for): Likewise
* hash-map.h: Added typedefs.
So the question here is whether or not the other uses are commonly
looking up elements we've already searched for -- that's the whole
purpose of a splay tree, to improve lookup performance for commonly hit
items.
I believe most of this is Jakub's code, so he's probably in the best
position to comment on whether or not we're commonly looking up nodes
repeatedly in the tables. I don't think so at first glance, but I could
easily be wrong.
Aditya, have you done any benchmarking of this change? In theory, if
we're no longer doing the adjustments to the tree on lookups you should
be able to see/measure some kind of compile-time performance difference.
If it's too small to be measured, then one could argue there's really
no benefit in changing the implementation.
Given we've got a lot more hash_map usage than std::map, I'd suggest
going with hash_map if this patch moves forward -- if I had a better
feel for the data, access patterns, etc then I might make a suggestion
based on that, but I simply don't have that kind of insight on this code.
Jeff
