should I pass map by value or by reference ?

[Ilyia Kaushansky]

Hi,

If I'm understanding Go correctly, if I want to create a function that might expand the slice that is passed via an argument, the argument needs to be *[]T. Otherwise, the caller's slice will keep referencing the old array.

What about a Map ? If a function adds data to the map and the caller wants to see this data, should the function take *map[x]y, or should the function take map[x]y ?

Thanks,

ilyia

[David Symonds]

Pass the map by value.

[Ilyia Kaushansky]

Thank you, David !

Is this documented anywhere ? I've seen some docs on implementation details of slices, but I haven't found anything that would explain implementation details of Maps, or why it is sufficient to pass by value.

Thanks,

ilyia

On Thursday, April 26, 2012 2:03:52 AM UTC-7, David Symonds wrote:

Pass the map by value.

[David Symonds]

On Thu, Apr 26, 2012 at 8:38 PM, Ilyia Kaushansky <ikau...@gmail.com> wrote:

> Is this documented anywhere ? I've seen some docs on implementation details
> of slices, but I haven't found anything that would explain implementation
> details of Maps, or why it is sufficient to pass by value.

http://golang.org/ref/spec#Making_slices_maps_and_channels

[Miguel Pignatelli]

On 26/04/12 11:38, Ilyia Kaushansky wrote:
> Thank you, David !
>
> Is this documented anywhere ? I've seen some docs on implementation
> details of slices, but I haven't found anything that would explain
> implementation details of Maps, or why it is sufficient to pass by value.
>

The only reference that comes to mind right now is:

http://golang.org/doc/effective_go.html#maps
"Like slices, maps are a reference type"

Meaning that when passed to a function, only the reference it holds is
passed.

M;

[Ilyia Kaushansky]

I read this part.  

What I find odd, however, is that in order to append to a slice, I need to pass by reference (otherwise the caller of the function might not see the changes), but in order to add to a map, I need to pass by value. If both slices and maps were truly reference types (as suggested by the following phrase of the doc: Slices, maps and channels are reference types), then this distinction would not be necessary.

I'm not suggesting that current implementation is bad. I'm merely pointing out that current documentation is somewhat incomplete.

[David Symonds]

On Thu, Apr 26, 2012 at 8:53 PM, Ilyia Kaushansky <ikau...@gmail.com> wrote:

> What I find odd, however, is that in order to append to a slice, I need to
> pass by reference (otherwise the caller of the function might not see the
> changes), but in order to add to a map, I need to pass by value. If both
> slices and maps were truly reference types (as suggested by the following
> phrase of the doc: Slices, maps and channels are reference types), then this
> distinction would not be necessary.

The key difference is that when you append to a slice, you are
potentially modifying the slice itself, not just what it holds. Slices
are a contiguous view onto an array, so appending to them might
require reallocating and copying, which does not affect any other copy
of that slice that might be looking at the original array. A map is
inherently non-contiguous, and you never need to reallocate the map
itself, only stuff that's buried inside it, and that means that a
change to a map is reflected in every copy of that map.

That is why you must pass a slice as a pointer if you want the
function to modify your copy of it, but you don't have to do that for
a map.


Dave.

[Ilyia Kaushansky]

Thank you for an explanation, David. 

For background, here is why I asked my original question:

According to the docs, slice is implemented as a small structure that among other things holds a pointer to an array. Many implementations of map are also based on an array. So I've made the assumption that maps are implemented similarly to slices: a small structure that among other things holds a pointer to a backing array.

I don't think this is a particularly terrible assumption to make. I'm sure many other people might make it too. If this assumption was correct, then I would need to pass the map by reference because the backing array could grow, and the pointer in the structure would need to be replaced. 

 

Dave.

[Lars Pensjö]

On Thursday, 26 April 2012 12:50:41 UTC+2, emepyc wrote:

The only reference that comes to mind right now is:

http://golang.org/doc/effective_go.html#maps
"Like slices, maps are a reference type"

I find the statement "a slice is a reference type" slightly misleading. A slice consists of two parts, a background array that is indeed referenced, and then a pointer and length information. The second part of this is just a value. If you pass a slice by value, only the underlying array can be changed.

A map, on the other hand, is a true reference type I think. If you pass it by value, you can still add elements to it.

What I am trying to say, is that it is difficult to understand the behaviour of maps compared to slices without understanding the internal representation.

 

Meaning that when passed to a function, only the reference it holds is
passed.

So that is not completely true, or at least difficult to interpret? Something that is passed as a reference can be modified by the called function. The length information about a slice is copied as a value, not as a reference, and so it cannot be modified.

A more correct statement could be "A slice holds a reference to the underlying array", instead of "A slice is a reference type"?

[Miguel Pignatelli]

On 26/04/12 14:11, Lars Pensjö wrote:
> A more correct statement could be "A slice holds a reference to the
> underlying array", instead of "A slice is a reference type"?

I agree that the documentation can be a bit clearer about this.
Also, I think that a blog post like [1] on map internals would be very
welcome (maybe now that Go1 is here).

[1] http://research.swtch.com/godata

Cheers,

M;

[Maxim Khitrov]

I'm a newcomer to Go, having used the language since this past
Saturday. Over these few days I've gone through all available
documentation on golang.org and most of the articles on Russ's site.

Personally, I think that this information should be included in the
official language documentation, not just a blog post. Russ's
descriptions of the data type internals (above), how interfaces are
implemented [1], and even the details of the language at the assembly
level [2], have been extremely helpful to me in building up an overall
picture of the ideas behind the language.

I'm not suggesting that any of this information be included in the
introduction for new users, but it should be there in an appendix
somewhere for people who are interested in this level of detail.

I would also suggest documenting things such as performance
characteristics of various data structures. After reading the official
documentation I still had no idea whether a map is implemented as a
hash table or as a red-black tree, for example. Sometimes it's very
helpful to know these things. I finally found the answer by skimming
through the source code.

- Max

[1] http://research.swtch.com/interfaces
[2] http://research.swtch.com/goabstract

[Kyle Lemons]

On Thu, Apr 26, 2012 at 8:33 AM, Maxim Khitrov <m...@mxcrypt.com> wrote:

On Thu, Apr 26, 2012 at 11:04 AM, Miguel Pignatelli <eme...@gmail.com> wrote:
> On 26/04/12 14:11, Lars Pensjö wrote:
>>
>> A more correct statement could be "A slice holds a reference to the
>> underlying array", instead of "A slice is a reference type"?
>
>
> I agree that the documentation can be a bit clearer about this.
> Also, I think that a blog post like [1] on map internals would be very
> welcome (maybe now that Go1 is here).
>
> [1] http://research.swtch.com/godata

I'm a newcomer to Go, having used the language since this past
Saturday. Over these few days I've gone through all available
documentation on golang.org and most of the articles on Russ's site.

Personally, I think that this information should be included in the
official language documentation, not just a blog post. Russ's
descriptions of the data type internals (above), how interfaces are
implemented [1], and even the details of the language at the assembly
level [2], have been extremely helpful to me in building up an overall
picture of the ideas behind the language.

While I absolutely agree with their utility, I believe the reason they are not in the repository (and thus not on golang.org) or even linked from there in a majority of cases is because the authors want to avoid canonizing their implementations.

The Go spec (and memory model) is intended to be the canonical description of what a correct program is and how it works, and the compilers should be free to change and evolve within that.

 

I'm not suggesting that any of this information be included in the
introduction for new users, but it should be there in an appendix
somewhere for people who are interested in this level of detail.

I would also suggest documenting things such as performance
characteristics of various data structures. After reading the official
documentation I still had no idea whether a map is implemented as a
hash table or as a red-black tree, for example. Sometimes it's very
helpful to know these things. I finally found the answer by skimming
through the source code.

The implementations can certainly be enlightening, but the data structures are deliberately left implementation-dependent.

As one example, relying on the two-word interface value implementation that currently exists in (I believe) both compilers is not guaranteed, as an implementation is perfectly within its rights to make an interface a pointer to a type-prefixed block of memory to make interface assignments atomic if it wishes.  Also, a go compiler for a shared environment like AppEngine has to ensure that code running within its bounds is safe, and is free to do so as long as it complies with the spec, even if it changes the performance dynamic of code.

[Maxim Khitrov]

I understand that reasoning completely. I'm just trying to convey my
own experiences in learning Go. Reading Russ's blog helped me grasp
the key language concepts, even though I understand that these details
may not match what other compilers are doing and may change in future
releases. Since the information is already available, I would simply
make it easy to find on golang.org and put a banner on it saying "this
information describes one of the current implementations of Go and is
not part of the language specifications" (or something to that
effect).

Speaking of the language spec, I do think that defining worst-case
performance of built-in data types should be a part of it. If a
compiler implements the map type using O(n^2) algorithm, that's
allowed by the current spec, but is probably not a good thing for the
Go community as a whole. People will simply stop relying on built-in
types in cases where they need some performance guarantees.

My suggestion would be to say something like "the built-in map is
guaranteed to have O(n*log(n)) insert/search/delete operations, but a
compiler may choose a different algorithm that provides amortized O(1)
performance." This would allow developers to make informed choices
regarding where and how to use the built-in types, yet provides
sufficient freedom for implementations select the best internal data
structures for the target environment.

- Max

[Maxim Khitrov]

I meant to say O(log(n)); have been doing a lot of sorting lately :)

- Max

[Steven Blenkinsop]

On Thu, Apr 26, 2012 at 9:11 AM, Lars Pensjö <lars....@gmail.com> wrote:

On Thursday, 26 April 2012 12:50:41 UTC+2, emepyc wrote:

The only reference that comes to mind right now is:

http://golang.org/doc/effective_go.html#maps
"Like slices, maps are a reference type"

I find the statement "a slice is a reference type" slightly misleading. A slice consists of two parts, a background array that is indeed referenced, and then a pointer and length information. The second part of this is just a value. If you pass a slice by value, only the underlying array can be changed.

A map, on the other hand, is a true reference type I think. If you pass it by value, you can still add elements to it.

A map also consists of two parts: the underlying map data structure which we don't have access to in Go code, and a pointer to it, which is just a value. The key thing about reference types in Go is that they aren't l-value references like in C++. Whenever you see:

a = ...

 

it doesn't matter if a is a reference type, you are performing an operation on it that won't be replicated on the callee's side, since you are reassigning the variable. In the case of maps, slices, and chans alike, there is no operation not in the form of a variable reassignment that breaks reference semantics. It just happens that a given slice value has a fixed size, and in order to extend it, you have to create a new slice value, which may or may not reference the same underlying array. People might be translating a = append(a, ...) into a.append(...) in their minds, but it is not a mutating operation, it is in fact a reassignment.

[⚛]

On Thursday, April 26, 2012 12:53:19 PM UTC+2, Ilyia Kaushansky wrote:

What I find odd, however, is that in order to append to a slice, I need to pass by reference (otherwise the caller of the function might not see the changes), but in order to add to a map, I need to pass by value. If both slices and maps were truly reference types (as suggested by the following phrase of the doc: Slices, maps and channels are reference types), then this distinction would not be necessary.

The difference between maps and slices are the operations supported by those data types, basically:

- map: insertion, deletion, lookup

- slice: sub-slicing, indexing, taking the address of an element

Go maps do not support any "sub-mapping", and do not support taking the address of a value.

If Go was an unsafe language like C it would be possible to implement slices in the same manner as maps: slice could be represented by a pointer to tuple (size, pointer-to-starting-element). It would be possible to change the built-in function 'append' so that it does not have to yield a result. But the safety would be gone, so a programming mistake could lead to memory corruption when the program is running.

The fact that a function like

  func ADD(a *[]int, x int) { *a = append(*a, x) }

needs to use *[]int for the slice is a necessary consequence of the following combination:

 - Go is a safe language,

 - you can write someSlice[low:high] or &someSlice[index],

 - you can append new elements to a slice.

The fact that the built-in function 'append' yields a value (maybe a slice pointing to a newly allocated array) is a consequence of the mentioned combination. The combination also implies that Go cannot resize slice's backing array (neither shrink it nor enlarge it).

In case of maps, there is no &someMap[key] which would give you a *bare* pointer to the value associated with the key so that you can rewrite the value (ability to rewrite the value in this way may benefit some programs). If there was &someMap[key] allowed in Go, then the implementation of Go maps would by necessity need to be close to the implementation of Go slices. In particular, insertion into a map would look like this:

  someMap = insert(someMap, k, v)

Deletion would look like:

  someMap = delete(someMap, k)

So allowing &someMap[key] in the Go language would by necessity imply that both insertion and deletion yields a value (a map potentially pointing to a newly allocated storage).

... ... this should explain why appending to a slice yields a value and why the ADD func (mentioned above) needs to use *[]int, and why you can pass maps to your functions by values.