Map of structs vs Array of structs

[col...@gmail.com]

Let's say I have a simple struct a with a string property b:

type A struct {
    B string
}

The following code using an array of A types:

testArray := []A{A{}}
testArray[0].B = "test1"
fmt.Println(testArray[0].B)

Will print out "test1" as expected.

But this code that seems equally simple:

testMap := make(map[string]A)
testMap["key"] = A{}
testMap["key"].B = "test2"
fmt.Println(testMap["key"].B)

Will not print out "test2" but instead will result in the following error:

cannot assign to testMap["key"].B

So, why does assigning to the subproperty in a map result in an error while assigning to the subproperty in an array work as expected? I want to know both why this doesn't work for maps AND why it does work for arrays. I would also love some speculation on why they designed the language with this difference between the two data structures.

I asked this same question on StackOverflow and the answer I was given was that arrays are magic:

http://stackoverflow.com/questions/18083044/map-of-structs-vs-array-of-structs-in-go/18083492#18083492

[Ian Lance Taylor]

On Tue, Aug 6, 2013 at 9:43 AM, <col...@gmail.com> wrote:
>
> So, why does assigning to the subproperty in a map result in an error while
> assigning to the subproperty in an array work as expected? I want to know
> both why this doesn't work for maps AND why it does work for arrays. I would
> also love some speculation on why they designed the language with this
> difference between the two data structures.

In language terms, you can only set a field in a struct value if the
struct value is addressable. See
http://golang.org/ref/spec#Assignments and
http://golang.org/ref/spec#Address_operators .

It is designed that way because we want to permit setting a new key in
a map to grow the hash table if necessary, moving the map around in
memory. That means that the language can not permit taking the
address of an entry in a map--if it could, it would not be possible to
move a map in memory. You can take the address of an entry in an
array or a slice, but that is OK, as the runtime will never move an
array or slice in memory.

To support maps moving around, internally they are implemented by
always copying complete values. You can read a value in a map, which
means you get a copy of the value in the map. Or you can assign a
value to a map, in which case a copy of the value is stored in the
map. An expression like

testMap["key"].B = "test2"

is a read-modify-write. It has to read testMap["key"], modify it, and
write the modified value back to testMap["key"].

Now, all that said, it would be possible to implement this. We could
permit read-modify-write on maps, which would mean permitting
assignments to fields of structs stored in maps. But I doubt we could
never permit taking the address of an entry in a map. So permitting
assignments to a field in a struct stored in a map would actually be
an additional feature in the language and an additional complication
that would to be supported by the various implementations. It's
possible, but there is a cost, and it needs to come with some
corresponding benefit. Since it's pretty easy to write
v := testMap["key"]
v.B = "test2"
testMap["key"] = v
and since that would be no less efficient than

testMap["key"].B = "test2"

the benefit of permitting the latter is fairly small, and it's not
clear that it is worth the cost.

Ian

[Christoph Hack]

Ian has already provided an in-depth answer. The practical answer however, is probably that you just store pointers in the map instead of the values itself:

http://play.golang.org/p/LUUQMGtYNj

[RickyS]

So when Go rebalances a map internally, it actually copies around the keys and values, and not just references to them?

In the name of efficiency?  I would have thought that the hash table is a table of pointers, since map keys and values could be huge.  But I suppose you've done your homework on this...

The Go coder could use maps with pointers as values and keys.  So once we know about, we can deal with it...

But it means my idea of a tagsort for maps can't work.  I'll survive.

[Ian Lance Taylor]

On Tue, Aug 6, 2013 at 12:06 PM, RickyS <rickys...@gmail.com> wrote:
> So when Go rebalances a map internally, it actually copies around the keys
> and values, and not just references to them?

Yes.

> In the name of efficiency?

Yes.

> I would have thought that the hash table is a
> table of pointers, since map keys and values could be huge. But I suppose
> you've done your homework on this...

Yes.

Code is in src/pkg/runtime/hashmap.c.

Ian

[col...@gmail.com]

Thank you!  That is very helpful.  It may be useful to post that entire reply in your stack overflow answer for future readers to find.

[Ian Lance Taylor]

On Tue, Aug 6, 2013 at 1:57 PM, Jakob Borg <ja...@nym.se> wrote:
> 2013/8/6 Ian Lance Taylor <ia...@golang.org>:

>> It is designed that way because we want to permit setting a new key in
>> a map to grow the hash table if necessary, moving the map around in
>> memory. That means that the language can not permit taking the
>> address of an entry in a map--if it could, it would not be possible to
>> move a map in memory.
>

> How come append to a slice doesn't ever need to move the contents in
> order to grow the slice?

When append needs to move the contents, it gives you a slice that
refers to a new backing store. The old backing store still exists and
pointers to it are still valid. And a program could even reasonable
use it.

This does mean that whether a function like this prints 2 or 100
depends on the details of the implementation of append.

func main() {
a := append([]int{}, 1, 2, 3)
a = append(a, 4)
p := &a[1]
a = append(a, 5, 6, 7)
a[1] = 100
fmt.Println(*p)
}

Ian

[Jakob Borg]

2013/8/6 Ian Lance Taylor <ia...@golang.org>:

> It is designed that way because we want to permit setting a new key in
> a map to grow the hash table if necessary, moving the map around in
> memory. That means that the language can not permit taking the
> address of an entry in a map--if it could, it would not be possible to
> move a map in memory.

How come append to a slice doesn't ever need to move the contents in
order to grow the slice?

//jb

[Dan Kortschak]

It may.

[sir...@gmail.com]

Thanks for these responses.

[Robert Engels]

Ian, can you clarify that for me, so the GC tracks interior pointers (to a slice of structs) so that even if there are no references to the outer slice it will not be GCd? That would seem to be very expensive. 

On Nov 9, 2019, at 9:36 AM, sir...@gmail.com wrote:



--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/a6acb447-ac6d-47e5-a2e8-eaa49e1b732a%40googlegroups.com.

[robert engels]

WellI ran some tests and that is indeed the case - but it looks like retains a reference to the entire slice (which is expected).

Can you point to some documentation on how the GC tracks these interior pointers?

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/C5210B7D-0139-42BC-A7AE-9D33E54EC539%40ix.netcom.com.

[keith....@gmail.com]

Note: this issue - assigning to a field of a compound map value - is a proposal at https://github.com/golang/go/issues/3117

> Ian, can you clarify that for me, so the GC tracks interior pointers (to a slice of structs) so that even if there are no references to the outer slice it will not be GCd? That would seem to be very expensive. 

Yes, the Go GC does that.  It's not super expensive, but it does have more overhead than other GCs, mostly because object headers don't work.

The additional task is just to round the pointer down to the beginning of the object. We keep some data structures per page (8KB) that make that computation quick.

> WellI ran some tests and that is indeed the case - but it looks like retains a reference to the entire slice (which is expected).

Right.

> Can you point to some documentation on how the GC tracks these interior pointers?

See src/runtime/mbitmap.go:findObject

To unsubscribe from this group and stop receiving emails from it, send an email to golan...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/a6acb447-ac6d-47e5-a2e8-eaa49e1b732a%40googlegroups.com.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.

To unsubscribe from this group and stop receiving emails from it, send an email to golan...@googlegroups.com.