4 ms·
The article explains how you can get arbitrarily typed values out of the map using unsafe pointers, but it never really explains how they're put in. The insert
by blixt 8y ago
The article explains how you can get arbitrarily typed values out of the map using unsafe pointers, but it never really explains how they're put in.
The insert example in the article uses a function that doesn't actually exist in the runtime package, and it implies you can just give it a plain value as input:
m["key"] = 9001 → runtime.mapinsert(m, ”key", 9001)
I would assume that is only possible if the 9001 value can make its way through as an actual value on the stack, not as a pointer. Here's what I would expect to actually happen:
ptr := runtime.mapallocate(m, "key") // unsafe.Pointer
*(*int)(ptr) = 9001 // Is there a non-typed way to do this?
While this is a good intro to hash tables in general, the Go specific part feels a little bit lacking.
- benmmurphy 8y agomy guess is it allocates the value onto the stack and then inside mapinsert it knows to memcpy the value into the bucket because it knows the size of the value. like tmp = 9001 runtime.mapinsert(m, "key", &tmp)
- blixt 8y agoYup, that looks simpler than what I put in my comment. Do you know where the actual implementation is so we can confirm?
- benmmurphy 8y agoNah. I just decompiled m["foo"] = 5 and it is closer to what is in your comment than mine. so for this it does: push addr of string push $3 call runtime.mapassign_faststr mov $5, 0($ax) test.go:4 0x104b4cb 488d05f9c20100 LEAQ go.string.*+91(SB), AX test.go:4 0x104b4d2 4889442410 MOVQ AX, 0x10(SP) test.go:4 0x104b4d7 48c744241803000000 MOVQ $0x3, 0x18(SP) test.go:4 0x104b4e0 e8cbc6fbff CALL runtime.mapassign_faststr(SB) test.go:4 0x104b4e5 488b442420 MOVQ 0x20(SP), AX test.go:4 0x104b4ea 48c70005000000 MOVQ $0x5, 0(AX) so its kind of like: ptr = runtime.mapassign_faststr("foo") *ptr = 5 EDIT: oops confused 0x3 with the value the first time around
- blixt 8y agoThanks! That clarifies a few things. Too bad this isn't covered in the blog post which was specifically about how Go implements maps efficiently. Here are two interesting things the post doesn't cover: 1) How the insert works and why it's this way instead of any other; 2) Apparently the runtime has specialized implementations to insert values for some key types (string in this case), which implies it does in fact have multiple implementations of the "same" code. Edit: I'm also curious how plain Go code can assign a value directly to an unsafe pointer without expressing the type? Or is that made unnecessary because the compiler rewrites the `myMap["key"] = value` step and has free reign to output unsafe, untyped Go code that isn't normally valid?
- benmmurphy 8y agoyeah. my guess is the compiler just outputs its intermediate format when it sees map assignment and can just do whatever it wants. for reference you can play around with this by doing: go build test.go go tool objdump ./test then search for test.go in the output and you should be able to find the go 'assembly' for your functions. also, if you use a big enough struct type then go will call into a memcpy() style routine to do the assignment. test.go:32 0x108d791 488d15d7170300 LEAQ go.string.*+255(SB), DX test.go:32 0x108d798 4889542410 MOVQ DX, 0x10(SP) test.go:32 0x108d79d 48c744241803000000 MOVQ $0x3, 0x18(SP) test.go:32 0x108d7a6 e835c2f7ff CALL runtime.mapassign_faststr(SB) test.go:32 0x108d7ab 488b7c2420 MOVQ 0x20(SP), DI test.go:32 0x108d7b0 488d742430 LEAQ 0x30(SP), SI test.go:32 0x108d7b5 48896c24f0 MOVQ BP, -0x10(SP) test.go:32 0x108d7ba 488d6c24f0 LEAQ -0x10(SP), BP test.go:32 0x108d7bf e83807fcff CALL 0x104defc 0x104defc for me looks like it duffcopy from this file: https://golang.org/src/runtime/duff_amd64.s https://golang.org/src/runtime/duff_amd64.s