Some GC marking inefficiency with chain_next and chain_prev

Some GC marking inefficiency with chain_next and chain_prev

[S. Bosscher]

Hi,

While investigating why marking for GC takes up much more time
for tree-ssa than for mainline, I noticed this cute piece of
inefficiency in gtype-desc.c:

void
gt_ggc_mx_tree_statement_list_node (void *x_p)
{
  struct tree_statement_list_node * x = (struct tree_statement_list_node
*)x_p;
  struct tree_statement_list_node * xlimit = x;
  while (ggc_test_and_set_mark (xlimit))
   xlimit = ((*xlimit).next);
  if (x != xlimit)
    for (;;)
      {
        struct tree_statement_list_node * const xprev = ((*x).prev);
        if (xprev == NULL) break;
        x = xprev;
        (void) ggc_test_and_set_mark (xprev);
      }
  while (x != xlimit)
    {
      gt_ggc_m_24tree_statement_list_node ((*x).prev);
      gt_ggc_m_24tree_statement_list_node ((*x).next);
      gt_ggc_m_9tree_node ((*x).stmt);
      x = ((*x).next);
    }
}

where in gtype-desc.h the field marked is defined as:

#define gt_ggc_m_24tree_statement_list_node(X) do { \
  if (X != NULL) gt_ggc_mx_tree_statement_list_node (X);\
  } while (0)

Recall the definition of a STATEMENT_LIST node:
struct tree_statement_list_node
  GTY ((chain_next ("%h.next"), chain_prev ("%h.prev")))
{
  struct tree_statement_list_node *prev;
  struct tree_statement_list_node *next;
  tree stmt;
};

In other words, first we go over the next and prev chains because
of the GTY markers "chain_next" and "chain_prev".  Then we look
at those fields again in the loop, calling ggc_set_mark() on the
prev and next fields again, but this has no effect since we've
already marked them.

We seem to do this for every struct that has a "chain_next" and
"chain_prev" GTY marker.  The effect is that we call ggc_set_mark
twice for a field that is also used in one of those markers.  This
happens on mainline at least for cgraph_edges, and on the tree-ssa
branch also for edges, basic_blocks, and tree_stmt_lists.  These
calls are completely redundant, but they do cause some (probably
non-negligible) call overhead.

I don't know gengtype.c well enough to propose a fix, but it seems
that we could save ourselves a few ggc_set_mark calls if someone
can fix this.

Gr.
Steven


P.S. ggc_test_and_set_mark is testing every pointer for "(void *) 0"
and "(void *) 1".  Most of these checks are also redundant, perhaps
we can avoid some of these checks if they're somehow moved into
gengtype...

Re: Some GC marking inefficiency with chain_next and chain_prev

[Geoffrey Keating]

On 10/12/2003, at 3:21 AM, S. Bosscher wrote:

> In other words, first we go over the next and prev chains because
> of the GTY markers "chain_next" and "chain_prev".  Then we look
> at those fields again in the loop, calling ggc_set_mark() on the
> prev and next fields again, but this has no effect since we've
> already marked them.

I noticed this when these options were implemented, but I couldn't see 
an easy to fix it without parsing the arguments to chain_next and 
chain_prev and knowing a lot about structure layout.  It's not a 
significant cost, since the data will already be in cache.

If you don't need chain_prev and chain_next, you shouldn't use them.  
When I tried automatically putting chain_next on every structure that 
looked like it could use it (*with* the improvement you suggest above, 
since if it's automatic you know which field doesn't need marking), GC 
slowed down measurably.