【翻译】Go 数据结构:接口

原创
2013/09/10 20:00
阅读数 2.5K

Go 的接口:静态、在编译时检查、必要时可变动态——这对我而言是 Go 语言所有设计中最令我激动不已的设计点。如果我可以任选一个 Go 语言中的特性到其它语言中,接口是我的不二选择。

这篇文章是建立在我写的 “gc“ 编译器(6g、8g 和 5g)对接口的实现的基础之上的。Ian Lance Taylor 已经写了两篇(http://www.airs.com/blog/archives/277 注 1)有关 gccgo 中接口的实现。两个编译器的实现上,共同点要多于不同点:最大的不同在于本篇文章有配图说明。

在开始了解实现之前,让我们先大概明白它必须支持什么。

用法

Go 的接口允许您像使用像动态语言 Python 那样进行 duck typing,但编译器依旧能够捕捉到像需要接收一个对象的方法传入一个 int 类型,或传入不正确的参数数量这样明显的错误。想要使用接口,就得先定义一个接口类型(例如:ReadCloser):

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 方法的签名,并且 Go 不像 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 语句内使用 “comma ok” 赋值模型来判断该接口值是否可以被转换为 Stringer 类型,即具有 String 方法。如果可以,在语句块中的代码就会调用它的 String 方法并返回,否则就会在函数结束之前使用 switch 结构判断是否为某种可能的基本类型。这是 fmt 包的基本工作原理的展现(其实可以将 Stringer 也放到第 1 个 case 中:我单独拿出来判断是为了让大家对这个情况予以重视)。

作为一个简单的示例,让我们考虑一下一个具有可以打印 Binary 值的 String 方法和随意的 Get方法的 64 位整数型:

type Binary uint64

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

func (i Binary) Get() uint64 {
    return uint64(i)
}
Binary 类型的值可以被传入使用 String 方法来进行格式化的 ToString 方法,尽管程序永远都不会说 Binary 会实现 Stringer 接口。这是没有必要的,因为 runtime 可以知道 Binary 具有 String 方法并实现了 Stringer 接口,即使 Binary 的作者从未听说过 Stringer。

这些示例展示了所有的隐式转换都是发生在编译时的,显式的接口到接口的转换能够在运行时完成:更多有关接口值的文档和示例请参考 “Effective Go”。

接口值

具有方法概念的语言一般都会是以下两个阵营中的一种:为所有被静态调用的方法准备 tables(比如 C++ 和 Java),或在每次调用方法时进行寻找(比如 Smalltalk 和它的变种,包括 JavaScript 和 Python)以及增加合适的缓存以提升调用的效率。Go 位于这两个阵营的中间位置:在运行时计算方法 tables。我不知道 Go 是不是第一个使用这项技术的语言,但很显然这种做法不常见(我对一些早期的例子比较感兴趣;请在文章结尾给我一些评论)。

先来点热身运动,一个 Binary 类型的值只是由两个 32 位字构成的一个 64 位整数(和上篇文章一样,我们继续使用 32 位机器;这次内存使用会减少而非增长)


接口值被使用一个双字对来给予有关接口中存储的类型和指针指向的关联数据来表示。给一个 Stringer 类型的接口值赋值会将其两个字都改变。



(指针是灰色的是用于强调是它们在 Go 中会隐式地包含接口值,而非直接暴露)。

接口值中的第一个字指向我所说的接口的 table 或 itable(发音为 i-table;在 runtime 包源码中,C 的实现名为 Itab)。这个 itable 会以一些关于被使用的类型的元数据开始,变成一个函数指针的列表。要注意的是,itable 与相应的接口类型有关,而非动态类型。按照我们的例子,Stringer 的 itable 包含 Binary 类型用于实现 Stringer 接口的方法列表,即方法 String:Binary 的其它方法(Get)不会展现在 itable 中。

接口值的第二个字指向实际的数据,在这个例子中,第二个所指向的就是 b 的值的拷贝。赋值语句 var s Stringer = b 是让 a 或得 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 位值。一般情况下,接口并不知道这个字的具体含义,也不知道指向的数据有多大。相反地,接口的代码通过在 itable 中存放函数的指针来实现使用 32 位即可表示存储在其中的值。因此,本例中的函数指针的本质为 (*Binary).String 而非 Binary.String。

这个例子所展示的接口只有一个方法。拥有更多方法的接口会在 itable 底部有趣的列表中拥有更多的条目。

计算 Itable

现在我们知道 itables 是个什么东西了,但它是从何而来的呢?Go 的动态类型转换说明了 Go 的编译器或链接器并不总是能够预先计算出相应的 itables:它们拥有太多组合(接口类型、具体类型),而且极大多数是用不上的。相反,编译器会为像 Binary、int 或 func(map[int]string) 这样的具体类型生成类型描述结构。在其它元数据中,类型描述结构包含了相应类型所实现的方法的列表。类似地,编译器为像 Stringer 这样的接口类型生成另一个(不同的)类型描述结构;它也包含一个方法列表。在运行时计算接口的 itable 是通过查找具体类型的方法表中的接口类型的方法表里的每一个方法。运行时会在生成 itable 后进行缓存,因此相应的计算只需要运算一次。

在我们这个简单的例子中,Stringer 的方法表只有一个方法,而 Binary 的方法表拥有 2 个方法。一般来说,接口类型应该有 ni 个方法,具体类型应该有 nt 个方法。很显然,搜索找到从接口方法映射的具体方法需要时间 O(ni * nt),但我们可以做得更好。通过将两个方法表排序并同时对他们进行迭代可以使映射时间变成 O(ni + nt)。

内存优化

前文描述的实现还有两个互补的优化空间。

第一种方法:如果涉及的接口类型为空,那么说明它没有方法,因此除了保存原有类型的指针之外, itable 没有任何用处。在这种情况下,itable 可以被丢失并让值直接指向其类型:


无论某个接口是否拥有方法都是一个静态属性,在代码中使用 interface{} 或 interface{ methods },因此编译器知道哪个表示代表程序中的某个点。

第二种方法:如果接口值的关联值可以被放置在一个单独的机器字中,则不再需要说明间接引用或栈分配。如果我们定义 Binary32 是类似 Binary 但是使用 uint32 实现,则它可以被存储在一个在第二个字中存储实际值的接口值中:



实际值是被指向或内联均取决于其类型的大小。编辑器会安排类型方法表中列出的函数传递相应的字到 itable 中。如果接收者类型正好可以被放置在一个字中,则直接使用它;否则被间接引用。图中显示:在 Binary 版本的最上端,itable 中的方法是 (*Binary).String,然后在 Binary32 的例子中,itable 中的方法是 Binary32.String 而非 (*Binary32).String.

当然,这两种优化的方法均可以应用于空接口且持有的字大小(或更小)的值:


方法查找性能

Smalltalk 和许多动态系统都遵循每次方法被调用时都会执行查找方法的行为。为了提高速度,许多实现在调用时使用一个简单的条目进行缓存,且一般存储在指令流本身当中。在多线程程序中,这些缓存必须被非常小心地管理,因为多个线程可能在相同的时刻对它们进行调用。甚至在避免一次数据竞争后,这些缓存还可能在内存中成为发生争执的源头。

因为 Go 在查找动态方法时具有静态类型的提示,所以当值存储在接口中时,它可以将查找调用点从函数被调用的地方移动回来。例如,请考虑如下代码:

var any interface{}  // initialized elsewhere
s := any.(Stringer)  // dynamic conversion
for i := 0; i < 100; i++ {
   fmt.Println(s.String()) 
}
在 Go 中,itable 在第 2 行的赋值中就已经被计算(或在高速缓存中找到);对 s.String() 的调用是在第 4 行的执行,一系列内存的读取和单一的间接调用指令。

相反,在像 Smalltalk(或 JavaScript 或 Python 或其它)动态语言中实现这个程序将会在第 4 行进行方法查找,也就是在一个循环中不断重复不必要的工作。之前所说的缓存可能使这个代价变得低廉一些,但它仍旧比一个单一的间接调用指令更昂贵。

当然,这只是一篇博客文章,我没有任何数字来作为讨论的后盾,但可以肯定的是没有内存争执将会是大型并行程序中的一个大胜利,即能够将方法查找范围跳出循环的限制。另外,我所讨论的是一般的架构,而非具体的实施:后者可能还是有一些特定的因素可以被优化。

更多信息

接口的运行时支持可以在 $GOROOT/src/pkg/runtime/iface.c 中找到。其实还有很多有关接口的东西没有讲(我们甚至都没有看到一个指针接收者的例子)以及类型描述(接口运行时的有力反射),但是这些内容不得不等到以后的博文中讲解。

代码

支持的代码(x.go):

package main

import (
 "fmt"
 "strconv"
)

type Stringer interface {
 String() string
}

type Binary uint64

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

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

func main() {
 b := Binary(200)
 s := Stringer(b)
 fmt.Println(s.String())
}
8g -S x.go 的部分输出:
0045 (x.go:25) LEAL    s+-24(SP),BX
0046 (x.go:25) MOVL    4(BX),BP
0047 (x.go:25) MOVL    BP,(SP)
0048 (x.go:25) MOVL    (BX),BX
0049 (x.go:25) MOVL    20(BX),BX
0050 (x.go:25) CALL    ,BX

LEAL 加载 s 的地址到寄存器 BX 中(符号 n(SP) 描述了在 SP+n 在内存中的字。0(SP) 可以被简写为 (SP))。接下来的两个 MOVL 指令从接口第二个字中获取值,并第一个函数的调用参数存储。最后两个 MOVL 指令获取 itable 以及 itable 中的函数指针,然后准备调用该函数。

备注:
1. 其中一篇已显示 404。

原文地址:http://research.swtch.com/interfaces

展开阅读全文
加载中
点击加入讨论🔥(5) 发布并加入讨论🔥
打赏
5 评论
37 收藏
1
分享
返回顶部
顶部