Varray memory consumption strikes back

[Jan Hubicka]

> On Sat, 2004-09-04 at 03:59, Jan Hubicka wrote:
> > and the proposed patch to make varrays allocatable either in GGC and
> > memory flag has been rejected and you mentioned to have better sollution
> > in prototype stage (moving away from varrays to sane datastructures and
> > improving them at the same time).
> Well, I haven't had time to pick it up, but it wouldn't be terribly
> hard for you to do so.  I would prefer reducing the amount of
> varrays we carry around as opposed to bypassing our memory allocation
> system design.

Yes, this is my prefference too and I did some work on this already too.
However it is depressing to see that the amount of varrays in the code
is increasing very quickly and consistently.

> 
> The first step is already done (by Diego), specifically we needed a
> formal SSA_NAME table.  As I said, this is already done.

Agreed.
> 
> What needs to happen now is to expand that simple table of SSA_NAMEs
> to be a table of SSA_NAMEs and their global properties (for example
> their equivalences and nonzero status indicators).

How this is different from putting this directly into SSA_NAMEs?
> 
> Once you do that, the const_and_copies global varray disappears. 
> 
> The second (closely related change) is that value range propagation
> (currently under development by Diego) needs to replace the very
> limited form we have in dom, which causes the VRP_DATA varray to
> totally disappear, along with the VRP_VARIABLES varray.  Again,
> this range information needs to be stored in the SSA_NAME table
> so that we don't just punt the problem into CCP.
> 
> [ Note that both CONST_AND_COPIES and VRP_DATA are grown as the
>   number of SSA_NAMEs grow, which can lead to significant
>   over-usage of varray space. ]

This is actually not included in the statistics, at least not in the
VARRAY kind block that just take optimistic estimation that varray takes
as much memory as is the maximal amount of elements in it.
> 
> There's more that can be done, but kililng those two global varrays
> would be a huge step forward and it's not a huge amount of work.

Looking on the top memory consumers (more than 1MB):

VARRAY Kind            Count      Bytes  Resized copied
-------------------------------------------------------
immediate_uses        254956   43235680  144954  144954
block_defs             28179   19576768   30032   30032
const_and_copies        1002   10140376      34       2
vrp_data                1002   10140376      34       2
ssa_names table          334    6489088    1074    1074
block_const_and_copies  7947    5335568   28111   28111
stack                  28523    3214692       0       0
block_avail_exprs       8800    1815520     719     719
aliases                26707    1772144   10223   10223
num_references          1002    1444588     523      92
processed_ptrs          1002    1358064     949     949
ib_boundaries_block      334    1381888     489     489
referenced_vars          334    1580128    1177    1177
work list               1336    1155840     517     517
current_lang_base      10355    1159760       0       0
stmts_to_rescan         5213    1094816     524     524

What you suggest here (and what is definitly good thing to do) will kill
constn_and_copies, vrp_data and replace them with presumably array-alike
ssa_names table.  These two arrays together are rougly 8% of overall
memory consumed by varrays and I would be surprised that the increased
ssa names would be terribly smaller.

I think we need to look the problem from the other side.

At least I do have dificulty to find examples of datastructures where
using dynamically sized arrays actually makes sense and even fewer
examples where using garbage collection help something.  They works as
all kind of stacks, worklists, queues mostly local with well defined
lifetimes.

I would say that we need way to make use of such datastructures cheaper
as current varray overhead is killing us.

As you pointed out in the earlier mails in January, the actual
percentage of places where we do need growing bounds checked garbage
allocated array is tiny.

We probably ought to have convenient way to do stacks - apparently
people (including me) preffer varrays instead of obstacks just because
the API is friendlier.
> 
> I can't emphasize enough how bad I think it would be to make
> varrays allocable in multiple memory regions.

I still think that for local data with obvious lifetimes (the case of
majority varrays in the list above) we should not use GGC.  It is both
faster and safer as we get sanity checking.

If you don't like varrays in the normal memory, would turning the
stack-like datastructures above to obstacks (or newly invented
friendlier stack datastructure perhaps with fixed object size)
and array-like datastructures to simple C arrays (where we would lose
bounds checking) or newly invented bound checked arrays without growing
facility make any sense to you?

If not (and under assumption that there is already plan for
immediate_uses, const_and_copies and vrp_data) what would you suggest
for block_defs, block_const_and_copies, block_avail_exprs, aliases,
num_references and friends?

Honza
> 
> jeff
>