public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug middle-end/18937] New: quadratic behaviour with many label "spaghetti" code
@ 2004-12-11 8:28 Thomas dot Koenig at online dot de
2004-12-11 8:45 ` [Bug fortran/18937] " pinskia at gcc dot gnu dot org
` (5 more replies)
0 siblings, 6 replies; 7+ messages in thread
From: Thomas dot Koenig at online dot de @ 2004-12-11 8:28 UTC (permalink / raw)
To: gcc-bugs
I've written a short script to generate test cases
with many random goto's.
Here it is, with sample output:
$ cat spaghetti
#! /usr/bin/perl
$last = shift;
for ($i=1; $i<=$last; $i++) {
push(@lines, sprintf("%5d i=i+1\n goto %d\n", $i, $i+1));
}
for ($i=0; $i<=$last; $i++) {
$j = int(rand($last));
$temp = $lines[$i];
$lines[$i] = $lines[$j];
$lines[$j] = $temp;
}
print " i=0\n";
print " goto 1\n";
print @lines;
printf "%5d continue\n",$last+1;
print " print *,i\n";
print " end\n";
$ ./spaghetti 10
i=0
goto 1
6 i=i+1
goto 7
1 i=i+1
goto 2
8 i=i+1
goto 9
3 i=i+1
goto 4
7 i=i+1
goto 8
2 i=i+1
goto 3
9 i=i+1
goto 10
10 i=i+1
goto 11
5 i=i+1
goto 6
4 i=i+1
goto 5
11 continue
print *,i
end
Compiling this with gfortran yielded compilation times which were pretty
long for large numbers of labels and which were quadratic:
$ ./spaghetti 10000 > spaghetti.f
$ time gfortran -O3 spaghetti.f
real 0m27.876s
user 0m27.827s
sys 0m0.041s
$ ./spaghetti 20000 > spaghetti.f
$ time gfortran -O3 spaghetti.f
real 1m51.228s
user 1m51.022s
sys 0m0.089s
$ ./spaghetti 40000 > spaghetti.f
$ time gfortran -O3 spaghetti.f
real 7m18.125s
user 7m16.173s
sys 0m0.215s
This is on an Atholon 2600+.
The quality of the resulting code is excellent, BTW - the additions
are reduced to a single assignment with -O3.
$ gfortran -v
Reading specs from /home/ig25/lib/gcc/i686-pc-linux-gnu/4.0.0/specs
Configured with: ../gcc/configure --prefix=/home/ig25 --enable-languages=c,c++,f95
Thread model: posix
gcc version 4.0.0 20041208 (experimental)
--
Summary: quadratic behaviour with many label "spaghetti" code
Product: gcc
Version: 4.0.0
Status: UNCONFIRMED
Severity: enhancement
Priority: P2
Component: middle-end
AssignedTo: unassigned at gcc dot gnu dot org
ReportedBy: Thomas dot Koenig at online dot de
CC: gcc-bugs at gcc dot gnu dot org
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18937
^ permalink raw reply [flat|nested] 7+ messages in thread
* [Bug fortran/18937] quadratic behaviour with many label "spaghetti" code
2004-12-11 8:28 [Bug middle-end/18937] New: quadratic behaviour with many label "spaghetti" code Thomas dot Koenig at online dot de
@ 2004-12-11 8:45 ` pinskia at gcc dot gnu dot org
2004-12-11 8:49 ` pinskia at gcc dot gnu dot org
` (4 subsequent siblings)
5 siblings, 0 replies; 7+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2004-12-11 8:45 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From pinskia at gcc dot gnu dot org 2004-12-11 08:45 -------
Actually all of the time is spent in the parser so this is not a middle-end problem.
Also note you did you did not disable checking which is enabled by default on non release branches.
parser : 20.34 (90%) usr 0.15 (19%) sys 22.35 (88%) wall
The compile time problems comes from transfering linked lists.
One is in resolve.c:3067-3076
Another is in symbol.c:1401-1403.
I don't know if the linked lists are long are just looked over and over. I am going to assume the former.
--
What |Removed |Added
----------------------------------------------------------------------------
Severity|enhancement |minor
Status|UNCONFIRMED |NEW
Component|middle-end |fortran
Ever Confirmed| |1
Keywords| |compile-time-hog
Last reconfirmed|0000-00-00 00:00:00 |2004-12-11 08:45:22
date| |
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18937
^ permalink raw reply [flat|nested] 7+ messages in thread
* [Bug fortran/18937] quadratic behaviour with many label "spaghetti" code
2004-12-11 8:28 [Bug middle-end/18937] New: quadratic behaviour with many label "spaghetti" code Thomas dot Koenig at online dot de
2004-12-11 8:45 ` [Bug fortran/18937] " pinskia at gcc dot gnu dot org
@ 2004-12-11 8:49 ` pinskia at gcc dot gnu dot org
2004-12-11 10:40 ` Thomas dot Koenig at online dot de
` (3 subsequent siblings)
5 siblings, 0 replies; 7+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2004-12-11 8:49 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From pinskia at gcc dot gnu dot org 2004-12-11 08:49 -------
One more note g77 in 3.3 is faster.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18937
^ permalink raw reply [flat|nested] 7+ messages in thread
* [Bug fortran/18937] quadratic behaviour with many label "spaghetti" code
2004-12-11 8:28 [Bug middle-end/18937] New: quadratic behaviour with many label "spaghetti" code Thomas dot Koenig at online dot de
2004-12-11 8:45 ` [Bug fortran/18937] " pinskia at gcc dot gnu dot org
2004-12-11 8:49 ` pinskia at gcc dot gnu dot org
@ 2004-12-11 10:40 ` Thomas dot Koenig at online dot de
2004-12-11 11:55 ` steven at gcc dot gnu dot org
` (2 subsequent siblings)
5 siblings, 0 replies; 7+ messages in thread
From: Thomas dot Koenig at online dot de @ 2004-12-11 10:40 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From Thomas dot Koenig at online dot de 2004-12-11 10:40 -------
(In reply to comment #1)
> Actually all of the time is spent in the parser so this is not a middle-end
problem.
You're correct. For example, the C frontend does not exhibit
this behavior:
$ ./spaghetti-c 1000 > sp.c
$ time gcc sp.c
real 0m0.244s
user 0m0.224s
sys 0m0.012s
$ ./spaghetti-c 10000 > sp.c
$ time gcc sp.c
real 0m2.594s
user 0m2.473s
sys 0m0.058s
$ ./spaghetti-c 100000 > sp.c
$ time gcc sp.c
real 0m32.483s
user 0m31.169s
sys 0m0.501s
$ gcc -v
Reading specs from /home/ig25/lib/gcc/i686-pc-linux-gnu/4.0.0/specs
Configured with: ../gcc/configure --prefix=/home/ig25 --enable-languages=c,c++,f95
Thread model: posix
gcc version 4.0.0 20041208 (experimental)
(also with checks enabled).
$ cat spaghetti-c
#! /usr/bin/perl
$last = shift;
for ($i=1; $i<=$last; $i++) {
push(@lines, sprintf("l_%d:\n i++;\n goto l_%d;\n", $i, $i+1));
}
for ($i=0; $i<=$last; $i++) {
$j = int(rand($last));
$temp = $lines[$i];
$lines[$i] = $lines[$j];
$lines[$j] = $temp;
}
print <<EOF;
#include <stdio.h>
int main()
{
int i=0;
goto l_1;
EOF
print @lines;
printf ("l_%d:\n",$last+1);
print <<EOF
printf("%d\\n",i);
return 0;
}
EOF
$ ./spaghetti-c 5
#include <stdio.h>
int main()
{
int i=0;
goto l_1;
l_4:
i++;
goto l_5;
l_1:
i++;
goto l_2;
l_5:
i++;
goto l_6;
l_3:
i++;
goto l_4;
l_2:
i++;
goto l_3;
l_6:
printf("%d\n",i);
return 0;
}
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18937
^ permalink raw reply [flat|nested] 7+ messages in thread
* [Bug fortran/18937] quadratic behaviour with many label "spaghetti" code
2004-12-11 8:28 [Bug middle-end/18937] New: quadratic behaviour with many label "spaghetti" code Thomas dot Koenig at online dot de
` (2 preceding siblings ...)
2004-12-11 10:40 ` Thomas dot Koenig at online dot de
@ 2004-12-11 11:55 ` steven at gcc dot gnu dot org
2004-12-12 16:19 ` Thomas dot Koenig at online dot de
2004-12-14 22:09 ` tobi at gcc dot gnu dot org
5 siblings, 0 replies; 7+ messages in thread
From: steven at gcc dot gnu dot org @ 2004-12-11 11:55 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From steven at gcc dot gnu dot org 2004-12-11 11:55 -------
The problem in gfc_get_st_label() is easy to solve - just turn st_labels
into a hash table. The problem in resolve.c is more difficult, I need to
think about that a little more...
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18937
^ permalink raw reply [flat|nested] 7+ messages in thread
* [Bug fortran/18937] quadratic behaviour with many label "spaghetti" code
2004-12-11 8:28 [Bug middle-end/18937] New: quadratic behaviour with many label "spaghetti" code Thomas dot Koenig at online dot de
` (3 preceding siblings ...)
2004-12-11 11:55 ` steven at gcc dot gnu dot org
@ 2004-12-12 16:19 ` Thomas dot Koenig at online dot de
2004-12-14 22:09 ` tobi at gcc dot gnu dot org
5 siblings, 0 replies; 7+ messages in thread
From: Thomas dot Koenig at online dot de @ 2004-12-12 16:19 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From Thomas dot Koenig at online dot de 2004-12-12 16:19 -------
g77 has the same problem:
$ time g77 spaghetti.f
real 0m11.649s
user 0m11.516s
sys 0m0.068s
$ ./spaghetti 20000 > spaghetti.f
$ time g77 spaghetti.f
real 0m50.604s
user 0m48.738s
sys 0m0.153s
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18937
^ permalink raw reply [flat|nested] 7+ messages in thread
* [Bug fortran/18937] quadratic behaviour with many label "spaghetti" code
2004-12-11 8:28 [Bug middle-end/18937] New: quadratic behaviour with many label "spaghetti" code Thomas dot Koenig at online dot de
` (4 preceding siblings ...)
2004-12-12 16:19 ` Thomas dot Koenig at online dot de
@ 2004-12-14 22:09 ` tobi at gcc dot gnu dot org
5 siblings, 0 replies; 7+ messages in thread
From: tobi at gcc dot gnu dot org @ 2004-12-14 22:09 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From tobi at gcc dot gnu dot org 2004-12-14 22:09 -------
*** Bug 18943 has been marked as a duplicate of this bug. ***
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18937
^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2004-12-14 22:09 UTC | newest]
Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2004-12-11 8:28 [Bug middle-end/18937] New: quadratic behaviour with many label "spaghetti" code Thomas dot Koenig at online dot de
2004-12-11 8:45 ` [Bug fortran/18937] " pinskia at gcc dot gnu dot org
2004-12-11 8:49 ` pinskia at gcc dot gnu dot org
2004-12-11 10:40 ` Thomas dot Koenig at online dot de
2004-12-11 11:55 ` steven at gcc dot gnu dot org
2004-12-12 16:19 ` Thomas dot Koenig at online dot de
2004-12-14 22:09 ` tobi 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).