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

Jump to bottom

cmd/compile: add special binary export encoding for iotas? #20088

Open
josharian opened this issue Apr 23, 2017 · 8 comments
Open

cmd/compile: add special binary export encoding for iotas? #20088

josharian opened this issue Apr 23, 2017 · 8 comments
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. ToolSpeed
Milestone
Unplanned

Comments

@josharian
Copy link
Contributor

Poking around the export data for the ssa package, I noticed a lot of runs of constants generated by iota--each with an int value + 1 and a line +1 from its predecessory. It is a somewhat common structure that admits of a compact encoding, something like this:

// export
func (p *exporter) iotas(e []*Node) {
    p.tag(iotaTag) 
    p.int(len(e))
    n := e[0]
    p.pos(n)                            
    p.typ(unidealType(n.Type, n.Val()))
    p.value(n.Val())                   
    for _, n := range e {
        p.qualifiedName(n.Sym) 
    }
}

// import
    // ...
    case iotaTag:
        niota := p.int()
        p.pos() // TODO: hook this up and increase by one line at each new node
        typ := p.typ()
        val := p.value(typ)
        for i := 0; i < niota; i++ {
            sym := p.qualifiedName()
            importconst(p.imp, sym, idealType(typ), nodintconst(val.Interface().(int64)+int64(i)))
        }
        return niota
    // ...

A possibly even more compact encoding is to detect common prefixes in names across the entire run, which is fairly common. Even without that, this has a pretty significant impact on the ssa package:

name        old export-bytes  new export-bytes  delta
Template          19.0k ± 0%        19.0k ± 0%     ~     (all equal)
Unicode           4.45k ± 0%        4.43k ± 0%   -0.31%  (p=0.002 n=6+6)
GoTypes           29.7k ± 0%        29.6k ± 0%   -0.53%  (p=0.002 n=6+6)
Compiler          75.6k ± 0%        74.3k ± 0%   -1.62%  (p=0.002 n=6+6)
SSA               76.2k ± 0%        65.7k ± 0%  -13.79%  (p=0.002 n=6+6)
Flate             4.98k ± 0%        4.98k ± 0%   +0.02%  (p=0.002 n=6+6)
GoParser          8.81k ± 0%        8.81k ± 0%   +0.01%  (p=0.002 n=6+6)
Reflect           6.25k ± 0%        6.10k ± 0%   -2.37%  (p=0.002 n=6+6)
Tar               9.49k ± 0%        9.46k ± 0%   -0.31%  (p=0.002 n=6+6)
XML               16.0k ± 0%        16.0k ± 0%     ~     (all equal)
[Geo mean]        15.1k             14.8k        -1.98%

It's not quite obvious that it's worth doing in general--SSA might be somewhat special.

For discussion, if we make another round of export format changes.
@josharian josharian added this to the Go1.9Maybe milestone Apr 23, 2017
@josharian josharian changed the title cmd/compile: add special encoding for iotas cmd/compile: add special binary export encoding for iotas? Apr 23, 2017
@josharian
Copy link
Contributor Author

Oops, forgot to cc @griesemer @mdempsky

@griesemer
Copy link
Contributor

griesemer commented Apr 24, 2017 •
edited

There's already a TODO in bexport.go to use a more condensed form for "long runs of constants". There are other packages that come to mind (Unicode, syscall) which perhaps don't use iota but still could benefit from more compact encoding. I think this is worthwhile doing, perhaps together with the string encoding change.

@josharian
Copy link
Contributor Author

I also have a local type export change I'm playing with now that saves another percent and change. I'll see about pulling together a handful of CLs.

I don't really know all the things that need to change when the export format changes. Is it just the compiler and go/type's gcimporter?

Also, for some of these changes, it might be rather invasive to try to gracefully support reading all old versions, the way we do now. :(

@griesemer
Copy link
Contributor

griesemer commented Apr 24, 2017 •
edited

Supporting old versions: Good point. If we do change the export format version, people will find out that the need to recompile, but it's going to be a major nuisance for a lot of people (including us) working at tip if we all have to recompile existing libraries. We probably should try to be backward compatible to make this a transparent change.

When changing the export format, we need to change:

  • compiler: bexport.go, bimport.go
  • go/importer: go/internal/gcimporter/bimport.go
  • x/tools: go/gcimporter15/bimport.go

If we're backward-compatible, it's ok to generate the old format in tools we don't know about.

@griesemer
Copy link
Contributor

PS: being backward compatible for the position encoding change may negate the effect. hmm... (maybe that one needs to handles separately).

@josharian
Copy link
Contributor Author

Basically none of the changes I've been considering are really backwards compatible. They'd all involve a version bump. But I thought you put in pretty good version skew detection and error messages.

Maybe I'll put together some compiler-only CLs for you to look at, and then we can decide together whether to proceed with them.

@griesemer
Copy link
Contributor

A compiler that can read the new format will be able to read the old format, and discern based on export format version. But yes, if the new format is present, one needs a compiler that understands the new format (but we don't need to upgrade all existing installed libraries).

@josharian
Copy link
Contributor Author

Punting to 1.10 because of uncertainty about interaction with #20070.

@josharian josharian modified the milestones: Go1.10, Go1.9Maybe May 2, 2017
@bradfitz bradfitz modified the milestones: Go1.10, Go1.11 Nov 29, 2017
@gopherbot gopherbot modified the milestones: Go1.11, Unplanned May 23, 2018
@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Jul 13, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. ToolSpeed
Projects
None yet
Milestone
Unplanned
Development

No branches or pull requests
4 participants
@bradfitz @josharian @griesemer @gopherbot