Can statement "y:=append(x, ele) " malloc space?


(Pamleft) #1
func subsetsWithDup(num int) []string {
    tr := append([][]byte{}, []byte{})
    for i := 0; i < num; i++ {
        l := len(tr)
        for j := 0; j < l; j++ {
            copy := append([]byte{}, tr[j]...)
            temp1 := append(copy, '(') 
            temp2 := append(copy, ')') 
            tr = append(tr, temp1)
            tr = append(tr, temp2)
            fmt.Printf("slice address: %p - array address: %p - slice value: %#v\n", &copy, copy, copy)
            fmt.Printf("slice address: %p - array address: %p - slice value: %#v\n", &temp1, temp1, temp1)
            fmt.Printf("slice address: %p - array address: %p - slice value: %#v\n", &temp2, temp2, temp2)
            fmt.Println()
        }
        tr = tr[l:]
    }
    ret := make([]string, 0)
    for i := 0; i < len(tr); i++ {
        ret = append(ret, string(tr[i]))
    }
    return ret
}

above,remalloc new space

func subsetsWithDup(nums []int) [][]int {
	res := [][]int{}
	sort.Ints(nums)

	var dfs func(int, []int)
	dfs = func(idx int, temp []int) {
		t := temp
		//copy(t, temp)
		res = append(res, t)

		for i := idx; i < len(nums); i++ {
			if i == idx || nums[i] != nums[i-1] {
			    t2 := append(temp, nums[i])
			    fmt.Printf("slice address: %p - array address: %p - slice value: %#v\n", &temp, temp, temp)
			    fmt.Printf("slice address: %p - array address: %p - slice value: %#v\n", &t2, t2, t2)
			    fmt.Println()
				dfs(i+1, t2)
			}
		}
	}

	temp := make([]int, 0, len(nums))
	dfs(0, temp)

	return res
}

Do not remalloc new space.

Why this happens.


(Johan Dahl) #2

append will allocate a new underlying array if the new length of a slice will be longer than the capacity. In the second example you create temp with length 0 and a capicity of len(nums) so it doesn’t need to allocate a new array. But in the first example you just creates a slice and then it will get a default capacity of 4 (i think) so then you append more elements than 4 will it allocate a new underlying array of 8, and so on.


(Pamleft) #3

I think it‘s all right! Thank you.