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

cmd/gc: superlinear slow-down compiling slice of interface literal #8354

Closed
bradfitz opened this issue Jul 10, 2014 · 7 comments
Closed

cmd/gc: superlinear slow-down compiling slice of interface literal #8354

bradfitz opened this issue Jul 10, 2014 · 7 comments
Labels
FrozenDueToAge
Milestone
Go1.3.1

Comments

@bradfitz
Copy link
Contributor 

As the number of elements in a slice of interface literal grows, cmd/gc slows down more
than linearly:

http://play.golang.org/p/5TDTCtaP3Q


package main

type I interface {
    foo()
}

type S string

func (S) foo() {}

var s = []I{
    S("foo"),
    S("foo"),
    S("foo"),
    S("foo"),
    S("foo"),
    S("foo"),
    S("foo"),
    S("foo"),
    S("foo"),
...


Observed times for "go build x.go":

  100   0.003s
 1000   0.187s
 2000   0.784s
 3000   1.593s
 4000   2.655s
 5000   4.016s
 6000   5.685s
 7000   7.600s
14000   29.234s
@bradfitz
Copy link
Contributor Author

Comment 1:

It also happens with append:
var s [5000]I
func init() {
    _ = append(s[:],
                S("foo"),
                S("foo"),
                S("foo"),
        S("foo"),
        S("foo"),
        S("foo"),
        S("foo"),
.....

@gopherbot
Copy link

Comment 2:

CL https://golang.org/cl/125720043 mentions this issue.

@rsc
Copy link
Contributor

rsc commented Aug 6, 2014

Comment 3:

This issue was closed by revision 7aa3031.

Status changed to Fixed.

@bradfitz
Copy link
Contributor Author

Comment 4:

Comparing tip to Go 1.3 (1.3.0):
With 5000 elements: 9.68x faster.
With 10000 elements: 17.95x faster.
5000:
mac:~ bradfitz$ time go13 build x.go
real    0m9.414s
user    0m9.135s
sys 0m0.211s
mac:~ bradfitz$ time go build x.go
real    0m0.972s
user    0m0.809s
sys 0m0.142s
10,000:
mac:~ bradfitz$ time go13 build x.go
real    0m52.722s
user    0m51.368s
sys 0m0.769s
mac:~ bradfitz$ time go build x.go
real    0m2.937s
user    0m2.441s
sys 0m0.397s

@rsc
Copy link
Contributor

rsc commented Aug 12, 2014

Comment 5:

Approved for Go 1.3.1 (CL 125720043).

Labels changed: added release-go1.3.1, removed release-go1.4.

@adg
Copy link
Contributor

adg commented Aug 12, 2014

Comment 6:

This issue was closed by revision 23f1ebe74d90.

@adg
Copy link
Contributor

adg commented Aug 12, 2014

Comment 7:

Applied to release-branch.go1.3.

@rsc rsc added this to the Go1.3.1 milestone Apr 14, 2015
adg added a commit that referenced this issue May 11, 2015
@adg
[release-branch.go1.3] cmd/gc: make liveness ~10x faster
69dc3a9 
««« CL 125720043 / b92e5df7d3ba
cmd/gc: make liveness ~10x faster

1) The arrayindexof lookup function is O(n). Replace with O(1) lookups.

2) The checkptxt function is O(n²) and is purely for debugging.
Only run when the debugging flags are turned on.

3) Iterating over sparse bitmaps can be done faster word by word.
Introduce and use bvnext for that.

Run times before and after, on my 2.5 GHz Core i5 MacBook Pro.

x.go       9.48  0.84  issue 8259

x100.go    0.01  0.01  issue 8354
x1000.go   0.10  0.10
x2000.go   0.62  0.19
x3000.go   1.33  0.34
x4000.go   2.29  0.49
x5000.go   3.89  0.67
x6000.go   5.00  0.90
x7000.go   6.70  1.13
x8000.go   9.44  1.38
x9000.go  11.23  1.87
x10000.go 13.78  2.09

Fixes #8259.
Fixes #8354.

LGTM=iant, r
R=golang-codereviews, iant, r
CC=golang-codereviews
https://golang.org/cl/125720043
»»»

TBR=rsc
CC=golang-codereviews
https://golang.org/cl/121600043
@golang golang locked and limited conversation to collaborators Jun 25, 2016
wheatman pushed a commit to wheatman/go-akaros that referenced this issue Jun 25, 2018
@rsc @wheatman
cmd/gc: make liveness ~10x faster
6ca573b 
1) The arrayindexof lookup function is O(n). Replace with O(1) lookups.

2) The checkptxt function is O(n²) and is purely for debugging.
Only run when the debugging flags are turned on.

3) Iterating over sparse bitmaps can be done faster word by word.
Introduce and use bvnext for that.

Run times before and after, on my 2.5 GHz Core i5 MacBook Pro.

x.go       9.48  0.84  issue 8259

x100.go    0.01  0.01  issue 8354
x1000.go   0.10  0.10
x2000.go   0.62  0.19
x3000.go   1.33  0.34
x4000.go   2.29  0.49
x5000.go   3.89  0.67
x6000.go   5.00  0.90
x7000.go   6.70  1.13
x8000.go   9.44  1.38
x9000.go  11.23  1.87
x10000.go 13.78  2.09

Fixes golang#8259.
Fixes golang#8354.

LGTM=iant, r
R=golang-codereviews, iant, r
CC=golang-codereviews
https://golang.org/cl/125720043
wheatman pushed a commit to wheatman/go-akaros that referenced this issue Jul 9, 2018
@rsc @wheatman
cmd/gc: make liveness ~10x faster
53fd14c 
1) The arrayindexof lookup function is O(n). Replace with O(1) lookups.

2) The checkptxt function is O(n²) and is purely for debugging.
Only run when the debugging flags are turned on.

3) Iterating over sparse bitmaps can be done faster word by word.
Introduce and use bvnext for that.

Run times before and after, on my 2.5 GHz Core i5 MacBook Pro.

x.go       9.48  0.84  issue 8259

x100.go    0.01  0.01  issue 8354
x1000.go   0.10  0.10
x2000.go   0.62  0.19
x3000.go   1.33  0.34
x4000.go   2.29  0.49
x5000.go   3.89  0.67
x6000.go   5.00  0.90
x7000.go   6.70  1.13
x8000.go   9.44  1.38
x9000.go  11.23  1.87
x10000.go 13.78  2.09

Fixes golang#8259.
Fixes golang#8354.

LGTM=iant, r
R=golang-codereviews, iant, r
CC=golang-codereviews
https://golang.org/cl/125720043
This issue was closed.
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Assignees
No one assigned
Labels
FrozenDueToAge
Projects
None yet
Milestone
Go1.3.1
Development

No branches or pull requests
4 participants
@bradfitz @rsc @adg @gopherbot