x/text/unicode/runenames: compiling tables.go is slow due to long string concatenation

[bradfitz]

The subrepos need to be building before we do a release.

The x/text/unicode/runenames is currently failing on the trybots due to lack of memory, even after I doubled their container memory limits from 2GB to 4GB.

Compiling x/text/unicode/runenames is taking over 4GB of ram.

Actually, my development VM (also 4GB, no swap) also fails to compile this. I do not want to make my VM larger.

Can we make the auto-generated tables nicer to the compiler, or can the compiler be smarter about not going pathological on this input and not optimize something it's trying to optimize?

/cc @nigeltao @randall77

[bradfitz]

/cc @mdempsky

[josharian]

Looks like O(n^2) in evconst. I'll take a quick peek.

[josharian]

The old gc parser turned a+b+c+d into OADD with a flat list a, b, c, d. Looks like the new parser generates a tree instead; based purely on the blow-up in this example, I think it must be generating a lopsided tree of depth n.

The logic in evconst to coalesce OADDSTRs expects a flat list, not a deep tree, and ends up building the giant string one piece at a time instead of all at once, thus O(n^2). I suspect the right fix is probably to change noder.go, to mimic the old parser's behavior, at least for now; there are probably other places where the compiler assumes flattened bin op trees. Leaving for @mdempsky after all.

[mdempsky]

The old gc parser turned a+b+c+d into OADD with a flat list a, b, c, d.

Can you clarify what makes you say this? As far as I can tell, we used to parse a+b+c+d into a tree of OADD nodes too: (*parser).bexpr

[mdempsky]

Is anyone able to confirm that tip is worse than Go 1.7.3 at compiling x/text/unicode/runenames? Some quick benchmarking on my workstation with /bin/time suggests that tip is using less memory than 1.7.3 ("maxresident" around 4.4M vs 8.6M, and 1.1M minor pagefaults instead of 2.1M).

[bradfitz]

On my Mac desktop (which has enough RAM to build this), yeah, I see Go 1.8 slightly better. Both numbers are after running once, then deleting the runenames.a file, then running again:

$ /usr/bin/time -l go install golang.org/x/text/unicode/runenames
        3.58 real         0.95 user         1.59 sys
3718422528  maximum resident set size
         0  average shared memory size
         0  average unshared data size
         0  average unshared stack size
   1116628  page reclaims
         2  page faults
         0  swaps
         0  block input operations
         5  block output operations
         0  messages sent
         0  messages received
         3  signals received
      3044  voluntary context switches
     19084  involuntary context switches

$ export GOROOT=$HOME/go1.7
$ /usr/bin/time -l $GOROOT/bin/go install golang.org/x/text/unicode/runenames
       10.90 real         2.46 user         3.70 sys
4469641216  maximum resident set size
         0  average shared memory size
         0  average unshared data size
         0  average unshared stack size
   2207512  page reclaims
      1215  page faults
         0  swaps
         1  block input operations
         5  block output operations
         0  messages sent
         0  messages received
         3  signals received
     20378  voluntary context switches
     71213  involuntary context switches

[mdempsky]

Oh, tables.go is a new file, only a couple weeks old. It's not a compiler regression.

I think we could efficiently handle the special case of concatenated string literals at least. I'll take a look. If it's non-intrusive enough, maybe we can still do it for 1.8.

But otherwise, we should probably look for a workaround in x/text/unicode/runenames instead. One possibility might be to use explicit parentheses to balance the concatenations. E.g., (a + b) + (c + d).