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: more compact initialization of maps with dynamic content #38784

Open
martisch opened this issue May 1, 2020 · 6 comments
Open

cmd/compile: more compact initialization of maps with dynamic content #38784

martisch opened this issue May 1, 2020 · 6 comments

Comments

@martisch
Copy link
Member

@martisch martisch commented May 1, 2020

Iooking into the size of unicode.init I found that the optimization to init maps from arrays of keys and values with a for loop instead of making an mapassign call for each key/value doesnt trigger for the maps in package unicode because the values are variables and not static.

The allowed types for this optimization were already expanded before and it seems there is room to go further.
https://go-review.googlesource.com/c/go/+/66050/

Writing a prototype compiler CL allowing ONAME to also be used as a value and marking value arrays used for initialization as dynamic and not readonly (when ONAME is present) cuts the size of unicode.init roughly in half (saves 8kb currently). A hello world binary gains a 4kb size reduction.

I dont see yet see a problem with side effects if all keys are static and all values are either ONAME or statics.

Unfortunately since the values in the unicode case are pointers there are still a lot of gcwritebarrier entries that bloat the init function. There seems more room to make unicode.init smaller by optimizing the init func generation.

@josharian @randall77 @bradfitz

@mdempsky
Copy link
Member

@mdempsky mdempsky commented May 1, 2020

Interesting, thanks for pointing this out.

To summarize, in package unicode we have:

var Categories = map[string]*RangeTable{
        "C":  C,
        ...
}
var C = _C
var _C = &RangeTable{...}

This currently gets optimized into:

var Categories = map[string]*RangeTable{
        "C":  C,
        ...
}
var C = &_C_storage    // <--
var _C = &_C_storage
var _C_storage = RangeTable{...}

The essence of this issue report is that we should further optimize it to:

var Categories = map[string]*RangeTable{
        "C":  &_C_storage,    // <--
        ...
}
var C = &_C_storage
var _C = &_C_storage
var _C_storage = RangeTable{...}

and then on with the static map initialization logic.

@martisch
Copy link
Member Author

@martisch martisch commented May 1, 2020

@mdempsky

yes there is another optimization here as you point out for getting rid of the write barriers by making the map values point to globals instead of copying pointers (we may have to rewrite the tables in unicode for that if we cant make the compiler reason about this) which I think warrants its on CL and rewrite of unicode.

The generic map optimization in addition to the write barriers here is that I think we can do (and already do for some maps) is to always transform:

var Categories = map[type1]type2{
        "static1":  Var1,
        "staric1":  Var2,
        ...
}

to

var _GlobalMapKeys = [...]{static1, static2, ...}
var _GlobalMapValues =[...]{Var1, Var2, ...}

func init() {
   GlobalMap = make(map[type1]type2, length)
   for i := 0; i < len(_GlobalMapKeys); i++ {
        GlobalMap[_GlobalMapKeys[i]] = _GlobalMapValues[i]
   }
}

instead of

func init() {
   GlobalMap = make(map[type1]type2, length)
   GlobalMap["static1"] = Var1
   GlobalMap["static2"] = Var2
   ...
}

Note that the current code even doesn't do the GlobalMap = make(map[type1]type2, length) but gives no size hint which we should fix too.

The optimization already triggers if Var1 and Var2 are not variables but static too. My proposal is to extend the optimization to the case where the map values are are variables (for some values or all of them apart from statics).

@bradfitz bradfitz added the binary-size label May 1, 2020
@mdempsky
Copy link
Member

@mdempsky mdempsky commented May 1, 2020

@martisch Is your idea that

var _GlobalMapValues =[...]{Var1, Var2, ...}

would then involve dynamic initialization for copying Var1 or Var2 if necessary?

That seems like it would work, but it would mean we can't mark _GlobalMapValues as ReadOnly.

@martisch
Copy link
Member Author

@martisch martisch commented May 1, 2020

The quick compiler CL prototype I wrote that passes ./all.bash basically allows ONAME in n.Right.Op for map init elements and sets the values array as initKindDynamic and does not set the ReadOnly flag when variables are encountered. (Its on another computer) So it is the same as initializing an array of variables as elements.

These two places need change:

vstate.MarkReadonly()

if !isStaticCompositeLiteral(r.Left) || !isStaticCompositeLiteral(r.Right) {

@mdempsky
Copy link
Member

@mdempsky mdempsky commented May 1, 2020

I see. Thanks.

I think that should work, but I'm a little hesitant about not being able to mark the memory as Readonly. Once memory is modified by a process, it can't be freed by the OS until the process exits (or until it indicates otherwise with madvise(2), which has page-granularity), whereas code and readonly data only used for process initialization can be flushed once they're no longer needed. In that sense, .data memory is somewhat more expensive than .text or .rodata.

I think we should try to start with just optimizing the same cases that (*InitSchedule).staticassign can handle, since that should handle the example of package unicode.

@andybons andybons added this to the Unplanned milestone May 1, 2020
@martisch
Copy link
Member Author

@martisch martisch commented May 2, 2020

I just realized that my explanation code above was not ideal and var _GlobalMapValues =[...]{Var1, Var2, ...} can be local to the init function.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
4 participants
You can’t perform that action at this time.