public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug c++/22635] New: OVERLOAD should not be a linked list of trees
@ 2005-07-23 20:32 pinskia at gcc dot gnu dot org
2005-07-23 22:14 ` [Bug c++/22635] " pinskia at gcc dot gnu dot org
` (9 more replies)
0 siblings, 10 replies; 12+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2005-07-23 20:32 UTC (permalink / raw)
To: gcc-bugs
I noticed this when looking at compile time / memory usage of PR 8361 and I noticed that OVERLOAD is
currently a link list and we only use about 2 of the fields in the tree which seems like a waste for a full
tree. I started to change it to be a VEC but ran into problems as it looks like we can be in the middle of
the linked list but I did not check for sure.
--
Summary: OVERLOAD should not be a linked list of trees
Product: gcc
Version: 4.1.0
Status: UNCONFIRMED
Keywords: memory-hog, compile-time-hog
Severity: enhancement
Priority: P2
Component: c++
AssignedTo: unassigned at gcc dot gnu dot org
ReportedBy: pinskia at gcc dot gnu dot org
CC: gcc-bugs at gcc dot gnu dot org
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=22635
^ permalink raw reply [flat|nested] 12+ messages in thread
* [Bug c++/22635] OVERLOAD should not be a linked list of trees
2005-07-23 20:32 [Bug c++/22635] New: OVERLOAD should not be a linked list of trees pinskia at gcc dot gnu dot org
@ 2005-07-23 22:14 ` pinskia at gcc dot gnu dot org
2005-07-23 22:33 ` pinskia at gcc dot gnu dot org
` (8 subsequent siblings)
9 siblings, 0 replies; 12+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2005-07-23 22:14 UTC (permalink / raw)
To: gcc-bugs
--
What |Removed |Added
----------------------------------------------------------------------------
OtherBugsDependingO| |12850
nThis| |
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=22635
^ permalink raw reply [flat|nested] 12+ messages in thread
* [Bug c++/22635] OVERLOAD should not be a linked list of trees
2005-07-23 20:32 [Bug c++/22635] New: OVERLOAD should not be a linked list of trees pinskia at gcc dot gnu dot org
2005-07-23 22:14 ` [Bug c++/22635] " pinskia at gcc dot gnu dot org
@ 2005-07-23 22:33 ` pinskia at gcc dot gnu dot org
2005-07-23 22:42 ` pinskia at gcc dot gnu dot org
` (7 subsequent siblings)
9 siblings, 0 replies; 12+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2005-07-23 22:33 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From pinskia at gcc dot gnu dot org 2005-07-23 22:32 -------
I added some stats to when chaining to the ovl and got the following interesting result for PR 12850:
average OVL length: 57.498998
So we have an average length of 57 which is long and shows that we are taking too much memory
because of this.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=22635
^ permalink raw reply [flat|nested] 12+ messages in thread
* [Bug c++/22635] OVERLOAD should not be a linked list of trees
2005-07-23 20:32 [Bug c++/22635] New: OVERLOAD should not be a linked list of trees pinskia at gcc dot gnu dot org
2005-07-23 22:14 ` [Bug c++/22635] " pinskia at gcc dot gnu dot org
2005-07-23 22:33 ` pinskia at gcc dot gnu dot org
@ 2005-07-23 22:42 ` pinskia at gcc dot gnu dot org
2005-07-23 22:45 ` pinskia at gcc dot gnu dot org
` (6 subsequent siblings)
9 siblings, 0 replies; 12+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2005-07-23 22:42 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From pinskia at gcc dot gnu dot org 2005-07-23 22:35 -------
8361 also have simular interesting results:
average OVL length: 44.709989
But I think my counting is wrong as we can have DECL in the chain.
--
What |Removed |Added
----------------------------------------------------------------------------
OtherBugsDependingO| |8361
nThis| |
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=22635
^ permalink raw reply [flat|nested] 12+ messages in thread
* [Bug c++/22635] OVERLOAD should not be a linked list of trees
2005-07-23 20:32 [Bug c++/22635] New: OVERLOAD should not be a linked list of trees pinskia at gcc dot gnu dot org
` (2 preceding siblings ...)
2005-07-23 22:42 ` pinskia at gcc dot gnu dot org
@ 2005-07-23 22:45 ` pinskia at gcc dot gnu dot org
2005-07-24 3:36 ` gdr at integrable-solutions dot net
` (5 subsequent siblings)
9 siblings, 0 replies; 12+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2005-07-23 22:45 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From pinskia at gcc dot gnu dot org 2005-07-23 22:44 -------
Though fixing that still gives the same number.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=22635
^ permalink raw reply [flat|nested] 12+ messages in thread
* [Bug c++/22635] OVERLOAD should not be a linked list of trees
2005-07-23 20:32 [Bug c++/22635] New: OVERLOAD should not be a linked list of trees pinskia at gcc dot gnu dot org
` (3 preceding siblings ...)
2005-07-23 22:45 ` pinskia at gcc dot gnu dot org
@ 2005-07-24 3:36 ` gdr at integrable-solutions dot net
2005-07-24 6:28 ` bangerth at dealii dot org
` (4 subsequent siblings)
9 siblings, 0 replies; 12+ messages in thread
From: gdr at integrable-solutions dot net @ 2005-07-24 3:36 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From gdr at integrable-solutions dot net 2005-07-24 03:32 -------
Subject: Re: New: OVERLOAD should not be a linked list of trees
"pinskia at gcc dot gnu dot org" <gcc-bugzilla@gcc.gnu.org> writes:
| I noticed this when looking at compile time / memory usage of PR
| 8361 and I noticed that OVERLOAD is
| currently a link list and we only use about 2 of the fields in the
| tree which seems like a waste for a full
| tree. I started to change it to be a VEC but ran into problems as
| it looks like we can be in the middle of the linked list but I did
| not check for sure.
A VEC is good for collections that do not expand often -- like temlate
parameter list after parsing, or member functions after class definition.
Consequently a vector is not a good use for reprensenting overload
sets in C++ -- they are dynamic entities that grow as the translation
unit is being compiled.
Getting rid of TREE_LIST does not necessarily mean mechanical
replacement with a VEC.
A plain single linked list should be sufficient.
-- Gaby
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=22635
^ permalink raw reply [flat|nested] 12+ messages in thread
* [Bug c++/22635] OVERLOAD should not be a linked list of trees
2005-07-23 20:32 [Bug c++/22635] New: OVERLOAD should not be a linked list of trees pinskia at gcc dot gnu dot org
` (4 preceding siblings ...)
2005-07-24 3:36 ` gdr at integrable-solutions dot net
@ 2005-07-24 6:28 ` bangerth at dealii dot org
2005-07-24 6:50 ` pinskia at gcc dot gnu dot org
` (3 subsequent siblings)
9 siblings, 0 replies; 12+ messages in thread
From: bangerth at dealii dot org @ 2005-07-24 6:28 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From bangerth at dealii dot org 2005-07-24 04:59 -------
I would imagine that in real world, there are either a rather small number
of overloads of a name (less than five) or very many (more than 20 or 30).
Most code I've seen don't use many overloads (falling into the first class)
but there are a few cases in libstdc++, especially in the streams and strings
libraries, that use very many overloads. I don't know if knowledge of such
overload set size statistics help any in finding an appropriate data
structure,
though...
W.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=22635
^ permalink raw reply [flat|nested] 12+ messages in thread
* [Bug c++/22635] OVERLOAD should not be a linked list of trees
2005-07-23 20:32 [Bug c++/22635] New: OVERLOAD should not be a linked list of trees pinskia at gcc dot gnu dot org
` (5 preceding siblings ...)
2005-07-24 6:28 ` bangerth at dealii dot org
@ 2005-07-24 6:50 ` pinskia at gcc dot gnu dot org
2005-07-24 13:16 ` giovannibajo at libero dot it
` (2 subsequent siblings)
9 siblings, 0 replies; 12+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2005-07-24 6:50 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From pinskia at gcc dot gnu dot org 2005-07-24 06:28 -------
If you look at both PR 8361 and 12850, they average both more than 40 Overloadeds. Those are both
real code so I don't know why people think this is stupid. Also linked lists especially with extra
locations still available is stupid. Look OVERLOAD only takes at max a pointer and boolean. The type is
shared.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=22635
^ permalink raw reply [flat|nested] 12+ messages in thread
* [Bug c++/22635] OVERLOAD should not be a linked list of trees
2005-07-23 20:32 [Bug c++/22635] New: OVERLOAD should not be a linked list of trees pinskia at gcc dot gnu dot org
` (6 preceding siblings ...)
2005-07-24 6:50 ` pinskia at gcc dot gnu dot org
@ 2005-07-24 13:16 ` giovannibajo at libero dot it
2005-07-24 13:25 ` pinskia at gcc dot gnu dot org
2005-08-06 6:47 ` pinskia at gcc dot gnu dot org
9 siblings, 0 replies; 12+ messages in thread
From: giovannibajo at libero dot it @ 2005-07-24 13:16 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From giovannibajo at libero dot it 2005-07-24 12:40 -------
Can you measure how much memory do all the overload nodes take in the big
testcases? Theoretically, an OVERLOAD could measure 8 bytes or so (on 32 bit
systems). So we currently waste more than 100 bytes per each node, but if there
are not so many of them it is not important.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=22635
^ permalink raw reply [flat|nested] 12+ messages in thread
* [Bug c++/22635] OVERLOAD should not be a linked list of trees
2005-07-23 20:32 [Bug c++/22635] New: OVERLOAD should not be a linked list of trees pinskia at gcc dot gnu dot org
` (7 preceding siblings ...)
2005-07-24 13:16 ` giovannibajo at libero dot it
@ 2005-07-24 13:25 ` pinskia at gcc dot gnu dot org
2005-08-06 6:47 ` pinskia at gcc dot gnu dot org
9 siblings, 0 replies; 12+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2005-07-24 13:25 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From pinskia at gcc dot gnu dot org 2005-07-24 13:23 -------
PR 12850 has the numbers.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=22635
^ permalink raw reply [flat|nested] 12+ messages in thread
* [Bug c++/22635] OVERLOAD should not be a linked list of trees
2005-07-23 20:32 [Bug c++/22635] New: OVERLOAD should not be a linked list of trees pinskia at gcc dot gnu dot org
` (8 preceding siblings ...)
2005-07-24 13:25 ` pinskia at gcc dot gnu dot org
@ 2005-08-06 6:47 ` pinskia at gcc dot gnu dot org
9 siblings, 0 replies; 12+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2005-08-06 6:47 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From pinskia at gcc dot gnu dot org 2005-08-06 06:47 -------
Confirmed.
--
What |Removed |Added
----------------------------------------------------------------------------
Status|UNCONFIRMED |NEW
Ever Confirmed| |1
Last reconfirmed|0000-00-00 00:00:00 |2005-08-06 06:47:46
date| |
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=22635
^ permalink raw reply [flat|nested] 12+ messages in thread
* [Bug c++/22635] OVERLOAD should not be a linked list of trees
[not found] <bug-22635-6528@http.gcc.gnu.org/bugzilla/>
@ 2009-02-22 14:01 ` steven at gcc dot gnu dot org
0 siblings, 0 replies; 12+ messages in thread
From: steven at gcc dot gnu dot org @ 2009-02-22 14:01 UTC (permalink / raw)
To: gcc-bugs
------- Comment #10 from steven at gcc dot gnu dot org 2009-02-22 14:01 -------
Trees were refactored, and we currently have:
struct tree_base
{
ENUM_BITFIELD(tree_code) code : 16;
/* 48 bits for various bitfield flags */
union tree_ann_d *ann;
} /* So on a 64-bit host this is 128bits = 16 bytes */
struct tree_common
{
struct tree_base; /* 16 bytes */
tree chain; /* 8 bytes */
tree type; /* 8 bytes */
} /* So on a 64-bit host, tree_common is 32 bytes */
struct tree_overload
{
struct tree_common; /* 32 bytes */
tree function; /* 8 bytes */
}
So in total 40 bytes per tree_overload. If a single linked list would really
be sufficient, then the ideal tree_overload would be 16 bytes (two pointers).
In reality, there are a few flags used on tree_overload, so two pointers is not
enough. Let's say we use 4 bytes for that. Then we have an overhead of
(40/(16+4))*100% = 100% overhead.
In any normal engineering project, 100% overhead would be reason for distress.
However, as long as the G++ front end are comfortable using trees instead of
front-end specific structures in the parser, we can't do any better at this
point. The overhead is much less than it was in the past. It was 3% before
the tree refactoring, so it will be much less now. And like Gaby already said:
If there are not so many of them (tree_overload objects) then it is not very
important (to squeeze out every last bit of overhead).
Therefore, closing as FIXED by Dan's refactoring.
--
steven at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
Status|NEW |RESOLVED
Resolution| |FIXED
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=22635
^ permalink raw reply [flat|nested] 12+ messages in thread
end of thread, other threads:[~2009-02-22 14:01 UTC | newest]
Thread overview: 12+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2005-07-23 20:32 [Bug c++/22635] New: OVERLOAD should not be a linked list of trees pinskia at gcc dot gnu dot org
2005-07-23 22:14 ` [Bug c++/22635] " pinskia at gcc dot gnu dot org
2005-07-23 22:33 ` pinskia at gcc dot gnu dot org
2005-07-23 22:42 ` pinskia at gcc dot gnu dot org
2005-07-23 22:45 ` pinskia at gcc dot gnu dot org
2005-07-24 3:36 ` gdr at integrable-solutions dot net
2005-07-24 6:28 ` bangerth at dealii dot org
2005-07-24 6:50 ` pinskia at gcc dot gnu dot org
2005-07-24 13:16 ` giovannibajo at libero dot it
2005-07-24 13:25 ` pinskia at gcc dot gnu dot org
2005-08-06 6:47 ` pinskia at gcc dot gnu dot org
[not found] <bug-22635-6528@http.gcc.gnu.org/bugzilla/>
2009-02-22 14:01 ` steven at gcc dot gnu dot org
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).