eclipse-langium / langium

Next-gen language engineering / DSL framework
https://langium.org/
MIT License
725 stars 65 forks source link

Non-linear performance during code generation #1293

Closed msujew closed 9 months ago

msujew commented 10 months ago

As outlined in https://github.com/eclipse-langium/langium/discussions/1292, there seems to be a performance issue in our generator functions.

The generator toString() function seems to run in quadratic (O(n^2)) time. We should be able to get this down to linear time.

Reproducible Example ```ts 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{ 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'); ```
spoenemann commented 9 months ago

Fixed with #1294.