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: traverse the symbol table less #14624

Open
josharian opened this Issue Mar 3, 2016 · 3 comments

Comments

Projects
None yet
4 participants
@josharian
Contributor

josharian commented Mar 3, 2016

@ianlancetaylor commented in CL 20165:

The single slowest operation a linker can do is traverse the symbol table and look at every symbol. The single biggest improvement in link time in the gold linker was changing the number of symbol table traversals from about 25 to about 3. Yet cmd/link traverses the entire symbol table all the time. It's not good.

@crawshaw replied:

Agreed. There are a couple of other not good features:

  • LSym has a Type word, but it's not filled out until some nebulous intermediate pass, so lots of code (like this) ends up string matching on the symbol name prefix.
  • dodata does some odd build-a-linked-list, then sort-the-linked-list-into-segments game.

I think these problems and the many traversals could be fixed by the object file reader assigning Type and building useful link-wide slices when a symbol is read in. But it is pretty major surgery I'm not ready to perform.

I've moved this to an issue, since folks look for work and ideas in issues.

cc @mwhudson who likes object files. :)

@mwhudson

This comment has been minimized.

Contributor

mwhudson commented Mar 3, 2016

Heh heh. I can't really see any reason why the loop in symtab couldn't be
done when the symbol is read from the file, although I wouldn't be
surprised if a hundred fiddly things depend on the current ordering (symtab
is called quite late in the process). Maybe I could just try it.

dodata is a horrifying mess of its own. Would be nice to rewrite it but I
think I'm definitely too scared.

On 4 March 2016 at 09:03, Josh Bleecher Snyder notifications@github.com
wrote:

@ianlancetaylor https://github.com/ianlancetaylor commented in CL 20165:

The single slowest operation a linker can do is traverse the symbol table
and look at every symbol. The single biggest improvement in link time in
the gold linker was changing the number of symbol table traversals from
about 25 to about 3. Yet cmd/link traverses the entire symbol table all the
time. It's not good.

@crawshaw https://github.com/crawshaw replied:

Agreed. There are a couple of other not good features:

  • LSym has a Type word, but it's not filled out until some nebulous
    intermediate pass, so lots of code (like this) ends up string matching on
    the symbol name prefix.
  • dodata does some odd build-a-linked-list, then
    sort-the-linked-list-into-segments game.

I think these problems and the many traversals could be fixed by the
object file reader assigning Type and building useful link-wide slices when
a symbol is read in. But it is pretty major surgery I'm not ready to
perform.

I've moved this to an issue, since folks look for work and ideas in issues.

cc @mwhudson https://github.com/mwhudson who likes object files. :)


Reply to this email directly or view it on GitHub
#14624.

@bradfitz bradfitz added this to the Unplanned milestone Apr 10, 2016

@josharian josharian added ToolSpeed and removed Performance labels Apr 16, 2017

@gopherbot

This comment has been minimized.

gopherbot commented Apr 17, 2017

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

josharian added a commit to josharian/go that referenced this issue Apr 19, 2017

cmd/internal/obj: fix LSym.Type during compilation, not linking
Prior to this CL, the compiler and assembler
were sloppy about the LSym.Type for LSyms
containing static data.

The linker then fixed this up, converting
Sxxx and SBSS to SDATA, and SNOPTRBSS to SNOPTRDATA
if it noticed that the symbol had associated data.

It is preferable to just get this right in cmd/compile
and cmd/asm, because it removes an unnecessary traversal
of the symbol table from the linker (see golang#14624).
Do this by touching up the LSym.Type fixes in
LSym.prepwrite and Link.Globl.

I have confirmed by instrumenting the linker
that the now-eliminated code paths were unreached.
And an additional check in the object file writing code
will help preserve that invariant.

Does not pass toolstash-check,
but does generate identical linked binaries.

No compiler performance changes.

Change-Id: I77b071ab103685ff8e042cee9abb864385488872

gopherbot pushed a commit that referenced this issue May 2, 2017

cmd/internal/obj: fix LSym.Type during compilation, not linking
Prior to this CL, the compiler and assembler
were sloppy about the LSym.Type for LSyms
containing static data.

The linker then fixed this up, converting
Sxxx and SBSS to SDATA, and SNOPTRBSS to SNOPTRDATA
if it noticed that the symbol had associated data.

It is preferable to just get this right in cmd/compile
and cmd/asm, because it removes an unnecessary traversal
of the symbol table from the linker (see #14624).
Do this by touching up the LSym.Type fixes in
LSym.prepwrite and Link.Globl.

I have confirmed by instrumenting the linker
that the now-eliminated code paths were unreached.
And an additional check in the object file writing code
will help preserve that invariant.

There was a case in the Windows linker,
with internal linking and cgo,
where we were generating SNOPTRBSS symbols with data.
For now, convert those at the site at which they occur
into SNOPTRDATA, just like they were.

Does not pass toolstash-check,
but does generate identical linked binaries.

No compiler performance changes.

Change-Id: I77b071ab103685ff8e042cee9abb864385488872
Reviewed-on: https://go-review.googlesource.com/40864
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Alex Brainman <alex.brainman@gmail.com>
Reviewed-by: Michael Hudson-Doyle <michael.hudson@canonical.com>

josharian added a commit to josharian/go that referenced this issue May 2, 2017

cmd/internal/obj: fix LSym.Type during compilation, not linking
Prior to this CL, the compiler and assembler
were sloppy about the LSym.Type for LSyms
containing static data.

The linker then fixed this up, converting
Sxxx and SBSS to SDATA, and SNOPTRBSS to SNOPTRDATA
if it noticed that the symbol had associated data.

It is preferable to just get this right in cmd/compile
and cmd/asm, because it removes an unnecessary traversal
of the symbol table from the linker (see golang#14624).
Do this by touching up the LSym.Type fixes in
LSym.prepwrite and Link.Globl.

I have confirmed by instrumenting the linker
that the now-eliminated code paths were unreached.
And an additional check in the object file writing code
will help preserve that invariant.

There was a case in the Windows linker,
with internal linking and cgo,
where we were generating SNOPTRBSS symbols with data.
For now, convert those at the site at which they occur
into SNOPTRDATA, just like they were.

Does not pass toolstash-check,
but does generate identical linked binaries.

No compiler performance changes.

Change-Id: I77b071ab103685ff8e042cee9abb864385488872
@gopherbot

This comment has been minimized.

gopherbot commented May 17, 2018

Change https://golang.org/cl/113635 mentions this issue: cmd/link/internal/ld: don't call fieldtrack if it's not enabled

gopherbot pushed a commit that referenced this issue May 17, 2018

cmd/link/internal/ld: don't call fieldtrack if it's not enabled
If go toolchain is not built with GOEXPERIMENT=fieldtrack,
skip fieldtrack pass in the linker as it does full symtab traversal.

For linking "hello world" example from net/http:

	name      old time/op  new time/op  delta
	Linker-4   530ms ± 2%   525ms ± 2%  -1.03%  (p=0.028 n=17+19)

Fixes #20318
Updates #14624

Change-Id: I99336513db77d13f95f47d27339d76f01c42a5da
Reviewed-on: https://go-review.googlesource.com/113635
Run-TryBot: Iskander Sharipov <iskander.sharipov@intel.com>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment