4

I'm very interested in go, and trying to read go function's implementations. I found some of these function doesn't have implementations there.

Such as append or call:

// The append built-in function appends elements to the end of a slice. If
// it has sufficient capacity, the destination is resliced to accommodate the
// new elements. If it does not, a new underlying array will be allocated.
// Append returns the updated slice. It is therefore necessary to store the
// result of append, often in the variable holding the slice itself:
//  slice = append(slice, elem1, elem2)
//  slice = append(slice, anotherSlice...)
// As a special case, it is legal to append a string to a byte slice, like this:
//  slice = append([]byte("hello "), "world"...)
func append(slice []Type, elems ...Type) []Type

// call calls fn with a copy of the n argument bytes pointed at by arg.
// After fn returns, reflectcall copies n-retoffset result bytes
// back into arg+retoffset before returning. If copying result bytes back,
// the caller must pass the argument frame type as argtype, so that
// call can execute appropriate write barriers during the copy.
func call(argtype *rtype, fn, arg unsafe.Pointer, n uint32, retoffset uint32)

It seems not calling a C code, because using cgo needs some special comments. Where is these function's implementations?

2
  • I believe the entire compiler has been translated to Go (self hosting). If you are reading an old version, you might have luck finding the Go code in the newest ones.
    – BoppreH
    Oct 29, 2015 at 3:19
  • @BoppreH I have heard that too. But there is still no implementation of append here: link Oct 29, 2015 at 3:28

3 Answers 3

14

The code you are reading and citing is just dummy code to have consistent documentation. The built-in functions are, well, built into the language and, as such, are included in the code processing step (the compiler).

Simplified what happens is: lexer will detect 'append(...)' as APPEND token, parser will translate APPEND, depending on the circumstances/parameters/environment to code, code is written as assembly and assembled. The middle step - the implementation of append - can be found in the compiler here.

What happens to an append call is best seen when looking at the assembly of an example program. Consider this:

b := []byte{'a'}
b = append(b, 'b')
println(string(b), cap(b))

Running it will yield the following output:

ab 2

The append call is translated to assembly like this:

// create new slice object
MOVQ    BX, "".b+120(SP)       // BX contains data addr., write to b.addr
MOVQ    BX, CX                 // store addr. in CX
MOVQ    AX, "".b+128(SP)       // AX contains len(b) == 1, write to b.len
MOVQ    DI, "".b+136(SP)       // DI contains cap(b) == 1, write to b.cap
MOVQ    AX, BX                 // BX now contains len(b)
INCQ    BX                     // BX++
CMPQ    BX, DI                 // compare new length (2) with cap (1)
JHI $1, 225                    // jump to grow code if len > cap
...
LEAQ    (CX)(AX*1), BX         // load address of newly allocated slice entry
MOVB    $98, (BX)              // write 'b' to loaded address

// grow code, call runtime.growslice(t *slicetype, old slice, cap int)
LEAQ    type.[]uint8(SB), BP
MOVQ    BP, (SP)               // load parameters onto stack
MOVQ    CX, 8(SP)
MOVQ    AX, 16(SP)
MOVQ    SI, 24(SP)
MOVQ    BX, 32(SP)
PCDATA  $0, $0
CALL    runtime.growslice(SB)  // call
MOVQ    40(SP), DI
MOVQ    48(SP), R8
MOVQ    56(SP), SI
MOVQ    R8, AX
INCQ    R8
MOVQ    DI, CX
JMP 108                        // jump back, growing done

As you can see, no CALL statement to a function called append can be seen. This is the full implementation of the append call in the example code. Another call with different parameters will look differently (other registers, different parameters depending on the slice type, etc.).

4

The Go append builtin function code is generated by the Go gc and gccgo compilers and uses Go package runtime functions (for example, runtime.growslice()) in go/src/runtime/slice.go.

For example,

package main

func main() {
    b := []int{0, 1}
    b = append(b, 2)
}

Go pseudo-assembler:

$ go tool compile -S a.go

"".main t=1 size=192 value=0 args=0x0 locals=0x68
    0x0000 00000 (a.go:3)   TEXT    "".main(SB), $104-0
    0x0000 00000 (a.go:3)   MOVQ    (TLS), CX
    0x0009 00009 (a.go:3)   CMPQ    SP, 16(CX)
    0x000d 00013 (a.go:3)   JLS 167
    0x0013 00019 (a.go:3)   SUBQ    $104, SP
    0x0017 00023 (a.go:3)   FUNCDATA    $0, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
    0x0017 00023 (a.go:3)   FUNCDATA    $1, gclocals·790e5cc5051fc0affc980ade09e929ec(SB)
    0x0017 00023 (a.go:4)   LEAQ    "".autotmp_0002+64(SP), BX
    0x001c 00028 (a.go:4)   MOVQ    BX, CX
    0x001f 00031 (a.go:4)   NOP
    0x001f 00031 (a.go:4)   MOVQ    "".statictmp_0000(SB), BP
    0x0026 00038 (a.go:4)   MOVQ    BP, (BX)
    0x0029 00041 (a.go:4)   MOVQ    "".statictmp_0000+8(SB), BP
    0x0030 00048 (a.go:4)   MOVQ    BP, 8(BX)
    0x0034 00052 (a.go:4)   NOP
    0x0034 00052 (a.go:4)   MOVQ    $2, AX
    0x003b 00059 (a.go:4)   MOVQ    $2, DX
    0x0042 00066 (a.go:5)   MOVQ    CX, "".b+80(SP)
    0x0047 00071 (a.go:5)   MOVQ    AX, "".b+88(SP)
    0x004c 00076 (a.go:5)   MOVQ    DX, "".b+96(SP)
    0x0051 00081 (a.go:5)   MOVQ    AX, BX
    0x0054 00084 (a.go:5)   INCQ    BX
    0x0057 00087 (a.go:5)   CMPQ    BX, DX
    0x005a 00090 (a.go:5)   JHI $1, 108
    0x005c 00092 (a.go:5)   LEAQ    (CX)(AX*8), BX
    0x0060 00096 (a.go:5)   MOVQ    $2, (BX)
    0x0067 00103 (a.go:6)   ADDQ    $104, SP
    0x006b 00107 (a.go:6)   RET
    0x006c 00108 (a.go:5)   LEAQ    type.[]int(SB), BP
    0x0073 00115 (a.go:5)   MOVQ    BP, (SP)
    0x0077 00119 (a.go:5)   MOVQ    CX, 8(SP)
    0x007c 00124 (a.go:5)   MOVQ    AX, 16(SP)
    0x0081 00129 (a.go:5)   MOVQ    DX, 24(SP)
    0x0086 00134 (a.go:5)   MOVQ    BX, 32(SP)
    0x008b 00139 (a.go:5)   PCDATA  $0, $0
    0x008b 00139 (a.go:5)   CALL    runtime.growslice(SB)
    0x0090 00144 (a.go:5)   MOVQ    40(SP), CX
    0x0095 00149 (a.go:5)   MOVQ    48(SP), AX
    0x009a 00154 (a.go:5)   MOVQ    56(SP), DX
    0x009f 00159 (a.go:5)   MOVQ    AX, BX
    0x00a2 00162 (a.go:5)   INCQ    BX
    0x00a5 00165 (a.go:5)   JMP 92
    0x00a7 00167 (a.go:3)   CALL    runtime.morestack_noctxt(SB)
    0x00ac 00172 (a.go:3)   JMP 0
1

To add to the assembly code given by the others, you can find the Go (1.5.1) code for gc there : https://github.com/golang/go/blob/f2e4c8b5fb3660d793b2c545ef207153db0a34b1/src/cmd/compile/internal/gc/walk.go#L2895

// expand append(l1, l2...) to
//   init {
//     s := l1
//     if n := len(l1) + len(l2) - cap(s); n > 0 {
//       s = growslice_n(s, n)
//     }
//     s = s[:len(l1)+len(l2)]
//     memmove(&s[len(l1)], &l2[0], len(l2)*sizeof(T))
//   }
//   s
//
// l2 is allowed to be a string.

with growslice_n being defined there : https://github.com/golang/go/blob/f2e4c8b5fb3660d793b2c545ef207153db0a34b1/src/runtime/slice.go#L36

// growslice_n is a variant of growslice that takes the number of new elements
// instead of the new minimum capacity.
// TODO(rsc): This is used by append(slice, slice...).
// The compiler should change that code to use growslice directly (issue #11419).
func growslice_n(t *slicetype, old slice, n int) slice {
    if n < 1 {
        panic(errorString("growslice: invalid n"))
    }
    return growslice(t, old, old.cap+n)
}

// growslice handles slice growth during append.
// It is passed the slice type, the old slice, and the desired new minimum capacity,
// and it returns a new slice with at least that capacity, with the old data
// copied into it.
func growslice(t *slicetype, old slice, cap int) slice {
    if cap < old.cap || t.elem.size > 0 && uintptr(cap) > _MaxMem/uintptr(t.elem.size) {
        panic(errorString("growslice: cap out of range"))
    }

    if raceenabled {
        callerpc := getcallerpc(unsafe.Pointer(&t))
        racereadrangepc(old.array, uintptr(old.len*int(t.elem.size)), callerpc, funcPC(growslice))
    }

    et := t.elem
    if et.size == 0 {
        // append should not create a slice with nil pointer but non-zero len.
        // We assume that append doesn't need to preserve old.array in this case.
        return slice{unsafe.Pointer(&zerobase), old.len, cap}
    }

    newcap := old.cap
    if newcap+newcap < cap {
        newcap = cap
    } else {
        for {
            if old.len < 1024 {
                newcap += newcap
            } else {
                newcap += newcap / 4
            }
            if newcap >= cap {
                break
            }
        }
    }

    if uintptr(newcap) >= _MaxMem/uintptr(et.size) {
        panic(errorString("growslice: cap out of range"))
    }
    lenmem := uintptr(old.len) * uintptr(et.size)
    capmem := roundupsize(uintptr(newcap) * uintptr(et.size))
    newcap = int(capmem / uintptr(et.size))
    var p unsafe.Pointer
    if et.kind&kindNoPointers != 0 {
        p = rawmem(capmem)
        memmove(p, old.array, lenmem)
        memclr(add(p, lenmem), capmem-lenmem)
    } else {
        // Note: can't use rawmem (which avoids zeroing of memory), because then GC can scan uninitialized memory.
        p = newarray(et, uintptr(newcap))
        if !writeBarrierEnabled {
            memmove(p, old.array, lenmem)
        } else {
            for i := uintptr(0); i < lenmem; i += et.size {
                typedmemmove(et, add(p, i), add(old.array, i))
            }
        }
    }

    return slice{p, old.len, newcap}
}

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.