generating and compiling a very large file

generating and compiling a very large file

[Stephen Leake]

I'm working on a parser generator. One of the files generated is very large; 20,000 lines. They build the LALR parse table with code like this:

      Table.States (1291).Productions := WisiToken.To_Vector ((1 => 185));
      Add_Action (Table.States (1291), (19, 20), 4, 589);
      Add_Action (Table.States (1291), (1 => 528), 5, 590);
      Add_Action (Table.States (1291), 13, Reduce, 66, 132, 0, 0, null, null);
      Add_Action (Table.States (1291), (1 => 80), 15, 591);
      Add_Action (Table.States (1291), 17, Reduce, 66, 132, 0, 0, null, null);
      Add_Action (Table.States (1291), (150, 151), 18, 592);
      Add_Action (Table.States (1291), 24, Reduce, 515, 304, 0, 0, null, null);
      Add_Action (Table.States (1291), 26, Reduce, 515, 304, 0, 0, null, null);
      Add_Action (Table.States (1291), (209, 210), 27, 593);
      Add_Action (Table.States (1291), 28, Reduce, 66, 132, 0, 0, null, null);
      Add_Action (Table.States (1291), (1 => 523), 31, 595);
      Add_Action (Table.States (1291), (296, 297, 298, 299), 32, 596);
      Add_Action (Table.States (1291), 37, Reduce, 66, 132, 0, 0, null, null);
      Add_Action (Table.States (1291), (1 => 520), 41, 597);
      Add_Action (Table.States (1291), (409, 410, 411), 48, 7);
      Add_Action (Table.States (1291), (449, 450, 451), 52, 598);
      Add_Action (Table.States (1291), (487, 488), 57, 599);
      Add_Action (Table.States (1291), (224, 225, 519), 58, 600);
      Add_Action (Table.States (1291), (54, 114, 497, 498, 567), 61, 601);
      Add_Action (Table.States (1291), 73, Reduce, 66, 132, 0, 0, null, null);
      Add_Action (Table.States (1291), (1 => 285), 93, 603);
      Add_Action (Table.States (1291), (65, 357), 104, 604);
      Add_Action (Table.States (1291), (1 => 364), 105, 48);
      Add_Action (Table.States (1291), (1 => 358), 106, 49);
      Add_Error (Table.States (1291));
      Add_Goto (Table.States (1291), 112, 113, 605);
      Add_Goto (Table.States (1291), 521, 123, 606);
      Add_Goto (Table.States (1291), 512, 126, 607);
      Add_Goto (Table.States (1291), 361, 128, 50);
      Add_Goto (Table.States (1291), 67, 131, 608);
      Add_Goto (Table.States (1291), 68, 132, 609);
      Add_Goto (Table.States (1291), 110, 133, 610);
      Add_Goto (Table.States (1291), 108, 139, 611);
      Add_Goto (Table.States (1291), 538, 151, 612);
      Add_Goto (Table.States (1291), 511, 152, 613);
      Add_Goto (Table.States (1291), 527, 162, 614);
      Add_Goto (Table.States (1291), 522, 191, 615);
      Add_Goto (Table.States (1291), 111, 197, 616);
      Add_Goto (Table.States (1291), 536, 218, 617);
      Add_Goto (Table.States (1291), 185, 219, 1294);
      Add_Goto (Table.States (1291), 107, 223, 619);
      Add_Goto (Table.States (1291), 109, 236, 620);
      Add_Goto (Table.States (1291), 45, 243, 621);
      Add_Goto (Table.States (1291), 530, 261, 622);
      Add_Goto (Table.States (1291), 524, 265, 623);
      Add_Goto (Table.States (1291), 363, 276, 53);
      Add_Goto (Table.States (1291), 529, 280, 624);
      Add_Goto (Table.States (1291), 526, 294, 625);
      Add_Goto (Table.States (1291), 360, 297, 54);
      Add_Goto (Table.States (1291), 509, 298, 626);
      Add_Goto (Table.States (1291), 113, 302, 627);
      Add_Goto (Table.States (1291), 514, 303, 628);
      Add_Goto (Table.States (1291), 286, 304, 629);
      Add_Goto (Table.States (1291), 525, 306, 630);
      Add_Goto (Table.States (1291), 537, 307, 631);
      Add_Goto (Table.States (1291), 513, 310, 632);
      Add_Goto (Table.States (1291), 510, 327, 633);

On my 64bit 32GB ram Windows box running GNAT GPL 2017, this takes 1.5 minutes to compile; slow, but acceptable since I don't compile it very often. In a Debian 8 VM on that same box, allocated 1 GB ram, it takes 11 minutes. I can allocate more ram to that VM, but 1 GB is enough for everything else I do in it, and other people who might use this have slow/small machines.

Is there anything I can do to the code to shorten the compile time? I have complete control over this; for example, I could combine all those Add_Goto statements into one line.

A more drastic change would be to put all the numbers in a text file, read in at run time. I haven't tried that yet, mostly because some of those 'null' values are procedure'access in other parts of the file.

I'm hoping someone here has hit this problem before, and has some helpful solutions :).

-- Stephe

Re: generating and compiling a very large file

[Dmitry A. Kazakov]

On 2018-06-03 21:14, Stephen Leake wrote:

> On my 64bit 32GB ram Windows box running GNAT GPL 2017, this takes 1.5 minutes to compile; slow, but acceptable since I don't compile it very often. In a Debian 8 VM on that same box, allocated 1 GB ram, it takes 11 minutes. I can allocate more ram to that VM, but 1 GB is enough for everything else I do in it, and other people who might use this have slow/small machines.

I don't think it is memory. In my case when the compiler runs out of 
memory it simply crashes with STORAGE_ERROR and prints the infamous BUG 
REPORT box.

Do you use a shared folder? Because if the guest has files in a host's 
shared folder that makes compilation drastically slower. You could try 
rsync or winscp to copy files between the host and the guests instead of 
shared folder.

> Is there anything I can do to the code to shorten the compile time? I have complete control over this; for example, I could combine all those Add_Goto statements into one line.

I know that using generic packages instances, even only in the 
with-clause causes a huge impact on both space and time.

> A more drastic change would be to put all the numbers in a text file, read in at run time. I haven't tried that yet, mostly because some of those 'null' values are procedure'access in other parts of the file.

What about writing a small Ada program that generates an initialized object:

    State : constant := ( large-generated-aggregate );

I used this approach to embed images.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: generating and compiling a very large file

[Shark8]

On Sunday, June 3, 2018 at 1:14:40 PM UTC-6, Stephen Leake wrote:
> I'm working on a parser generator. One of the files generated is very large; 

The idea of a large aggregate is good, another thing that you could do is spread this out via SEPARATE, or perhaps via generics. Working with an interpreter I combined SEPARATE, GENERIC and overloading to do a static set of operations, see the "risi_script-types-implementation*.ad?" here: https://github.com/OneWingedShark/Risi/tree/master/src

That might not be appropriate given that you're not interpreting things, though.
If that's the case what you could do is make TABLE a constant and populate it in-source.

Re: generating and compiling a very large file

[Randy Brukardt]

"Shark8" <onewingedshark@gmail.com> wrote in message 
news:e1aaa443-00b7-4217-8fe8-dfc9098e247b@googlegroups.com...
On Sunday, June 3, 2018 at 1:14:40 PM UTC-6, Stephen Leake wrote:
>> I'm working on a parser generator. One of the files generated is very 
>> large;
>
>The idea of a large aggregate is good,...

I can't speak to GNAT specifically, but in the case of Janus/Ada, the best 
solution would be to use a number of medium-size aggregates. The usual 
performance problem in Janus/Ada is the optimizer, and very large aggregates 
get really slow as the code to construct them gets rearranged by the 
optimizer. OTOH, lots of tiny subprogram calls also can get rearranged by 
the optimizer.

So I'd suggest (a) turning off optimization to see if that alone is the 
culprit, and (b) using fewer calls using medium size aggregates - one for 
each state, perhaps?

BTW, what Janus/Ada does for its own LALR parse tables is have a program to 
stream out a binary representation of them to a file ("Janus1.Ovl"), the 
compiler then streams that in to start. (It's a pure binary read/write - 
these days, I'd use Stream_IO to do it, avoid stream attributes as they can 
easily drop to component-by-component.) A text file would be quite a bit 
slower, since Text_IO requires a lot more processing that just pure binary 
I/O.

                                                     Randy.

Re: generating and compiling a very large file

[Stephen Leake]

I found a solution; divide the list of statements into subroutines. In this case, one subroutine for state.

Apparently GNAT has some strongly non-linear dependence on the number of statements in a subroutine; one subroutine with thousands of statements is significantly slower than hundreds of subroutines with the same statements, followed by hundreds of calls to those subroutines.