This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Remove splay_tree from gimplify.c


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  <hiraditya@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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]