Escapes inside string interpolation drastically increase the compilation time of a Stratego program.

UPDATE: The immediate cause of the code explosion is now resolved. More improvement is still necessary but only possible by rewriting the interpolation algorithm.

On my machine the Spoofax entity project builds in 6 seconds. Adding the following to the Stratego rules drives the compilation time to 24 seconds:

	big-template:
	  _ -> p1
	  with
	    x := "foobar";
	    p1 := $[
	    [x][x][x][x][x][x][x][x][x][x]
	    [x][x][x][x][x][x][x][x][x][x]
	    [x][x][x][x][x][x][x][x][x][x]
	    [x][x][x][x][x][x][x][x][x][x]
	    [x][x][x][x][x][x][x][x][x][x]
	    [x][x][x][x][x][x][x][x][x][x]
	    ]

It seems compilation of escapes is expensive to start with, but the number of escapes per interpolated string influences the duration as well. For example, if i replace the above code with the one below (split into two strings), the compilation time drops to 18 seconds:

	big-template:
	  _ -> p3
	  with
	    x := "foobar";
	    p1 := $[
	    [x][x][x][x][x][x][x][x][x][x]
	    [x][x][x][x][x][x][x][x][x][x]
	    [x][x][x][x][x][x][x][x][x][x]
	    ];
	    p2 := $[
                [x][x][x][x][x][x][x][x][x][x]
                [x][x][x][x][x][x][x][x][x][x]
                [x][x][x][x][x][x][x][x][x][x]
	    ];
	    p3 := $[[p1][p2]]

Further splitting these up into two different strategies (like below) does not modify the compilation time:

big-templates:
  _ -> $[[p1][p2]]
  with
    p1 := <big-template>;
    p2 := <big-template2>

	big-template:
	  _ -> p1
	  with
	    x := "foobar";
	    p1 := $[
	    [x][x][x][x][x][x][x][x][x][x]
	    [x][x][x][x][x][x][x][x][x][x]
	    [x][x][x][x][x][x][x][x][x][x]
	    ]
	
	big-template2:
	  _ -> p2
	  with
	    x := "foobar";
	    p2 := $[
                [x][x][x][x][x][x][x][x][x][x]
                [x][x][x][x][x][x][x][x][x][x]
                [x][x][x][x][x][x][x][x][x][x]
	    ]
Submitted by Vlad Vergu on 28 October 2013 at 21:07

On 30 October 2013 at 15:47 Vlad Vergu commented:

[The statement below is most likely incorrect]

This seems to happen only for rewrite rules and not in strategies. Rewriting the big-template rule from the first example as a strategy brings the compilation time back to normal:

  big-template = 
    x := "foobar";
    p1 := $[
    [x][x][x][x][x][x][x][x][x][x]
    [x][x][x][x][x][x][x][x][x][x]
    [x][x][x][x][x][x][x][x][x][x]
    [x][x][x][x][x][x][x][x][x][x]
    [x][x][x][x][x][x][x][x][x][x]
    [x][x][x][x][x][x][x][x][x][x]
    ];
    !p1

This hints that this is a front-end bug.


On 30 October 2013 at 19:46 Vlad Vergu commented:

All of the above happens in both the compiler and the interpreter. It seems more and more like frontend bug.


On 6 November 2013 at 15:00 Vlad Vergu commented:

The problem is caused by a non-linear explosion in code by the desugaring of the string interpolation. I have pushed an improvement. This improvement reduces the compilation time for the original big-template example to 13 seconds.


On 6 November 2013 at 15:20 Vlad Vergu commented:

Further improvement achieved. The compilation time of the original big-template is now 8.4 seconds. This is still very slow but further improvements require redesign of the interpolation algorithm.


On 6 November 2013 at 20:09 Vlad Vergu commented:

I’m flagging this as improvement.


On 6 November 2013 at 20:09 Vlad Vergu tagged improvement

On 6 November 2013 at 20:09 Vlad Vergu removed tag error

Log in to post comments