设为首页 加入收藏

TOP

Go语言数组和切片的原理(二)
2019-03-26 16:13:29 】 浏览:398
Tags:语言 切片 原理
d { case initKindStatic: genAsStatic(a) default: Fatalf("fixedlit: bad kind %d", kind) } } }

假设,我们在代码中初始化 []int{1, 2, 3, 4, 5} 数组,那么我们可以将上述过程理解成以下的伪代码:

var arr [5]int
statictmp_0[0] = 1
statictmp_0[1] = 2
statictmp_0[2] = 3
statictmp_0[3] = 4
statictmp_0[4] = 5
arr = statictmp_0

总结起来,如果数组中元素的个数小于或者等于 4 个,那么所有的变量会直接在栈上初始化,如果数组元素大于 4 个,变量就会在静态存储区初始化然后拷贝到栈上,这些转换后的代码才会继续进入 中间代码生成机器码生成 两个阶段,最后生成可以执行的二进制文件。

访问和赋值

无论是在栈上还是静态存储区,数组在内存中其实就是一连串的内存空间,表示数组的方法就是一个指向数组开头的指针,这一片内存空间不知道自己存储的是什么变量:

数组访问越界的判断也都是在编译期间由静态类型检查完成的,typecheck1 函数会对访问的数组索引进行验证:

func typecheck1(n *Node, top int) (res *Node) {
    switch n.Op {
    case OINDEX:
        ok |= ctxExpr
        l := n.Left
        r := n.Right
        t := l.Type
        switch t.Etype {
        case TSTRING, TARRAY, TSLICE:
            why := "string"
            if t.IsArray() {
                why = "array"
            } else if t.IsSlice() {
                why = "slice"
            }

            if n.Right.Type != nil && !n.Right.Type.IsInteger() {
                yyerror("non-integer %s index %v", why, n.Right)
                break
            }

            if !n.Bounded() && Isconst(n.Right, CTINT) {
                x := n.Right.Int64()
                if x < 0 {
                    yyerror("invalid %s index %v (index must be non-negative)", why, n.Right)
                } else if t.IsArray() && x >= t.NumElem() {
                    yyerror("invalid array index %v (out of bounds for %d-element array)", n.Right, t.NumElem())
                } else if Isconst(n.Left, CTSTR) && x >= int64(len(n.Left.Val().U.(string))) {
                    yyerror("invalid string index %v (out of bounds for %d-byte string)", n.Right, len(n.Left.Val().U.(string)))
                }
            }
        }
    //...
    }
}

无论是编译器还是字符串,它们的越界错误都会在编译期间发现,但是数组访问操作 OINDEX 会在编译期间被转换成两个 SSA 指令:

PtrIndex <t> ptr idx
Load <t> ptr mem

编译器会先获取数组的内存地址和访问的下标,然后利用 PtrIndex 计算出目标元素的地址,再使用 Load 操作将指针中的元素加载到内存中。

数组的赋值和更新操作 a[i] = 2 也会生成 SSA 期间就计算出数组当前元素的内存地址,然后修改当前内存地址的内容,其实会被转换成如下所示的 SSA 操作:

LocalAddr {sym} base _
PtrIndex <t> ptr idx
Store {t} ptr val mem

在这个过程中会确实能够目标数组的地址,再通过 PtrIndex 获取目标元素的地址,最后将数据存入地址中,从这里我们可以看出无论是数组的寻址还是赋值都是在编译阶段完成的,没有运行时的参与。

切片

数组其实在 Go 语言中没有那么常用,更加常见的数据结构其实是切片,切片其实就是动态数组,它的长度并不固定,可以追加元素并会在切片容量不足时进行扩容。

在 Golang 中,切片类型的声明与数组有一些相似,由于切片是『动态的』,它的长度并不固定,所以声明类型时只需要指定切片中的元素类型:

[]int
[]interface{}

从这里的定义我们其实也能推测出,切片在编译期间的类型应该只会包含切片中的元素类型,NewSlice 就是编译期间用于创建 Slice 类型的函数:

func NewSlice(elem *Type) *Type {
    if t := elem.Cache.slice; t != nil {
        if t.Elem() != elem {
            Fatalf("elem mismatch")
        }
        return t
    }

    t := New(TSLICE)
    t.Extra = Slice{Elem: elem}
    elem.Cache.slice = t
    return t
}

我们可以看到上述方法返回的类型 TSLICEExtra 字段是一个只包含切片内元素类型的 Slice{Elem: elem}结构,也就是说切片内元素的类型是在编译期间确定的。

结构

编译期间的切片其实就是一个 Slice 类型,但是在运行时切片其实由如下的 SliceHeader 结构体表示,其中 Data 字段是一个指向数组的指针,Len 表示当前切片的长度,而 Cap 表示当前切片的容量,也就是 Data 数组的大小:

type SliceHeader struct {
    Data uintptr
    Len  int
    Cap  int
}

Data 作为一个指针指向的数组其实就是一片连续的内存空间,这片内存空间可以用于存储切片中保存的全部元素,数组其实就是一片连续的内存空间,数组中的元素只是逻辑上的概念,底层存储其实都是连续的,所以我们可以将切片理解成一片连续的内存空间加上长度与容量标识。

与数组不同,数组中大小、其中的元素还有对数组的访问和更新在编译期间就已经全部转换成了直接对内存的操作,但是切片是运行时才会确定的结构,所有的操作还需要依赖 Go 语言的运行时来完成,我们接下来就会介绍切片的一些常见操作的实现原理。

初始化

首先需要介绍的就是切片的创建过程,Go 语言中的切片总共有两种初始化的方式,一种是使用字面量初始化新的切片,另一种是使用关键字 make 创建切片:

slice := []int{1, 2, 3}
slice := make([]int, 10)

字面量

我们先来介绍如何使用字面量的方式创建新的切片结构,[]int{1, 2, 3} 其实会在编译期间由 slicelit 转换成如下所示的代码:

var vstat [3]int
vstat[0] = 1
vstat[1] = 2
vstat[2] = 3
var vauto *[3]int = new([3]int)
*vauto = vstat
slice
首页 上一页 1 2 3 4 5 下一页 尾页 2/5/5
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇理解Golang哈希表Map的元素 下一篇Go指南 - 笔记

最新文章

热门文章

Hot 文章

Python

C 语言

C++基础

大数据基础

linux编程基础

C/C++面试题目