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 "m[k] op= r" #23661

Closed
vkuzmin-uber opened this issue Feb 2, 2018 · 5 comments
Closed

cmd/compile: We can avoid extra mapaccess in "m[k] op= r" #23661

vkuzmin-uber opened this issue Feb 2, 2018 · 5 comments

Comments

@vkuzmin-uber
Copy link
Contributor

vkuzmin-uber commented Feb 2, 2018

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

1.9.2

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?

Optimization for map[i] op= r, except /= and %= (it has possibility of /= 0 and %= 0 that we can not optimize using proposed strategy)

What did you expect to see?

"map[k] op= r" should be using only single call:
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer

What did you see instead?

"map[k] op= r" is using:
func mapaccess*(..) unsafe.Pointer
func mapassign*(...) unsafe.Pointer

We can avoid mapaccess in most cases (except /=).

Description (will simplify some details that are not important here):

This is slightly related to #21687

Currently orderexpr performs transformation of node with OP OASOP (op=) into OAS (=):

l op= r into l = l op r

For map
m[k] op= r

It creates safe expressions:

tmp1 := m[k]
m[k] = tmp1 op r

then walkexpr replaces it with:

tmp1 := mapaccess(m, k) // this never changes m but returns default value if necessary.
tmp2 := massign(m, k) // inserts if necessary
tmp2 = tmp1 op r

We always evaluate r before massign (see test fixedbugs/issue22881.go).

Consider this, mapaccess is not necessary.

Except the m[k] /= r , you may see example at fixedbugs/issue22881.go, f6 where r == 0 causes panic. Other Op doesn't have this problem.

Implementation trick is to do it during walkexpr when m[k] is already replaced with massign.

@vkuzmin-uber vkuzmin-uber changed the title cmd/compile: We can easily avoid extra mapaccess1 in "m[i] op= r" cmd/compile: We can avoid extra mapaccess1 in "m[i] op= r" Feb 2, 2018
@vkuzmin-uber vkuzmin-uber changed the title cmd/compile: We can avoid extra mapaccess1 in "m[i] op= r" cmd/compile: We can avoid extra mapaccess in "m[k] op= r" Feb 2, 2018
@gopherbot
Copy link

Change https://golang.org/cl/91557 mentions this issue: cmd/compile: avoid extra mapaccess in "m[i] op= r"

@rasky
Copy link
Member

rasky commented Feb 2, 2018

Related: #17133

@vkuzmin-uber
Copy link
Contributor Author

vkuzmin-uber commented Feb 2, 2018

As a proof of patch, generated Go's Assembler for test.go:

package main

func main() {
	m := map[int]int{}
	x := 0xFF
	m[0] += x
}

@vkuzmin-uber
Copy link
Contributor Author

There is no runtime.mapaccess1_fast in Go's asm

	0x0082 00130 (test.go:6)	LEAQ	type.map[int]int(SB), AX
	0x0089 00137 (test.go:6)	MOVQ	AX, (SP)
	0x008d 00141 (test.go:6)	LEAQ	""..autotmp_2+176(SP), AX
	0x0095 00149 (test.go:6)	MOVQ	AX, 8(SP)
	0x009a 00154 (test.go:6)	MOVQ	$0, 16(SP)
	0x00a3 00163 (test.go:6)	PCDATA	$0, $1
	0x00a3 00163 (test.go:6)	CALL	runtime.mapassign_fast64(SB)
	0x00a8 00168 (test.go:6)	MOVQ	24(SP), AX
	0x00ad 00173 (test.go:6)	ADDQ	$255, (AX)
	0x00b4 00180 (test.go:7)	MOVQ	224(SP), BP
	0x00bc 00188 (test.go:7)	ADDQ	$232, SP
	0x00c3 00195 (test.go:7)	RET

@vkuzmin-uber
Copy link
Contributor Author

Added a benchmark tests go/test/bench/go1/map_test.go,

3 runs of "go/bin/go test -bench Map"

Before optimization:
1)
BenchmarkMapInsert-8 3000000 421 ns/op
BenchmarkMapUpdate-8 5000000 365 ns/op
2)
BenchmarkMapInsert-8 3000000 423 ns/op
BenchmarkMapUpdate-8 5000000 359 ns/op
3)
BenchmarkMapInsert-8 3000000 426 ns/op
BenchmarkMapUpdate-8 5000000 367 ns/op

After optimization:
1)
BenchmarkMapInsert-8 5000000 415 ns/op
BenchmarkMapUpdate-8 5000000 312 ns/op
2)
BenchmarkMapInsert-8 5000000 410 ns/op
BenchmarkMapUpdate-8 5000000 313 ns/op
3)
BenchmarkMapInsert-8 3000000 377 ns/op
BenchmarkMapUpdate-8 5000000 311 ns/op

All 3 runs demonstrates minor improvement for "insert" and ~10% or "update". This is expected.

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Development

No branches or pull requests

3 participants