Reducing compilation memory usage

Reducing compilation memory usage

[Alejandro Pulver]

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

Hello.

There is a Core War simulator (an interpreter for a minimalistic
machine, called MARS, with a language named redcode) called fmars
(http://www.v-lo.krakow.pl/~michal/fmars.html), which uses computed
gotos to achieve very good performance.

The original version only uses a subset of the available redcode
instructions (~250), instead of the full set (~8000). The author told
me GCC dumped core if trying to use all of them (I don't remember if he
was referring to 2.95 or 3.3).

I decided to try with GCC 4 (4.2.3 20071219 prerelease and 4.3.0
20080111 experimental), and it builds (both) without optimizations
(-O0), but runs twice as slower than the reduced fmars built with -O2.

Version 3.4.6 (20060305) runs out of memory (with and without
optimizations), as 4.x does even with -O1. I have 2GB of RAM (and
allowed processes to use it).

The strange thing is that when looking at options enabled at different
-O levels (trying to remove the ones that were using more memory),
ended up with a GCC 4.2.3 command-line that specified exactly all the
options enabled by -O2 (as listed in the manpage), and built. But ran
at the same speed as without them.

The source file is a function with the ~250/~8000 cases like this one
(they are generated by an intermediate program):

dat_f_immediate_direct:
      {if (!--w->nprocs)
      {
      *death_tab++ = w->id;
      if (--alive_cnt < 2)goto out; w->prev->next = w->next;
      w->next->prev = w->prev;
      cycles -= cycles / alive_cnt;
      }w = w->next;
      ip = *w->head;if (++w->head == queue_end)
            w->head = queue_start;if (!--cycles)
          goto out;
      goto *ip->i;}

So my question is, what optimizations options can I use in this file
without using too much memory (I've read the docs and tried with
various ones, but was annoyed about the fact that using equivalent -f*
options worked without effect but -O/-O2 didn't)?

If more information is needed, please ask. Also please CC me as I'm not
subscribed. I'm using FreeBSD 6.2 (with mentioned GCC 3.4.6 as base
compiler).

Thanks and Best Regards,
Ale

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 187 bytes --]

RE: Reducing compilation memory usage

[John (Eljay) Love-Jensen]

Hi Alejandro,

> The strange thing is that when looking at options enabled at different
-O levels (trying to remove the ones that were using more memory),
ended up with a GCC 4.2.3 command-line that specified exactly all the
options enabled by -O2 (as listed in the manpage), and built. But ran
at the same speed as without them.

Which -O# level were you using in conjunction with the specified -f?

Keep in mind, that at -O0, all optimizations are disabled, and the -f to enable a particular optimization have no effect since all optimizations are disabled.

Sincerely,
--Eljay

Re: Reducing compilation memory usage

[Alejandro Pulver]

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

On Thu, 17 Jan 2008 04:06:04 -0800
"John (Eljay) Love-Jensen" <eljay@adobe.com> wrote:

> Hi Alejandro,
> 
> > The strange thing is that when looking at options enabled at different
> -O levels (trying to remove the ones that were using more memory),
> ended up with a GCC 4.2.3 command-line that specified exactly all the
> options enabled by -O2 (as listed in the manpage), and built. But ran
> at the same speed as without them.
> 
> Which -O# level were you using in conjunction with the specified -f?
> 
> Keep in mind, that at -O0, all optimizations are disabled, and the -f to enable a particular optimization have no effect since all optimizations are disabled.
> 

I didn't use them simultaneously. There are 3 scenarios:

1. No options: builds.
2. -O1/-O2/-O3: runs out of memory.
3. -f* (corresponding to when enabling -O2 as manpage says, but NOT
   -O2): builds, but the final program runs at the same speed.

More specifically this step is just the compilation of preprocessed
code to assembly source.

Do you want the preprocessed source (don't know if the mailing lists
accepts attachments, and encoded ones), and the exact -f* options?

I was initially looking for using -O2 with necessary -f-no-* to avoid
running out of memory.

Thanks and Best Regards,
Ale

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 187 bytes --]

RE: Reducing compilation memory usage

[John (Eljay) Love-Jensen]

Hi Alejandro,

> I didn't use them simultaneously. There are 3 scenarios:
> 1. No options: builds.

That is the same as -O0 "do not optimize".

> 2. -O1/-O2/-O3: runs out of memory.

Did you try -O1 (or -O2 or -O3) and -fno-* disable all the optimizations that can be disabled?

Note that most optimizations enabled by -O1 (and greater) do not have -f* toggles.

> 3. -f* (corresponding to when enabling -O2 as manpage says, but NOT -O2): builds, but the final program runs at the same speed.

That is the same as -O0 "do not optimize".

The -f* are ignored.

> Do you want the preprocessed source, and the exact -f* options?

No.

> I was initially looking for using -O2 with necessary -f-no-* to avoid running out of memory.

That is the approach I recommend.

HTH,
--Eljay

Re: Reducing compilation memory usage

[Alejandro Pulver]

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

On Thu, 17 Jan 2008 08:24:46 -0800
"John (Eljay) Love-Jensen" <eljay@adobe.com> wrote:

> Hi Alejandro,
> 
> > I didn't use them simultaneously. There are 3 scenarios:
> > 1. No options: builds.
> 
> That is the same as -O0 "do not optimize".
> 

Yes.

> > 2. -O1/-O2/-O3: runs out of memory.
> 
> Did you try -O1 (or -O2 or -O3) and -fno-* disable all the optimizations that can be disabled?
> 

Tried -O1 with all -fno-*, and runs out of memory.

> Note that most optimizations enabled by -O1 (and greater) do not have -f* toggles.
> 

This explains the previous behavior, thanks.

> > 3. -f* (corresponding to when enabling -O2 as manpage says, but NOT -O2): builds, but the final program runs at the same speed.
> 
> That is the same as -O0 "do not optimize".
> 
> The -f* are ignored.
> 

Ah, so it's normal (never tried this, so I didn't know, sorry).

> > Do you want the preprocessed source, and the exact -f* options?
> 
> No.
> 
> > I was initially looking for using -O2 with necessary -f-no-* to avoid running out of memory.
> 
> That is the approach I recommend.
> 

As it fails with -O1 and all -fno-*, I tried parameters like
max-pending-list-length=1 without success.

Do you know about an option or something that could help in this case?

I've read something about compilers and this high memory usage could be
caused by keeping references to variables of other blocks (compilation
units, IIRC). So if there is a way to disable that optimizations (tried
-fno-unit-at-a-time and max-pending-list-length=1), and to make it the
most "linear" as possible, it would help (if there are such additional
things I missed).

Or should I ask this more specific question in another place?

Thanks and Best Regards,
Ale

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 187 bytes --]

Re: Reducing compilation memory usage

[Tony Wetmore]

Alejandro Pulver wrote:
 > As it fails with -O1 and all -fno-*, I tried parameters like
 > max-pending-list-length=1 without success.
 >
 > Do you know about an option or something that could help in this case?

Alejandro,

I may have missed this earlier, but are the source files causing GCC to 
crash particularly large?  Perhaps the problem could be avoided by 
splitting the code into more (smaller) files, so that GCC is compiling 
less of the code at once.

If I understand what you are doing, this code is program-generated, so 
you would have to modify the generator program to create multiple files. 
  But you might be able to test this by manually splitting one file 
yourself.

Good luck!

--
Tony Wetmore

Re: Reducing compilation memory usage

[Alejandro Pulver]

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

On Thu, 17 Jan 2008 14:22:33 -0500
Tony Wetmore <tony.wetmore@solipsys.com> wrote:

> Alejandro Pulver wrote:
>  > As it fails with -O1 and all -fno-*, I tried parameters like
>  > max-pending-list-length=1 without success.
>  >
>  > Do you know about an option or something that could help in this case?
> 
> Alejandro,
> 

Hello.

Thank you for your reply.

> I may have missed this earlier, but are the source files causing GCC to 
> crash particularly large?  Perhaps the problem could be avoided by 
> splitting the code into more (smaller) files, so that GCC is compiling 
> less of the code at once.
> 

Yes, the source is 4MB, consisting of one function with a jump table
and ~8000 labels (with little code on each), to simulate each machine
instruction.

GCC doesn't crash, just outputs something like this and exits:

cc1: out of memory allocating 4072 bytes after a total of 1073158016 bytes

> If I understand what you are doing, this code is program-generated, so 
> you would have to modify the generator program to create multiple files. 
>   But you might be able to test this by manually splitting one file 
> yourself.
> 
> Good luck!
> 

I really don't know if I could split it, as it's inside the same
function (all the ~8000 labels with very short code), and it uses
computed gotos (like the ones generated by a switch statement, with a
"jump table" so there is no comparison of the cases), so this may not
work in different files (at least 2 jump tables are used instead of 1,
using a dictionary-like setup, see below).

For example, I've seen a Motorola 68K emulator (included in Generator,
a SEGA Genesis emulator) generating 16 C files, each one containing the
code for instructions starting with 0 to F (in hexadecimal). It uses
switch and case statements for the jump table (not computed gotos),
which is more or less the same in practice. I haven't fully read the
source, but it seems that has 2 jump tables to avoid this problem.

I'll see if they can be split, but I just was surprised when I tried
with GCC 4.x and actually compiled it (without optimizations). So I
thought there could be a way to optimize it by telling GCC specific
information about how to do it (as optimizing each block independently
should work fine).

Thanks and Best Regards,
Ale

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 187 bytes --]

Re: Reducing compilation memory usage

[Andrew Haley]

Alejandro Pulver wrote:
> On Thu, 17 Jan 2008 14:22:33 -0500
> Tony Wetmore <tony.wetmore@solipsys.com> wrote:
>
>   
>> Alejandro Pulver wrote:
>>  > As it fails with -O1 and all -fno-*, I tried parameters like
>>  > max-pending-list-length=1 without success.
>>  >
>>  > Do you know about an option or something that could help in this case?
>>
>> Alejandro,
>>
>>     
>
> Hello.
>
> Thank you for your reply.
>
>   
>> I may have missed this earlier, but are the source files causing GCC to 
>> crash particularly large?  Perhaps the problem could be avoided by 
>> splitting the code into more (smaller) files, so that GCC is compiling 
>> less of the code at once.
>>
>>     
>
> Yes, the source is 4MB, consisting of one function with a jump table
> and ~8000 labels (with little code on each), to simulate each machine
> instruction.
>
> GCC doesn't crash, just outputs something like this and exits:
>
> cc1: out of memory allocating 4072 bytes after a total of 1073158016 bytes
>
>   
>> If I understand what you are doing, this code is program-generated, so 
>> you would have to modify the generator program to create multiple files. 
>>   But you might be able to test this by manually splitting one file 
>> yourself.
>>
>> Good luck!
>>
>>     
>
> I really don't know if I could split it, as it's inside the same
> function (all the ~8000 labels with very short code), and it uses
> computed gotos (like the ones generated by a switch statement, with a
> "jump table" so there is no comparison of the cases), so this may not
> work in different files (at least 2 jump tables are used instead of 1,
> using a dictionary-like setup, see below).
>
> For example, I've seen a Motorola 68K emulator (included in Generator,
> a SEGA Genesis emulator) generating 16 C files, each one containing the
> code for instructions starting with 0 to F (in hexadecimal). It uses
> switch and case statements for the jump table (not computed gotos),
> which is more or less the same in practice. I haven't fully read the
> source, but it seems that has 2 jump tables to avoid this problem.
>
> I'll see if they can be split, but I just was surprised when I tried
> with GCC 4.x and actually compiled it (without optimizations). So I
> thought there could be a way to optimize it by telling GCC specific
> information about how to do it (as optimizing each block independently
> should work fine).
>   

Yeah, but that's not what gcc does -- we hold an entire function as 
trees and a data-flow
graph, and then we optimize the whole thing.  In your case the behaviour 
of gcc is not
at all surprising, and the obvious way to solve your problem is to go 
out and buy more
RAM!  Of course we could make gcc more economical, and we could somewhat
reduce memory usage, but you're asking for something really hard.

Andrew.

Re: Reducing compilation memory usage

[Alejandro Pulver]

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

On Fri, 18 Jan 2008 10:35:09 +0000
Andrew Haley <aph@redhat.com> wrote:

> > I really don't know if I could split it, as it's inside the same
> > function (all the ~8000 labels with very short code), and it uses
> > computed gotos (like the ones generated by a switch statement, with a
> > "jump table" so there is no comparison of the cases), so this may not
> > work in different files (at least 2 jump tables are used instead of 1,
> > using a dictionary-like setup, see below).
> >
> > For example, I've seen a Motorola 68K emulator (included in Generator,
> > a SEGA Genesis emulator) generating 16 C files, each one containing the
> > code for instructions starting with 0 to F (in hexadecimal). It uses
> > switch and case statements for the jump table (not computed gotos),
> > which is more or less the same in practice. I haven't fully read the
> > source, but it seems that has 2 jump tables to avoid this problem.
> >

I was wrong, generator uses one function for every instruction.

> > I'll see if they can be split, but I just was surprised when I tried
> > with GCC 4.x and actually compiled it (without optimizations). So I
> > thought there could be a way to optimize it by telling GCC specific
> > information about how to do it (as optimizing each block independently
> > should work fine).
> >   
> 
> Yeah, but that's not what gcc does -- we hold an entire function as 
> trees and a data-flow graph, and then we optimize the whole thing.

I thought that -fno-unit-at-a-time avoided it (and
max-pending-list-length could help). Maybe I misunderstood their
meaning.

Is there a way to estimate the memory usage of the compilation process?

> In your case the behaviour of gcc is not
> at all surprising, and the obvious way to solve your problem is to go 
> out and buy more
> RAM!  Of course we could make gcc more economical, and we could somewhat
> reduce memory usage, but you're asking for something really hard.
> 

I wasn't asking to change the program, I was just asking if there is an
already existing option. Even if I add more RAM, most users won't be
able to build it (and I'm looking for a general solution).

But I guess it's fine enough that GCC 4.x can build it (version 3.x
couldn't).

So far I have 2 alternatives in mind, do you have others (in addition
to adding RAM)?

1. Use 8 functions and files, with only 1000 cases each.
2. Use 2 or more jump tables in the same file, reducing the total
   number of cases (if possible, have to check).

Note that this program is focused on speed (currently the fastest MARS
simulator).

Thanks and Best Regards,
Ale

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 187 bytes --]

Re: Reducing compilation memory usage

[Tony Wetmore]

Alejandro Pulver wrote:
 >> RAM!  Of course we could make gcc more economical, and
 >> we could somewhat reduce memory usage, but you're asking
 >> for something really hard.
 >
 > I wasn't asking to change the program, I was just asking
 > if there is an already existing option.

I think Andrew may have meant that you are asking GCC to do something 
really hard, to optimize a single function that is so large.  And asking 
the compiler to do something that hard has a price -- it requires lots 
of memory, as you have discovered.

 > So far I have 2 alternatives in mind, do you have others (in addition
 > to adding RAM)?
 >
 > 1. Use 8 functions and files, with only 1000 cases each.
 > 2. Use 2 or more jump tables in the same file, reducing the total
 >    number of cases (if possible, have to check).
 >
 > Note that this program is focused on speed (currently the fastest MARS
 > simulator).

Well, it is currently the fastest MARS simulator that only implements a 
small subset of the overall instruction set, right?

And isn't your goal to implement the entire set?  You may indeed have to 
trade some speed for that extra functionality.  Of course, once you are 
finished, you may still have the fast MARS simulator (that implements 
the full instruction set).  But it may not be as fast as one that 
implements only a small fraction of the instructions. :)

Since I haven't looked at the code, I cannot offer good advice on how 
best to restructure it.

But one (hopefully simple) change might be to have every instruction 
implemented by its own function, so you would have 8,000 functions 
(perhaps even each in its own file).  Of course, I have no idea how that 
will impact performance.  Would the optimizer be able to improve 
performance enough to offset the overhead of the additional function 
calls?  I don't know.  I suspect you won't know either, unless you 
implement it and measure the performance.

I assume you have some benchmarks you can run, to compare against the 
original speed.  So you might want to try several different 
modifications, beginning with the simplest to implement.

Good luck!

--
Tony Wetmore

Re: Reducing compilation memory usage

[Andrew Haley]

Tony Wetmore wrote:
> Alejandro Pulver wrote:
>  >> RAM!  Of course we could make gcc more economical, and
>  >> we could somewhat reduce memory usage, but you're asking
>  >> for something really hard.
>  >
>  > I wasn't asking to change the program, I was just asking
>  > if there is an already existing option.
> 
> I think Andrew may have meant that you are asking GCC to do something 
> really hard, to optimize a single function that is so large.  And asking 
> the compiler to do something that hard has a price -- it requires lots 
> of memory, as you have discovered.

I was saying exactly that, thank you for clarifying.

The thing to realize is that it is really hard to do a great job of optimizing
huge functions.  So, it's quite likely that gcc will do a better job of
optimizing a bunch of small functions, with well-contained locality of variables,
than one huge function.

OK, so you will have the overhead of a function call.  But on most architectures
that isn't enormous.

Andrew.

Re: Reducing compilation memory usage

[Tom St Denis]

Andrew Haley wrote:
> Tony Wetmore wrote:
>> Alejandro Pulver wrote:
>>  >> RAM!  Of course we could make gcc more economical, and
>>  >> we could somewhat reduce memory usage, but you're asking
>>  >> for something really hard.
>>  >
>>  > I wasn't asking to change the program, I was just asking
>>  > if there is an already existing option.
>>
>> I think Andrew may have meant that you are asking GCC to do something 
>> really hard, to optimize a single function that is so large.  And 
>> asking the compiler to do something that hard has a price -- it 
>> requires lots of memory, as you have discovered.
>
> I was saying exactly that, thank you for clarifying.
>
> The thing to realize is that it is really hard to do a great job of 
> optimizing
> huge functions.  So, it's quite likely that gcc will do a better job of
> optimizing a bunch of small functions, with well-contained locality of 
> variables,
> than one huge function.
>
> OK, so you will have the overhead of a function call.  But on most 
> architectures
> that isn't enormous.

Dropping some Friday afternoon pair of cents ...

You shouldn't really have large functions unless their machine made 
anyways.  And even then it's best to try and factor them as much as 
possible.  In one of my math libraries I have huge unrolled multipliers, 
for things like 1024x1024 bit multiplications (on a 32-bit platform that 
means 1024 MULADD macros).  Originally, I had all of the multipliers 
[different functions] in a single .C file which was machine generated.  
Later I found GCC performs much better on the same code if I left it one 
huge function per file.

Anyways ... on code that's human-written, you should never really run 
into any of these sorts of limits.  Otherwise, you're not thinking about 
your design properly.

Tom

Re: Reducing compilation memory usage

[Alejandro Pulver]

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

On Fri, 18 Jan 2008 14:07:29 -0500
Tom St Denis <tstdenis@ellipticsemi.com> wrote:

> Andrew Haley wrote:
> > Tony Wetmore wrote:
> >> Alejandro Pulver wrote:
> >>  >> RAM!  Of course we could make gcc more economical, and
> >>  >> we could somewhat reduce memory usage, but you're asking
> >>  >> for something really hard.
> >>  >
> >>  > I wasn't asking to change the program, I was just asking
> >>  > if there is an already existing option.
> >>
> >> I think Andrew may have meant that you are asking GCC to do something 
> >> really hard, to optimize a single function that is so large.  And 
> >> asking the compiler to do something that hard has a price -- it 
> >> requires lots of memory, as you have discovered.
> >
> > I was saying exactly that, thank you for clarifying.
> >
> > The thing to realize is that it is really hard to do a great job of 
> > optimizing
> > huge functions.  So, it's quite likely that gcc will do a better job of
> > optimizing a bunch of small functions, with well-contained locality of 
> > variables,
> > than one huge function.
> >
> > OK, so you will have the overhead of a function call.  But on most 
> > architectures
> > that isn't enormous.
> 
> Dropping some Friday afternoon pair of cents ...
> 
> You shouldn't really have large functions unless their machine made 
> anyways.  And even then it's best to try and factor them as much as 
> possible.  In one of my math libraries I have huge unrolled multipliers, 
> for things like 1024x1024 bit multiplications (on a 32-bit platform that 
> means 1024 MULADD macros).  Originally, I had all of the multipliers 
> [different functions] in a single .C file which was machine generated.  
> Later I found GCC performs much better on the same code if I left it one 
> huge function per file.
> 
> Anyways ... on code that's human-written, you should never really run 
> into any of these sorts of limits.  Otherwise, you're not thinking about 
> your design properly.
> 
> Tom

I'll see how it goes with functions. However a jump table is just a
reference to an array index plus a jump there. With functions, it has
to set the return address and pass variables (creating a new context),
in addition to the jump. Well, in different architectures this could
perform different, and passing variables could be avoided by using
global variables.

Thanks to all of you for the answers. About the compiler I'm very happy
with it, just wanted to do some crazy things.

BTW without the optimizations, it's as fast as the closest competitor.

Best Regards,
Ale

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 187 bytes --]

RE: Reducing compilation memory usage

[John (Eljay) Love-Jensen]

Hi Alejandro,

> Do you know about an option or something that could help in this case?

No, sorry.  Your problem exceeds my experience.

> I've read something about compilers and this high memory usage could be caused by keeping references to variables of other blocks (compilation units, IIRC). So if there is a way to disable that optimizations (tried -fno-unit-at-a-time and max-pending-list-length=1), and to make it the most "linear" as possible, it would help (if there are such additional things I missed).

> Or should I ask this more specific question in another place?

I think this is the best (and correct) forum for your question.

Sincerely,
--Eljay