Bad compile time complexity for large files ??? (fwd)

Bad compile time complexity for large files ??? (fwd)

[Gabriel Dos Reis]

[-- Attachment #1: Type: text/plain, Size: 304 bytes --]


FYI.  Joris's messages seem to have been blocked...
Please, CC: Joris when replying.

Joris --

  It might help if you can provide information about the version of GCC
you're using. You might also want to try

   http://gcc.gnu.org/bugzilla/

That way, your report will be recorded in the PR database.


[-- Attachment #2: Type: message/rfc822, Size: 5341 bytes --]

From: Joris van der Hoeven <vdhoeven@texmacs.org>
To: <gdr@integrable-solutions.net>
Subject: Bad compile time complexity for large files ??? (fwd)
Date: Wed, 10 Nov 2004 12:19:22 +0100 (CET)
Message-ID: <Pine.GSO.4.33.0411101216210.24591-100000@sunanh>



Salut Gabriel,

J'ai essaye plusieurs fois de poster le message ci-dessous
sur la liste gcc, mais c'est systematiquement refuse.
Peut-etre que tu peux le poster et me forwarder d'eventuelles reponses.
Je me suis desinscrit de la liste, car il y avait trop de messages.

A+, Joris


---------- Forwarded message ----------
Date: Tue, 9 Nov 2004 12:00:47 +0100 (CET)
From: Joris van der Hoeven <texmacs@math.u-psud.fr>
To: gcc-owner@gcc.gnu.org
Subject: Bad compile time complexity for large files ??? (fwd)

Hi,

I have suscribed to the gcc mailing list in order to send
the message below, but it keeps being rejected. Why?

Joris

---------- Forwarded message ----------
Date: Tue, 9 Nov 2004 11:36:29 +0100 (CET)
From: Joris van der Hoeven <texmacs@math.u-psud.fr>
To: gcc@gcc.gnu.org
Subject: Bad compile time complexity for large files ???


Hi *,

I am using g++ for compiling automatically generated glue files
for another language (mathemagix). These glue files tend to become
quite big when I want to glue big C++ libraries. More precisely,
they contain a lot of small methods and routines, like

--------------------------------------------------
[...]
ext_inst
ext_mml_vector_rep::gen_timesassign (ext_inst &arg_1, ext_inst arg_2) {
  ext_type save_1 = ext_cur_1;
  ext_cur_1 = x_1;
  ext_inst ret = convert<ext_inst, mml_vector<ext_inst_1> > (convert<mml_vector<ext_inst_1>&, ext_inst& > (arg_1) *= convert<mml_vector<ext_inst_1>, ext_inst> (arg_2));
  ext_cur_1 = save_1;
  return ret;
}
[...]
static mmx::generic
FUN_29 (mmx::generic g) {
  return mmx::as_mmx<double, TID> (mmx::as_cpp<double&, TID> (g[1]) *= mmx::as_cpp<double, TID> (g[2]));
}
[...]
--------------------------------------------------

The number of classes is relatively small.

When the number of routines increases, I noticed a far more than
linear time complexity for the compilation time. This is very
disappointing for me, since it makes it nearly impossible to compile
glue files with more than a few hundred routines.

I suspect that this behaviour is due to a lack of optimization
in the way identifiers are stored by the compiler: does gcc use
a linked list instead of a hash table? Is there a compilation
option that I may have overlooked?

I would be very interested in having this important drawback being
removed; such an optimization will probably be interesting anyway,
since the performance already drops sharply for files with a few
thousand lines. If I can somehow help with improving this point,
then please let me know; I know nothing about the g++ source code,
but may learn the necessary if somebody guides me.

Best wishes, Joris

-----------------------------------------------------------
Joris van der Hoeven <vdhoeven@texmacs.org>
http://www.texmacs.org: GNU TeXmacs scientific text editor
http://www.math.u-psud.fr/~vdhoeven: personal homepage
-----------------------------------------------------------

[-- Attachment #3: Type: text/plain, Size: 264 bytes --]



-- 
                                                        Gabriel Dos Reis
                                                         gdr@cs.tamu.edu
	Texas A&M University -- Department of Computer Science
	301, Bright Building -- College Station, TX 77843-3112

Re: Bad compile time complexity for large files ??? (fwd)

[Matt Austern]

On Nov 10, 2004, at 11:14 AM, Gabriel Dos Reis wrote:

>
> FYI.  Joris's messages seem to have been blocked...
> Please, CC: Joris when replying.
>
> Joris --
>
>   It might help if you can provide information about the version of GCC
> you're using. You might also want to try
>
>    http://gcc.gnu.org/bugzilla/
>
> That way, your report will be recorded in the PR database.

I would be interested in seeing a test case.  Compilation speed is 
important, and if there really is something that cases superlinear 
behavior I would like to fix it.

			--Matt

Re: Bad compile time complexity for large files ??? (fwd)

[Mike Stump]

On Nov 10, 2004, at 11:14 AM, Gabriel Dos Reis wrote:
> Date: Tue, 9 Nov 2004 11:36:29 +0100 (CET)
> From: Joris van der Hoeven <texmacs@math.u-psud.fr>
> To: gcc@gcc.gnu.org
> Subject: Bad compile time complexity for large files ???

> When the number of routines increases, I noticed a far more than
> linear time complexity for the compilation time.

If you are serious about this, abstract down the glue code, plot a 
graph of size v compile time, and see if it is bad (n^2 2^n...).  If it 
is submit it as a bug report.

By abstract down, I mean, take the full code, and keep trimming out 
elements such that the compile times stay bad.

Another approach might be to submit a profile of the compiler as it 
compiles your code.

Be sure to use a top of the tree 4.0.0 compiler, as there have been a 
lot of work done recently to improve the compiler in this regard.

I'll give you an example of known slow things.  Template instantiations 
are (were) done by a linear search, causing n^2 behavior.  Not sure if 
this impacts you, as you abstracted out too much detail for me to tell.

Another possibility, try -O0.

A -ftime-report might also be useful in figuring out what is going 
wrong.

And most of all, be sure that you have an appropriate amount of memory 
for the task at hand.  The garbage collector will run often, if you 
have a `small' machine.

And lastly, you'll want to get a yahoo or gmail account, if you can't 
manage to sort out your ISP problems.  See 
http://gcc.gnu.org/lists.html for some details...

Re: Bad compile time complexity for large files ??? (fwd)

[Gabriel Dos Reis]

---------- Forwarded message ----------
Date: Thu, 11 Nov 2004 18:46:26 +0100 (CET)
From: Joris van der Hoeven <vdhoeven@texmacs.org>
To: Gabriel Dos Reis <gdr@cs.tamu.edu>
Cc: vdhoeven@texmacs.org
Subject: Re: Bad compile time complexity for large files ???


Salut Gabriel,

Je viens de nettoyer un peu mes bench et de les refaire pour les deux
versions de g++. Voici les resultats ; merci de les forwarder aux listes.

---------------------------------------------------------------

Hi *,

I have attempted to provide some more precise benchmarks which show
the worse than linear behaviour for the compilation time. If anyone is
interested in reproducing them (which implies that you have to install
mmxlib and mathemagix), then please let me know and I will try to
smooth the installation procedure.

First of all, let me explain more precisely what the timings stand for.
Mathemagix is a high level language, futuring template types like C++,
and which allows you to glue C++ template libraries (the interpreter is
still very slow, so this is a way to provide basic functionality at
a high speed). I also started to write a C++ template library Mmxlib
(the standard mathematical library for Mathemagix, containg many
routines for symbolic computation).

The glue description for Mmxlib contains two parts A (the scalar types)
and B (the template types). When compiling the generated glue code,
the contribution of each part should be relatively independent
(apart from a small overhead and some common includes).
Of course, part B will give rise to many template instantiations.

Now I made the following experiment: generate and compile 4 times
the glue code with A and B either disabled or enabled. I did this
both with gcc-2.95.3 and gcc-3.4.3. Here are the approximate timings:

-------------------------------------------------------------
Configuration	Timings for gcc-2.95.3	Timings for gcc-3.4.3
-------------------------------------------------------------
None		1			2
A		25			14
B		58			18
A+B		192			51
-------------------------------------------------------------

One first remark: gcc-3.4.3 is quite a bit slower for small files,
but clearly much better for large files (which is encouraging).
Nevertheless, in both cases, one notices a behaviour which is much
worse than linear (191 > 81 and 49 > 28).

I hope that this "real-life experiment" convinces you that there is
still room for improvement. I am afraid that I cannot produce
a more incremental graph for you. A final note: I have a 2.4GHz
Athlon processor and 512Mb of memory.

Best wishes and thanks for your attention, Joris

-----------------------------------------------------------
Joris van der Hoeven <vdhoeven@texmacs.org>
http://www.texmacs.org: GNU TeXmacs scientific text editor
http://www.math.u-psud.fr/~vdhoeven: personal homepage
-----------------------------------------------------------