* cutting the size of CONST_DECLs
@ 2004-02-28 0:21 Robert Bowdidge
2004-02-28 1:09 ` Dan Nicolaescu
0 siblings, 1 reply; 3+ messages in thread
From: Robert Bowdidge @ 2004-02-28 0:21 UTC (permalink / raw)
To: gcc; +Cc: 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
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: cutting the size of CONST_DECLs
2004-02-28 0:21 cutting the size of CONST_DECLs Robert Bowdidge
@ 2004-02-28 1:09 ` Dan Nicolaescu
2004-02-28 2:38 ` Robert Bowdidge
0 siblings, 1 reply; 3+ messages in thread
From: Dan Nicolaescu @ 2004-02-28 1:09 UTC (permalink / raw)
To: Robert Bowdidge; +Cc: gcc
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.
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: cutting the size of CONST_DECLs
2004-02-28 1:09 ` Dan Nicolaescu
@ 2004-02-28 2:38 ` Robert Bowdidge
0 siblings, 0 replies; 3+ messages in thread
From: Robert Bowdidge @ 2004-02-28 2:38 UTC (permalink / raw)
To: Dan Nicolaescu; +Cc: gcc, 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
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2004-02-28 1:09 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2004-02-28 0:21 cutting the size of CONST_DECLs Robert Bowdidge
2004-02-28 1:09 ` Dan Nicolaescu
2004-02-28 2:38 ` Robert Bowdidge
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).