On Mon, Sep 12, 2016 at 8:17 PM Fei Ding <[email protected]> wrote: > Hi guys: > > I met a problem when I try to understand slice when using as function > parameters. After writing some code, I made a conclusion by myself, but > need some real check and explanation here, with your help. > > As far as I know, Golang's function parameters are passed by value, and > slice could be treated as a descriptor, which seems like *{pointer to > first element of underlying array, length of element, capacity of array}* > according to Go Slices: usage and internals > <https://blog.golang.org/go-slices-usage-and-internals>. So, can I say: > > *When passing a slice as a function parameter, it is, in fact, passing a > pointer, and two int values (or as a whole struct, or maybe more parameters > to describe the slice, whatever).* > > To make it clear using code: > > func foo(s []T) {...} > // can this function be treated as following 3-parameter function? > func foo(p Pointer, length, capa int) {...} > > // Note: type is not the point here, > // and we just need 3 parameters, while there maybe more > > You may wonder why I have this question? Here is where everything started: > > func foo(s []int) { > s := []int{1,2,3} > foo(s) > fmt.Println(s) > } > > Everyone know it will print [1 2 3], not [1 2 3 100]. But what I am > interested in, is *whether the function call does modify the memory* just > after the tail of element 3, to an int of 100. If my assumption above is > right, then the modification may happen. > > So, I made some experiments. > > package main > > import "fmt" > import "strconv" > > type Node struct { > val int > left *Node > right *Node > } > > func (n Node) String () string { > return strconv.Itoa(n.val) > } > > func newNode(val int) *Node { > return &Node{val, nil, nil} > } > > // Given a binary tree and a target sum, find all root-to-leaf paths > // where each path's sum equals the given sum > func bs(root *Node, path []*Node, now int, target int, ret *[][]*Node) { > if root == nil { > return > } > path = append(path, root) > now += root.val > if now == target && root.left == nil && root.right == nil { > *ret = append(*ret, path) > return > } > bs(root.left, path, now, target, ret) > bs(root.right, path, now, target, ret) > } > > func main() { > // a simple tree like: > // 0 > // / \ > // 1 2 > root := newNode(0) > left := newNode(1) > right := newNode(2) > root.left = left > root.right = right > > ret := [][]*Node{} > bs(root, make([]*Node, 0, 10), 0, 1, &ret) > fmt.Println(ret) > } > > > As the code above, it is a function to find all root-to-leaf paths where > each path's sum equals the given sum in a binary tree, and, I make a simple > test case which there are only 3 nodes: one root, two children, with values > of 0, 1 and 2. > > Say, I want to find the paths of sum of 1. So, I call this function as: > > bs(root, make([]*Node, 0, 10), 0, 1, &ret) > > It is petty common to make a guess that, this call will give us a final > result of [0, 1], which is obviously the correct answer, however, it gives > us [0, 2], try yourself if you don't believe: > > https://play.golang.org/p/hSKIOaVK2S > > The algorithm here is correct, don't worry about it. Instead, please pay > attention to the second parameter of bs(). It makes a slice which has no > element in it, and has a capacity of 10. What if we change this parameter > to: > > bs(root, make([]*Node, 0, 1), 0, 1, &ret) > > Yes, just make the slice's capacity as 1. This time you will get the right > answer, [0, 1]. Try yourself if you are interested. > > Here is my understanding of this strange problem, feel free to point out > anything wrong: > > Still the simplest code: > > package main > > import ( > "fmt" > ) > > func foo(s []int) { > fmt.Println(len(s), cap(s)) // 3 3 > s = append(s, 100) > fmt.Println(len(s), cap(s)) // 4 8 > } > > func main() { > s := []int{1,2,3} > foo(s) > fmt.Println(len(s), cap(s)) // 3 3 > fmt.Println(s) // [1 2 3] > } > > When the function foo() called, it has 3 parameters: a pointer of the > first element of the array, which points to the element 1, an int for array > length: 3, an int for array capacity: 3. In foo(), it tries to append 100 > at the tail, but there is no room for it, according to the parameter of > capacity it receive, so, it makes a larger array, which capacity is 8, then > do some copy-and-append job. Unfortunately, all the work it does is useless > because all three parameters is still themselves. So, at last, it prints [1 > 2 3] > > But, what will happen if the slice passed into foo() is large enough > already? > > package main > > import ( > "fmt" > ) > > func foo(s []int) { > fmt.Println(len(s), cap(s)) // 3 10 > s = append(s, 100) > fmt.Println(len(s), cap(s)) // 4 10 > } > > func main() { > s := make([]int, 3, 10) > s[0], s[1], s[2] = 1, 2, 3 > foo(s) > fmt.Println(len(s), cap(s)) // 3 10 > fmt.Println(s) // [1 2 3] > } > > Now, foo() is lucky, he does not need to allocate any memory, he just > append 100 at the tail, the descriptor now becomes {address somewhere, 4, > 10}. However, in main, it is still {address somewhere, 3, 10} on account of > the pass-by-value-calling-rule, *so, we just care about the first 3 > elements of the array, and ignore others because the descriptor tells us > to, even though there does exist the 4th one.* > > How to prove there is a 4th one? Which is equal to ask, how to prove the > function call modify the passed slice? Check the path-of-sum algorithm > above, it may show something indirectly. > > The algorithm starts from the root, 0, then goes to his left child, 1, > there it meets the target sum, 1 (0+1), so it append 1 into the path slice > (which now is [0,1], descriptor as {address, 2, 10}) and append the path > slice into ret. After this, it will find no child exists, so it returns > from current position and goes back to the root to check root's right > child. Now, the path slice's descriptor is {address, 1, 10}. When checking > the right child, it append 2 into path, which does modify the memory where > 1 sits already. At last, it will print [0, 2] as the wrong result. > > This tells us one thing: function calls may modify your passed slice, but > the slice descriptor keeps you from knowing it. >
Yes, the slice header is copied when passed to a function, not the backing array. Also note, `append` return a modified slice as it may need to create a new backing array and copy over the contents of the existing backing array if needed to ensure sufficient capacity. Similarly if you write a function that modifies a slice in some way you should return a slice (could be the same slice). > > My personal explanation is done, and here are my questions: > > 1. Am I right? What's wrong? > 2. If I am right, mostly, how to prevent it gracefully? Any rules, or any > blogs I can learn from? > Prevent what exactly? If you know the eventual capacity of your slice, just create one with that capacity to start with. The go blog you listed above is good. > 3. Any better code snippet to do some experiment to make it more > convincing? Does packet reflect <https://golang.org/pkg/reflect/> > helpful? can I just print the 4th element even though the slice descriptor > tell me its length is 3? > You can't, or at the very least shouldn't try. These are effectively implementation details of how slices work. Why do you feel the need to prevent/work against slices? > 4. Where can I find the code of implementation of slice? > https://golang.org/src/runtime/slice.go > Thanks a lot. > > -- > 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 [email protected]. > For more options, visit https://groups.google.com/d/optout. > -- 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 [email protected]. For more options, visit https://groups.google.com/d/optout.
