Compilation of lengthy C++ Files

Compilation of lengthy C++ Files

[Kai Song]

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

Dear GCC Developers,

I am unsuccessfully using g++ 12.0.4 to compile lengthy c++ codes. Those
codes are automatically generated from my own code-generator tools that
depend on parameters p.
Typical applications are:
- Taylor series of order p inserted into consistency conditions of
numerical schemes, to determine optimal method parameters (think of, e.g.,
Runge-Kutta methods)
- recursive automatic code transformation (think of adjoints of adjoints of
adjoints...) of recursion level p
- Hilbert curves or other space-filling curves to generate code that
simulates cache utilization in a Monte-Carlo context

I verify that for small p the codes compile and execute to the expected
result. However, there is always a threshold for p so that the generated
cpp file is so long that the compiler will just terminate after ~10min
without monitor output but return the value +1.
My cpp files range from 600k LOC up to 1Bio LOC. Often, the file comprises
of one single c++ template class member function definition that relies on
a few thousand lines of template-classes.

I would like to know:
1) Am I doing something wrong in that GCC should be able to compile lengthy
codes?
2) Is it known that GCC is unable to compile lengthy codes?
3) Is it acknowledged that a compiler's ability to compile large files is
relevant?
4) Are possible roots known for this inability and are these deliberate?

To give just one glimpse at the relevance: I analyzed methods for solving
F(x)=0 by using k stages -DF(x)*vk= F(x+sum_i bki*vi).
Compiling a Taylor series code with p=3, I was able to verify that three
iterations of the Chord method converge of fourth order, thus surpassing
Newton's method (same cost, but only quadratic order).
Checking whether any four-stage method exists that converges of fifth order
necessitates the compilation of a single cpp file function that is 1.2Mio
lines of code long. Since 2018 I am occasionally trying to find a way to
compile it.
I also used this code to automatically generate Butcher-type tableaus for
generalizations to initial-value problem solvers. One could really only
dream of what scientific leaps become possible only if lengthy codes were
compilable.

Right now, whenever a situation of this kind occurs, I have to give up, cut
my (possibly months of work) losses, and move on to working on something
else -- because it seems there is nothing I can do about it.
Even spitting a code of 1Bio LOC into chunks of 100k LOC and then
automating to compile and link these in turn seems hopeless; and probably
the linker has limitations as well..
But since this problem is to frequent to my life, I would really like to
find out how to fix it once and for all.
This is a problem that I have been suffering from severely for years
because it basically cripples how I can put my mathematical expertise to
use.

Thank you for getting in touch.

Kind regards,
Kai

Re: Compilation of lengthy C++ Files

[Jonathan Wakely]

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

On Wed, 18 Oct 2023, 17:05 Kai Song via Gcc-help, <gcc-help@gcc.gnu.org>
wrote:

> Dear GCC Developers,
>
> I am unsuccessfully using g++ 12.0.4 to compile lengthy c++ codes. Those
> codes are automatically generated from my own code-generator tools that
> depend on parameters p.
> Typical applications are:
> - Taylor series of order p inserted into consistency conditions of
> numerical schemes, to determine optimal method parameters (think of, e.g.,
> Runge-Kutta methods)
> - recursive automatic code transformation (think of adjoints of adjoints of
> adjoints...) of recursion level p
> - Hilbert curves or other space-filling curves to generate code that
> simulates cache utilization in a Monte-Carlo context
>
> I verify that for small p the codes compile and execute to the expected
> result. However, there is always a threshold for p so that the generated
> cpp file is so long that the compiler will just terminate after ~10min
> without monitor output but return the value +1.
> My cpp files range from 600k LOC up to 1Bio LOC. Often, the file comprises
> of one single c++ template class member function definition that relies on
> a few thousand lines of template-classes.
>
> I would like to know:
> 1) Am I doing something wrong in that GCC should be able to compile lengthy
> codes?
>

Do you have enough RAM?

2) Is it known that GCC is unable to compile lengthy codes?
>

Yes, there are loads of bug reports about this kind of thing, some fixed,
some not.

3) Is it acknowledged that a compiler's ability to compile large files is
> relevant?
>

Yes, within reason. Some generated code is just silly and could be written
differently.

4) Are possible roots known for this inability and are these deliberate?
>

It depends on the code. Sometimes there are quadratic (or worse) algorithms
involved. Sometimes GCC's intermediate representation is just too memory
hungry.


> To give just one glimpse at the relevance: I analyzed methods for solving
> F(x)=0 by using k stages -DF(x)*vk= F(x+sum_i bki*vi).
> Compiling a Taylor series code with p=3, I was able to verify that three
> iterations of the Chord method converge of fourth order, thus surpassing
> Newton's method (same cost, but only quadratic order).
> Checking whether any four-stage method exists that converges of fifth order
> necessitates the compilation of a single cpp file function that is 1.2Mio
> lines of code long.


That's going to use insane amounts of memory just to represent the
function, before even trying to analyse it out optimise it.

Since 2018 I am occasionally trying to find a way to
> compile it.
> I also used this code to automatically generate Butcher-type tableaus for
> generalizations to initial-value problem solvers. One could really only
> dream of what scientific leaps become possible only if lengthy codes were
> compilable.
>
> Right now, whenever a situation of this kind occurs, I have to give up, cut
> my (possibly months of work) losses, and move on to working on something
> else -- because it seems there is nothing I can do about it.
>

Have you tried using clang instead?

Even spitting a code of 1Bio LOC into chunks of 100k LOC and then
> automating to compile and link these in turn seems hopeless; and probably
> the linker has limitations as well..
>

Very different ones though.

But since this problem is to frequent to my life, I would really like to
> find out how to fix it once and for all.
> This is a problem that I have been suffering from severely for years
> because it basically cripples how I can put my mathematical expertise to
> use.
>
> Thank you for getting in touch.
>
> Kind regards,
> Kai
>

Re: Compilation of lengthy C++ Files

[Andrew Haley]

> On Wed, 18 Oct 2023, 17:05 Kai Song via Gcc-help, <gcc-help@gcc.gnu.org>
> wrote:
> 
>> But since this problem is to frequent to my life, I would really like to
>> find out how to fix it once and for all.
>> This is a problem that I have been suffering from severely for years
>> because it basically cripples how I can put my mathematical expertise to
>> use.

It's time to generate subroutines. When you output a slab of code,
don't just spit it all out inline, but put it into a subroutine.

-- 
Andrew Haley  (he/him)
Java Platform Lead Engineer
Red Hat UK Ltd. <https://www.redhat.com>
https://keybase.io/andrewhaley
EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671

Re: Compilation of lengthy C++ Files

[David Brown]

On 18/10/2023 18:04, Kai Song via Gcc-help wrote:
> Dear GCC Developers,
> 
> I am unsuccessfully using g++ 12.0.4 to compile lengthy c++ codes. Those
> codes are automatically generated from my own code-generator tools that
> depend on parameters p.
> Typical applications are:
> - Taylor series of order p inserted into consistency conditions of
> numerical schemes, to determine optimal method parameters (think of, e.g.,
> Runge-Kutta methods)
> - recursive automatic code transformation (think of adjoints of adjoints of
> adjoints...) of recursion level p
> - Hilbert curves or other space-filling curves to generate code that
> simulates cache utilization in a Monte-Carlo context
> 
> I verify that for small p the codes compile and execute to the expected
> result. However, there is always a threshold for p so that the generated
> cpp file is so long that the compiler will just terminate after ~10min
> without monitor output but return the value +1.
> My cpp files range from 600k LOC up to 1Bio LOC. Often, the file comprises
> of one single c++ template class member function definition that relies on
> a few thousand lines of template-classes.
> 
> I would like to know:
> 1) Am I doing something wrong in that GCC should be able to compile lengthy
> codes?
> 2) Is it known that GCC is unable to compile lengthy codes?
> 3) Is it acknowledged that a compiler's ability to compile large files is
> relevant?
> 4) Are possible roots known for this inability and are these deliberate?
> 

I am curious to know why you are generating code like this.  I can see 
how some code generators for mathematical code could easily produce 
large amounts of code, but it is rarely ideal for real-world uses.  Such 
flattened code can reduce overheads and improve optimisation 
opportunities (like inlining, constant folding, function cloning, etc.) 
for small cases, but then they get impractical for compiling while the 
costs for cache misses outweigh the overhead cost for the loops or 
recursion needed for general solutions.

Any compiler is going to be targeted and tuned towards "normal" or 
"typical" code.  That means primarily hand-written code, or smaller 
generated code.  I know that some systems generate very large functions 
or large files, but those are primarily C code, and the code is often 
very simple and "flat".  (Applications here include compilers that use C 
as a intermediary target language, and simulators of various kinds.)  It 
typically makes sense to disable certain optimisation passes here, and a 
number of passes scale badly (quadratic or perhaps worse) with function 
size.

However, if you are generating huge templates in C++, you are going a 
big step beyond that - templates are, in a sense, code generators 
themselves that run at compile time as an interpreted meta-language.  I 
don't expect that there has been a deliberate decision to limit GCC's 
handling of larger files, but I can't imagine that huge templates are a 
major focus for the compiler development.  And I would expect enormous 
memory use and compile times even when it does work.

Re: Compilation of lengthy C++ Files

[David Brown]

On 18/10/2023 18:04, Kai Song via Gcc-help wrote:
> Dear GCC Developers,
> 
> I am unsuccessfully using g++ 12.0.4 to compile lengthy c++ codes. Those
> codes are automatically generated from my own code-generator tools that
> depend on parameters p.
> Typical applications are:
> - Taylor series of order p inserted into consistency conditions of
> numerical schemes, to determine optimal method parameters (think of, e.g.,
> Runge-Kutta methods)
> - recursive automatic code transformation (think of adjoints of adjoints of
> adjoints...) of recursion level p
> - Hilbert curves or other space-filling curves to generate code that
> simulates cache utilization in a Monte-Carlo context
> 
> I verify that for small p the codes compile and execute to the expected
> result. However, there is always a threshold for p so that the generated
> cpp file is so long that the compiler will just terminate after ~10min
> without monitor output but return the value +1.
> My cpp files range from 600k LOC up to 1Bio LOC. Often, the file comprises
> of one single c++ template class member function definition that relies on
> a few thousand lines of template-classes.
> 
> I would like to know:
> 1) Am I doing something wrong in that GCC should be able to compile lengthy
> codes?
> 2) Is it known that GCC is unable to compile lengthy codes?
> 3) Is it acknowledged that a compiler's ability to compile large files is
> relevant?
> 4) Are possible roots known for this inability and are these deliberate?
> 

I am curious to know why you are generating code like this.  I can see 
how some code generators for mathematical code could easily produce 
large amounts of code, but it is rarely ideal for real-world uses.  Such 
flattened code can reduce overheads and improve optimisation 
opportunities (like inlining, constant folding, function cloning, etc.) 
for small cases, but then they get impractical for compiling while the 
costs for cache misses outweigh the overhead cost for the loops or 
recursion needed for general solutions.

Any compiler is going to be targeted and tuned towards "normal" or 
"typical" code.  That means primarily hand-written code, or smaller 
generated code.  I know that some systems generate very large functions 
or large files, but those are primarily C code, and the code is often 
very simple and "flat".  (Applications here include compilers that use C 
as a intermediary target language, and simulators of various kinds.)  It 
typically makes sense to disable certain optimisation passes here, and a 
number of passes scale badly (quadratic or perhaps worse) with function 
size.

However, if you are generating huge templates in C++, you are going a 
big step beyond that - templates are, in a sense, code generators 
themselves that run at compile time as an interpreted meta-language.  I 
don't expect that there has been a deliberate decision to limit GCC's 
handling of larger files, but I can't imagine that huge templates are a 
major focus for the compiler development.  And I would expect enormous 
memory use and compile times even when it does work.

Re: Compilation of lengthy C++ Files

[Kai Song]

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

Thank you for your feedback!

I forward the requested information to everyone as it may be relevant.

>> Jonathan & David: How much RAM? Quadratic time-complexity.
I have 256GB of RAM and 64 cores. I launch g++ from the Windows 10
Terminal. From my information, Windows 10 will not limit the resources
given to the Terminal.
I am perfectly fine if compile times are in the time-span of months. For
the Runge-Kutta method, I would be happy with compile times of years as
this would mean I have a faster method in a few years.

>> Probably everyone: Is your code reasonable?
When trying to code-gen into shorter code, there are a few considerations:
1) Will any generated application be limitable into a certain volume of
source-code? Certainly not, so why even argue on one particular instance of
volume?
2) May it necessitate significant amounts of work to enable a
code-generator to produce shorter code? Certainly.
3) Suppose a code-generator exploits structure of a given user-provided
problem instance for generation of shorter code. Will this mean the set of
feasible problems treatable by the code-generator shinks? Likely.
4) Is 99% of the code trivial and should be compilable in read-time? I
believe so, given my naive information.
5) Should months of work be invested into generating shorter code in order
for that to be able to compile in 5 minutes when really this code is
compiled and used only once in a lifetime? I am unsure about this.

The stinging issue of argument may be on aspect 4), which makes it seem as
though the other 99% should be wrappable into functions.
The, if we call it so, mis-expectation is that then clean interfaces to
these functions are generatable or may even not exist. To give an example,
suppose a skein of code-strings in which each invoked 1% non-trivial code
is changing one string so that it induces chaos into the naming of all
other temporary variable names, causing mismatch between contiguity between
data at code-gen time and generated-code time. That is the central issue
that I --admittedly-- brute-force by committing into lengthy code.

>> Jonathan: Have you tried using clang instead?

I tried ICC (won't install successfully on my Windows 10 PC) and then CLANG
17.0.0 .

CLANG requires a provided STL, so I used the ones from Microsoft Visual
Studio 2022, which I referenced via the -isystem flag.
In order to compile it, I had to make tons of changes that g++ would not
have complained about; like putting a "d" at the end of a floating-point
value.

To test all these changes, I chose a smaller codegen parameter for which
g++ is able to compile the code and yields the expected result.
On that smaller code, clang instead fails with the following error:

// source code from line 201: therein, k is a template parameter, nx is a
static constexpr std::array<const size_t>, and mx is a static constexpr
size_t .
random_generator.template setRandn<(size_t)(mx-nx[k])>(  x+nx[k]);
random_generator.template setRandn<(size_t)(mx-nx[k])>(  xp+nx[k]);
random_generator.template setRandn<(size_t)(mb-nb[k])>( Ax+nb[k]);
random_generator.template setRandn<(size_t)(mb-nb[k])>( Axp+nb[k]);
random_generator.template setRandn<(size_t)(mx-nx[k])>( dx+nx[k]);
random_generator.template setRandn<(size_t)(mb-nb[k])>(dAx+nb[k]);
for(size_t i=nc[k];i<mc;++i){ calc.template setRandn<numPages>(gc[i]);
calc.template setRandn<numPages>(gc0[i]); }
random_generator.template setRandn<(size_t)(mx-nx[k])>( x0+nx[k]);

// clang compiler error message
error: no matching member function for call to 'setRandn'
206 | random_generator.template setRandn<(size_t)(mx-nx[k])>( x0+nx[k]);

The error appears unsensical to me, particularly since g++ was able to
compile it, and since clang accepts the same expression five lines earlier
but not in the present line.
The code snippet is from a test class that adds noise to vector-components
that should be uninvolved in certain test computations.

If it helps, I can work on making it compilable to clang in an effort to
identify up to which size either compiler is capable of compiling it.
Please let me know what helps.

Kind regards,
Kai

On Thu, Oct 19, 2023 at 2:47 PM David Brown <david@westcontrol.com> wrote:

> On 18/10/2023 18:04, Kai Song via Gcc-help wrote:
> > Dear GCC Developers,
> >
> > I am unsuccessfully using g++ 12.0.4 to compile lengthy c++ codes. Those
> > codes are automatically generated from my own code-generator tools that
> > depend on parameters p.
> > Typical applications are:
> > - Taylor series of order p inserted into consistency conditions of
> > numerical schemes, to determine optimal method parameters (think of,
> e.g.,
> > Runge-Kutta methods)
> > - recursive automatic code transformation (think of adjoints of adjoints
> of
> > adjoints...) of recursion level p
> > - Hilbert curves or other space-filling curves to generate code that
> > simulates cache utilization in a Monte-Carlo context
> >
> > I verify that for small p the codes compile and execute to the expected
> > result. However, there is always a threshold for p so that the generated
> > cpp file is so long that the compiler will just terminate after ~10min
> > without monitor output but return the value +1.
> > My cpp files range from 600k LOC up to 1Bio LOC. Often, the file
> comprises
> > of one single c++ template class member function definition that relies
> on
> > a few thousand lines of template-classes.
> >
> > I would like to know:
> > 1) Am I doing something wrong in that GCC should be able to compile
> lengthy
> > codes?
> > 2) Is it known that GCC is unable to compile lengthy codes?
> > 3) Is it acknowledged that a compiler's ability to compile large files is
> > relevant?
> > 4) Are possible roots known for this inability and are these deliberate?
> >
>
> I am curious to know why you are generating code like this.  I can see
> how some code generators for mathematical code could easily produce
> large amounts of code, but it is rarely ideal for real-world uses.  Such
> flattened code can reduce overheads and improve optimisation
> opportunities (like inlining, constant folding, function cloning, etc.)
> for small cases, but then they get impractical for compiling while the
> costs for cache misses outweigh the overhead cost for the loops or
> recursion needed for general solutions.
>
> Any compiler is going to be targeted and tuned towards "normal" or
> "typical" code.  That means primarily hand-written code, or smaller
> generated code.  I know that some systems generate very large functions
> or large files, but those are primarily C code, and the code is often
> very simple and "flat".  (Applications here include compilers that use C
> as a intermediary target language, and simulators of various kinds.)  It
> typically makes sense to disable certain optimisation passes here, and a
> number of passes scale badly (quadratic or perhaps worse) with function
> size.
>
> However, if you are generating huge templates in C++, you are going a
> big step beyond that - templates are, in a sense, code generators
> themselves that run at compile time as an interpreted meta-language.  I
> don't expect that there has been a deliberate decision to limit GCC's
> handling of larger files, but I can't imagine that huge templates are a
> major focus for the compiler development.  And I would expect enormous
> memory use and compile times even when it does work.
>
>
>

Re: Compilation of lengthy C++ Files

[Jonathan Wakely]

On Thu, 19 Oct 2023 at 15:17, Kai Song via Gcc-help
<gcc-help@gcc.gnu.org> wrote:
>
> Thank you for your feedback!
>
> I forward the requested information to everyone as it may be relevant.
>
> >> Jonathan & David: How much RAM? Quadratic time-complexity.
> I have 256GB of RAM and 64 cores. I launch g++ from the Windows 10
> Terminal. From my information, Windows 10 will not limit the resources
> given to the Terminal.
> I am perfectly fine if compile times are in the time-span of months. For
> the Runge-Kutta method, I would be happy with compile times of years as
> this would mean I have a faster method in a few years.
>
> >> Probably everyone: Is your code reasonable?
> When trying to code-gen into shorter code, there are a few considerations:
> 1) Will any generated application be limitable into a certain volume of
> source-code? Certainly not, so why even argue on one particular instance of
> volume?

I have no idea what this means.

> 2) May it necessitate significant amounts of work to enable a
> code-generator to produce shorter code? Certainly.

Well at the moment your code doesn't even compile. So you can keep
generating billion line functions that don't work, or you could try
refactoring it. It might not be easy, but if it compiles and works,
surely that's better than billion line functions that don't work?


> 3) Suppose a code-generator exploits structure of a given user-provided
> problem instance for generation of shorter code. Will this mean the set of
> feasible problems treatable by the code-generator shinks? Likely.

I don't see why that should be true.

> 4) Is 99% of the code trivial and should be compilable in read-time? I
> believe so, given my naive information.

A billion lines of trivial operations still consumes ridiculous
amounts of resources to compile. Your naive view doesn't seem
relevant.

> 5) Should months of work be invested into generating shorter code in order
> for that to be able to compile in 5 minutes when really this code is
> compiled and used only once in a lifetime? I am unsure about this.
>
> The stinging issue of argument may be on aspect 4), which makes it seem as
> though the other 99% should be wrappable into functions.
> The, if we call it so, mis-expectation is that then clean interfaces to
> these functions are generatable or may even not exist. To give an example,
> suppose a skein of code-strings in which each invoked 1% non-trivial code
> is changing one string so that it induces chaos into the naming of all
> other temporary variable names, causing mismatch between contiguity between
> data at code-gen time and generated-code time. That is the central issue
> that I --admittedly-- brute-force by committing into lengthy code.

I don't understand this either, sorry.

Nothing you have said actually explains why you can't refactor the
code into utility functions that avoid doing everything in one huge
function.

>
> >> Jonathan: Have you tried using clang instead?
>
> I tried ICC (won't install successfully on my Windows 10 PC) and then CLANG
> 17.0.0 .
>
> CLANG requires a provided STL, so I used the ones from Microsoft Visual
> Studio 2022, which I referenced via the -isystem flag.
> In order to compile it, I had to make tons of changes that g++ would not
> have complained about; like putting a "d" at the end of a floating-point
> value.

Eh?!

You must be doing something wrong. Clang does not require that.

> To test all these changes, I chose a smaller codegen parameter for which
> g++ is able to compile the code and yields the expected result.
> On that smaller code, clang instead fails with the following error:
>
> // source code from line 201: therein, k is a template parameter, nx is a
> static constexpr std::array<const size_t>, and mx is a static constexpr
> size_t .
> random_generator.template setRandn<(size_t)(mx-nx[k])>(  x+nx[k]);
> random_generator.template setRandn<(size_t)(mx-nx[k])>(  xp+nx[k]);
> random_generator.template setRandn<(size_t)(mb-nb[k])>( Ax+nb[k]);
> random_generator.template setRandn<(size_t)(mb-nb[k])>( Axp+nb[k]);
> random_generator.template setRandn<(size_t)(mx-nx[k])>( dx+nx[k]);
> random_generator.template setRandn<(size_t)(mb-nb[k])>(dAx+nb[k]);
> for(size_t i=nc[k];i<mc;++i){ calc.template setRandn<numPages>(gc[i]);
> calc.template setRandn<numPages>(gc0[i]); }
> random_generator.template setRandn<(size_t)(mx-nx[k])>( x0+nx[k]);
>
> // clang compiler error message
> error: no matching member function for call to 'setRandn'
> 206 | random_generator.template setRandn<(size_t)(mx-nx[k])>( x0+nx[k]);
>
> The error appears unsensical to me, particularly since g++ was able to
> compile it, and since clang accepts the same expression five lines earlier
> but not in the present line.
> The code snippet is from a test class that adds noise to vector-components
> that should be uninvolved in certain test computations.
>
> If it helps, I can work on making it compilable to clang in an effort to
> identify up to which size either compiler is capable of compiling it.
> Please let me know what helps.
>
> Kind regards,
> Kai
>
> On Thu, Oct 19, 2023 at 2:47 PM David Brown <david@westcontrol.com> wrote:
>
> > On 18/10/2023 18:04, Kai Song via Gcc-help wrote:
> > > Dear GCC Developers,
> > >
> > > I am unsuccessfully using g++ 12.0.4 to compile lengthy c++ codes. Those
> > > codes are automatically generated from my own code-generator tools that
> > > depend on parameters p.
> > > Typical applications are:
> > > - Taylor series of order p inserted into consistency conditions of
> > > numerical schemes, to determine optimal method parameters (think of,
> > e.g.,
> > > Runge-Kutta methods)
> > > - recursive automatic code transformation (think of adjoints of adjoints
> > of
> > > adjoints...) of recursion level p
> > > - Hilbert curves or other space-filling curves to generate code that
> > > simulates cache utilization in a Monte-Carlo context
> > >
> > > I verify that for small p the codes compile and execute to the expected
> > > result. However, there is always a threshold for p so that the generated
> > > cpp file is so long that the compiler will just terminate after ~10min
> > > without monitor output but return the value +1.
> > > My cpp files range from 600k LOC up to 1Bio LOC. Often, the file
> > comprises
> > > of one single c++ template class member function definition that relies
> > on
> > > a few thousand lines of template-classes.
> > >
> > > I would like to know:
> > > 1) Am I doing something wrong in that GCC should be able to compile
> > lengthy
> > > codes?
> > > 2) Is it known that GCC is unable to compile lengthy codes?
> > > 3) Is it acknowledged that a compiler's ability to compile large files is
> > > relevant?
> > > 4) Are possible roots known for this inability and are these deliberate?
> > >
> >
> > I am curious to know why you are generating code like this.  I can see
> > how some code generators for mathematical code could easily produce
> > large amounts of code, but it is rarely ideal for real-world uses.  Such
> > flattened code can reduce overheads and improve optimisation
> > opportunities (like inlining, constant folding, function cloning, etc.)
> > for small cases, but then they get impractical for compiling while the
> > costs for cache misses outweigh the overhead cost for the loops or
> > recursion needed for general solutions.
> >
> > Any compiler is going to be targeted and tuned towards "normal" or
> > "typical" code.  That means primarily hand-written code, or smaller
> > generated code.  I know that some systems generate very large functions
> > or large files, but those are primarily C code, and the code is often
> > very simple and "flat".  (Applications here include compilers that use C
> > as a intermediary target language, and simulators of various kinds.)  It
> > typically makes sense to disable certain optimisation passes here, and a
> > number of passes scale badly (quadratic or perhaps worse) with function
> > size.
> >
> > However, if you are generating huge templates in C++, you are going a
> > big step beyond that - templates are, in a sense, code generators
> > themselves that run at compile time as an interpreted meta-language.  I
> > don't expect that there has been a deliberate decision to limit GCC's
> > handling of larger files, but I can't imagine that huge templates are a
> > major focus for the compiler development.  And I would expect enormous
> > memory use and compile times even when it does work.
> >
> >
> >

Re: Compilation of lengthy C++ Files

[Kai Song]

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

Dear everyone,

Now CLANG does compile the lengthy code of 600k LOC into a functioning
object that can be linked and yields the expected result.
Clang was just reluctant to make a certain pointer type-cast by itself.

Given that CLANG compiles the object, what can be inferred?

Further questions:
- Are there any pragmas that can help the compiler identify code portions
with linear compile-complexity?
- What compiler flag combination should I try to increase chances at
successful compilation of lengthy files?


@Jonathan, I am happy to clarify:

> >
> > 1) Will any generated application be limitable into a certain volume of
> > source-code? Certainly not, so why even argue on one particular instance
> of
> > volume?
>
> I have no idea what this means.
>

Is every program on earth writable into X lines of code? Then, which value
is X?
If X exists and is known, one can discuss whether source code of length Y
should exist.


> > 2) May it necessitate significant amounts of work to enable a
> > code-generator to produce shorter code? Certainly.
>
> Well at the moment your code doesn't even compile. So you can keep
> generating billion line functions that don't work, or you could try
> refactoring it. It might not be easy, but if it compiles and works,
> surely that's better than billion line functions that don't work?
>

But certainly, executing a code of length N is an easier problem (linear in
N) than figuring out whether a code of length N can be reduced into length
M (exponentially hard in N).
Also, being able to execute a code of length N is by far more useful than
knowing for one niche class of problems by how much N can be reduced, not
even mentioning whether M is smaller enough..


> > 3) Suppose a code-generator exploits structure of a given user-provided
> > problem instance for generation of shorter code. Will this mean the set
> of
> > feasible problems treatable by the code-generator shinks? Likely.
>
> I don't see why that should be true.
>

In order to seek a structure that the code-generator would track from the
user-provided instance, that information-processor would have to be
implemented, verified, executed, and function reliably.
Whenever the structure does not apply, the benefit cannot be stroked. Then
still the program length won't reduce and all effort was in vain.

In the context of information theory, the general hyperbola applies that
then attempting to solve problems more "smartly", this results in a solver
that is more efficient but less robust.
Efficacy, robustness, and genericity do always form a Pareto curve. Think
of higher-order numerical methods, which always add overhead while only
paying off when instances are sufficiently smooth.
Or think of advanced alpha-beta-pruning-schemes that only work beneficially
for highly structured niche problems, such as chess.


>
> > 4) Is 99% of the code trivial and should be compilable in read-time? I
> > believe so, given my naive information.
>
> A billion lines of trivial operations still consumes ridiculous
> amounts of resources to compile. Your naive view doesn't seem
> relevant.
>

I am a prisoner of myself, so I must respect that you say I cannot know.
I do know that I would know how to compute my particular code in linear
time of length with pencil and paper -- just my human machine-speed is 9
orders of magnitude too slow.


> > 5) Should months of work be invested into generating shorter code in
> order
> > for that to be able to compile in 5 minutes when really this code is
> > compiled and used only once in a lifetime? I am unsure about this.
> >
> > The stinging issue of argument may be on aspect 4), which makes it seem
> as
> > though the other 99% should be wrappable into functions.
> > The, if we call it so, mis-expectation is that then clean interfaces to
> > these functions are generatable or may even not exist. To give an
> example,
> > suppose a skein of code-strings in which each invoked 1% non-trivial code
> > is changing one string so that it induces chaos into the naming of all
> > other temporary variable names, causing mismatch between contiguity
> between
> > data at code-gen time and generated-code time. That is the central issue
> > that I --admittedly-- brute-force by committing into lengthy code.
>
> I don't understand this either, sorry.
>

Argument 5 was on the proportionality between work time and compile time. I
should rather spend 5 minutes into coding and 5 months into compiling than
1 week into coding and 5min into compiling, unless the code must be
compiled and run multiple times.

The elaboration on four gives a plastical description of code pattern that
results in chaos, supporting the hypothesis that the problem of reducing a
program of length N is in O(exp(N)) whereas running it is in O(N).


> Nothing you have said actually explains why you can't refactor the
> code into utility functions that avoid doing everything in one huge
> function.
>

Because there are no two pieces of code that are exactly identical. The
relative distance of two variables being involved into an identical formula
will change with every line.
Example:
Line 1000: tmp[100]=foo(tmp[101],tmp[102]);
Line 2000: tmp[200]=foo(tmp[201],tmp[203]); // dang it, not tmp[202] but
tmp[203]
It is like with penrose tiling. It seems all identical but the details
break it. You just do not find two identical local areas. No-where. And if,
you have to particularly search for them by brute-force, and that should
become useless whenever the particular pattern you try to find does just
not exist in that particular user's instance.


>
> >
> > >> Jonathan: Have you tried using clang instead?
> >
> > I tried ICC (won't install successfully on my Windows 10 PC) and then
> CLANG
> > 17.0.0 .
> >
> > CLANG requires a provided STL, so I used the ones from Microsoft Visual
> > Studio 2022, which I referenced via the -isystem flag.
> > In order to compile it, I had to make tons of changes that g++ would not
> > have complained about; like putting a "d" at the end of a floating-point
> > value.
>
> Eh?!
>
> You must be doing something wrong. Clang does not require that.
>

As I now found, ICC might now work because my CPU is AMD.
I was told LLVM does not come with its own STL. I understand you say it
does.
While g++ accepts Tfloat a=0.1d; the same appeared untrue for CLANG.

Kind regards,
Kai

Re: Compilation of lengthy C++ Files

[David Brown]

On 19/10/2023 16:16, Kai Song via Gcc-help wrote:
> Thank you for your feedback!
> 
> I forward the requested information to everyone as it may be relevant.

(Note - I am not a GCC developer, I am just a user, whereas Jonathan is 
one of the key developers of GCC.  So if he ever writes something that 
contradicts me, believe Jonathan, not me!)

> 
>>> Jonathan & David: How much RAM? Quadratic time-complexity.
> I have 256GB of RAM and 64 cores. I launch g++ from the Windows 10
> Terminal. From my information, Windows 10 will not limit the resources
> given to the Terminal.

I don't want to sound anti-Windows, but I think it is very unusual to 
see someone using Windows with something like this.  My own experience, 
as someone who has both Linux and Windows machines on my desk since I 
have work that uses both systems, is that big builds with GCC can be at 
least twice as fast on Linux than Windows with the same hardware.  Linux 
is simply better than Windows for this kind of thing - it has better 
handling of large amounts of ram, better multi-core handling, better 
file handling and better handling of multiple processes.  (Windows is 
better for some other things, but not this kind of thing.)  What kind of 
difference it would make for you here, I don't know - but with the 
massive compile times you have, it is worth the effort checking.

It also seems crazy to use off-the-shelf builds of GCC here, if that is 
what you are doing - under the same circumstances, I'd be looking at 
building GCC from source with the best choice of flags to shave the last 
few percent off the times.  I'd be using "-march=native" to fine-tune 
GCC to get the best from my 64 cores.  (Consider a Linux distro like 
Gentoo that compiles everything from source if you don't want to learn 
how to build GCC yourself.)

> I am perfectly fine if compile times are in the time-span of months. For
> the Runge-Kutta method, I would be happy with compile times of years as
> this would mean I have a faster method in a few years.
> 

But would the resulting binary, generated after months, actually be 
faster?  A big source code is going to result in a big binary, which is 
likely to be slower in practice due to cache misses.

Also note that there are pretty much no calculations taking years to run 
that are actually worth running.  If a calculation is going to take 2 
years to do, you are better off selling your current computer, investing 
the money in a fund, taking it out in a years time, buying a new 
computer at that point which is three times the speed, and running the 
calculation in 8 months - finishing sooner than if you started today 
with your current machine.

Perhaps I am completely misunderstanding what you are actually trying to 
achieve.

In my mind, I am comparing your task to something simpler (one that 
everyone here can understand, avoiding the post-grad level mathematics). 
  Sometimes it is nice to have bigger integer types available than the 
usual biggest size of 64 bits.  It's reasonably straightforward to make 
a C++ class for a 128 bit integer type with operator overloading, built 
from two 64-bit integers.  Then you can make a 256 bit integer type 
build from two 128 bit integers.  Then a template that does this 
automatically, and your recursive template setup will let you write:

	using uint4096_t = big_uint<14>;	// 2 ** 14 bits

and you are ready to use it in your RSA encryption code.  It sounds 
simple - and works well for 128-bit and 256-bit integers.  But while it 
will compile for 4096-bit integers, and give the right answers, it is 
likely to be terrible in performance.  Long before reaching 4096 bits, 
it will make sense to move to arbitrary-precision integer libraries, 
using loops over 64-bit chunks rather than just throwing a big template 
at the compiler and drinking coffee during compiles.

Your problem sounds like the same principle, only more so.  But as I 
say, maybe I am missing something vital in my understanding of your problem.

Re: Compilation of lengthy C++ Files

[David Brown]

On 19/10/2023 17:11, Kai Song via Gcc-help wrote:

(It can be helpful to include attributions when replying, so that it is 
clear who wrote what.  Thus you should have this line included:)

 > On 19/10/2023 16:26, Jonathan Wakely via Gcc-help wrote:


>> Nothing you have said actually explains why you can't refactor the
>> code into utility functions that avoid doing everything in one huge
>> function.
>>
> 
> Because there are no two pieces of code that are exactly identical. The
> relative distance of two variables being involved into an identical formula
> will change with every line.
> Example:
> Line 1000: tmp[100]=foo(tmp[101],tmp[102]);
> Line 2000: tmp[200]=foo(tmp[201],tmp[203]); // dang it, not tmp[202] but
> tmp[203]
> It is like with penrose tiling. It seems all identical but the details
> break it. You just do not find two identical local areas. No-where. And if,
> you have to particularly search for them by brute-force, and that should
> become useless whenever the particular pattern you try to find does just
> not exist in that particular user's instance.
> 

Surely this is screaming out for a table?

const int foo_table[][3] = {
     { 100, 101, 102 },
     { 200, 201, 203 },
	...
};


	for (int i = 0; i < 100000000; i++) {
		tmp[foo_table[i][0]] =
			foo(tmp[foo_table[i][1]], tmp[foo_table[i][2]]);
	}

This will turn your million-line program into a four line program with a 
big table, which will compile quickly and run faster.

Re: Compilation of lengthy C++ Files

[Kai Song]

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

@David: I am sorry there was a misunderstanding with the example. You wrote
four lines of code to be able to replace two lines of code into a for-loop
of length 2, somewhere in a 1Bio line program where this pattern
coincidentally occured once in one generated instance. (In the next
instance, the "pattern" might not occur, so then you just added four
lines.) Also, it is unclear how you would implement in turn the code which
locates the line 200 and decides to replace it with the for-loop. Further,
you left unclear where to place this for-loop (in line 100 or line 200?),
both of which will lead to the wrong result in the generated program due to
false assumption on raise-conditions.

I think my initial question has been mis-correlated. I think so because we
drift into a discussion of speed and what is better and faster and
what-not. But this is not the question at all.
The setting is rather: I have a list of lengthy instructions. Think of a
grocery list. The most convenient language for me to write this grocery
list in is c++.
Now I don't care whether my doctor thinks I want to eat this all by myself
or on a weekly basis, and likes that thought or not. I just need to get the
groceries.
I can get them myself. In this case, it would mean I have to learn to
generate code of linear compile-complexity into assembly directly by myself.

I am not even interested in the compilation per se. I just need to be able
to evaluate the code as written.
I am equally fine with using an interpreted language or a different
language. But interpreters have the exact same issue: They refuse to start
computing a flat program code when the file containing it is too big.
So suppose I have a substitution of Taylor serieses into serieses and it
_does_ become chaotic after reordering of terms. That is after all the work
that the program does. That is what it is made for.
And now I just want some way to evaluate that formula once to tell me
whether y=f(x) yields y=0 for a particular value of x. This is as basic as
it gets.

I suppose the enablement of this capability is not in the scope of GCC. Is
there a name for this problem (evaluating lengthy list of compute
instructions/formulas)? Where should I look to find a solution to that
problem?

On Thu, Oct 19, 2023 at 6:03 PM David Brown <david@westcontrol.com> wrote:

> On 19/10/2023 17:11, Kai Song via Gcc-help wrote:
>
> (It can be helpful to include attributions when replying, so that it is
> clear who wrote what.  Thus you should have this line included:)
>
>  > On 19/10/2023 16:26, Jonathan Wakely via Gcc-help wrote:
>
>
> >> Nothing you have said actually explains why you can't refactor the
> >> code into utility functions that avoid doing everything in one huge
> >> function.
> >>
> >
> > Because there are no two pieces of code that are exactly identical. The
> > relative distance of two variables being involved into an identical
> formula
> > will change with every line.
> > Example:
> > Line 1000: tmp[100]=foo(tmp[101],tmp[102]);
> > Line 2000: tmp[200]=foo(tmp[201],tmp[203]); // dang it, not tmp[202] but
> > tmp[203]
> > It is like with penrose tiling. It seems all identical but the details
> > break it. You just do not find two identical local areas. No-where. And
> if,
> > you have to particularly search for them by brute-force, and that should
> > become useless whenever the particular pattern you try to find does just
> > not exist in that particular user's instance.
> >
>
> Surely this is screaming out for a table?
>
> const int foo_table[][3] = {
>      { 100, 101, 102 },
>      { 200, 201, 203 },
>         ...
> };
>
>
>         for (int i = 0; i < 100000000; i++) {
>                 tmp[foo_table[i][0]] =
>                         foo(tmp[foo_table[i][1]], tmp[foo_table[i][2]]);
>         }
>
> This will turn your million-line program into a four line program with a
> big table, which will compile quickly and run faster.
>
>
>
>

Re: Compilation of lengthy C++ Files

[Jonathan Wakely]

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

On Fri, 20 Oct 2023, 10:32 Kai Song, <kaisong1515@gmail.com> wrote:

> @David: I am sorry there was a misunderstanding with the example. You
> wrote four lines of code to be able to replace two lines of code into a
> for-loop of length 2, somewhere in a 1Bio line program where this pattern
> coincidentally occured once in one generated instance. (In the next
> instance, the "pattern" might not occur, so then you just added four
> lines.) Also, it is unclear how you would implement in turn the code which
> locates the line 200 and decides to replace it with the for-loop. Further,
> you left unclear where to place this for-loop (in line 100 or line 200?),
> both of which will lead to the wrong result in the generated program due to
> false assumption on raise-conditions.
>
> I think my initial question has been mis-correlated. I think so because we
> drift into a discussion of speed and what is better and faster and
> what-not. But this is not the question at all.
> The setting is rather: I have a list of lengthy instructions. Think of a
> grocery list. The most convenient language for me to write this grocery
> list in is c++.
> Now I don't care whether my doctor thinks I want to eat this all by myself
> or on a weekly basis, and likes that thought or not. I just need to get the
> groceries.
> I can get them myself. In this case, it would mean I have to learn to
> generate code of linear compile-complexity into assembly directly by myself.
>
> I am not even interested in the compilation per se. I just need to be able
> to evaluate the code as written.
> I am equally fine with using an interpreted language or a different
> language. But interpreters have the exact same issue: They refuse to start
> computing a flat program code when the file containing it is too big.
>

So break it up into smaller functions. You've been given the answer, but
you don't want to accept it and want to argue that it's too difficult.

Maybe that's true, but it's the only way you're going to get the code to
compile.


So suppose I have a substitution of Taylor serieses into serieses and it
> _does_ become chaotic after reordering of terms. That is after all the work
> that the program does. That is what it is made for.
> And now I just want some way to evaluate that formula once to tell me
> whether y=f(x) yields y=0 for a particular value of x. This is as basic as
> it gets.
>
> I suppose the enablement of this capability is not in the scope of GCC. Is
> there a name for this problem (evaluating lengthy list of compute
> instructions/formulas)? Where should I look to find a solution to that
> problem?
>

Use subroutines. Put some of the instructions into a separate function, and
call that function.

The way you're generating code is not going to work at scale.





> On Thu, Oct 19, 2023 at 6:03 PM David Brown <david@westcontrol.com> wrote:
>
>> On 19/10/2023 17:11, Kai Song via Gcc-help wrote:
>>
>> (It can be helpful to include attributions when replying, so that it is
>> clear who wrote what.  Thus you should have this line included:)
>>
>>  > On 19/10/2023 16:26, Jonathan Wakely via Gcc-help wrote:
>>
>>
>> >> Nothing you have said actually explains why you can't refactor the
>> >> code into utility functions that avoid doing everything in one huge
>> >> function.
>> >>
>> >
>> > Because there are no two pieces of code that are exactly identical. The
>> > relative distance of two variables being involved into an identical
>> formula
>> > will change with every line.
>> > Example:
>> > Line 1000: tmp[100]=foo(tmp[101],tmp[102]);
>> > Line 2000: tmp[200]=foo(tmp[201],tmp[203]); // dang it, not tmp[202] but
>> > tmp[203]
>> > It is like with penrose tiling. It seems all identical but the details
>> > break it. You just do not find two identical local areas. No-where. And
>> if,
>> > you have to particularly search for them by brute-force, and that should
>> > become useless whenever the particular pattern you try to find does just
>> > not exist in that particular user's instance.
>> >
>>
>> Surely this is screaming out for a table?
>>
>> const int foo_table[][3] = {
>>      { 100, 101, 102 },
>>      { 200, 201, 203 },
>>         ...
>> };
>>
>>
>>         for (int i = 0; i < 100000000; i++) {
>>                 tmp[foo_table[i][0]] =
>>                         foo(tmp[foo_table[i][1]], tmp[foo_table[i][2]]);
>>         }
>>
>> This will turn your million-line program into a four line program with a
>> big table, which will compile quickly and run faster.
>>
>>
>>
>>

Re: Compilation of lengthy C++ Files

[Kai Song]

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

Yes. I have invested time on my end to cause some understanding for an
issue. But as I can confirm onto what has been my experience in that regard
all along, when speaking to niche experts in an interdisciplinary interface
and attempting to do something unconventional or maybe even novel, they are
refuting, denying, obscuring, defaming, fatiguing, reinterpreting,
straw-manning, etc. your problem/situation/fact from who you are, what you
are doing, what you are knowing, what you are even asking, why you are even
asking, the way you are asking, etc. I think what really happens is that
when a person in domain X is contacting to a person in domain Y and asks x
then Y will go all the way to transform x into y. And I would harshly claim
that the motivation in doing so is to pull x out of X into the domain Y
where they can claim with upper hand that what you do makes no sense.
Essentially I have been asking (maybe eight times or so) to execute lengthy
instructions. C++ does not forbid this. You cannot do it. And you give me
flack for it by basically repeating "you must be doing something wrong",
equivalent in saying to <I can add 1 and 1>. I won't participate in further
dialogue.

On Fri, Oct 20, 2023 at 4:15 PM Andrew Bell <andrew.bell.ia@gmail.com>
wrote:

>
> On Fri, Oct 20, 2023 at 5:33 AM Kai Song via Gcc-help <
> gcc-help@gcc.gnu.org> wrote:
>
>> @David: I am sorry there was a misunderstanding with the example. You
>> wrote
>> four lines of code to be able to replace two lines of code into a for-loop
>> of length 2, somewhere in a 1Bio line program where this pattern
>> coincidentally occured once in one generated instance. (In the next
>> instance, the "pattern" might not occur, so then you just added four
>> lines.) Also, it is unclear how you would implement in turn the code which
>> locates the line 200 and decides to replace it with the for-loop. Further,
>> you left unclear where to place this for-loop (in line 100 or line 200?),
>> both of which will lead to the wrong result in the generated program due
>> to
>> false assumption on raise-conditions.
>>
>
> Hi,
>
> You seem out of your depth with regard to this programming task. You are
> conversing with experts who have kindly given their time to help address
> your issue. Perhaps you should hire someone locally to help you turn your
> current effort into something more manageable. There are many ways to solve
> most problems and it seems likely that your current method is not the best.
>
> --
> Andrew Bell
> andrew.bell.ia@gmail.com
>

Re: Compilation of lengthy C++ Files

[Paul Smith]

On Fri, 2023-10-20 at 23:08 +0200, Kai Song via Gcc-help wrote:
> Yes. I have invested time on my end to cause some understanding for
> an issue.

Maybe I can provide context.  Note I'm not a GCC developer although I
have worked on compiler implementations in the past.

The C++ standard defines an abstract definition.  Individual
implementations of compilers for the C++ standard will have limitations
on the abstract definition, obviously: computers are not abstract and
so they are limited.

When a compiler compiles a single function, _especially_ if you enable
optimization, it's not the case that it can simply churn through that
function line by line, process that line and spit out some assembly,
then move to the next line without any context.  Instead, within a
single function the compiler must remember all sorts of things about
the lines in the function that it already parsed.

The longer your function is, the more things the compiler has to
remember about all the previous content that it already parsed.

When programmers write code they naturally break it up into functions
that can managed and understood by other programmers, so compilers
expect that individual functions are of "mangeable" size and aren't
hundreds of thousands of lines long, and implementations make choices
that reflect that expectation.

As a result there will be some limitations on the size of a function
that a compiler can handle with any sort of grace: beyond that the
implementation may well run into asymptotic runtimes due to choices in
internal data structure and algorithms.

Is this unfortunate?  Of course, abstractly it's always unfortunate
when a compiler limits the program you want to write.  But, it's quite
reasonable for the compiler authors to decide to concentrate on the
99.999% of code they expect to see, and not worrying about the 0.001%
of code they don't expect, and of which they probably don't even have
examples to test.

So, you can either decide you want to try to help fix the compiler to
be able to better handle code like yours, by doing performance analysis
and figuring out where the bottlenecks are and providing patches that
help the compiler in these extreme edge cases (without damaging it in
the "normal" cases).

Or, you can change your code generator to output code which is more
like what the compiler expects, where you have many more smaller
functions, potentially even in separate source files, rather than one
gigantic function containing all the code.

Or, I guess, you can look for a different compiler that has different
goals.

So to answer your questions:

> 1) Am I doing something wrong in that GCC should be able to compile
> lengthy codes?

I'm not sure exactly what this question is asking.  If what you mean
is, is there some flag or option you can give to GCC to get it to build
your code then no, I doubt it.  Disabling optimization altogether will
help, but may not be enough; I assume you already tried that.

If you are asking should GCC be able to compile these huge functions,
then I guess the answer is that the GCC authors don't think that this
is an important use-case so they haven't tried to make it work well.

> 2) Is it known that GCC is unable to compile lengthy codes?

I doubt that it's known per se because I'm quite sure that there are no
tests in the compiler test suite that try to compile functions at this
scale.

But if you tell us you do see that it's unable to be done, I doubt that
anyone on this list is particularly surprised by that.

> 3) Is it acknowledged that a compiler's ability to compile large
> files is relevant?

As above, I doubt the GCC developers feel that it's particularly
relevant, no.  Which is not the same thing as saying that, if someone
points out a specific problem and provides a reasonable fix, that they
wouldn't include it.

> 4) Are possible roots known for this inability and are these
> deliberate?

I would say, as above, that the GCC developers do not have such huge
functions in their test suite and so no, they are not aware of exactly
what problems would occur when trying to compile them.  If they were to
sit and think about it for a while, I'm sure various developers could
imagine possible bottlenecks that would cause huge functions to compile
slowly, but as always with performance the only way to really know is
to measure it.

I don't know what you mean by "are they deliberate".  I'm sure they
didn't sit down to write the compiler implementation and say "let's
make it slow for huge functions!"

But it could well be that when making design choices if there was a way
to do it that was much easier to implement or allowed for faster
compilation for medium-sized functions but would be hugely inefficient
for gigantic functions, they may have said "well, these huge functions
are extremely unlikely so we won't optimize for that".

There's no way to know until, as above, someone sits down with such a
huge file and performs performance analysis on the compiler as it tries
to compile the function, and figures out what is going on.

Re: Compilation of lengthy C++ Files

[Jonathan Wakely]

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

On Fri, 20 Oct 2023, 23:04 Paul Smith via Gcc-help, <gcc-help@gcc.gnu.org>
wrote:

> On Fri, 2023-10-20 at 23:08 +0200, Kai Song via Gcc-help wrote:
> > Yes. I have invested time on my end to cause some understanding for
> > an issue.
>
> Maybe I can provide context.  Note I'm not a GCC developer although I
> have worked on compiler implementations in the past.
>
> The C++ standard defines an abstract definition.  Individual
> implementations of compilers for the C++ standard will have limitations
> on the abstract definition, obviously: computers are not abstract and
> so they are limited.
>

And this is explicitly called out in the C++ standard:
https://eel.is/c++draft/intro.compliance#general-2.1
https://eel.is/c++draft/implimits


Kai, we are not sceptics who are doubting your marvelous theories. It is an
empirical fact that gcc will fail to compile ridiculously large functions
written in your preferred coding style. Some of us have tried to suggest
alternatives that might have more success.

At this point I consider any further engagement in this thread to be a
waste of time. You have answers to your questions now, but you seem
unwilling to take the advice given.

Good luck compiling your ridiculously constructed programs.

Re: Compilation of lengthy C++ Files

[Kai Song]

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

Thank you to Jonathan and Paul for clarifying the scope of the discussion.
I was under the impression that the goal was to move the subject at "if
your code is too long you have to refactor it", which I interpreted after
all as "you must be doing something wrong". Because we both proceeded by
alternately replying with the same piece of information.

Today I did implement a cpp program that will evaluate a file containing a
formula of length N and its derivative in O(N), compiled with GCC :D. Of
course my program can only treat very trivial files and is slow but for
most of my tasks that does not matter. I understand (and needless to say
couldn't do it better) that it may just be for now a too difficult problem
to actually compile lengthy cpp. The question that I was targeting at is:
What can I realistically do (implying that refactoring in the remaining
project's period appears nonviable)? The formula evaluator programs helps
for a subset of these problems, clearly. Are there languages with similar
capabilities to cpp that I could generate into equivalently and that are as
easy to learn (i.e., excluding assembly or any languages that won't permit
templates or flexible types)?

My initial phrasing of "how can I complie my code?" was wrong as I can see
now. It should have been "how can I somehow just make it so I can evaluate
it?, particularly when I see myself unable for now to transform it into
equivalent shorter code?"

On Sat, Oct 21, 2023 at 8:52 AM Jonathan Wakely <jwakely.gcc@gmail.com>
wrote:

>
>
> On Fri, 20 Oct 2023, 23:04 Paul Smith via Gcc-help, <gcc-help@gcc.gnu.org>
> wrote:
>
>> On Fri, 2023-10-20 at 23:08 +0200, Kai Song via Gcc-help wrote:
>> > Yes. I have invested time on my end to cause some understanding for
>> > an issue.
>>
>> Maybe I can provide context.  Note I'm not a GCC developer although I
>> have worked on compiler implementations in the past.
>>
>> The C++ standard defines an abstract definition.  Individual
>> implementations of compilers for the C++ standard will have limitations
>> on the abstract definition, obviously: computers are not abstract and
>> so they are limited.
>>
>
> And this is explicitly called out in the C++ standard:
> https://eel.is/c++draft/intro.compliance#general-2.1
> https://eel.is/c++draft/implimits
>
>
> Kai, we are not sceptics who are doubting your marvelous theories. It is
> an empirical fact that gcc will fail to compile ridiculously large
> functions written in your preferred coding style. Some of us have tried to
> suggest alternatives that might have more success.
>
> At this point I consider any further engagement in this thread to be a
> waste of time. You have answers to your questions now, but you seem
> unwilling to take the advice given.
>
> Good luck compiling your ridiculously constructed programs.
>
>
>

Re: Compilation of lengthy C++ Files

[Paul Smith]

On Sat, 2023-10-21 at 16:10 +0200, Kai Song via Gcc-help wrote:
> I understand (and needless to say couldn't do it better) that it may
> just be for now a too difficult problem to actually compile lengthy
> cpp.

I just want to be very clear here.  When you say "lengthy cpp" that is
not very precise because "cpp" is not an accurate term.

What is true is the the compiler will have problems compiling extremely
long SINGLE FUNCTIONS.  It doesn't really matter how long the source
file is (how many functions it contains).  What matters is now large
each function is.

In order to make your generated code digestible for compilers, you need
to break up your algorithms into multiple smaller functions.

> The question that I was targeting at is: What can I realistically do
> (implying that refactoring in the remaining project's period appears
> nonviable)?

Of course we cannot decide what is realistic or not.  Your comments
here seem to imply that you would be wiling to rewrite the entire thing
to generate output in a completely different language so it seems you
are willing and able to make very sweeping changes.

It's hard for us to understand why you can't extract parts of your
generated code and put them into separate functions.  Surely you must
have loops in your code: can't the body of some of these loops become
separate functions?  If there are steps to the algorithm can't each of
these steps become a separate function?  You can collect all the state
of the algorithm into one large global structure, rather than having
individual local variables, and all the functions can refer to that
global state structure, so you don't have to pass the data around as
arguments.

> Are there languages with similar capabilities to cpp that I could
> generate into equivalently and that are as easy to learn

Since we don't know which particular capabilities of C++ you are
relying on that's difficult to say.  However, my feeling is that no
matter what language you use you will run into these limitations:
compilers in general simply are not written to have single functions
which are hundreds of thousands of lines long.  Functions help humans
organize their thinking and programming, but they also are critical for
compilers to make their jobs simpler (or even possible).

Rather than learning a new language, I think you should be revisiting
your code generation and attempting to understand how to break it up. 
I don't think there's any feasible alternative.

Re: Compilation of lengthy C++ Files

[Richard Earnshaw]

On 24/10/2023 15:57, Paul Smith via Gcc-help wrote:
> On Sat, 2023-10-21 at 16:10 +0200, Kai Song via Gcc-help wrote:
>> I understand (and needless to say couldn't do it better) that it may
>> just be for now a too difficult problem to actually compile lengthy
>> cpp.
> 
> I just want to be very clear here.  When you say "lengthy cpp" that is
> not very precise because "cpp" is not an accurate term.
> 
> What is true is the the compiler will have problems compiling extremely
> long SINGLE FUNCTIONS.  It doesn't really matter how long the source
> file is (how many functions it contains).  What matters is now large
> each function is.
> 

That's only partially true.  Modern compilers read the whole translation 
unit into memory, parse all of it and then optimize the various 
functions.  Smaller functions helps to reduce the overall memory 
footprint while doing the optimizations, but does not entirely eliminate 
the file size issue.

> In order to make your generated code digestible for compilers, you need
> to break up your algorithms into multiple smaller functions.
> 
>> The question that I was targeting at is: What can I realistically do
>> (implying that refactoring in the remaining project's period appears
>> nonviable)?
> 
> Of course we cannot decide what is realistic or not.  Your comments
> here seem to imply that you would be wiling to rewrite the entire thing
> to generate output in a completely different language so it seems you
> are willing and able to make very sweeping changes.
> 
> It's hard for us to understand why you can't extract parts of your
> generated code and put them into separate functions.  Surely you must
> have loops in your code: can't the body of some of these loops become
> separate functions?  If there are steps to the algorithm can't each of
> these steps become a separate function?  You can collect all the state
> of the algorithm into one large global structure, rather than having
> individual local variables, and all the functions can refer to that
> global state structure, so you don't have to pass the data around as
> arguments.
> 
>> Are there languages with similar capabilities to cpp that I could
>> generate into equivalently and that are as easy to learn
> 
> Since we don't know which particular capabilities of C++ you are
> relying on that's difficult to say.  However, my feeling is that no
> matter what language you use you will run into these limitations:
> compilers in general simply are not written to have single functions
> which are hundreds of thousands of lines long.  Functions help humans
> organize their thinking and programming, but they also are critical for
> compilers to make their jobs simpler (or even possible).
> 
> Rather than learning a new language, I think you should be revisiting
> your code generation and attempting to understand how to break it up.
> I don't think there's any feasible alternative.

The most important consideration doesn't seem to have been mentioned on 
this thread: CPU architectures.  Modern CPUs have a very strong 
preference to repeatedly executing small bits of code.  Linear code will 
kill their performance.  This comes from the fact that the CPU can 
consume instructions far faster than the memory system can supply them. 
So to keep performance up, the system uses caches; but those are tiny 
and they only help if the instructions held in them are re-used. 
Furthermore, branches for most programs are practically free these days, 
especially when you take the benefit of caches into account: the days of 
unrolling loops dozens (or more) times to avoid branch overheads are 
pretty much gone.

Finally, there are practical limits (especially on RISC processors) of 
how large a function can be before you need to take defensive 
compilation measures to handle very large offsets between addresses. 
Those defensive measures further slow down your compiled programs.

R.

Re: Compilation of lengthy C++ Files

[Paul Smith]

On Wed, 2023-10-25 at 12:09 +0100, Richard Earnshaw wrote:
> Those defensive measures further slow down your compiled programs.

Just to remind, Kai Song has said multiple times in these threads that
they're not asking about improving the performance of the resulting
compiled program.  They don't seem to mind if the resulting program
takes days or weeks to run.

They are asking here about how to get the compiler to successfully
compile the code, not how to make the compiled code faster.

Re: Compilation of lengthy C++ Files

[David Brown]

On 25/10/2023 16:49, Paul Smith via Gcc-help wrote:
> On Wed, 2023-10-25 at 12:09 +0100, Richard Earnshaw wrote:
>> Those defensive measures further slow down your compiled programs.
> 
> Just to remind, Kai Song has said multiple times in these threads that
> they're not asking about improving the performance of the resulting
> compiled program.  They don't seem to mind if the resulting program
> takes days or weeks to run.
> 

He has actually said he doesn't mind if the /compile/ time is months, or 
even years!

> They are asking here about how to get the compiler to successfully
> compile the code, not how to make the compiled code faster.
> 

Yes - with an emphasis on wanting to persuade GCC to compile his 
generated code, rather than on wanting to generate code that can be 
compiled by GCC.