Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

cmd/gofmt: quadratic handling of large addition expressions #23350

rsc opened this issue Jan 5, 2018 · 3 comments

cmd/gofmt: quadratic handling of large addition expressions #23350

rsc opened this issue Jan 5, 2018 · 3 comments


Copy link

@rsc rsc commented Jan 5, 2018

Given a program with a large string addition

var x = 1 + 1 + 1 + ... 1

gofmt takes time quadratic in the size of the expression to print it back out. Note that this is an integer addition, not a string addition: the problem does not involve string concatenation.

go get -u
bigprog gofmt

prints on my system:

          1000  int   0.035s  strbal   0.008s  strbigbal   0.030s  str   0.026s  strbig    0.047s
          2000  int   0.071s  strbal   0.012s  strbigbal   0.051s  str   0.079s  strbig    0.115s
          4000  int   0.291s  strbal   0.022s  strbigbal   0.092s  str   0.271s  strbig    0.362s
          8000  int   1.049s  strbal   0.032s  strbigbal   0.173s  str   1.092s  strbig    1.249s
         16000  int   4.332s  strbal   0.070s  strbigbal   0.346s  str   4.338s  strbig    4.852s
         32000  int  18.897s  strbal   0.112s  strbigbal   0.662s  str  18.212s  strbig   18.889s
         64000  int  82.845s  strbal   0.224s  strbigbal   1.292s  str  84.138s  strbig   83.718s
        128000  int 382.780s  strbal   0.425s  strbigbal   2.588s  str 381.781s  strbig  392.788s

See #23222 for full description of this table, but the important part here is that the int, str, and strbig columns are addition chains like above, while the faster strbal and strbigbal columns have parentheses added to make the addition parse trees balanced. The balanced times double nicely as the input size doubles, so there is no problem with actually generating large outputs. In contrast the unbalanced inputs quadruple as input size doubles, a clear quadratic slowdown. The obvious guess is that it is in the code that decides how to format expressions, and probably in the code that decides whether to insert spaces around expressions. (If so, it's my fault and I apologize.)

This is a fairly minor issue, but it would make gofmt 4X faster even on concatenations of size 1000, which are plausible in generated code (I started this after finding one of size 729).

/cc @griesemer

@rsc rsc added this to the Go1.11 milestone Jan 5, 2018
@griesemer griesemer self-assigned this Jan 5, 2018
@griesemer griesemer modified the milestones: Go1.11, Go1.12 Jun 4, 2018
Copy link

@griesemer griesemer commented Jun 4, 2018

Too late for 1.11.

Copy link

@griesemer griesemer commented Dec 5, 2018

Too late for 1.12.

@griesemer griesemer modified the milestones: Go1.12, Go1.13 Dec 5, 2018
Copy link

@gopherbot gopherbot commented Dec 24, 2018

Change mentions this issue: go/printer: generalize bench harness, add unbalanced benchmark

@griesemer griesemer modified the milestones: Go1.13, Go1.14 May 6, 2019
@rsc rsc modified the milestones: Go1.14, Backlog Oct 9, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
4 participants