Performance of CompositeGeneratorNode for large outputs

[goto40]

In one of our projects (still on langium 1.2) we have large file outputs with CompositeGeneratorNode.

It seems that toString(node) takes very long(!) time (minutes for 38000 LOC)... Is this a known issue? I did not find any ticket for that in your repo...

[msujew]

cc @sailingKieler Are you aware of any performance issues in that area?

On another note: @goto40 Do you have a repro example for this? It would be great to get some tracing on badly behaving parts of the framework to identify bottlenecks that can be fixed.

[goto40]

I could prepare something.
Until then: we use indent(...) and as leaf mostly apoend(string, NL)...

[goto40]

Demo:

import { CompositeGeneratorNode, NL, toString } from 'langium';

console.log('perfromance test');
const node = new CompositeGeneratorNode();

function prepare(node: CompositeGeneratorNode, l: number, r: number): void {
    if (r<=0) {
        for (let i=0;i<l;i++) {
            node.append(`i=${i} this is a demo line...`, NL);
        }    
    }
    else {
        for (let i=0;i<3;i++) {
            node.append(`open=${i}`, NL);
            node.indent(node=>{
                prepare(node, l, r-1);
            });
            node.append(`close=${i}`, NL);
        }    
    }
}

const t0 = new Date().getTime();
prepare(node, 200, 4); // <-------------------------------- play with the second argument
const t1 = new Date().getTime();


console.log('data prepared');
console.log('convert to text:');
const t2 = new Date().getTime();
const text = toString(node);
const t3 = new Date().getTime();
console.log('print text:');
console.log(text);
console.log(`nb lines: ${text.split('\n').length}`)
console.log(`time to generate text:  ${(t1-t0)/1000} sec`);
console.log(`time to convert text:  ${(t3-t2)/1000} sec`);
console.log('end');

When playing with the code on my machine (now with langium 2.1.2)

• With prepare(node, 100, 4);: I get 4.xxx seconds for 8341 LOC (for toString)
• With prepare(node, 200, 4);: I get 16.xxx seconds for 16441 LOC (for toString)

For me, it seems that some O(N^2) is hidden somewhere...
Also: 4 seconds to process 8000 LOC seems to be too long... (probably a follow-up effect of some O(N^2))

[msujew]

Interesting, thanks for the repro! We'll look into it. Definitely hints at O(n^2) behavior @sailingKieler👍

[sailingKieler]

Hi @goto40,

my first guess is that the computation of the actual indentation string being prepended to each individual line is done way too often -- for each individual line.

You code run's lightning fast if I change

            node.indent(node=>{
                prepare(node, l, r-1);
            });

to

            node.indent( () =>{
                prepare(node, l, r-1);
            });

i.e. append everything to the root node.

We'll have a look at that.

Thank you very much for reporting! 🙏

[goto40]

As far as I understand, you are explaining where to find the bug? - not how to change our code (appending to the root node, does skip indentation - which is not what we want).

Thank you for your nice product (lamgium) and the competent and prompt feedback (<<1day)!!

[sailingKieler]

As far as I understand, you are explaining where to find the bug? - not how to change our code (appending to the root node, does skip indentation - which is not what we want).

Correct.
I'm just taking some time to harden my suspicion (while sitting in a sports center and waiting my daughter's training session to finish). Once it's clear I maybe can give you an advice or provide a fix.
It seems this is a leftover from the early days of Langium.

[sailingKieler]

Independently of my findings:
Your benchmark is far away from linear in complexity wrt. r, isn't it?
My first gut feeling was that it looks like a variant of https://en.wikipedia.org/wiki/Ackermann_function - correct me if I'm wrong.

The number of indentNodes is equal to sum(3^i for i in range(1, r)).

r = 1 => noOfIndentNodes === 3^1
r = 2 => noOfIndentNodes === 3^2 + 3^1 = 12
r = 3 => noOfIndentNodes === 3^3 + 3^2 + 3^1 = 39
r = 4 => noOfIndentNodes === 3^4 + 3^3 + 3^2 + 3^1 = 120
r = 4 => noOfIndentNodes === 3^5 + 3^4 + 3^3 + 3^2 + 3^1 = 363

Does your actual code generator have this complexity?

[goto40]

r ist just to generate some "wild indentation scenario" with depth r. And yes, it is not linear...
Once r is fixed, you can play with l to roughly scale (e.g. *2) the number of lines.

• The number of lines are printed at the end.
• The time is printed at the end.

--> Here, we see a O(N^2) effect when comparing the (number of lines) and the (time it took to compute toString).

Note: I do not want to predict the time with respect to r! But you can use r to control depth of indentation.

(I hope this was clear...)

[sailingKieler]

@goto40 can you test the fix in #1294?
If possible, feel free to comment on the PR.

--> Here, we see a O(N^2) effect when comparing the (number of lines) and the (time it took to compute toString).

Correct, and I introduced it while adding the construction of source-target-region-tracing information.
I vaguely remember that I thought about that potential issue, but didn't want to add pre-mature optimizations.

[goto40]

I will have a deeper look this weekend. Thank you for the work!

[sailingKieler]

@goto40 @msujew published Langium v2.1.3 including the fix of #1294 a few hours ago.
Please let us know if everything works as expected again.

[goto40]

Seems it works for us (langium 2.1.3 + langium-cli 2.1.0). Thank you very much for the support! Good work!!!