Go 数据结构

[SyMind]

原文： Go Data Structures Go Data Structures: Interfaces

在向新手解释 Go 时，我发现，解释 Go 值在内存中的样子通常有助于建立正确的直觉，判断哪些操作是昂贵的，哪些操作不是。这篇文章是关于基本类型、结构、数组和切片的。

基本类型

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

变量 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个 int 的数组。

Go 像 C 而非 Java 一样，让开发者拥有控制指针的权利。例如下面这个类型定义：

type Point struct { X, Y int }

定义了一个名为 Point 的结构体类型，来表示内存中两个相邻的 int。

Point{10, 20} 表示初始化 Point，在内存中占用两个字节。接着获取指向新分配和初始化的 Point 的指针，指针在内存中占用两个字节。

结构体中的字段在内存中并排放置。

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

Rect1 是一个拥有两个 Point 字段的结构体，在内存中占用连续的4个 init。Rect2 是一个拥有两个 *Point 字段的结构体，在内存中连续的2个指针。

使用过 C 的开发者可能会很熟悉 Point 字段和 *Point 字段之间的区别，而只使用过 Java 或Python 的开发者可能会感到一些心智负担。Go 提供了控制给定数据结构集合的总大小、分配数量和内存访问模式的能力，让开发者能够控制基本内存布局，这些对于构建性能良好的系统非常重要。

字符串

有了这些初步知识，我们可以继续学习更有趣的数据类型。

（灰色箭头表示在实现内部的指针，没有直接暴露在程序中。）

一个 string 在内存中占用2个字节，包含一个指向字符串数据的指针和长度。因为 string 是不可变的，让多个字符串共享同一块内存区域是安全的，所以切片 s 会产生一个新的2个字节的内存空间，其指针和长度可能不同，但仍然引用相同的字符串数据。这意味着切片可以在不分配或复制内存的情况下完成，使字符串切片与传递显式索引一样高效。

切片

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

就像对字符串进行切片一样，对数组进行切片不会生成副本：它只会创建一个包含不同指针、长度和容量的新结构。在示例中，[]int{2, 3, 5, 7, 11} 会创建一个包含五个值的新数组，然后设置切片 x 来描述该数组。切片表达式 x[1:3] 不会分配更多的内存：它只是写入新切片结构的字段以引用相同的数组数据。

因为切片是多字节结构，而不是指针，所以切片不需要在堆中分配内存，甚至切片头也不需要，通常可以将其保存在栈中。这种表示使得切片使用起来与在 C 中递显式地传递指针和长度对一样便宜。Go 最初将切片表示为指向上面所示结构的指针，但这样做意味着每个切片操作都会在堆中分配一个新的内存对象。即使使用快速的内存分配器，也会为垃圾收集器带来很多不必要的工作，我们发现，与上述字符串的情况一样，程序避免了切片操作，转而使用显式索引。删除间接和分配使切片足够便宜，可以避免在大多数情况下显式传递索引。

new 和 make

Go 有两个创建数据结构的方法：new 和 make。这种区别是初期常见的混淆点，但似乎很快就会变得自然。基本区别在于 new(T) 返回一个 *T，Go 程序可以隐式取消引用的指针（图中的黑色指针），而 make(T, args) 返回普通的 T，而不是指针。通常 T 里面有一些隐式指针（图中的灰色指针）。new 返回一个指向归零内存的指针，make 返回一个复杂的结构。

接口

Go 的接口在 —— 在编译时检查时表现为静态，在运行时类型断言时表现为动态——从语言设计的角度来看，它是 Go 最令人兴奋的部分。如果我选择 Go 的一个特性导出到其他语言中，那就是接口。

使用

Go 的接口像动态语言的鸭子类型，比如 Python。但仍然会在编译时捕获一些明显的错误，例如当传递一个 int 给一个期望拥有 Read 方法的对象时，或使用错误的参数数量调用 Read 方法时。使用接口前，首先要先定义接口类型：

type ReadCloser interface {
    Read(b []byte) (n int, err os.Error)
    Close()
}

然后定义一个需要 ReadCloser 的方法。例如，下面的方法重复调用 Read 方法，来获取所有的数据，最后调用 Close 方法：

func ReadAndClose(r ReadCloser, buf []byte) (n int, err os.Error) {
    for len(buf) > 0 && err == nil {
        var nr int
        nr, err = r.Read(buf)
        n += nr
        buf = buf[nr:]
    }
    r.Close()
    return
}

调用 ReadAndClose 的代码可以传入任意值，只要它拥有正确的 Read 和 Close 方法。与 Python 不同，如果你传入一个错误的类型，会在编译时报错，而非运行时。

不过，接口仅能够在编译时检查，也可以在运行时检查。例如：

type Stringer interface {
    String() string
}

func ToString(any interface{}) string {
    if v, ok := any.(Stringer); ok {
        return v.String()
    }
    switch v := any.(type) {
    case int:
        return strconv.Itoa(v)
    case float:
        return strconv.Ftoa(v, 'g', -1)
    }
    return "???"
}

any 的静态类型是 interface{}，意味着不存在任何候选方法：它可以包含任何类型。if 语句中的 ok 表达式判断是否能够将 any 转换为 Stringer 类型，它包含一个 String 方法。如果可以，将调用该方法来获得一个字符串并将其返回。否则，switch 会在放弃之前选择将它转换为一些基本类型。这基本上是 fmt 包的精简版本。

一个简单的例子，让我们考虑一个64位整数类型，它拥有一个将自身值返回为一个字符串的 String 方法，和一个简单的 Get 方法。

type Binary uint64

func (i Binary) String() string {
    return strconv.Uitob64(i.Get(), 2)
}

func (i Binary) Get() uint64 {
    return uint64(i)
}

Binary 类型的值可以传递给 ToString，ToString 将使用 String 方法对其进行格式化，即使程序从未说过 Binary 打算实现 Stringer。没有必要：运行时可以看到 Binary 有一个 String 方法，所以它实现了 Stringer，即使 Binary 的作者从未听说过 Stringer。

这些示例表明，即使在编译时检查所有隐式转换，显式的接口到接口转换也可以在运行时查询方法集。

接口值

带有方法的语言通常分为两个阵营：静态地为所有方法调用准备一张表（如 C++ 和 Java），或者在每次调用时进行方法查找（如 Smalltalk 及其许多模仿者，包括 JavaScript 和 Python），并添加缓存以使调用高效。Go 介于两者之间：它有方法表，但在运行时计算它们。我不知道 Go 是否是第一种使用这种技巧的语言，但它肯定不是一种常见的做法。

作为预热，Binary 类型的值是由两个32位字节组成的64位整数（就像上一篇文章中一样，我们将假设一个32位机器；这一次内存会向下增长，而不是向右增长）：

接口值在内存中占用2个字节，一个指针指向类型信息，一个指针指向关联的数据。将 b 赋给Stringer 类型的接口值将设置接口值的两个字节。

（接口值中包含的指针是灰色的，以强调它们是隐式的，而不是直接暴露在 Go 程序中。）

接口值中的第一个字节，指向 itable（发音为 i-table）。itable 中先是一些涉及到类型的元数据，接着是指向方法的指针列表。注意 itable 与 interface type 相关联，不是动态类型。在我们的例子中，被转换为 Stringer 的 Binary 的 itable 中列出了用于满足 Stringer 的方法，Get 方法没有出现在 itable 中。

接口值中的第二个字节，指向实际的值，在这个例子下是 b 的副本。var s Stringer = b 创建了一个 b 的副本，而不是指向 b，这与 var c uint64 = b 创建副本的原因相同：如果 b 之后变更了，s 和 c 拥有的应该是原始值，而非新值。存储在接口中的值是任意大的，但只有一个字节用于保存值，因此在堆上分配一块内存，并将指针记录在这个字节中。（当该值确实适合存储在该字节中时，会有一个明显的优化；稍后我们将对此进行讨论。）

要检查接口值是否包含特定类型，如上面的 type switch 所示，Go 编译器会生成与 C 表达式 s.tab->type 等效的代码，以获取类型指针并将其与所需类型进行比较。如果类型匹配，则可以通过取消 s.data 额引用来复制值。

为了调用 s.String()，Go 编译器生成的代码与 C 表达式 s.tab->fun[0](s.data) 相当：它从 itable 中调用适当的函数指针，将接口值的数据作为函数的第一个（仅在本例中）参数进行传递。如果你运行 8g -S x.go，你可以看到这段代码（详细信息见本文底部）。注意，itable 中的函数是从接口值的第二个字节传递32位指针，而不是它指向的64位值。通常，接口调用站点不知道这个字的含义，也不知道它指向多少数据。相反，接口代码安排可编辑文件中的函数指针期望存储在接口值中的32位表示。因此，本例中的函数指针是（*Binary）.String而不是Binary.String。

计算 Itable

现在我们知道了 itable 是什么样子，但它们是怎么来的呢？Go 的动态类型转换意味着编译器或链接器预先计算所有可能的 itable 是不合理的：大多数的组合都不需要。相反，编译器为每个具体类型（如 Binary、int 或 func(map[int]string)）生成类型描述结构。在其他元数据中，类型描述结构包含由该类型实现的方法的列表。类似地，编译器为每个接口类型（如 Stringer）生成一个（不同的）类型描述结构；它还包含一个方法列表。接口运行时通过在具体类型的方法表中查找接口类型方法表中列出的每个方法来计算 itable。运行时在生成 itable 后对其进行缓存，因此这种对应关系只需计算一次。

在我们简单的例子中，Stringer 的方法表有一个方法，而 Binary 的表有两个方法。通常，接口类型可能有 ni 个方法，具体类型可能有 nt 个方法。显然，构建从接口方法到具体方法的映射需要 O(ni × nt) 时间，但我们可以做得更好。通过对两个方法表进行排序并同时遍历它们，我们可以在 O(ni + nt) 时间内构建完映射。

内存优化

上述实现所使用的内存空间可以通过两种互补的方式优化。

首先，如果所涉及的接口类型是空的，那么它没有方法，那么除了保持指向原始类型的指针之外，itable 没有任何作用。在这种情况下，可以删除 itable，直接指向类型：

接口类型是否具有方法是一个静态属性，类型在源代码中要么是 interface{}，要么是 interace{ methods... }，因此编译器知道程序中每处是哪种表示。

第二，如果与接口值所关联的值可以存储在一个字节中，则无需间接引用或分配堆内存。如果我们参照 Binary 定义 Binary32 但其实现为 uint32，则可以将实际值存储在第二个字节中来将其存储在接口值中：

Of course, empty interfaces holding word-sized (or smaller) values can take advantage of both optimizations:

当然，小于等于一个字节的值的空接口可以同时利用这两种优化：

方法查找性能

Smalltalk 和其他许多动态语言在每次调用方法时都会执行方法查找。为了提升速度，许多实现在每个调用位置增加一些简单的单条目缓存。在多线程中，必须小心管理这些缓存，因为多个线程可能同时出于同一调用位置。即使避免了竞争，缓存也会导致内存争用。

由于 Go 在动态方法查找中还拥有静态类型信息，因此它可以将查找操作从调用位置移回到接口值。例如，考虑以下代码段：

1   var any interface{}  // initialized elsewhere
2   s := any.(Stringer)  // dynamic conversion
3   for i := 0; i < 100; i++ {
4       fmt.Println(s.String())
5   }

在 Go 中，在第2行的赋值过程中计算（或在缓存中找到）itable；在第4行调用 s.String() 时发生两次内存读取和一个间接的调用指令。

相比之下，用 Smalltalk（或 JavaScript、Python 等）之类的动态语言实现将在第4行执行方法查找，这将在循环中重复不必要的工作。前面提到的缓存会使这个过程更高效一些，但它仍然比一个间接调用指令更昂贵。

[keelii]

Point{10, 20} 表示初始化 Point，在内存中占用两个字节

The composite literal syntax Point{10, 20} denotes an initialized Point. Taking the address of a composite literal denotes a pointer to a freshly allocated and initialized Point. The former is two words in memory; the latter is a pointer to two words in memory.

—— 原文似乎没有说占用了两个字节。

原文说 32-bit memory layout，那 go 中一个 int 类型数据也占 32 个 bit 位，那按通俗的理解应该是一个 int 占用两个字节（8bit一个字节），那 Point{10, 20} 应该是占用四个字节才对？