cutting the size of CONST_DECLs

cutting the size of CONST_DECLs

[Robert Bowdidge]

Hi, all,

At Apple, the compiler's memory use (and its effect on compile speed) 
is our biggest concern.  One specific worry is declarations.  On common 
Mac programs which include headers for our GUI libraries, declarations 
fill a significant amount of garbage-collected memory.  With 
-fmem-report, we usually see about 35% of memory filled with 
declarations.
CONST_DECLs are an obvious offender in our programs; many of the Mac 
headers make heavy use of enums to define symbolic constants.   In some 
programs, CONST_DECLS are the third most common kind of declaration 
after FUNCTION_DECL and PARM_DECL, and can be responsible for 30% of 
declarations and 10% of gc'd memory.

I've tried one change to cut memory use: creating a new, smaller 
structure for CONST_DECLs only, and having all other declarations 
inherit this structure and extend it with the rest of the fields.  On a 
couple typical applications, this change cuts memory use by 4-6% and 
compilation time by 0-3%.

I'm interested in hearing whether others believe such a data structure 
change would be appropriate in gcc, and whether similar tricks could be 
done in other parts of gcc.

The changes would look something like the following:

struct tree_super_decl {
   struct tree_common common;
   /* fields needed by CONST_DECL only */
  ...
}

struct tree_decl {
   struct tree_super_decl super_decl;
   /* Fields needed by all other declarations */
   ...
}

Parse tree nodes using the tree_super_decl as their structure have a 
different size from other declarations, so the nodes get a new tree 
code class ('D' rather than 'd')  Macros accessing fields in 
tree_super_decl now just need to be changed slightly:

#define DECL_NAME(x)  (DECL_CHECK(x)->decl.name)
becomes
#define DECL_NAME(x) (SUPER_DECL_CHECK(x)->super_decl.name)

In addition, DECL_P() would need to be changed to recognize both 'D' 
and 'd' as classes.  Case statements switching on the tree code class 
would need the new class added.

Similar approaches have been proposed in the past; the difference is 
that we're focusing on specific kinds of declarations, and we've seen 
measurable differences in real code.  Dan Nicolaescu proposed a similar 
scheme in February 2003 to take fields only used by FUNCTION_DECL out 
of the tree_decl structure:

http://gcc.gnu.org/ml/gcc/2003-02/msg00587.html

Carlo Wood also suggested similar ideas for tree_expr, though he 
proposed extending tree_expr for CALL_EXPR nodes only:
http://gcc.gnu.org/ml/gcc/2003-10/msg00170.html

Advantages:

* Cuts the size of CONST_DECL.  On 3.3, I've been able to get 
CONST_DECL down to 72 bytes as compared to 116 bytes.  More shrinking 
may be possible by figuring out which field accesses on CONST_DECLs are 
accidental or pointless.

* The same technique could be used to shrink other declarations: 
PARM_DECL, TYPE_DECL, and RESULT_DECL all appear to use a subset of the 
tree_decl fields.  All three can be shrunk to 100 bytes with no 
changes.

* The change doesn't change tree.h much, and appears only to require 
minor fixes elsewhere in the gcc sources: some changes in the tree 
allocation code, adding additional case statements or if clauses when 
the tree class code is checked explicitly for 'd', changing the 
DECL_P() to detect both kinds of declaration structures.

Disadvantages:

* All the bit field and flag variables should be placed in the 
"tree_super_decl" field to avoid structure size growth due to padding.

* Deciding which fields should be in the "small" declaration requires a 
combination of knowledge of the gcc code and runtime tracing to figure 
out which fields in a declaration are used for constants.  I chose the 
functions by instrumenting the accessor macros to record references to 
the different variables over several runs, then did more compiles with 
"--enable-checking" on to catch the last few stragglers.  There's 
always a chance that some bit of code deep in the compiler accesses a 
small declaration in the large sense; the only way to catch these is 
with --enable-checking.

* Similarly, bug fixes made after changes to the data structure could 
add cases where fields not available in a particular declaration; 
again, these will only get caught by runtime checks.  This may be a 
good thing; once folks are worrying much more about what sort of 
declaration they may reference, it may encourage more care about which 
fields are truly needed for each type of declaration.

I'm not sure there's any good way to statically identify the spots 
where constant declarations may be accessed.  Although we could use 
something like the Stanford MC checker to propagage potential types 
through function calls and if clauses; I'd guess we'd still get bitten 
by cases where we couldn't prove a declaration might never be a 
constant declaration.  So far, tracking down the last few stragglers by 
turning on --enable-checking and passing lots of code through the 
compiler seemed pretty quick.  I'd feel even more confident by building 
all of Apple's sources with an instrumented compiler; the only 
remaining issues would be port-specific field access patterns.

Comments?

Robert

Re: cutting the size of CONST_DECLs

[Dan Nicolaescu]

Robert Bowdidge <bowdidge@apple.com> writes:

  > Hi, all,
>
  > At Apple, the compiler's memory use (and its effect on compile speed)
  > is our biggest concern.  One specific worry is declarations.  On
  > common Mac programs which include headers for our GUI libraries,
  > declarations fill a significant amount of garbage-collected memory.
  > With -fmem-report, we usually see about 35% of memory filled with
  > declarations.
  > CONST_DECLs are an obvious offender in our programs; many of the Mac
  > headers make heavy use of enums to define symbolic constants.   In
  > some programs, CONST_DECLS are the third most common kind of
  > declaration after FUNCTION_DECL and PARM_DECL, and can be responsible
  > for 30% of declarations and 10% of gc'd memory.
>
  > I've tried one change to cut memory use: creating a new, smaller
  > structure for CONST_DECLs only, and having all other declarations
  > inherit this structure and extend it with the rest of the fields.  On
  > a couple typical applications, this change cuts memory use by 4-6% and
  > compilation time by 0-3%.

You might also want to look at doing something about FUNCTION_DECLs. There are
a few  fields in struct tree_decl that are only used for
FUNCTION_DECLs: inlined_fns, saved_tree. If you somehow reorganize 
struct tree_decl and manage to leave these fields out for everything
but FUNCTION_DECLs you will get some memory savings. 
Also "vindex" is only used for languages that use inheritance, so it
is useless for C. Moving "vindex" to "lang_specific" might be
interesting too. 

        

Re: cutting the size of CONST_DECLs

[Robert Bowdidge]

On Feb 27, 2004, at 4:20 PM, Dan Nicolaescu wrote:
> You might also want to look at doing something about FUNCTION_DECLs. 
> There are
> a few  fields in struct tree_decl that are only used for
> FUNCTION_DECLs: inlined_fns, saved_tree.

Yep, separating FUNCTION_DECLs from everything else would definitely 
help. One problem is that function declarations aren't the most common 
node we see when parsing our headers; in my examples, FUNCTION_DECLs 
were only 14-20% of declarations.  PARM_DECLs were usually 33-36% of 
declarations, so separating them out makes twice the difference.

Here's the distributions of declaration kinds I saw on some example 
compiles:

		PARAM	FN		CONST	TYPE	FIELD	VAR
FinderFE	30%		29%		24%		16%		?		?
gcc		30%		34%		10%		3%		21%		3%
rogue	27%		59%		0%		5%		9%		5%
AppearanceSample
		36%		20%		18%		16%		7%		0%
SimpleText
		33%		14%		28%		13%		11%		4%

Each represents declaration kinds found during compile of a 
representative file.  FinderFE is the C++ front end to the Mac OS 
Finder.  Appearance Sample and SimpleText are two GUI applications from 
Apple's sample code; AppearanceSample is C++, and SimpleText C.

One possibility I've strongly considered is to have three levels of 
declarations:

small: CONST_DECL
medium: PARM_DECL, TYPE_DECL,FIELD_DECL
large: FN_DECL, VAR_DECL

On 3.3, small declarations to 72 bytes, medium declarations 100 bytes, 
and large declarations 116 bytes.    I've done a few measurements with 
this set of objects; memory use and compile times improve again from 
the CONST_DECL/everything else scheme, though the memory improvements 
are still in the <10% ballpark, and compile time improvements are much 
smaller.  I still need to do more measurements on non-Apple source 
code, and double-check that the changes aren't slowing the compiler.

Adding different kinds of declarations adds a bit of overhead, so we 
don't want to take this too far.  At a minimum, the DECL_P() macro 
needs to do more work to decide if a given node is a declaration.  On a 
stock system, this is a single comparison: is the tree code class 'd'?  
With three kinds of declarations, I could make the tree code classes 
'd', 'D', and '$'.  With these characters, the test in DECL_P() can use 
a bitmask to see if (tree_code & 0x1f) == 0x04 rather than doing three 
comparisons.

Deciding which kinds of declarations behave similarly can be difficult 
from just the table of access patterns.  I ended up using concept 
analysis to identify likely hierarchies.  (Snelting and Tip, 
"Understanding Class Hierarchies using Concept Analysis", ACM 
Transactions on Programming Languages and Systems 22(3), May 2000).  
There's a tool available on Sourceforge ("conexp") to draw an optimized 
class hierarchy (well, a concept lattice) given a set of objects and 
properties.  The three-level scheme pretty much fell out once I looked 
at the lattice.

Robert