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/link: loading N packages takes O(N²) time #20578

Closed
rsc opened this issue Jun 5, 2017 · 4 comments

Comments

Projects
None yet
4 participants
@rsc
Copy link
Contributor

commented Jun 5, 2017

There are some deduplication scans in the linker to avoid loading the same package (same import path) multiple times. These use a linear scan over all packages already loaded, so loading N packages takes O(N²) time (even with no duplicates). These scans should be replaced by map checks, cutting the time for N packages to O(N).

I have a CL and will send it.

@rsc rsc added this to the Go1.9 milestone Jun 5, 2017

@rsc rsc self-assigned this Jun 5, 2017

@gopherbot

This comment has been minimized.

Copy link

commented Jun 5, 2017

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

Llewellynvdm pushed a commit to Llewellynvdm/go that referenced this issue Jun 5, 2017

cmd/link: fix accidentally-quadratic library loading
Programs built from N libraries required O(N²) time to do the
deduplication checks, even if there were never any duplicates.
In most programs N is small enough not to worry, but this may
affect large programs.

Noticed by inspection, not any specific bug report.

Fixes golang#20578.

Change-Id: Ic4108f1058be39da990a79b1e0b8ce95fde44cef
Reviewed-on: https://go-review.googlesource.com/44852
Run-TryBot: Russ Cox <rsc@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Ian Lance Taylor <iant@golang.org>
@odeke-em

This comment has been minimized.

Copy link
Member

commented Jun 5, 2017

Hmm, how come gobot didn't close this issue when CL https://go-review.googlesource.com/c/44852/ was merged into master as 51711d1.

@bradfitz

This comment has been minimized.

Copy link
Member

commented Jun 5, 2017

Maybe because Github has been having problems today? https://status.github.com/messages

@bradfitz bradfitz closed this Jun 5, 2017

@odeke-em

This comment has been minimized.

Copy link
Member

commented Jun 5, 2017

Ah, gotcha.

@golang golang locked and limited conversation to collaborators Jun 5, 2018

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
You can’t perform that action at this time.