Thanks, Edward, you make a good point.
What's more, I wrote more code yesterday, and found that we can in fact get
the 4th element even if the descriptor tells us there are only 3, by
using package
unsafe <https://golang.org/pkg/unsafe/>, and doing some simple pointer
calculation. It shows that function calls may modify the slice in
parameters under the cover, which is a bad thing if it is not on purpose. I
will keep this in mind.
Thanks.
2016-09-13 12:09 GMT+08:00 Edward Muller <edwar...@interlix.com>:
>
>
> On Mon, Sep 12, 2016 at 8:17 PM Fei Ding <fding...@gmail.com> 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 golang-nuts+unsubscr...@googlegroups.com.
>> 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 golang-nuts+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.
