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: We can avoid extra mapaccess in map[k] = append(m[k],...) #24364

Closed
vkuzmin-uber opened this issue Mar 12, 2018 · 10 comments

Comments

Projects
None yet
5 participants
@vkuzmin-uber
Copy link
Contributor

commented Mar 12, 2018

Please answer these questions before submitting your issue. Thanks!

What version of Go are you using (go version)?

go 1.9, go 1.10

Does this issue reproduce with the latest release?

yes

What operating system and processor architecture are you using (go env)?

darwin_amd64

What did you do?

Looked at ASM code of:

map[k] = append(map[k],...)

If possible, provide a recipe for reproducing the error.
A complete runnable program is good.
A link on play.golang.org is best.

What did you expect to see?

Namely in this case mapaccess(m, k) can be avoided, see optimization #23661 that was merged. I intentionally separated it and willing to provide fix for "map + append" case.

What did you see instead?

see 2 calls
func mapaccess*(..) unsafe.Pointer
func mapassign*(...) unsafe.Pointer

@vkuzmin-uber

This comment has been minimized.

Copy link
Contributor Author

commented Mar 12, 2018

I am going to provide fix and create pull request. I will take in account all comments and changes made in scope of #23661 that is connected.

@vkuzmin-uber

This comment has been minimized.

Copy link
Contributor Author

commented Mar 15, 2018

Just realized that more likely optimization is going to have the following restrictions:

It works namely for case: m[k] = append(m[k], ...) where we can tell that right and left parts are exactly the same during Order. It will not be able to work:

  1. m[f(k)] = append(m[f(k)], ...)
  2. sink, m[k] = sink, append(m[k]...)
  3. m[k] = append(..., m[k],...)

2 and 3 are feasible but they are so rare that I don't want to add specific optimization.

I am testing implementation now and added BenchmarkMapAppendAssign:

Run it before and after
../bin/go test -bench=BenchmarkMapAppendAssign -run=^map ./runtime/ -count 20

name                           old time/op    new time/op    delta
MapAppendAssign/Int32/256-8      33.5ns ± 3%    22.4ns ±10%  -33.24%  (p=0.000 n=16+18)
MapAppendAssign/Int32/65536-8    68.2ns ± 6%    48.5ns ±29%  -28.90%  (p=0.000 n=20+20)
MapAppendAssign/Int64/256-8      34.3ns ± 4%    23.3ns ± 5%  -32.23%  (p=0.000 n=17+18)
MapAppendAssign/Int64/65536-8    65.9ns ± 7%    61.2ns ±19%   -7.06%  (p=0.002 n=18+20)
MapAppendAssign/Str/256-8         116ns ±12%      79ns ±16%  -31.70%  (p=0.000 n=20+19)
MapAppendAssign/Str/65536-8       134ns ±15%     111ns ±45%  -16.95%  (p=0.000 n=19+20)

name                           old alloc/op   new alloc/op   delta
MapAppendAssign/Int32/256-8       47.0B ± 0%     46.0B ± 0%   -2.13%  (p=0.000 n=19+18)
MapAppendAssign/Int32/65536-8     27.0B ± 0%     20.7B ±30%  -23.33%  (p=0.000 n=20+20)
MapAppendAssign/Int64/256-8       47.0B ± 0%     46.0B ± 0%   -2.13%  (p=0.000 n=20+17)
MapAppendAssign/Int64/65536-8     27.0B ± 0%     27.0B ± 0%     ~     (all equal)
MapAppendAssign/Str/256-8         94.0B ± 0%     78.0B ± 0%  -17.02%  (p=0.000 n=20+16)
MapAppendAssign/Str/65536-8       54.0B ± 0%     54.0B ± 0%     ~     (all equal)
@josharian

This comment has been minimized.

Copy link
Contributor

commented Mar 15, 2018

Also need to take care with channel ops and things that can panic. See func samesafeexpr.

@gopherbot

This comment has been minimized.

Copy link

commented Mar 15, 2018

Change https://golang.org/cl/100838 mentions this issue: cmd/compile: avoid mapaccess at m[k]=append(m[k]..

@bradfitz

This comment has been minimized.

Copy link
Member

commented Mar 15, 2018

Somewhat related: #5147 (#5147 (comment) etc)

@vkuzmin-uber

This comment has been minimized.

Copy link
Contributor Author

commented Mar 15, 2018

I checked that after fix mapaccess is not present in asm code:

 map_append_clean.go                                                                                                                                                                                                                    
    1 package main
    2 
    3
    4 func main() {
    5    m := make(map[string][]string)
    6    m["hello"] = append(m["hello"], "test1")
    7 }

go tool compile -S map_append_clean.go
        0x0076 00118 (map_append_clean.go:6)    LEAQ    type.map[string][]string(SB), AX
        0x007d 00125 (map_append_clean.go:6)    MOVQ    AX, (SP)
        0x0081 00129 (map_append_clean.go:6)    LEAQ    ""..autotmp_2+72(SP), AX
        0x0086 00134 (map_append_clean.go:6)    MOVQ    AX, 8(SP)
        0x008b 00139 (map_append_clean.go:6)    LEAQ    go.string."hello"(SB), AX
        0x0092 00146 (map_append_clean.go:6)    MOVQ    AX, 16(SP)
        0x0097 00151 (map_append_clean.go:6)    MOVQ    $5, 24(SP)
        0x00a0 00160 (map_append_clean.go:6)    PCDATA  $0, $1
        0x00a0 00160 (map_append_clean.go:6)    CALL    runtime.mapassign_faststr(SB)
        0x00a5 00165 (map_append_clean.go:6)    MOVQ    32(SP), AX
        0x00aa 00170 (map_append_clean.go:6)    MOVQ    16(AX), CX
        0x00ae 00174 (map_append_clean.go:6)    MOVQ    (AX), DX
        0x00b1 00177 (map_append_clean.go:6)    MOVQ    8(AX), BX
        0x00b5 00181 (map_append_clean.go:6)    LEAQ    1(BX), SI
        0x00b9 00185 (map_append_clean.go:6)    CMPQ    SI, CX
        0x00bc 00188 (map_append_clean.go:6)    JGT     265
        0x00be 00190 (map_append_clean.go:6)    LEAQ    1(BX), CX
        0x00c2 00194 (map_append_clean.go:6)    MOVQ    CX, 8(AX)
        0x00c6 00198 (map_append_clean.go:6)    SHLQ    $4, BX
        0x00ca 00202 (map_append_clean.go:6)    MOVQ    $5, 8(DX)(BX*1)
        0x00d3 00211 (map_append_clean.go:6)    LEAQ    (DX)(BX*1), DI
        0x00d7 00215 (map_append_clean.go:6)    CMPL    runtime.writeBarrier(SB), $0
        0x00de 00222 (map_append_clean.go:6)    JNE     251
        0x00e0 00224 (map_append_clean.go:6)    LEAQ    go.string."test1"(SB), AX
        0x00e7 00231 (map_append_clean.go:6)    MOVQ    AX, (DX)(BX*1)
        0x00eb 00235 (map_append_clean.go:7)    MOVQ    456(SP), BP
        0x00f3 00243 (map_append_clean.go:7)    ADDQ    $464, SP
        0x00fa 00250 (map_append_clean.go:7)    RET
        0x00fb 00251 (map_append_clean.go:6)    LEAQ    go.string."test1"(SB), AX
        0x0102 00258 (map_append_clean.go:6)    CALL    runtime.gcWriteBarrier(SB)
        0x0107 00263 (map_append_clean.go:6)    JMP     235
        0x0109 00265 (map_append_clean.go:6)    MOVQ    AX, ""..autotmp_6+64(SP)
        0x010e 00270 (map_append_clean.go:6)    LEAQ    type.string(SB), AX
        0x0115 00277 (map_append_clean.go:6)    MOVQ    AX, (SP)
        0x0119 00281 (map_append_clean.go:6)    MOVQ    DX, 8(SP)
        0x011e 00286 (map_append_clean.go:6)    MOVQ    BX, 16(SP)
        0x0123 00291 (map_append_clean.go:6)    MOVQ    CX, 24(SP)
        0x0128 00296 (map_append_clean.go:6)    MOVQ    SI, 32(SP)
        0x012d 00301 (map_append_clean.go:6)    PCDATA  $0, $2
        0x012d 00301 (map_append_clean.go:6)    CALL    runtime.growslice(SB)
        0x0132 00306 (map_append_clean.go:6)    MOVQ    40(SP), AX
        0x0137 00311 (map_append_clean.go:6)    MOVQ    48(SP), CX
        0x013c 00316 (map_append_clean.go:6)    MOVQ    56(SP), DX
        0x0141 00321 (map_append_clean.go:6)    MOVQ    ""..autotmp_6+64(SP), DI
        0x0146 00326 (map_append_clean.go:6)    MOVQ    DX, 16(DI)
        0x014a 00330 (map_append_clean.go:6)    CMPL    runtime.writeBarrier(SB), $0
        0x0151 00337 (map_append_clean.go:6)    JNE     356
        0x0153 00339 (map_append_clean.go:6)    MOVQ    AX, (DI)
        0x0156 00342 (map_append_clean.go:6)    MOVQ    CX, BX
        0x0159 00345 (map_append_clean.go:6)    MOVQ    AX, DX
        0x015c 00348 (map_append_clean.go:6)    MOVQ    DI, AX
        0x015f 00351 (map_append_clean.go:6)    JMP     190
        0x0164 00356 (map_append_clean.go:6)    CALL    runtime.gcWriteBarrier(SB)
        0x0169 00361 (map_append_clean.go:6)    JMP     342
        0x016b 00363 (map_append_clean.go:6)    NOP

@bradfitz

This comment has been minimized.

Copy link
Member

commented Mar 15, 2018

@vkuzmin-uber, you can add a code generation tests to your CL. They are pretty easy to add nowadays.

@vkuzmin-uber

This comment has been minimized.

Copy link
Contributor Author

commented Mar 16, 2018

@bradfitz Brad, could you please point me to some example with "code generation tests"? I think such test is pretty critical for change like that. It's too easy to add regression accidentally. (We just found, for instance, that optimization doesn't cover particular types with "mapslow")

@randall77

This comment has been minimized.

Copy link
Contributor

commented Mar 16, 2018

@gopherbot gopherbot closed this in c12b185 Mar 20, 2018

@vkuzmin-uber

This comment has been minimized.

Copy link
Contributor Author

commented Mar 20, 2018

Thanks, I provided mapaccess codegen test. I also wrote small article https://kuzminva.wordpress.com/2018/03/18/146-coverage-codegen-tests/

@golang golang locked and limited conversation to collaborators Mar 20, 2019

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
You can’t perform that action at this time.