设为首页 加入收藏

TOP

Go语言数组和切片的原理(五)
2019-03-26 16:13:29 】 浏览:381
Tags:语言 切片 原理
} }

切片的操作基本都是在编译期间完成的,除了访问切片的长度、容量或者其中的元素之外,使用 range 遍历切片时也是在编译期间被转换成了形式更简单的代码,我们会在后面的章节中介绍 range 关键字的实现原理。

追加

向切片中追加元素应该是最常见的切片操作,在 Go 语言中我们会使用 append 关键字向切片中追加元素,追加元素会根据是否 inplace 在中间代码生成阶段转换成以下的两种不同流程,如果 append 之后的切片不需要赋值回原有的变量,也就是如 append(slice, 1, 2, 3) 所示的表达式会被转换成如下的过程:

ptr, len, cap := slice
newlen := len + 3
if newlen > cap {
    ptr, len, cap = growslice(slice, newlen)
    newlen = len + 3
}
*(ptr+len) = 1
*(ptr+len+1) = 2
*(ptr+len+2) = 3
return makeslice(ptr, newlen, cap)

我们会先对切片结构体进行解构获取它的数组指针、大小和容量,如果新的切片大小大于容量,那么就会使用 growslice 对切片进行扩容并将新的元素依次加入切片并创建新的切片,但是 slice = apennd(slice, 1, 2, 3) 这种 inplace 的表达式就只会改变原来的 slice 变量:

a := &slice
ptr, len, cap := slice
newlen := len + 3
if uint(newlen) > uint(cap) {
   newptr, len, newcap = growslice(slice, newlen)
   vardef(a)
   *a.cap = newcap
   *a.ptr = newptr
}
newlen = len + 3
*a.len = newlen
*(ptr+len) = 1
*(ptr+len+1) = 2
*(ptr+len+2) = 3

上述两段代码的逻辑其实差不多,最大的区别在于最后的结果是不是赋值会原有的变量,不过从 inplace 的代码可以看出 Go 语言对类似的过程进行了优化,所以我们并不需要担心 append 会在数组容量足够时导致发生切片的复制。

到这里我们已经了解了在切片容量足够时如何向切片中追加元素,但是如果切片的容量不足时就会调用 growslice 为切片扩容:

func growslice(et *_type, old slice, cap int) slice {
    newcap := old.cap
    doublecap := newcap + newcap
    if cap > doublecap {
        newcap = cap
    } else {
        if old.len < 1024 {
            newcap = doublecap
        } else {
            for 0 < newcap && newcap < cap {
                newcap += newcap / 4
            }
            if newcap <= 0 {
                newcap = cap
            }
        }
    }

扩容其实就是需要为切片分配一块新的内存空间,分配内存空间之前需要先确定新的切片容量,Go 语言根据切片的当前容量选择不同的策略进行扩容:

  1. 如果期望容量大于当前容量的两倍就会使用期望容量;
  2. 如果当前切片容量小于 1024 就会将容量翻倍;
  3. 如果当前切片容量大于 1024 就会每次增加 25% 的容量,直到新容量大于期望容量;

确定了切片的容量之后,我们就可以开始计算切片中新数组的内存占用了,计算的方法就是将目标容量和元素大小相乘:

    var overflow bool
    var lenmem, newlenmem, capmem uintptr
    switch {
    // ...
    default:
        lenmem = uintptr(old.len) * et.size
        newlenmem = uintptr(cap) * et.size
        capmem, overflow = math.MulUintptr(et.size, uintptr(newcap))
        capmem = roundupsize(capmem)
        newcap = int(capmem / et.size)
    }

    var p unsafe.Pointer
    if et.kind&kindNoPointers != 0 {
        p = mallocgc(capmem, nil, false)
        memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
    } else {
        p = mallocgc(capmem, et, true)
        if writeBarrier.enabled {
            bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(old.array), lenmem)
        }
    }
    memmove(p, old.array, lenmem)

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

如果当前切片中元素不是指针类型,那么就会调用 memclrNoHeapPointers 函数将超出当前长度的位置置空并在最后使用 memmove 将原数组内存中的内容拷贝到新申请的内存中, 不过无论是 memclrNoHeapPointers 还是 memmove 函数都使用目标机器上的汇编指令进行实现,例如 WebAssembly 使用如下的命令实现 memclrNoHeapPointers 函数:

TEXT runtime·memclrNoHeapPointers(SB), NOSPLIT, $0-16
    MOVD ptr+0(FP), R0
    MOVD n+8(FP), R1

loop:
    Loop
        Get R1
        I64Eqz
        If
            RET
        End

        Get R0
        I32WrapI64
        I64Const $0
        I64Store8 $0

        Get R0
        I64Const $1
        I64Add
        Set R0

        Get R1
        I64Const $1
        I64Sub
        Set R1

        Br loop
    End
    UNDEF

growslice 函数最终会返回一个新的 slice 结构,其中包含了新的数组指针、大小和容量,这个返回的三元组最终会改变原有的切片,帮助 append 完成元素追加的功能。

拷贝

切片的拷贝虽然不是一个常见的操作类型,但是却是我们学习切片实现原理必须要谈及的一个问题,当我们使用 copy(a, b) 的形式对切片进行拷贝时,编译期间会被转换成 slicecopy 函数:

func slicecopy(to, fm slice, width uintptr) int {
    if fm.len == 0 || to.len == 0 {
        return 0
    }

    n := fm.len
    if to.len < n {
        n = to.len
    }

    if width == 0 {
        return n
    }
    
    // ...

    size := uintptr(n) * width
    if size == 1 {
        *(*byte)(to.array) = *(*byte)(fm.array)
    } else {
        memmove(to.array, fm.array, size)
    }
    return n
}

上述函数的实现非常直接,它将切片中的全部元素通过 memmove 或者数组指针的方式将整块内存中的内容拷贝到目标的内存区域:

相比于依次对元素进行拷贝,这种方式能够提供更好的性能,但是需要注

首页 上一页 2 3 4 5 下一页 尾页 5/5/5
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇理解Golang哈希表Map的元素 下一篇Go指南 - 笔记

最新文章

热门文章

Hot 文章

Python

C 语言

C++基础

大数据基础

linux编程基础

C/C++面试题目