public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug target/18927] New: O(n^2) compile time with -O0 (n= number of basic blocks) in global alloc
@ 2004-12-10 15:43 heinrich dot brand at fujitsu-siemens dot com
2004-12-10 16:05 ` [Bug middle-end/18927] " pinskia at gcc dot gnu dot org
` (5 more replies)
0 siblings, 6 replies; 9+ messages in thread
From: heinrich dot brand at fujitsu-siemens dot com @ 2004-12-10 15:43 UTC (permalink / raw)
To: gcc-bugs
Some C-Code is (with Option -O0) processed by an algorithm with O(n^2) time.
This simple code scheme shows that the compile time grows fast with
the number of basic blocks in a function. If the number of
basic blocks is doubled the compile time is almost quadrupled.
The output of -ftime-report shows that global alloc uses most of the time.
But C-Code with a small difference has roughly O(n) compile time.
expensive code:
if(*i0){int a; a=(*i1);*i2=(a/3+a/7);} : roughly O(n*n) compile time
if(*i0){int a; a=(*i1);*i2=(a/3+(*i2)/7);} : roughly O(n*n) compile time
cheap code:
if(*i0){int a; a=(*i1);*i2=(a*3+a*7);} : roughly O(n) compile time
if(*i0){int a; a=(*i1);*i2=(a*3+(*i2)*7);} : roughly O(n) compile time
Used Code Scheme:
void test(int *i0,int *i1,int *i2){
if(*i0){int a; a=(*i1);*i2=(a/3+a/7);}
... copies of the last statement
return;}
The body of the test function consists of a number of copies of
the following Statement:
if(*i0){int a; a=(*i1);*i2=(a/3+a/7);}
Each statement produces 2 basic blocks.
Content of the following table:
BBs : number of basic blocks in if-statements
user : user time from /usr/bin/time gcc
global_alloc : from output of -ftime-report
lines of assembler code : lines of gcc output
(Intel Pentium 700Mhz or an old SPARC-Computer)
Table relating number of basic block to compile time for gcc 3.4.3 intel
========================================================================
BBs user global_alloc lines of assembler code
---------------------------------------------------------------
100 0.22 0.12 (55%) 1468
200 0.54 0.30 (56%) 2918
400 1.36 0.91 (67%) 5818
800 4.09 3.15 (77%) 11618
1600 15.52 13.67 (88%) 23218
3200 76.63 72.87 (95%) 46418
6400 277.25 269.49 (97%) 92818
12800 1072.58 1057.20 (99%) 185618
Table relating number of basic block to compile time for gcc 3.2 intel
======================================================================
BBs user global_alloc lines of assembler code
---------------------------------------------------------------
100 0.17 0.07 (41%) 1369
200 0.37 0.15 (42%) 2719
400 0.76 0.36 (48%) 5419
800 1.53 0.76 (50%) 10819
1600 3.50 1.80 (52%) 21619
3200 8.13 4.59 (56%) 43219
6400 21.59 14.33 (66%) 86419
12800 62.03 45.75 (74%) 172819
Table relating number of basic block to compile time for gcc 3.4.3 sparc
=========================================================================
BBs user global_alloc lines of assembler code
---------------------------------------------------------------
100 0.32 0.05 (16%) 1218
200 0.49 0.07 (15%) 2418
400 0.87 0.16 (19%) 4818
800 1.49 0.30 (20%) 9618
1600 3.10 0.67 (22%) 19218
3200 6.72 1.51 (23%) 38418
6400 14.95 4.45 (30%) 76818
12800 54.73 32.43 (59%) 153618
Table relating number of basic block to compile time for gcc 2.95.2 sparc
=========================================================================
BBs user global_alloc lines of assembler code
---------------------------------------------------------------
100 0.11 1173
200 0.17 2323
400 0.30 4623
800 0.62 9223
1600 1.35 18423
3200 2.90 36823
6400 6.19 73623
12800 14.97 147223
Table relating number of basic block to compile time for gcc 3.4.3 intel
for this Code: if(*i0){int a; a=(*i1);*i2=(a*3+a*7);}
=========================================================================
BBs user global_alloc lines of assembler code
---------------------------------------------------------------
100 0.11 0.01 (10%) 713
200 0.16 0.03 (20%) 1413
400 0.35 0.07 (21%) 2813
800 0.65 0.14 (22%) 5613
1600 1.33 0.28 (21%) 11213
3200 2.93 0.58 (20%) 22413
6400 5.80 1.15 (20%) 44813
12800 12.09 2.68 (22%) 89613
Shellscripts:
-----------------------------------------------------------------------
for x in 50 100 200 400 800 1600 3200 6400
do
echo "############ $x"
run $x
done
---------------------------------------------------------------------------
[[ -z $1 ]] && exit 1
N=$1
echo 'void test(int *i0,int *i1,int *i2){' >z.c
IF="if(*i0){int a; a=(*i1);*i2=(a/3+(*i2)/7);}"
((i=$N))
while((i>0))
do
echo " $IF" >>z.c
((i=i-1))
done
echo 'return;}' >>z.c
wc z.c
echo "$IF"
/usr/bin/time -p gcc -S -O0 -ftime-report z.c
((BB=N+N))
echo "### BB $BB"
wc z.s
-----------------------------------------------------------------------------
gawk '
$1=="global" && $2 == "alloc" {gsub(":"," ");ga=$3; proz=$4 }
$1=="user" { u=$2; }
$1=="###" && $2=="BB" {bb=$3;}
$4=="z.s" {printf("%s\t %s\t %s\t %s\t %s\n",bb,u,ga,proz ,$1)};
' nohup.out
--
Summary: O(n^2) compile time with -O0 (n= number of basic blocks)
in global alloc
Product: gcc
Version: 3.4.3
Status: UNCONFIRMED
Severity: minor
Priority: P3
Component: target
AssignedTo: unassigned at gcc dot gnu dot org
ReportedBy: heinrich dot brand at fujitsu-siemens dot com
CC: gcc-bugs at gcc dot gnu dot org
GCC build triplet: Intel SUSE 8.1
GCC host triplet: Intel SUSE 8.1
GCC target triplet: Intel SUSE 8.1
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18927
^ permalink raw reply [flat|nested] 9+ messages in thread
* [Bug middle-end/18927] O(n^2) compile time with -O0 (n= number of basic blocks) in global alloc
2004-12-10 15:43 [Bug target/18927] New: O(n^2) compile time with -O0 (n= number of basic blocks) in global alloc heinrich dot brand at fujitsu-siemens dot com
@ 2004-12-10 16:05 ` pinskia at gcc dot gnu dot org
2004-12-11 8:50 ` pinskia at gcc dot gnu dot org
` (4 subsequent siblings)
5 siblings, 0 replies; 9+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2004-12-10 16:05 UTC (permalink / raw)
To: gcc-bugs
--
What |Removed |Added
----------------------------------------------------------------------------
Component|target |middle-end
Keywords| |compile-time-hog
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18927
^ permalink raw reply [flat|nested] 9+ messages in thread
* [Bug middle-end/18927] O(n^2) compile time with -O0 (n= number of basic blocks) in global alloc
2004-12-10 15:43 [Bug target/18927] New: O(n^2) compile time with -O0 (n= number of basic blocks) in global alloc heinrich dot brand at fujitsu-siemens dot com
2004-12-10 16:05 ` [Bug middle-end/18927] " pinskia at gcc dot gnu dot org
@ 2004-12-11 8:50 ` pinskia at gcc dot gnu dot org
2004-12-11 12:48 ` steven at gcc dot gnu dot org
` (3 subsequent siblings)
5 siblings, 0 replies; 9+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2004-12-11 8:50 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From pinskia at gcc dot gnu dot org 2004-12-11 08:50 -------
Confirmed also on ppc.
--
What |Removed |Added
----------------------------------------------------------------------------
Status|UNCONFIRMED |NEW
Ever Confirmed| |1
Last reconfirmed|0000-00-00 00:00:00 |2004-12-11 08:50:32
date| |
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18927
^ permalink raw reply [flat|nested] 9+ messages in thread
* [Bug middle-end/18927] O(n^2) compile time with -O0 (n= number of basic blocks) in global alloc
2004-12-10 15:43 [Bug target/18927] New: O(n^2) compile time with -O0 (n= number of basic blocks) in global alloc heinrich dot brand at fujitsu-siemens dot com
2004-12-10 16:05 ` [Bug middle-end/18927] " pinskia at gcc dot gnu dot org
2004-12-11 8:50 ` pinskia at gcc dot gnu dot org
@ 2004-12-11 12:48 ` steven at gcc dot gnu dot org
2004-12-11 13:14 ` [Bug middle-end/18927] O(n^2) compile time with -O0 (n= number of basic blocks) in local alloc steven at gcc dot gnu dot org
` (2 subsequent siblings)
5 siblings, 0 replies; 9+ messages in thread
From: steven at gcc dot gnu dot org @ 2004-12-11 12:48 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From steven at gcc dot gnu dot org 2004-12-11 12:48 -------
I'm puzzled how global can take so much time at -O0, since we don't
run global unless we're optimizing.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18927
^ permalink raw reply [flat|nested] 9+ messages in thread
* [Bug middle-end/18927] O(n^2) compile time with -O0 (n= number of basic blocks) in local alloc
2004-12-10 15:43 [Bug target/18927] New: O(n^2) compile time with -O0 (n= number of basic blocks) in global alloc heinrich dot brand at fujitsu-siemens dot com
` (2 preceding siblings ...)
2004-12-11 12:48 ` steven at gcc dot gnu dot org
@ 2004-12-11 13:14 ` steven at gcc dot gnu dot org
2004-12-13 11:37 ` heinrich dot brand at fujitsu-siemens dot com
2004-12-23 11:21 ` steven at gcc dot gnu dot org
5 siblings, 0 replies; 9+ messages in thread
From: steven at gcc dot gnu dot org @ 2004-12-11 13:14 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From steven at gcc dot gnu dot org 2004-12-11 13:14 -------
Ah, but it's not *global* alloc, it is *local* alloc! From your scripts:
local alloc : 0.16 (59%) usr 0.00 ( 0%) sys 0.00 ( 0%) wall
local alloc : 0.63 (72%) usr 0.00 ( 0%) sys 0.50 (50%) wall
local alloc : 2.69 (85%) usr 0.00 ( 0%) sys 2.50 (83%) wall
local alloc : 10.89 (92%) usr 0.02 (15%) sys 11.00 (92%) wall
local alloc : 58.39 (96%) usr 0.04 (14%) sys 58.50 (95%) wall
(last 3 omitted for obvious reasons)
--
What |Removed |Added
----------------------------------------------------------------------------
Summary|O(n^2) compile time with -O0|O(n^2) compile time with -O0
|(n= number of basic blocks) |(n= number of basic blocks)
|in global alloc |in local alloc
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18927
^ permalink raw reply [flat|nested] 9+ messages in thread
* [Bug middle-end/18927] O(n^2) compile time with -O0 (n= number of basic blocks) in local alloc
2004-12-10 15:43 [Bug target/18927] New: O(n^2) compile time with -O0 (n= number of basic blocks) in global alloc heinrich dot brand at fujitsu-siemens dot com
` (3 preceding siblings ...)
2004-12-11 13:14 ` [Bug middle-end/18927] O(n^2) compile time with -O0 (n= number of basic blocks) in local alloc steven at gcc dot gnu dot org
@ 2004-12-13 11:37 ` heinrich dot brand at fujitsu-siemens dot com
2004-12-23 11:21 ` steven at gcc dot gnu dot org
5 siblings, 0 replies; 9+ messages in thread
From: heinrich dot brand at fujitsu-siemens dot com @ 2004-12-13 11:37 UTC (permalink / raw)
To: gcc-bugs
[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 2972 bytes --]
------- Additional Comments From heinrich dot brand at fujitsu-siemens dot com 2004-12-13 11:37 -------
My compiler outputs really this line:
global alloc :1083.72 (99%) usr 0.39 (51%) sys1085.19 (99%) wall
Line with context:
hei@pgtd2308:~/CCS/GLOBALALLOC/04> /home/hei/GCCBIN/3.4.3/bin/gcc -S -O0 -v -
ftime-report z.c
Lese Spezifikationen von /home/hei/GCCBIN/3.4.3/lib/gcc/i686-pc-linux-
gnu/3.4.3/specs
Konfiguriert mit: ../gcc-3.4.3/configure -prefix /home/hei/GCCBIN/3.4.3 --
enable-checking
Thread-Modell: posix
gcc-Version 3.4.3
/home/hei/GCCBIN/3.4.3/libexec/gcc/i686-pc-linux-gnu/3.4.3/cc1 -quiet -v z.c -
quiet -dumpbase z.c -mtune=pentiumpro -auxbase z -O0 -version -ftime-report -o
z.s
nicht vorhandenes Verzeichnis »/home/hei/GCCBIN/3.4.3/lib/gcc/i686-pc-linux-
gnu/3.4.3/../../../../i686-pc-linux-gnu/include« wird ignoriert
#include "..." - Suche beginnt hier:
#include <...> - Suche beginnt hier:
/usr/local/include
/home/hei/GCCBIN/3.4.3/include
/home/hei/GCCBIN/3.4.3/lib/gcc/i686-pc-linux-gnu/3.4.3/include
/usr/include
Ende der Suchliste.
GNU C version 3.4.3 (i686-pc-linux-gnu)
compiled by GNU C version 3.2.
GGC-Heuristik: --param ggc-min-expand=30 --param ggc-min-heapsize=4096
Ausführungszeiten (Sekunden)
garbage collection : 1.27 ( 0%) usr 0.00 ( 0%) sys 1.27 ( 0%) wall
cfg construction : 0.56 ( 0%) usr 0.00 ( 0%) sys 0.56 ( 0%) wall
cfg cleanup : 0.17 ( 0%) usr 0.00 ( 0%) sys 0.17 ( 0%) wall
trivially dead code : 0.26 ( 0%) usr 0.00 ( 0%) sys 0.26 ( 0%) wall
life analysis : 0.98 ( 0%) usr 0.00 ( 0%) sys 0.98 ( 0%) wall
life info update : 0.43 ( 0%) usr 0.00 ( 0%) sys 0.43 ( 0%) wall
register scan : 0.49 ( 0%) usr 0.03 ( 4%) sys 0.52 ( 0%) wall
rebuild jump labels : 0.31 ( 0%) usr 0.00 ( 0%) sys 0.31 ( 0%) wall
preprocessing : 0.20 ( 0%) usr 0.05 ( 6%) sys 0.24 ( 0%) wall
lexical analysis : 0.26 ( 0%) usr 0.09 (12%) sys 0.36 ( 0%) wall
parser : 0.89 ( 0%) usr 0.05 ( 6%) sys 0.95 ( 0%) wall
expand : 1.22 ( 0%) usr 0.05 ( 6%) sys 1.27 ( 0%) wall
jump : 0.07 ( 0%) usr 0.00 ( 0%) sys 0.07 ( 0%) wall
flow analysis : 0.35 ( 0%) usr 0.01 ( 1%) sys 0.36 ( 0%) wall
local alloc : 2.50 ( 0%) usr 0.06 ( 8%) sys 2.56 ( 0%) wall
global alloc :1083.72 (99%) usr 0.39 (51%) sys1085.19 (99%) wall
flow 2 : 0.96 ( 0%) usr 0.00 ( 0%) sys 0.96 ( 0%) wall
shorten branches : 0.94 ( 0%) usr 0.01 ( 1%) sys 0.95 ( 0%) wall
final : 1.25 ( 0%) usr 0.03 ( 4%) sys 1.37 ( 0%) wall
rest of compilation : 2.50 ( 0%) usr 0.00 ( 0%) sys 2.50 ( 0%) wall
GESAMT :1099.35 0.77 1101.32
hei@pgtd2308:~/CCS/GLOBALALLOC/04>
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18927
^ permalink raw reply [flat|nested] 9+ messages in thread
* [Bug middle-end/18927] O(n^2) compile time with -O0 (n= number of basic blocks) in local alloc
2004-12-10 15:43 [Bug target/18927] New: O(n^2) compile time with -O0 (n= number of basic blocks) in global alloc heinrich dot brand at fujitsu-siemens dot com
` (4 preceding siblings ...)
2004-12-13 11:37 ` heinrich dot brand at fujitsu-siemens dot com
@ 2004-12-23 11:21 ` steven at gcc dot gnu dot org
5 siblings, 0 replies; 9+ messages in thread
From: steven at gcc dot gnu dot org @ 2004-12-23 11:21 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From steven at gcc dot gnu dot org 2004-12-23 11:21 -------
Right... OK, so for mainline the problem is different from 3.4
apparently. Someone should get profile information for this to
see what is going on here.
--
What |Removed |Added
----------------------------------------------------------------------------
GCC build triplet|Intel SUSE 8.1 |
GCC host triplet|Intel SUSE 8.1 |
GCC target triplet|Intel SUSE 8.1 |
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18927
^ permalink raw reply [flat|nested] 9+ messages in thread
* [Bug middle-end/18927] O(n^2) compile time with -O0 (n= number of basic blocks) in local alloc
[not found] <bug-18927-4@http.gcc.gnu.org/bugzilla/>
@ 2012-05-20 22:23 ` steven at gcc dot gnu.org
0 siblings, 0 replies; 9+ messages in thread
From: steven at gcc dot gnu.org @ 2012-05-20 22:23 UTC (permalink / raw)
To: gcc-bugs
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18927
Steven Bosscher <steven at gcc dot gnu.org> changed:
What |Removed |Added
----------------------------------------------------------------------------
Status|NEW |RESOLVED
CC| |steven at gcc dot gnu.org
Resolution| |FIXED
--- Comment #7 from Steven Bosscher <steven at gcc dot gnu.org> 2012-05-20 21:47:37 UTC ---
Made some new timings with a bunch of compilers, and looking at IRA timings:
############ gcc-3.4.6 (stock FSF)
100 0.12 0.03 (25%) 1604
200 0.23 0.06 (26%) 3154
400 0.15 0.04 (29%) 6254
800 0.28 0.08 (29%) 12454
1600 0.62 0.17 (27%) 24854
3200 1.17 0.35 (30%) 49654
############ gcc-4.2.4 (stock FSF)
100 0.04 0.02 (50%) 1759
200 0.09 0.03 (33%) 3459
400 0.14 0.05 (36%) 6859
800 0.30 0.11 (38%) 13659
1600 0.64 0.23 (36%) 27259
3200 1.16 0.45 (39%) 54459
############ gcc-4.3.3 (stock FSF)
100 0.04 0.03 (75%) 1759
200 0.13 0.07 (54%) 3459
400 0.41 0.28 (68%) 6859
800 1.24 1.04 (85%) 13659
1600 4.52 4.11 (91%) 27259
3200 16.88 16.05 (95%) 54459
############ gcc-4.4.7 (Ubuntu)
100 0.04 0.01 (25%) 1627
200 0.10 0.03 (30%) 3227
400 0.17 0.05 (31%) 6427
800 0.39 0.14 (36%) 12827
1600 0.78 0.25 (32%) 25627
3200 1.64 0.52 (32%) 51227
############ gcc-4.6.3 (Ubuntu)
100 0.04 0.01 (25%) 1624
200 0.10 0.03 (33%) 3224
400 0.18 0.06 (35%) 6424
800 0.35 0.10 (29%) 12824
1600 0.69 0.20 (29%) 25624
3200 1.47 0.41 (28%) 51224
Thus fixes for all open branches.
^ permalink raw reply [flat|nested] 9+ messages in thread
* [Bug middle-end/18927] O(n^2) compile time with -O0 (n= number of basic blocks) in local alloc
[not found] <bug-18927-5884@http.gcc.gnu.org/bugzilla/>
@ 2009-06-10 1:54 ` pinskia at gcc dot gnu dot org
0 siblings, 0 replies; 9+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2009-06-10 1:54 UTC (permalink / raw)
To: gcc-bugs
------- Comment #6 from pinskia at gcc dot gnu dot org 2009-06-10 01:53 -------
Hmm, I wonder what are the numbers are for 4.4 with IRA.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18927
^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~2012-05-20 22:06 UTC | newest]
Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2004-12-10 15:43 [Bug target/18927] New: O(n^2) compile time with -O0 (n= number of basic blocks) in global alloc heinrich dot brand at fujitsu-siemens dot com
2004-12-10 16:05 ` [Bug middle-end/18927] " pinskia at gcc dot gnu dot org
2004-12-11 8:50 ` pinskia at gcc dot gnu dot org
2004-12-11 12:48 ` steven at gcc dot gnu dot org
2004-12-11 13:14 ` [Bug middle-end/18927] O(n^2) compile time with -O0 (n= number of basic blocks) in local alloc steven at gcc dot gnu dot org
2004-12-13 11:37 ` heinrich dot brand at fujitsu-siemens dot com
2004-12-23 11:21 ` steven at gcc dot gnu dot org
[not found] <bug-18927-5884@http.gcc.gnu.org/bugzilla/>
2009-06-10 1:54 ` pinskia at gcc dot gnu dot org
[not found] <bug-18927-4@http.gcc.gnu.org/bugzilla/>
2012-05-20 22:23 ` steven at gcc dot gnu.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).