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/compile: add column info to export data #28259

Open
alandonovan opened this issue Oct 17, 2018 · 24 comments
Assignees
Labels
Milestone

Comments

@alandonovan
Copy link
Contributor

@alandonovan alandonovan commented Oct 17, 2018

None of the compiler's historical or present export data formats ($$, $$B, indexed) support column information, even though the compiler and the go/{token,ast,types}) packages are capable of producing and consuming this information. We should add it to the export data file using a suitably efficient encoding.

Otherwise various analysis tools will continue to report either the correct column, or column 1, depending on whether they are reporting the position of an object loaded from source or export data.

@ianthehat

@griesemer

This comment has been minimized.

Copy link
Contributor

@griesemer griesemer commented Oct 17, 2018

We should do this for the new indexed format. The old formats are not produced anymore .

@alandonovan

This comment has been minimized.

Copy link
Contributor Author

@alandonovan alandonovan commented Oct 17, 2018

There is no golang.org/x/tools/go/internal/gcimporter/iexport.go, so go/types today can only export in the $$B format. Should I file a separate issue to port iexport.go to go/types?

@griesemer

This comment has been minimized.

Copy link
Contributor

@griesemer griesemer commented Oct 17, 2018

@alandonovan Yes, please. I think this would have to be an x/tools issue. The std lib doesn't support this mechanism even for the $BB format. (And I am about to remove the support for importing the $BB format from the std lib's gcimporter.)

@FiloSottile FiloSottile added this to the Unplanned milestone Oct 19, 2018
@mdempsky

This comment has been minimized.

Copy link
Member

@mdempsky mdempsky commented Sep 23, 2019

I think the first step is deciding how to encode position information.

iexport inherited the optimized position encoding from bexport, which used delta encoding for line numbers within the same source file, and then an escape sequence for file:line pairs in another file.

Off hand, I can imagine a handful of different ways we might try encoding file:line:column deltas, but no clear idea of which would be best. Simplest would probably be to continue using the existing scheme for the "file:line" delta, and then an extra int64() for a separate "column" delta.

Does DWARF have any clever (and hopefully not overly clever) way of efficiently encoding file:line:column tuples?

@mdempsky

This comment has been minimized.

Copy link
Member

@mdempsky mdempsky commented Sep 23, 2019

go/internal/gcimporter.fakeFileSet will need work too, to be able to return positions with columns:

https://github.com/golang/go/blob/master/src/go/internal/gcimporter/bimport.go#L340-L366

The cmd/compile side of things looks straight forward though.

@alandonovan

This comment has been minimized.

Copy link
Contributor Author

@alandonovan alandonovan commented Sep 23, 2019

For Starlark's bytecode format I found delta encoding of columns worked nicely. When encoding a sequence of file positions, column numbers tend to increase in small increments within each line. Even across newlines there is lots of locality because all the statements in a loop body (say) are similarly indented. See:
https://github.com/google/starlark-go/blob/master/internal/compile/compile.go#L430

@gopherbot

This comment has been minimized.

Copy link

@gopherbot gopherbot commented Sep 23, 2019

Change https://golang.org/cl/196963 mentions this issue: cmd/compile: add column details to export data

@mdempsky

This comment has been minimized.

Copy link
Member

@mdempsky mdempsky commented Sep 23, 2019

CL 196963 naively adds delta-encoded column position information, and it appears to grow export data by about 9%:

[Geo mean] +9.29%
name                                                                               old alloc/op  new alloc/op  delta
ExportSize:archive/tar                                                              10.5kB ± 0%   11.6kB ± 0%  +10.84%
ExportSize:archive/zip                                                              17.3kB ± 0%   19.0kB ± 0%   +9.98%
ExportSize:bufio                                                                    4.04kB ± 0%   4.51kB ± 0%  +11.53%
ExportSize:bytes                                                                    8.51kB ± 0%   9.46kB ± 0%  +11.20%
ExportSize:bytes/hash                                                               1.01kB ± 0%   1.13kB ± 0%  +11.23%
ExportSize:cmd/asm/internal/arch                                                    15.3kB ± 0%   16.7kB ± 0%   +9.14%
ExportSize:cmd/asm/internal/asm                                                     29.3kB ± 0%   32.3kB ± 0%  +10.34%
ExportSize:cmd/asm/internal/flags                                                     570B ± 0%     613B ± 0%   +7.54%
ExportSize:cmd/asm/internal/lex                                                     17.2kB ± 0%   19.0kB ± 0%  +10.80%
ExportSize:cmd/compile/internal/amd64                                               46.1kB ± 0%   50.7kB ± 0%  +10.01%
ExportSize:cmd/compile/internal/arm                                                 45.1kB ± 0%   49.6kB ± 0%   +9.98%
ExportSize:cmd/compile/internal/arm64                                               45.1kB ± 0%   49.6kB ± 0%   +9.98%
ExportSize:cmd/compile/internal/gc                                                   109kB ± 0%    120kB ± 0%   +9.70%
ExportSize:cmd/compile/internal/mips                                                45.1kB ± 0%   49.6kB ± 0%   +9.98%
ExportSize:cmd/compile/internal/mips64                                              45.1kB ± 0%   49.6kB ± 0%   +9.98%
ExportSize:cmd/compile/internal/ppc64                                               46.1kB ± 0%   50.7kB ± 0%  +10.01%
ExportSize:cmd/compile/internal/s390x                                               45.8kB ± 0%   50.4kB ± 0%  +10.04%
ExportSize:cmd/compile/internal/ssa                                                  137kB ± 0%    146kB ± 0%   +6.16%
ExportSize:cmd/compile/internal/ssa/builder                                         35.1kB ± 0%   38.7kB ± 0%  +10.08%
ExportSize:cmd/compile/internal/syntax                                              7.31kB ± 0%   7.88kB ± 0%   +7.71%
ExportSize:cmd/compile/internal/test                                                 16.0B ± 0%    16.0B ± 0%    0.00%
ExportSize:cmd/compile/internal/types                                               33.1kB ± 0%   36.4kB ± 0%   +9.91%
ExportSize:cmd/compile/internal/wasm                                                45.7kB ± 0%   50.3kB ± 0%  +10.06%
ExportSize:cmd/compile/internal/x86                                                 45.1kB ± 0%   49.6kB ± 0%   +9.98%
ExportSize:cmd/go/internal/auth                                                     21.9kB ± 0%   24.0kB ± 0%   +9.70%
ExportSize:cmd/go/internal/base                                                     16.4kB ± 0%   18.0kB ± 0%   +9.90%
ExportSize:cmd/go/internal/bug                                                      13.9kB ± 0%   15.4kB ± 0%  +10.59%
ExportSize:cmd/go/internal/cache                                                    8.73kB ± 0%   9.65kB ± 0%  +10.49%
ExportSize:cmd/go/internal/cfg                                                      11.2kB ± 0%   12.2kB ± 0%   +8.96%
ExportSize:cmd/go/internal/clean                                                    14.0kB ± 0%   15.4kB ± 0%  +10.56%
ExportSize:cmd/go/internal/cmdflag                                                    712B ± 0%     768B ± 0%   +7.87%
ExportSize:cmd/go/internal/dirhash                                                    554B ± 0%     604B ± 0%   +9.03%
ExportSize:cmd/go/internal/doc                                                      14.0kB ± 0%   15.5kB ± 0%  +10.53%
ExportSize:cmd/go/internal/envcmd                                                   14.2kB ± 0%   15.7kB ± 0%  +10.39%
ExportSize:cmd/go/internal/fix                                                      14.0kB ± 0%   15.5kB ± 0%  +10.56%
ExportSize:cmd/go/internal/fmtcmd                                                   14.0kB ± 0%   15.5kB ± 0%  +10.56%
ExportSize:cmd/go/internal/generate                                                 14.5kB ± 0%   16.0kB ± 0%  +10.40%
ExportSize:cmd/go/internal/get                                                      15.5kB ± 0%   17.1kB ± 0%  +10.27%
ExportSize:cmd/go/internal/help                                                     14.3kB ± 0%   15.8kB ± 0%  +10.39%
ExportSize:cmd/go/internal/imports                                                  1.12kB ± 0%   1.21kB ± 0%   +8.24%
ExportSize:cmd/go/internal/list                                                     15.1kB ± 0%   16.7kB ± 0%  +10.47%
ExportSize:cmd/go/internal/load                                                     12.4kB ± 0%   13.6kB ± 0%   +9.30%
ExportSize:cmd/go/internal/lockedfile                                               13.9kB ± 0%   15.3kB ± 0%  +10.04%
ExportSize:cmd/go/internal/lockedfile/internal/filelock                             6.53kB ± 0%   7.21kB ± 0%  +10.45%
ExportSize:cmd/go/internal/modcmd                                                   14.1kB ± 0%   15.6kB ± 0%  +10.47%
ExportSize:cmd/go/internal/modconv                                                  4.48kB ± 0%   4.86kB ± 0%   +8.50%
ExportSize:cmd/go/internal/modfetch                                                 17.7kB ± 0%   19.5kB ± 0%  +10.18%
ExportSize:cmd/go/internal/modfetch/codehost                                        7.25kB ± 0%   7.98kB ± 0%  +10.05%
ExportSize:cmd/go/internal/modfile                                                  11.2kB ± 0%   12.3kB ± 0%  +10.06%
ExportSize:cmd/go/internal/modget                                                   14.0kB ± 0%   15.5kB ± 0%  +10.50%
ExportSize:cmd/go/internal/modinfo                                                  5.67kB ± 0%   6.29kB ± 0%  +10.97%
ExportSize:cmd/go/internal/modload                                                  26.8kB ± 0%   29.5kB ± 0%  +10.31%
ExportSize:cmd/go/internal/module                                                   1.35kB ± 0%   1.46kB ± 0%   +7.91%
ExportSize:cmd/go/internal/mvs                                                      1.01kB ± 0%   1.11kB ± 0%   +9.07%
ExportSize:cmd/go/internal/note                                                     1.55kB ± 0%   1.67kB ± 0%   +7.40%
ExportSize:cmd/go/internal/par                                                      1.99kB ± 0%   2.16kB ± 0%   +8.48%
ExportSize:cmd/go/internal/renameio                                                 1.35kB ± 0%   1.48kB ± 0%   +9.48%
ExportSize:cmd/go/internal/robustio                                                   845B ± 0%     909B ± 0%   +7.57%
ExportSize:cmd/go/internal/run                                                      14.0kB ± 0%   15.5kB ± 0%  +10.56%
ExportSize:cmd/go/internal/search                                                   1.03kB ± 0%   1.11kB ± 0%   +8.67%
ExportSize:cmd/go/internal/semver                                                     749B ± 0%     829B ± 0%  +10.68%
ExportSize:cmd/go/internal/str                                                        647B ± 0%     712B ± 0%  +10.05%
ExportSize:cmd/go/internal/sumweb                                                   29.3kB ± 0%   32.2kB ± 0%   +9.65%
ExportSize:cmd/go/internal/test                                                     14.1kB ± 0%   15.6kB ± 0%  +10.41%
ExportSize:cmd/go/internal/tlog                                                     3.12kB ± 0%   3.40kB ± 0%   +8.87%
ExportSize:cmd/go/internal/tool                                                     13.9kB ± 0%   15.4kB ± 0%  +10.59%
ExportSize:cmd/go/internal/txtar                                                      280B ± 0%     298B ± 0%   +6.43%
ExportSize:cmd/go/internal/version                                                  14.0kB ± 0%   15.5kB ± 0%  +10.56%
ExportSize:cmd/go/internal/vet                                                      14.1kB ± 0%   15.6kB ± 0%  +10.47%
ExportSize:cmd/go/internal/web                                                      3.65kB ± 0%   3.97kB ± 0%   +9.00%
ExportSize:cmd/go/internal/work                                                     31.9kB ± 0%   35.2kB ± 0%  +10.37%
ExportSize:cmd/internal/bio                                                         15.6kB ± 0%   17.2kB ± 0%  +10.49%
ExportSize:cmd/internal/browser                                                       134B ± 0%     140B ± 0%   +4.48%
ExportSize:cmd/internal/buildid                                                       556B ± 0%     592B ± 0%   +6.47%
ExportSize:cmd/internal/dwarf                                                       15.8kB ± 0%   16.5kB ± 0%   +4.41%
ExportSize:cmd/internal/edit                                                          882B ± 0%     987B ± 0%  +11.90%
ExportSize:cmd/internal/gcprog                                                        804B ± 0%     879B ± 0%   +9.33%
ExportSize:cmd/internal/goobj                                                       10.4kB ± 0%   11.4kB ± 0%   +9.97%
ExportSize:cmd/internal/obj                                                         21.2kB ± 0%   23.2kB ± 0%   +9.28%
ExportSize:cmd/internal/objabi                                                      8.97kB ± 0%   9.61kB ± 0%   +7.13%
ExportSize:cmd/internal/obj/arm                                                     17.2kB ± 0%   18.5kB ± 0%   +7.43%
ExportSize:cmd/internal/obj/arm64                                                   44.2kB ± 0%   46.9kB ± 0%   +6.18%
ExportSize:cmd/internal/objfile                                                     25.4kB ± 0%   28.1kB ± 0%  +10.65%
ExportSize:cmd/internal/obj/mips                                                    19.5kB ± 0%   21.1kB ± 0%   +7.95%
ExportSize:cmd/internal/obj/ppc64                                                   35.6kB ± 0%   38.5kB ± 0%   +8.04%
ExportSize:cmd/internal/obj/riscv                                                   19.0kB ± 0%   20.3kB ± 0%   +7.06%
ExportSize:cmd/internal/obj/s390x                                                   28.7kB ± 0%   30.5kB ± 0%   +6.36%
ExportSize:cmd/internal/obj/wasm                                                    17.0kB ± 0%   18.2kB ± 0%   +7.25%
ExportSize:cmd/internal/obj/x86                                                     61.5kB ± 0%   65.1kB ± 0%   +5.80%
ExportSize:cmd/internal/src                                                         5.36kB ± 0%   5.99kB ± 0%  +11.83%
ExportSize:cmd/internal/sys                                                         1.54kB ± 0%   1.67kB ± 0%   +8.29%
ExportSize:cmd/internal/test2json                                                     335B ± 0%     357B ± 0%   +6.57%
ExportSize:cmd/link/internal/amd64                                                  27.7kB ± 0%   30.5kB ± 0%  +10.15%
ExportSize:cmd/link/internal/arm                                                    28.2kB ± 0%   31.0kB ± 0%   +9.93%
ExportSize:cmd/link/internal/arm64                                                  28.1kB ± 0%   30.9kB ± 0%   +9.93%
ExportSize:cmd/link/internal/ld                                                     64.7kB ± 0%   69.8kB ± 0%   +7.77%
ExportSize:cmd/link/internal/loadelf                                                24.1kB ± 0%   26.4kB ± 0%   +9.32%
ExportSize:cmd/link/internal/loadmacho                                              21.7kB ± 0%   23.8kB ± 0%   +9.45%
ExportSize:cmd/link/internal/loadpe                                                 24.3kB ± 0%   26.4kB ± 0%   +8.72%
ExportSize:cmd/link/internal/loadxcoff                                              20.8kB ± 0%   22.8kB ± 0%   +9.73%
ExportSize:cmd/link/internal/mips                                                   28.2kB ± 0%   31.1kB ± 0%   +9.93%
ExportSize:cmd/link/internal/mips64                                                 28.2kB ± 0%   31.0kB ± 0%   +9.94%
ExportSize:cmd/link/internal/objfile                                                16.3kB ± 0%   17.9kB ± 0%   +9.53%
ExportSize:cmd/link/internal/ppc64                                                  28.3kB ± 0%   31.1kB ± 0%   +9.88%
ExportSize:cmd/link/internal/s390x                                                  28.0kB ± 0%   30.8kB ± 0%   +9.95%
ExportSize:cmd/link/internal/sym                                                    13.2kB ± 0%   14.4kB ± 0%   +9.13%
ExportSize:cmd/link/internal/wasm                                                   27.7kB ± 0%   30.4kB ± 0%   +9.92%
ExportSize:cmd/link/internal/x86                                                    28.2kB ± 0%   30.9kB ± 0%   +9.92%
ExportSize:cmd/vendor/github.com/google/pprof/driver                                46.2kB ± 0%   50.7kB ± 0%   +9.88%
ExportSize:cmd/vendor/github.com/google/pprof/internal/binutils                     14.4kB ± 0%   15.7kB ± 0%   +9.52%
ExportSize:cmd/vendor/github.com/google/pprof/internal/driver                       39.9kB ± 0%   43.8kB ± 0%   +9.85%
ExportSize:cmd/vendor/github.com/google/pprof/internal/elfexec                      9.14kB ± 0%  10.04kB ± 0%   +9.80%
ExportSize:cmd/vendor/github.com/google/pprof/internal/graph                        14.7kB ± 0%   16.0kB ± 0%   +8.97%
ExportSize:cmd/vendor/github.com/google/pprof/internal/measurement                  11.8kB ± 0%   12.8kB ± 0%   +8.57%
ExportSize:cmd/vendor/github.com/google/pprof/internal/plugin                       44.9kB ± 0%   49.3kB ± 0%   +9.70%
ExportSize:cmd/vendor/github.com/google/pprof/internal/report                       31.9kB ± 0%   35.3kB ± 0%  +10.62%
ExportSize:cmd/vendor/github.com/google/pprof/internal/symbolizer                   43.8kB ± 0%   48.1kB ± 0%   +9.64%
ExportSize:cmd/vendor/github.com/google/pprof/internal/symbolz                      11.8kB ± 0%   12.8kB ± 0%   +8.59%
ExportSize:cmd/vendor/github.com/google/pprof/internal/transport                    34.0kB ± 0%   37.2kB ± 0%   +9.37%
ExportSize:cmd/vendor/github.com/google/pprof/profile                               11.2kB ± 0%   12.2kB ± 0%   +9.24%
ExportSize:cmd/vendor/github.com/google/pprof/third_party/d3                         136kB ± 0%    136kB ± 0%   +0.00%
ExportSize:cmd/vendor/github.com/google/pprof/third_party/d3flamegraph              24.1kB ± 0%   24.1kB ± 0%   +0.01%
ExportSize:cmd/vendor/github.com/google/pprof/third_party/svgpan                    8.05kB ± 0%   8.05kB ± 0%   +0.01%
ExportSize:cmd/vendor/github.com/ianlancetaylor/demangle                            16.2kB ± 0%   18.1kB ± 0%  +11.99%
ExportSize:cmd/vendor/golang.org/x/arch/arm64/arm64asm                              17.9kB ± 0%   19.5kB ± 0%   +9.38%
ExportSize:cmd/vendor/golang.org/x/arch/arm/armasm                                   124kB ± 0%    129kB ± 0%   +4.09%
ExportSize:cmd/vendor/golang.org/x/arch/ppc64/ppc64asm                              36.8kB ± 0%   38.7kB ± 0%   +5.30%
ExportSize:cmd/vendor/golang.org/x/arch/x86/x86asm                                  18.5kB ± 0%   19.4kB ± 0%   +5.05%
ExportSize:cmd/vendor/golang.org/x/crypto/ssh/terminal                              3.14kB ± 0%   3.37kB ± 0%   +7.33%
ExportSize:cmd/vendor/golang.org/x/sys/unix                                          168kB ± 0%    176kB ± 0%   +5.19%
ExportSize:cmd/vendor/golang.org/x/sys/windows                                       19.0B ± 0%    19.0B ± 0%    0.00%
ExportSize:cmd/vendor/golang.org/x/tools/go/analysis                                35.4kB ± 0%   39.2kB ± 0%  +10.77%
ExportSize:cmd/vendor/golang.org/x/tools/go/analysis/internal/analysisflags         30.8kB ± 0%   34.3kB ± 0%  +11.43%
ExportSize:cmd/vendor/golang.org/x/tools/go/analysis/internal/facts                 7.63kB ± 0%   8.47kB ± 0%  +11.07%
ExportSize:cmd/vendor/golang.org/x/tools/go/analysis/passes/asmdecl                 32.2kB ± 0%   35.7kB ± 0%  +10.73%
ExportSize:cmd/vendor/golang.org/x/tools/go/analysis/passes/assign                  32.5kB ± 0%   36.0kB ± 0%  +10.76%
ExportSize:cmd/vendor/golang.org/x/tools/go/analysis/passes/atomic                  32.5kB ± 0%   36.0kB ± 0%  +10.76%
ExportSize:cmd/vendor/golang.org/x/tools/go/analysis/passes/bools                   30.5kB ± 0%   33.9kB ± 0%  +11.19%
ExportSize:cmd/vendor/golang.org/x/tools/go/analysis/passes/buildtag                32.3kB ± 0%   35.7kB ± 0%  +10.72%
ExportSize:cmd/vendor/golang.org/x/tools/go/analysis/passes/cgocall                 32.2kB ± 0%   35.7kB ± 0%  +10.74%
ExportSize:cmd/vendor/golang.org/x/tools/go/analysis/passes/composite               32.7kB ± 0%   36.2kB ± 0%  +10.58%
ExportSize:cmd/vendor/golang.org/x/tools/go/analysis/passes/copylock                32.5kB ± 0%   36.0kB ± 0%  +10.74%
ExportSize:cmd/vendor/golang.org/x/tools/go/analysis/passes/ctrlflow                34.8kB ± 0%   38.4kB ± 0%  +10.31%
ExportSize:cmd/vendor/golang.org/x/tools/go/analysis/passes/errorsas                32.3kB ± 0%   35.7kB ± 0%  +10.72%
ExportSize:cmd/vendor/golang.org/x/tools/go/analysis/passes/httpresponse            32.8kB ± 0%   36.2kB ± 0%  +10.66%
ExportSize:cmd/vendor/golang.org/x/tools/go/analysis/passes/inspect                 32.2kB ± 0%   35.7kB ± 0%  +10.73%
ExportSize:cmd/vendor/golang.org/x/tools/go/analysis/passes/internal/analysisutil   6.84kB ± 0%   7.54kB ± 0%  +10.17%
ExportSize:cmd/vendor/golang.org/x/tools/go/analysis/passes/loopclosure             32.8kB ± 0%   36.3kB ± 0%  +10.64%
ExportSize:cmd/vendor/golang.org/x/tools/go/analysis/passes/lostcancel              32.6kB ± 0%   36.1kB ± 0%  +10.72%
ExportSize:cmd/vendor/golang.org/x/tools/go/analysis/passes/nilfunc                 32.4kB ± 0%   35.9kB ± 0%  +10.78%
ExportSize:cmd/vendor/golang.org/x/tools/go/analysis/passes/printf                  32.2kB ± 0%   35.7kB ± 0%  +10.73%
ExportSize:cmd/vendor/golang.org/x/tools/go/analysis/passes/shift                   30.5kB ± 0%   33.9kB ± 0%  +11.19%
ExportSize:cmd/vendor/golang.org/x/tools/go/analysis/passes/stdmethods              33.0kB ± 0%   36.5kB ± 0%  +10.58%
ExportSize:cmd/vendor/golang.org/x/tools/go/analysis/passes/structtag               32.4kB ± 0%   35.9kB ± 0%  +10.77%
ExportSize:cmd/vendor/golang.org/x/tools/go/analysis/passes/tests                   32.6kB ± 0%   36.1kB ± 0%  +10.70%
ExportSize:cmd/vendor/golang.org/x/tools/go/analysis/passes/unmarshal               32.3kB ± 0%   35.7kB ± 0%  +10.72%
ExportSize:cmd/vendor/golang.org/x/tools/go/analysis/passes/unreachable             32.5kB ± 0%   36.0kB ± 0%  +10.74%
ExportSize:cmd/vendor/golang.org/x/tools/go/analysis/passes/unsafeptr               32.7kB ± 0%   36.2kB ± 0%  +10.69%
ExportSize:cmd/vendor/golang.org/x/tools/go/analysis/passes/unusedresult            32.6kB ± 0%   36.1kB ± 0%  +10.71%
ExportSize:cmd/vendor/golang.org/x/tools/go/analysis/unitchecker                    15.7kB ± 0%   17.4kB ± 0%  +10.85%
ExportSize:cmd/vendor/golang.org/x/tools/go/ast/astutil                             11.3kB ± 0%   12.6kB ± 0%  +10.97%
ExportSize:cmd/vendor/golang.org/x/tools/go/ast/inspector                           2.17kB ± 0%   2.37kB ± 0%   +9.12%
ExportSize:cmd/vendor/golang.org/x/tools/go/cfg                                     3.37kB ± 0%   3.69kB ± 0%   +9.37%
ExportSize:cmd/vendor/golang.org/x/tools/go/types/objectpath                        2.70kB ± 0%   2.93kB ± 0%   +8.60%
ExportSize:cmd/vendor/golang.org/x/tools/go/types/typeutil                          8.97kB ± 0%   9.80kB ± 0%   +9.23%
ExportSize:compress/bzip2                                                             359B ± 0%     377B ± 0%   +5.01%
ExportSize:compress/flate                                                           4.89kB ± 0%   5.32kB ± 0%   +8.90%
ExportSize:compress/gzip                                                            10.2kB ± 0%   11.2kB ± 0%   +9.93%
ExportSize:compress/lzw                                                               509B ± 0%     546B ± 0%   +7.27%
ExportSize:compress/zlib                                                            5.04kB ± 0%   5.48kB ± 0%   +8.80%
ExportSize:container/heap                                                             346B ± 0%     379B ± 0%   +9.54%
ExportSize:container/list                                                           2.33kB ± 0%   2.64kB ± 0%  +13.49%
ExportSize:container/ring                                                             650B ± 0%     733B ± 0%  +12.77%
ExportSize:context                                                                  5.72kB ± 0%   6.34kB ± 0%  +10.81%
ExportSize:crypto                                                                   1.49kB ± 0%   1.61kB ± 0%   +7.64%
ExportSize:crypto/aes                                                                 597B ± 0%     635B ± 0%   +6.37%
ExportSize:crypto/cipher                                                            1.96kB ± 0%   2.12kB ± 0%   +8.28%
ExportSize:crypto/des                                                                 603B ± 0%     645B ± 0%   +6.97%
ExportSize:crypto/dsa                                                               8.98kB ± 0%  10.00kB ± 0%  +11.42%
ExportSize:crypto/ecdsa                                                             10.3kB ± 0%   11.4kB ± 0%  +11.38%
ExportSize:crypto/ed25519                                                           1.16kB ± 0%   1.25kB ± 0%   +8.47%
ExportSize:crypto/ed25519/internal/edwards25519                                     2.61kB ± 0%   2.83kB ± 0%   +8.32%
ExportSize:crypto/elliptic                                                          10.9kB ± 0%   12.1kB ± 0%  +11.52%
ExportSize:crypto/hmac                                                                534B ± 0%     568B ± 0%   +6.37%
ExportSize:crypto/internal/randutil                                                   201B ± 0%     209B ± 0%   +3.98%
ExportSize:crypto/internal/subtle                                                     374B ± 0%     442B ± 0%  +18.18%
ExportSize:crypto/md5                                                                 874B ± 0%     968B ± 0%  +10.76%
ExportSize:crypto/rand                                                              8.37kB ± 0%   9.49kB ± 0%  +13.36%
ExportSize:crypto/rc4                                                                 507B ± 0%     545B ± 0%   +7.50%
ExportSize:crypto/rsa                                                               11.3kB ± 0%   12.5kB ± 0%  +10.84%
ExportSize:crypto/sha1                                                                986B ± 0%    1093B ± 0%  +10.85%
ExportSize:crypto/sha256                                                              920B ± 0%    1004B ± 0%   +9.13%
ExportSize:crypto/sha512                                                            1.36kB ± 0%   1.50kB ± 0%   +9.75%
ExportSize:crypto/subtle                                                              530B ± 0%     601B ± 0%  +13.40%
ExportSize:crypto/tls                                                               47.4kB ± 0%   52.0kB ± 0%   +9.60%
ExportSize:crypto/x509                                                              30.1kB ± 0%   32.9kB ± 0%   +9.43%
ExportSize:crypto/x509/pkix                                                         15.5kB ± 0%   17.2kB ± 0%  +10.64%
ExportSize:database/sql                                                             25.0kB ± 0%   27.8kB ± 0%  +11.26%
ExportSize:database/sql/driver                                                      15.1kB ± 0%   16.8kB ± 0%  +10.96%
ExportSize:debug/dwarf                                                              14.4kB ± 0%   15.4kB ± 0%   +6.83%
ExportSize:debug/elf                                                                50.1kB ± 0%   53.0kB ± 0%   +5.77%
ExportSize:debug/gosym                                                              3.31kB ± 0%   3.61kB ± 0%   +9.13%
ExportSize:debug/macho                                                              14.6kB ± 0%   15.8kB ± 0%   +8.06%
ExportSize:debug/pe                                                                 11.3kB ± 0%   12.2kB ± 0%   +7.63%
ExportSize:debug/plan9obj                                                           1.54kB ± 0%   1.68kB ± 0%   +8.80%
ExportSize:encoding                                                                   287B ± 0%     303B ± 0%   +5.57%
ExportSize:encoding/ascii85                                                         1.11kB ± 0%   1.21kB ± 0%   +8.84%
ExportSize:encoding/asn1                                                            1.89kB ± 0%   2.03kB ± 0%   +7.02%
ExportSize:encoding/base32                                                          1.81kB ± 0%   1.99kB ± 0%   +9.55%
ExportSize:encoding/base64                                                          1.98kB ± 0%   2.16kB ± 0%   +9.42%
ExportSize:encoding/binary                                                          3.30kB ± 0%   3.84kB ± 0%  +16.50%
ExportSize:encoding/csv                                                             3.14kB ± 0%   3.46kB ± 0%  +10.28%
ExportSize:encoding/gob                                                             11.4kB ± 0%   12.6kB ± 0%  +10.93%
ExportSize:encoding/hex                                                             1.56kB ± 0%   1.70kB ± 0%   +9.16%
ExportSize:encoding/json                                                            15.2kB ± 0%   16.9kB ± 0%  +11.26%
ExportSize:encoding/pem                                                               334B ± 0%     356B ± 0%   +6.59%
ExportSize:encoding/xml                                                             16.7kB ± 0%   18.6kB ± 0%  +10.90%
ExportSize:errors                                                                     414B ± 0%     455B ± 0%   +9.90%
ExportSize:expvar                                                                   26.6kB ± 0%   29.2kB ± 0%   +9.80%
ExportSize:flag                                                                     15.5kB ± 0%   17.2kB ± 0%  +10.87%
ExportSize:fmt                                                                      10.6kB ± 0%   11.7kB ± 0%  +10.80%
ExportSize:go/ast                                                                   30.7kB ± 0%   34.2kB ± 0%  +11.37%
ExportSize:go/build                                                                 9.74kB ± 0%  10.70kB ± 0%   +9.87%
ExportSize:go/constant                                                              2.26kB ± 0%   2.56kB ± 0%  +13.30%
ExportSize:go/doc                                                                   6.09kB ± 0%   6.69kB ± 0%   +9.83%
ExportSize:go/format                                                                2.30kB ± 0%   2.52kB ± 0%   +9.43%
ExportSize:go/importer                                                              4.99kB ± 0%   5.46kB ± 0%   +9.36%
ExportSize:go/internal/gccgoimporter                                                3.40kB ± 0%   3.68kB ± 0%   +8.02%
ExportSize:go/internal/gcimporter                                                   5.69kB ± 0%   6.25kB ± 0%   +9.71%
ExportSize:go/internal/srcimporter                                                  12.8kB ± 0%   14.2kB ± 0%  +10.36%
ExportSize:go/parser                                                                8.49kB ± 0%   9.39kB ± 0%  +10.70%
ExportSize:go/printer                                                               3.23kB ± 0%   3.54kB ± 0%   +9.59%
ExportSize:go/scanner                                                               4.90kB ± 0%   5.43kB ± 0%  +10.80%
ExportSize:go/token                                                                 5.19kB ± 0%   5.67kB ± 0%   +9.26%
ExportSize:go/types                                                                 35.0kB ± 0%   38.5kB ± 0%  +10.14%
ExportSize:hash                                                                       292B ± 0%     319B ± 0%   +9.25%
ExportSize:hash/adler32                                                               765B ± 0%     850B ± 0%  +11.11%
ExportSize:hash/crc32                                                                 717B ± 0%     771B ± 0%   +7.53%
ExportSize:hash/crc64                                                                 945B ± 0%    1040B ± 0%  +10.05%
ExportSize:hash/fnv                                                                 2.05kB ± 0%   2.35kB ± 0%  +14.31%
ExportSize:html                                                                       924B ± 0%     997B ± 0%   +7.90%
ExportSize:html/template                                                            18.5kB ± 0%   20.5kB ± 0%  +10.79%
ExportSize:image                                                                    15.5kB ± 0%   17.5kB ± 0%  +12.74%
ExportSize:image/color                                                              3.08kB ± 0%   3.51kB ± 0%  +13.93%
ExportSize:image/color/palette                                                        220B ± 0%     229B ± 0%   +4.09%
ExportSize:image/draw                                                               3.39kB ± 0%   3.85kB ± 0%  +13.44%
ExportSize:image/gif                                                                4.82kB ± 0%   5.39kB ± 0%  +11.76%
ExportSize:image/internal/imageutil                                                 2.07kB ± 0%   2.33kB ± 0%  +12.92%
ExportSize:image/jpeg                                                               6.68kB ± 0%   7.43kB ± 0%  +11.13%
ExportSize:image/png                                                                8.52kB ± 0%   9.41kB ± 0%  +10.38%
ExportSize:index/suffixarray                                                        5.77kB ± 0%   6.40kB ± 0%  +10.91%
ExportSize:internal/bytealg                                                           780B ± 0%     831B ± 0%   +6.54%
ExportSize:internal/cfg                                                               647B ± 0%     648B ± 0%   +0.15%
ExportSize:internal/cpu                                                             1.50kB ± 0%   1.59kB ± 0%   +6.33%
ExportSize:internal/fmtsort                                                         8.96kB ± 0%  10.05kB ± 0%  +12.17%
ExportSize:internal/goroot                                                            136B ± 0%     142B ± 0%   +4.41%
ExportSize:internal/goversion                                                        81.0B ± 0%    82.0B ± 0%   +1.23%
ExportSize:internal/lazyregexp                                                      5.89kB ± 0%   6.54kB ± 0%  +10.97%
ExportSize:internal/lazytemplate                                                    13.8kB ± 0%   15.4kB ± 0%  +11.31%
ExportSize:internal/nettrace                                                          301B ± 0%     317B ± 0%   +5.32%
ExportSize:internal/oserror                                                           172B ± 0%     178B ± 0%   +3.49%
ExportSize:internal/poll                                                            7.91kB ± 0%   8.68kB ± 0%   +9.66%
ExportSize:internal/race                                                              386B ± 0%     421B ± 0%   +9.07%
ExportSize:internal/reflectlite                                                     4.35kB ± 0%   4.82kB ± 0%  +10.74%
ExportSize:internal/singleflight                                                      970B ± 0%    1051B ± 0%   +8.35%
ExportSize:internal/syscall/unix                                                    1.04kB ± 0%   1.11kB ± 0%   +6.04%
ExportSize:internal/testenv                                                         22.4kB ± 0%   24.6kB ± 0%   +9.84%
ExportSize:internal/testlog                                                           883B ± 0%     964B ± 0%   +9.17%
ExportSize:internal/trace                                                           17.0kB ± 0%   18.6kB ± 0%   +9.55%
ExportSize:internal/xcoff                                                           12.9kB ± 0%   13.9kB ± 0%   +7.72%
ExportSize:io                                                                       4.39kB ± 0%   4.81kB ± 0%   +9.71%
ExportSize:io/ioutil                                                                13.5kB ± 0%   14.9kB ± 0%  +10.01%
ExportSize:log                                                                      4.17kB ± 0%   4.71kB ± 0%  +12.99%
ExportSize:log/syslog                                                               5.72kB ± 0%   6.30kB ± 0%  +10.21%
ExportSize:math                                                                     6.15kB ± 0%   6.61kB ± 0%   +7.53%
ExportSize:math/big                                                                 13.9kB ± 0%   15.6kB ± 0%  +12.20%
ExportSize:math/bits                                                                5.10kB ± 0%   5.85kB ± 0%  +14.76%
ExportSize:math/cmplx                                                               2.58kB ± 0%   2.83kB ± 0%   +9.70%
ExportSize:math/rand                                                                2.56kB ± 0%   2.84kB ± 0%  +11.01%
ExportSize:mime                                                                     1.46kB ± 0%   1.59kB ± 0%   +8.97%
ExportSize:mime/multipart                                                           4.14kB ± 0%   4.51kB ± 0%   +8.97%
ExportSize:mime/quotedprintable                                                     1.82kB ± 0%   2.03kB ± 0%  +11.12%
ExportSize:net                                                                      38.5kB ± 0%   42.7kB ± 0%  +10.96%
ExportSize:net/http                                                                 65.9kB ± 0%   71.9kB ± 0%   +9.16%
ExportSize:net/http/cgi                                                             33.2kB ± 0%   36.5kB ± 0%   +9.89%
ExportSize:net/http/cookiejar                                                       7.49kB ± 0%   8.27kB ± 0%  +10.53%
ExportSize:net/http/fcgi                                                            22.3kB ± 0%   24.4kB ± 0%   +9.65%
ExportSize:net/http/httptest                                                        52.7kB ± 0%   57.8kB ± 0%   +9.71%
ExportSize:net/http/httptrace                                                       20.6kB ± 0%   22.6kB ± 0%   +9.58%
ExportSize:net/http/httputil                                                        36.9kB ± 0%   40.6kB ± 0%   +9.92%
ExportSize:net/http/internal                                                        1.30kB ± 0%   1.42kB ± 0%   +8.51%
ExportSize:net/http/pprof                                                           22.1kB ± 0%   24.2kB ± 0%   +9.77%
ExportSize:net/internal/socktest                                                    2.61kB ± 0%   2.83kB ± 0%   +8.15%
ExportSize:net/mail                                                                 7.66kB ± 0%   8.49kB ± 0%  +10.79%
ExportSize:net/rpc                                                                  31.8kB ± 0%   35.2kB ± 0%  +10.51%
ExportSize:net/rpc/jsonrpc                                                          11.0kB ± 0%   12.1kB ± 0%  +10.83%
ExportSize:net/smtp                                                                 38.9kB ± 0%   42.7kB ± 0%   +9.91%
ExportSize:net/textproto                                                            6.29kB ± 0%   6.89kB ± 0%   +9.58%
ExportSize:net/url                                                                  3.13kB ± 0%   3.45kB ± 0%  +10.09%
ExportSize:os                                                                       23.5kB ± 0%   25.8kB ± 0%   +9.84%
ExportSize:os/exec                                                                  18.7kB ± 0%   20.5kB ± 0%   +9.78%
ExportSize:os/signal                                                                  498B ± 0%     530B ± 0%   +6.43%
ExportSize:os/signal/internal/pty                                                   13.7kB ± 0%   15.0kB ± 0%  +10.03%
ExportSize:os/user                                                                  1.51kB ± 0%   1.63kB ± 0%   +7.46%
ExportSize:path                                                                       614B ± 0%     669B ± 0%   +8.96%
ExportSize:path/filepath                                                            4.39kB ± 0%   4.87kB ± 0%  +11.01%
ExportSize:plugin                                                                     861B ± 0%     931B ± 0%   +8.13%
ExportSize:reflect                                                                  11.4kB ± 0%   12.7kB ± 0%  +11.36%
ExportSize:regexp                                                                   6.41kB ± 0%   7.08kB ± 0%  +10.32%
ExportSize:regexp/syntax                                                            4.52kB ± 0%   4.83kB ± 0%   +6.97%
ExportSize:runtime                                                                  16.6kB ± 0%   17.8kB ± 0%   +7.48%
ExportSize:runtime/cgo                                                               15.0B ± 0%    15.0B ± 0%    0.00%
ExportSize:runtime/debug                                                            6.14kB ± 0%   6.77kB ± 0%  +10.11%
ExportSize:runtime/internal/atomic                                                  1.15kB ± 0%   1.25kB ± 0%   +8.58%
ExportSize:runtime/internal/math                                                      240B ± 0%     265B ± 0%  +10.42%
ExportSize:runtime/internal/sys                                                     2.76kB ± 0%   2.97kB ± 0%   +7.56%
ExportSize:runtime/pprof                                                            6.68kB ± 0%   7.36kB ± 0%  +10.09%
ExportSize:runtime/pprof/internal/profile                                           8.60kB ± 0%   9.43kB ± 0%   +9.68%
ExportSize:runtime/race                                                              16.0B ± 0%    16.0B ± 0%    0.00%
ExportSize:runtime/trace                                                            6.40kB ± 0%   7.05kB ± 0%  +10.16%
ExportSize:sort                                                                     2.36kB ± 0%   2.61kB ± 0%  +10.55%
ExportSize:strconv                                                                  3.10kB ± 0%   3.42kB ± 0%  +10.33%
ExportSize:strings                                                                  7.71kB ± 0%   8.53kB ± 0%  +10.64%
ExportSize:sync                                                                     4.06kB ± 0%   4.41kB ± 0%   +8.59%
ExportSize:sync/atomic                                                              1.60kB ± 0%   1.76kB ± 0%  +10.06%
ExportSize:syscall                                                                  78.1kB ± 0%   82.9kB ± 0%   +6.13%
ExportSize:testing                                                                  15.0kB ± 0%   16.5kB ± 0%   +9.92%
ExportSize:testing/internal/testdeps                                                  705B ± 0%     751B ± 0%   +6.52%
ExportSize:testing/iotest                                                           1.37kB ± 0%   1.50kB ± 0%   +9.80%
ExportSize:testing/quick                                                            10.4kB ± 0%   11.6kB ± 0%  +11.74%
ExportSize:text/scanner                                                             3.48kB ± 0%   3.85kB ± 0%  +10.90%
ExportSize:text/tabwriter                                                           1.38kB ± 0%   1.53kB ± 0%  +10.65%
ExportSize:text/template                                                            15.0kB ± 0%   16.7kB ± 0%  +11.26%
ExportSize:text/template/parse                                                      8.84kB ± 0%   9.85kB ± 0%  +11.43%
ExportSize:time                                                                     9.06kB ± 0%   9.90kB ± 0%   +9.20%
ExportSize:unicode                                                                  7.92kB ± 0%   8.44kB ± 0%   +6.49%
ExportSize:unicode/utf16                                                              491B ± 0%     563B ± 0%  +14.66%
ExportSize:unicode/utf8                                                             1.63kB ± 0%   1.86kB ± 0%  +14.43%
ExportSize:vendor/golang.org/x/crypto/chacha20poly1305                                626B ± 0%     656B ± 0%   +4.79%
ExportSize:vendor/golang.org/x/crypto/cryptobyte                                    15.9kB ± 0%   17.6kB ± 0%  +10.77%
ExportSize:vendor/golang.org/x/crypto/cryptobyte/asn1                                 544B ± 0%     579B ± 0%   +6.43%
ExportSize:vendor/golang.org/x/crypto/curve25519                                      400B ± 0%     418B ± 0%   +4.50%
ExportSize:vendor/golang.org/x/crypto/hkdf                                            533B ± 0%     574B ± 0%   +7.69%
ExportSize:vendor/golang.org/x/crypto/internal/chacha20                               727B ± 0%     775B ± 0%   +6.60%
ExportSize:vendor/golang.org/x/crypto/internal/subtle                                 394B ± 0%     462B ± 0%  +17.26%
ExportSize:vendor/golang.org/x/crypto/poly1305                                      1.06kB ± 0%   1.15kB ± 0%   +8.11%
ExportSize:vendor/golang.org/x/net/dns/dnsmessage                                   8.94kB ± 0%   9.90kB ± 0%  +10.81%
ExportSize:vendor/golang.org/x/net/http2/hpack                                      5.21kB ± 0%   5.67kB ± 0%   +8.89%
ExportSize:vendor/golang.org/x/net/http/httpguts                                      568B ± 0%     604B ± 0%   +6.34%
ExportSize:vendor/golang.org/x/net/http/httpproxy                                   1.94kB ± 0%   2.11kB ± 0%   +8.94%
ExportSize:vendor/golang.org/x/net/idna                                             2.18kB ± 0%   2.36kB ± 0%   +8.02%
ExportSize:vendor/golang.org/x/net/nettest                                          10.9kB ± 0%   11.9kB ± 0%   +9.45%
ExportSize:vendor/golang.org/x/sys/cpu                                              1.22kB ± 0%   1.30kB ± 0%   +6.57%
ExportSize:vendor/golang.org/x/text/secure/bidirule                                   906B ± 0%     971B ± 0%   +7.17%
ExportSize:vendor/golang.org/x/text/transform                                       1.59kB ± 0%   1.75kB ± 0%   +9.91%
ExportSize:vendor/golang.org/x/text/unicode/bidi                                    2.75kB ± 0%   2.98kB ± 0%   +8.42%
ExportSize:vendor/golang.org/x/text/unicode/norm                                    7.58kB ± 0%   8.27kB ± 0%   +9.05%
[Geo mean]                                                                          6.01kB        6.57kB        +9.29%
@robpike

This comment has been minimized.

Copy link
Contributor

@robpike robpike commented Sep 24, 2019

Binary size is out of control. Please don't do this until there is genuine progress on reining in the bloat.

@mdempsky

This comment has been minimized.

Copy link
Member

@mdempsky mdempsky commented Sep 24, 2019

Binary size is out of control. Please don't do this until there is genuine progress on reining in the bloat.

This is export data size. Binary size is unaffected.

(Edit: Binary size might be affected if this means DWARF debugging information grows from having more precise column information for inlined function bodies. I meant though that I wasn't measuring binary size.)

@mdempsky

This comment has been minimized.

Copy link
Member

@mdempsky mdempsky commented Sep 26, 2019

Latest revision of CL 196963 uses a better encoding for adding column details, so it only increases export data size by about 4% on (geometric) average.

Also, as mentioned in the commit message, it actually shrinks k8s.io/kubernetes/cmd/kubelet's binary size by 24kB, but I haven't been able to explain why exactly. The best I've tracked it down so far is that it shrinks the .rodata and .debug_zinfo sections for some reason.

@gopherbot

This comment has been minimized.

Copy link

@gopherbot gopherbot commented Sep 27, 2019

Change https://golang.org/cl/197678 mentions this issue: go/internal/gcimporter: support reading column details from export data

gopherbot pushed a commit to golang/tools that referenced this issue Sep 27, 2019
Mirrors the changes in the main repo.

Updates golang/go#28259.

Change-Id: I0cc9bc2f120d513f2f3d4ab503981c653e4ee7c2
Reviewed-on: https://go-review.googlesource.com/c/tools/+/197678
Run-TryBot: Matthew Dempsky <mdempsky@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Robert Griesemer <gri@golang.org>
gopherbot pushed a commit that referenced this issue Sep 27, 2019
This CL updates the export data format to include column details when
writing out position data. cmd/compile is updated to generate and make
use of the new details, but go/internal/gcimporter only knows how to
read the data. It doesn't yet actually make use of it.

Experimentally across a wide range of packages, this increases export
data size by around 4%. However, it has no impact on binary size.
(Notably, it actually shrinks k8s.io/kubernetes/cmd/kubelet's binary
size by 24kB, but it's unclear to me why at this time.)

Updates #28259.

Change-Id: I351fb340839df8d3adced49b3757c4537fb91b3f
Reviewed-on: https://go-review.googlesource.com/c/go/+/196963
Run-TryBot: Matthew Dempsky <mdempsky@google.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Robert Griesemer <gri@golang.org>
Reviewed-by: Rob Pike <r@golang.org>
@mdempsky

This comment has been minimized.

Copy link
Member

@mdempsky mdempsky commented Sep 27, 2019

Okay, cmd/compile is now exporting column position, and gcimporter knows how to read that extra information.

However, fakeFileSet is currently dropping that data on the floor when it converts it into token.Pos. So someone needs to work on a CL to extend fakeFileSet.

For what it's worth, cmd/compile currently only records 8 bits of column data:

// Layout constants: 20 bits for line, 8 bits for column, 2 for isStmt, 2 for pro/epilogue

So the naive solution would be to just reserve 256x as much token.Pos space, but I'm worried that's not an appealing option on 32-bit platforms (where token.Pos is 32-bits): reserving maxlines (64k) * maxcolumns (256) per referenced file is 24 bits. So 32-bit CPUs wouldn't be able import packages that reference more than 256 source files. (Maybe only 128 because of sign?)

Aside: In retrospect, token.Pos probably should have been an int64 instead of int, since it refers to file offsets, not memory offsets. Can't change that now though.

@adonovan

This comment has been minimized.

Copy link

@adonovan adonovan commented Sep 27, 2019

I wonder: could we change token.Pos to int64? Technically it's a breaking change, but these values are never treated as integers (aside from zero); they're more like opaque pointers into a virtual address space defined by a FileSet.

It would double its space usage, which could be a concern.

@mdempsky

This comment has been minimized.

Copy link
Member

@mdempsky mdempsky commented Sep 27, 2019

Two thoughts:

  1. Is it okay if behavior differs between 32-bit and 64-bit CPUs? E.g., can we use a lossier token.Pos encoding so that 32-bit CPUs can still reference more files at once?

  2. One option is to use a split encoding scheme where we reserve column Pos-space for the first N lines (e.g., 3k); and then past that we fallback to only returning column offset. (That would still increase Pos-space usage by 12x though.)

Looking at Kubernetes source code there are files as large as 161,105 lines, but the 99%ile line count is ~2700 lines.

@mdempsky

This comment has been minimized.

Copy link
Member

@mdempsky mdempsky commented Sep 27, 2019

I wonder: could we change token.Pos to int64?

Maybe? Looks like as precedent we changed math/big.Word from uintptr (since Go 1) to uint in Go 1.9.

@griesemer

This comment has been minimized.

Copy link
Contributor

@griesemer griesemer commented Sep 30, 2019

The primary reason for the choice of uint32 was the use of token.Pos values in the index of the (original) godoc. Not sure how much of that code we're still using and whether it matters. Increasing to 64bit will significantly increase (roughly double) the index size, which used to be in memory.

@robpike

This comment has been minimized.

Copy link
Contributor

@robpike robpike commented Sep 30, 2019

@adonovan : why?

@alandonovan

This comment has been minimized.

Copy link
Contributor Author

@alandonovan alandonovan commented Sep 30, 2019

@robpike: why increase the width of token.Pos? @mdempsky suggested it above as a possible workaround to the problem of creating token.Pos values when parsing export data. See https://golang.org/src/go/internal/gcimporter/bimport.go#L340. The issue is that token.File contains a table of offsets of newlines within the source file, so that it can map byte offsets to line/column pairs. We don't have that information for source files when we load export data, so we currently use a fake table corresponding to a file containing only 64K newlines. The line number is simply the offset, and the column is zero. If we instead built a fake table corresponding to a file containing 64K lines each of 256 spaces, then we could represent any line < 64K and any column < 256 accurately. However, that uses up a lot of token.Pos "address space" for each file.

@robpike

This comment has been minimized.

Copy link
Contributor

@robpike robpike commented Oct 1, 2019

Thanks, @adonovan but I still don't see why that needs a 64-bit integer.

@adonovan

This comment has been minimized.

Copy link

@adonovan adonovan commented Oct 1, 2019

A token.FileSet is conceptually a concatenation of token.Files: it provides a number (token.Pos) for every index in the concatenation, a bit like a bunch of files memory-mapped adjacently in virtual address space. Each File usually reserves a block of this concatenation equal to its length. However, for files described by export data, we don't know the length of the file (or even the highest offset referenced by a token.Pos in the export data), so we would reserve a range of offsets for them equivalent to a 64KLoC file containing lines of 256 spaces, allowing us to compute the Pos for any line/col pair in that range, even though of course most aren't needed. (The actual fake table need not be materialized, though today it is, as a shared constant.)

However, a FileSet is typically a global variable of an application, so an app that reads hundreds of files from export data within its lifetime will keep appending these 24-bit-sized chunks to the mapping, which allows only 1<<(32-24) = 256 iterations before we run out.

Besides increasing the "address space", two alternative approaches would be to encode the line offset table of each file, which would compress well but nonetheless occupy more space in the export data and in memory after parsing, or, to have the export data specify the maximum significant line and column numbers in that file, in effect still giving a rectangular overapproximation of the true raggedy shape of the file, but using a smaller rectangle. This latter approach would have almost no space overhead, but may be trickier to encode.

@robpike

This comment has been minimized.

Copy link
Contributor

@robpike robpike commented Oct 1, 2019

Got it, thanks for taking the time to explain it.

I must say though, so much tech and space and overhead for "column" information doesn't feel like the right call to me, but fortunately it's not up to me.

@alandonovan

This comment has been minimized.

Copy link
Contributor Author

@alandonovan alandonovan commented Oct 1, 2019

FileSet is the problem, really. It does a great job of making the marginal cost of a position very small (32 bits), but it imposes a number of other costs, such as a monotonically increasing memory footprint, the need for an application-wide global, and the inability to easily synthesize arbitrary positions.

If we were to design the syntax tree anew, I would look more carefully at simpler alternatives like (at the cost of another word per node) putting a reference to the token.File into every syntax node so that each node can report its position without the need for an external table, or, even simpler, putting just a pointer to a shared filename string in every node, and encoding the line and column of each token into the high 24 and low 8 bits of a uint32.

@griesemer

This comment has been minimized.

Copy link
Contributor

@griesemer griesemer commented Oct 1, 2019

For a bit of perspective: The reason for the FileSet data structure is historic. The search index for the original godoc needed a dense encoding of positions (to save space), which is where the 32bit encoding used for token.Pos is coming from. It worked well for that application but unfortunately, the popularity of the go/ast lead to the pervasiveness of token.Pos(itions) and with that the need to carry around FileSets which are cumbersome to manipulate.

The compiler (cmd/compile) uses a more modern AST version (cmd/compile/internal/syntax) which has a new position representation. Each position is "stand-alone" but also significantly larger (two 64bit words); in essence it's one more word per position.

I'd love to replace FileSet and token.Pos but until modules are a wide-spread default we can't do that. Once modules are widely adopted, we can start making changes.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
7 participants
You can’t perform that action at this time.