Types with power-of-two size in ggc-page.c extra_order_size_table[]

Types with power-of-two size in ggc-page.c extra_order_size_table[]

[Oliver Kellogg]

Hi,

Looking at ggc-page.c:175ff.,

static const size_t extra_order_size_table[] = {
  sizeof (struct var_ann_d),
  sizeof (struct tree_decl_non_common),
  sizeof (struct tree_field_decl),
  sizeof (struct tree_parm_decl),
  sizeof (struct tree_var_decl),
  sizeof (struct tree_list),
  sizeof (struct tree_ssa_name),
  sizeof (struct function),
  sizeof (struct basic_block_def),
  sizeof (bitmap_element),
  sizeof (bitmap_head),
  TREE_EXP_SIZE (2),
  RTL_SIZE (2),			/* MEM, PLUS, etc.  */
  RTL_SIZE (9),			/* INSN */
};

On my openSuSE-11.1 i686-pc-linux-gnu, sizeof (struct basic_block_def)
is 64 and sizeof (bitmap_head) is 16.
Why are these types entered into extra_order_size_table?

ggc-page.c (init_ggc):1567ff.
  for (order = HOST_BITS_PER_PTR; order < NUM_ORDERS; ++order)
    {
      int o;
      int i;

      i = OBJECT_SIZE (order);
      if (i >= NUM_SIZE_LOOKUP)
        continue;

      for (o = size_lookup[i]; o == size_lookup [i]; --i)
        size_lookup[i] = order;
    }

At order 42, OBJECT_SIZE returns 16 (from extra_order_size_table[10])
and size_lookup[16] down to [9] is changed to 42.
That seems strange to me, given the documentation of size_lookup[],

/* This table provides a fast way to determine ceil(log_2(size)) for
   allocation requests.  The minimum allocation size is eight bytes.  */


Thanks,

Oliver

Re: Types with power-of-two size in ggc-page.c extra_order_size_table[]

[Richard Guenther]

On Wed, Sep 16, 2009 at 12:39 AM, Oliver Kellogg
<oliver.kellogg@t-online.de> wrote:
> Hi,
>
> Looking at ggc-page.c:175ff.,
>
> static const size_t extra_order_size_table[] = {
>  sizeof (struct var_ann_d),
>  sizeof (struct tree_decl_non_common),
>  sizeof (struct tree_field_decl),
>  sizeof (struct tree_parm_decl),
>  sizeof (struct tree_var_decl),
>  sizeof (struct tree_list),
>  sizeof (struct tree_ssa_name),
>  sizeof (struct function),
>  sizeof (struct basic_block_def),
>  sizeof (bitmap_element),
>  sizeof (bitmap_head),
>  TREE_EXP_SIZE (2),
>  RTL_SIZE (2),                 /* MEM, PLUS, etc.  */
>  RTL_SIZE (9),                 /* INSN */
> };
>
> On my openSuSE-11.1 i686-pc-linux-gnu, sizeof (struct basic_block_def)
> is 64 and sizeof (bitmap_head) is 16.
> Why are these types entered into extra_order_size_table?

They likely changed in size and/or the 64bit host-wide-int variants are not
power-of-two sized.

>
> ggc-page.c (init_ggc):1567ff.
>  for (order = HOST_BITS_PER_PTR; order < NUM_ORDERS; ++order)
>    {
>      int o;
>      int i;
>
>      i = OBJECT_SIZE (order);
>      if (i >= NUM_SIZE_LOOKUP)
>        continue;
>
>      for (o = size_lookup[i]; o == size_lookup [i]; --i)
>        size_lookup[i] = order;
>    }
>
> At order 42, OBJECT_SIZE returns 16 (from extra_order_size_table[10])
> and size_lookup[16] down to [9] is changed to 42.
> That seems strange to me, given the documentation of size_lookup[],

I don't remember exactly but the last time I spent with the code it did
the right thing.  Giving more context might help to understand the problem
you are seeing.

Richard.

> /* This table provides a fast way to determine ceil(log_2(size)) for
>   allocation requests.  The minimum allocation size is eight bytes.  */
>
>
> Thanks,
>
> Oliver
>
>
>
>
>

Re: Types with power-of-two size in ggc-page.c extra_order_size_table[]

[Jan Hubicka]

> On Wed, Sep 16, 2009 at 12:39 AM, Oliver Kellogg
> <oliver.kellogg@t-online.de> wrote:
> > Hi,
> >
> > Looking at ggc-page.c:175ff.,
> >
> > static const size_t extra_order_size_table[] = {
> >  sizeof (struct var_ann_d),
> >  sizeof (struct tree_decl_non_common),
> >  sizeof (struct tree_field_decl),
> >  sizeof (struct tree_parm_decl),
> >  sizeof (struct tree_var_decl),
> >  sizeof (struct tree_list),
> >  sizeof (struct tree_ssa_name),
> >  sizeof (struct function),
> >  sizeof (struct basic_block_def),
> >  sizeof (bitmap_element),
> >  sizeof (bitmap_head),
> >  TREE_EXP_SIZE (2),
> >  RTL_SIZE (2),                 /* MEM, PLUS, etc.  */
> >  RTL_SIZE (9),                 /* INSN */
> > };
> >
> > On my openSuSE-11.1 i686-pc-linux-gnu, sizeof (struct basic_block_def)
> > is 64 and sizeof (bitmap_head) is 16.
> > Why are these types entered into extra_order_size_table?
> 
> They likely changed in size and/or the 64bit host-wide-int variants are not
> power-of-two sized.

If I remember right, I originally added those based on exploring the
memory report dumps looking for types causing largest overhead. So these
definitly wasn't power of two at that time.  We might try to re-do the
tunning by simply removing these and then compiling larger testcase with
-fmem-report and adding those with largest overhead.  But this would
have to be done both on 32bit and 64bit host at least.

Honza