我的名字叫浩仔/[译]Go数据结构

Created Tue, 14 Jun 2022 18:44:59 +0800 Modified Thu, 16 Jun 2022 00:25:06 +0800
2290 Words

原文:Go Data Structures

自己水平有限,仅供参考,如有错误,请指正。联系方式可评论,或者邮件 itcuihao@gmail.com

Russ Cox亲自解惑,值得学习。

在向新的程序员解释Go时,我发现解释Go的值在内存中是什么样子的,往往有助于建立正确的直觉,了解哪些操作是昂贵的,哪些是不昂贵的。这篇文章是关于基本类型、结构、数组和切片的。

基本类型

让我们从一些简单的例子开始:

basic-type

变量i的类型为int,在内存中表示为一个32位的字。(所有这些图片显示的是32位的内存布局;在目前的实现中,只有指针在64位机器上会变大–int仍然是32位–尽管一个实现可以选择使用64位来代替)。

变量j的类型是int32,因为有明确的转换。尽管i和j有相同的内存布局,但它们有不同的类型:赋值i = j是一个类型错误,必须用显式转换来编写:i = int(j)。

变量f的类型是float,目前的实现将其表示为32位浮点值。它的内存占用与int32相同,但内部布局不同。

结构和指针

现在事情开始有了起色。变量bytes的类型为[5]byte,是一个5字节的数组。它的内存表示就是这5个字节,一个接一个,就像C语言的数组。同样地,primes是一个4个字节的数组。

Go与C语言一样,但与Java不同,它让程序员控制什么是指针,什么不是指针。例如,这个类型定义。

type Point struct { X, Y int }

定义了一个名为Point的简单结构类型,在内存中表示为两个相邻的Int

point-type

复合字面语法Point{10, 20}表示一个初始化的Point。以复合字面的地址表示一个指向新分配和初始化的Point的指针。前者是内存中的两个字;后者是一个指向内存中两个字的指针。

结构中的字段在内存中是并排排列。

type Rect1 struct { Min, Max Point }
type Rect2 struct { Min, Max *Point }

point2-type

Rect1是一个有两个Point字段的结构,由两个Powers–四个ints–组成的一行表示。Rect2是一个有两个*Point字段的结构,由两个*Points表示。

使用过C语言的程序员可能不会对Point字段和*Point字段之间的区别感到惊讶,而只使用过Java或Python(或……)的程序员可能会对必须做出这种决定感到惊讶。通过让程序员控制基本的内存布局,Go提供了控制特定数据结构集合的总大小、分配数量和内存访问模式的能力,所有这些对于构建性能良好的系统都很重要。

字符串

有了这些初步的认识,我们就可以转向更有趣的数据类型。

string-type

(灰色箭头表示在实现中存在的指针,但在程序中不直接可见)。

一个字符串在内存中被表示为一个2个字的结构,包含一个指向字符串数据的指针和一个长度。因为字符串是不可改变的,所以多个字符串共享同一个存储空间是安全的,所以切分s的结果是一个新的2个字结构,它的指针和长度可能不同,但仍然指向同一个字节序列。这意味着切分可以在不分配或复制的情况下进行,使字符串切分和传递显式索引一样有效。

(另外,在Java和其他语言中,有一个众所周知的问题,当你切开一个字符串以保存一小部分时,对原始字符串的引用会将整个原始字符串保留在内存中,尽管只有一小部分仍然需要。Go也有这个问题。我们曾尝试过另一种方法,但被拒绝了,那就是让字符串切分变得如此昂贵–一次分配和一次复制–以至于大多数程序都会避免这样做)。

切片

slice-type

一个切片是对一个数组的一个部分的引用。在内存中,它是一个3个字的结构,包括第一个元素的指针,分片的长度和容量。长度是索引操作的上限,如x[i],而容量是切片操作的上限,如x[i:j]。

和切分字符串一样,切分数组并不产生副本:它只是创建一个新的结构,持有不同的指针、长度和容量。在这个例子中,评估复合字面[]int{2, 3, 5, 7, 11}会创建一个包含五个值的新数组,然后设置切片x的字段来描述该数组。切片表达式x[1:3]并没有分配更多的数据:它只是写了一个新的切片结构的字段来引用相同的后备存储。在这个例子中,长度是2-y[0]和y[1]是唯一有效的索引-但是容量是4-y[0:4]是一个有效的切片表达式。(关于长度和容量以及如何使用切片的更多信息,请参见Effective Go)。

因为切片是多字结构,而不是指针,所以切片操作不需要分配内存,甚至不需要分配切片头,切片头通常可以保留在堆栈中。这种表示方法使得切片的使用与C语言中传递显式指针和长度对一样便宜。Go最初将切片表示为指向上图所示结构的指针,但这样做意味着每个切片操作都要分配一个新的内存对象。即使有一个快速的分配器,这也会给垃圾收集器带来很多不必要的工作,我们发现,就像上面字符串的情况一样,程序会避免切分操作而选择传递显式索引。去掉中介和分配,使得切片的成本足够低,在大多数情况下可以避免传递显式索引。

New 与 Make

Go有两个数据结构创建函数:newmake。这种区别是早期常见的混淆点,但似乎很快就变得自然了。基本的区别是new(T)返回一个*T,一个Go程序可以隐式解除引用的指针(图中的黑色指针),而make(T, args)返回一个普通的T,不是一个指针。通常这个T里面有一些隐式指针(图中的灰色指针)。New返回一个指向归零内存的指针,而make返回一个复杂的结构。

new-type

有一种方法可以将这两者统一起来,但这将是对C和C++传统的重大突破:定义make(*T)来返回一个指向新分配的T的指针,这样,当前的new(Point)将被写成make(*Point)。我们尝试了几天,但认为这与人们对分配函数的期望差别太大。

即将到来…

这篇文章已经有点长了。接口值、映射和通道将不得不等待未来的文章。

JS
Arrow Up