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 special binary export encoding for iotas? #20088

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

Comments

Projects
None yet
4 participants
@josharian
Contributor

josharian commented Apr 23, 2017

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 the ToolSpeed label Apr 23, 2017

@josharian josharian added this to the Go1.9Maybe milestone Apr 23, 2017

@josharian josharian changed the title from cmd/compile: add special encoding for iotas to cmd/compile: add special binary export encoding for iotas? Apr 23, 2017

@josharian

This comment has been minimized.

Contributor

josharian commented Apr 23, 2017

Oops, forgot to cc @griesemer @mdempsky

@griesemer

This comment has been minimized.

Contributor

griesemer commented Apr 24, 2017

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

This comment has been minimized.

Contributor

josharian commented Apr 24, 2017

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

This comment has been minimized.

Contributor

griesemer commented Apr 24, 2017

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

This comment has been minimized.

Contributor

griesemer commented Apr 24, 2017

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

@josharian

This comment has been minimized.

Contributor

josharian commented Apr 24, 2017

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

This comment has been minimized.

Contributor

griesemer commented Apr 24, 2017

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

This comment has been minimized.

Contributor

josharian commented May 2, 2017

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment