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; 17+ 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] 17+ messages in thread
end of thread, other threads:[~2007-04-13 14:16 UTC | newest]

Thread overview: 17+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
     [not found] <bug-18937-9515@http.gcc.gnu.org/bugzilla/>
2006-01-09 18:57 ` [Bug fortran/18937] quadratic behaviour with many label "spaghetti" code tobi at gcc dot gnu dot org
2006-01-14 19:03 ` tobi at gcc dot gnu dot org
2006-01-18 20:54 ` tobi at gcc dot gnu dot org
2006-01-18 21:07 ` tobi at gcc dot gnu dot org
2006-01-26 16:46 ` tobi at gcc dot gnu dot org
2007-03-23 22:27 ` tobi at gcc dot gnu dot org
2007-03-23 22:35 ` tobi at gcc dot gnu dot org
2007-03-25 18:51 ` tobi at gcc dot gnu dot org
2007-03-26  3:41 ` patchapp at dberlin dot org
2007-04-13 13:48 ` tobi at gcc dot gnu dot org
2007-04-13 14:16 ` tobi at gcc dot gnu dot org
2004-12-11  8:28 [Bug middle-end/18937] New: " 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).