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.

Sign up for GitHub

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

Jump to bottom

go/types: inefficient handling of large string additions #23348

Closed
rsc opened this issue Jan 5, 2018 · 2 comments
Closed

go/types: inefficient handling of large string additions #23348

rsc opened this issue Jan 5, 2018 · 2 comments
Labels
FrozenDueToAge release-blocker
Milestone
Go1.10

Comments

@rsc
Copy link
Contributor

rsc commented Jan 5, 2018

Given a program with a large string addition

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

go/types creates a quadratic amount of garbage evaluating the string corresponding to each of the N subexpressions of the concatenation. This makes go/types-based tools like cmd/vet run out of memory easily. Now that vet is run during go test that's a bigger problem than it used to be.

There is a simple fix: let go/types keep adding the pieces as it does, but make go/constant construct the final value lazily. I will send a CL for this for Go 1.10.

/cc @griesemer @adonovan

See the vet failures in #23222 and in particular #23222 (comment) for more details. CL on its way.
@rsc rsc added this to the Go1.10 milestone Jan 5, 2018
@rsc
Copy link
Contributor Author

rsc commented Jan 5, 2018

Before (32-bit on Mac):

      1000  int   0.024s  strbal   0.005s  strbigbal   0.020s  str   0.008s  strbig    0.287s
      2000  int   0.014s  strbal   0.007s  strbigbal   0.039s  str   0.014s  strbig    1.115s
      4000  int   0.033s  strbal   0.010s  strbigbal   0.072s  str   0.022s  strbig      mem! 
      8000  int   0.074s  strbal   0.016s  strbigbal   0.142s  str   0.040s
     16000  int   0.208s  strbal   0.033s  strbigbal   0.290s  str   0.091s
     32000  int   0.608s  strbal   0.060s  strbigbal   0.616s  str   0.188s
     64000  int   1.843s  strbal   0.131s  strbigbal   1.222s  str   0.374s
    128000  int  stack!   strbal   0.272s  strbigbal   2.585s  str   stack! 
    256000  int  stack!   strbal   0.640s  strbigbal     mem!   str  stack!

After CL:

      1000  int   0.023s  strbal   0.005s  strbigbal   0.013s  str   0.008s  strbig    0.016s
      2000  int   0.013s  strbal   0.006s  strbigbal   0.024s  str   0.012s  strbig    0.028s
      4000  int   0.022s  strbal   0.009s  strbigbal   0.040s  str   0.020s  strbig    0.051s
      8000  int   0.043s  strbal   0.017s  strbigbal   0.075s  str   0.040s  strbig    0.101s
     16000  int   0.081s  strbal   0.030s  strbigbal   0.150s  str   0.088s  strbig    0.199s
     32000  int   0.198s  strbal   0.059s  strbigbal   0.293s  str   0.188s  strbig    0.388s
     64000  int   0.400s  strbal   0.133s  strbigbal   0.605s  str   0.391s  strbig    0.838s
    128000  int   stack!  strbal   0.273s  strbigbal   1.242s  str   stack!  strbig    stack!
    256000  int   stack!  strbal   0.515s  strbigbal   2.545s  str   stack!

I think that's good enough.

@gopherbot
Copy link

Change https://golang.org/cl/86395 mentions this issue: go/constant: make string addition compute actual string lazily

@golang golang locked and limited conversation to collaborators Jan 5, 2019
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
FrozenDueToAge release-blocker
Projects
None yet
Milestone
Go1.10
Development

No branches or pull requests
2 participants
@rsc @gopherbot