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

[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.

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

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.

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.

I’m flagging this as improvement.