Art of Hacking Golang compiler

Featured ~ kuzminva

UPDATE 03/19/2018

CL https://golang.org/cl/91557 and https://golang.com/cl/100838 are committed and will be a part of Go 1.11.

UPDATE 06/25/2018

Found a bug https://golang.org/issue/25936. Fixed by CL https://golang.org/cl/120255

What?

map and append

When I just started to learn Golang, found this example:

map_append

You may see two likes[l] that are obviously not free if final machine code is doing it. There is no other way to write the same code without double lookup. I have decided to investigate if there is a Compiler optimization. In Go

map[KeyType]ValueType

is a built-in map type that implements a hash table https://golang.org/src/runtime/hashmap.go. You may generate Go’s Asm and find there are two map’s calls that look in my system like that:

go tool compile -S test_file.go
...
CALL runtime.mapaccess1_fast64(SB)
...
CALL runtime.mapassign_fast64(SB)
...

Ok, no surprise since this is not a “hidden cost” and you get what you see. But my next thought was – how does it work with Compound-Assignment Operators?

map and Compound-Assignment Operators

What is “Compound-Assignment Operators”?

compound-assignment-operators

This time I had to look at Go compiler code. Note that it is not hard because Golang compiler is written by Go! Eventually I found the code that performs ordering of nodes of Abstract Syntax Tree https://golang.org/src/cmd/compile/internal/gc/order.go and it answered my question in comments

OASOP

Well, this time it was unexpected that m[key] += x  becomes m[key] = m[key] + x internally.

This is obvious that the code can be optimized. You may see that some optimizations https://github.com/golang/go/wiki/CompilerOptimizations are also done by mutating AST tree. I decided to implement it.

AST mutations Before optimization

AST_before

AST mutations required for optimization

AST_after

Exception for /= and %=

This optimization fails on a test f6 at https://github.com/golang/go/blob/master/test/fixedbugs/issue22881.go

m := map[int]int{}
func() { // wrapper to scope the defer.
defer func() {
recover()
}()
var z int
m[0] /= z // Will panic. Shouldn't modify m.
}()

if len(m) != 0 {
fmt.Printf("map insert happened, that is not expected\n", i)
}

In this case the original code works because it uses runtime.mapassign to read from map and it does not insert a new key in the hash map, instead it returns a default value for map’s value type.

Contributing to Golang

Configuring environment for contribution is mostly automated and the rest is documented very well https://golang.org/doc/contribute.html

Issues

https://github.com/golang/go/issues/23661

https://github.com/golang/go/issues/24364

Changes

https://golang.org/cl/91557 committed at 03/12/2018

https://golang.com/cl/100838 committed at 03/19/2018

Reference

Inside the Map Implementation

Published by kuzminva

High Frequency Trading and Large Scale Cloud experience

2 thoughts on “Art of Hacking Golang compiler”

  2. Hi Iskander,

    Thank you for feedback. I really tried to keep this article short, mostly explained motivation and how this optimization can be achieved and then thought that code talks more.The review has comments and questions, even final implementation is not exactly the same as it was published initially.

    If you want to understand it and feel gaps, I am willing to address it. First look at the link where Go map design is explained https://github.com/gophercon/2016-talks/tree/master/KeithRandall-InsideTheMapImplementation. It may close some holes. (btw., slide 39 mentions that m[k] += requires 2 map operations).

    Then send questions to particular part of article/code where you need more details. Also you can ask question in review itself even it’s submitted, I guess it still open for comments.

    Like

    Reply

Leave a comment