Dig101-Go之读懂interface的底层设计

文章目录

  1. 1. 0x01 底层结构一样么
    1. 1.1. eface
    2. 1.2. iface
  2. 2. 0x02 类型如何相互转换
    1. 2.1. convXXX的命名
    2. 2.2. 起初的convT2{I,E} 和 convI2I
    3. 2.3. 针对类型优化后的convXXX
  3. 3. 0x03 类型断言如何实现
    1. 3.1. 查表是否匹配
    2. 3.2. 尝试插入更新
    3. 3.3. 动态判定效率优化

Dig101: dig more, simplified more and know more

今天我们聊聊万物皆可为的接口(interface)的底层设计。

interface被定义为一组方法的签名。

有了它,我们可以订立方法契约,去抽象和约束实现。

而Go的基础类型,可以认为是没有实现任何方法的空interface,也就是万物皆为的interface。

(Go语言没有泛型,接口可以作为一种替代实现)

接口也被寄予厚望,主力开发Russ Cox曾说过:

从语言设计的角度来看,Go的接口是静态的,在编译时检查过的,在需要时是动态的。如果我可以将Go的一个特性导出到其他语言中,那就是接口。
Go Data Structures: Interfaces

那到底interface是怎么设计的底层结构呢?

又怎么支持的duck typing

在类型断言时又发生了什么?

带着这些问题,我们往下看

0x01 底层结构一样么

我们知道定义接口有这两种方式,那他们底层结构是一样的么?

1
2
3
4
5
6
7
// 方式1
var a interface{}
// 方式2
type Stringer interface {
String() string
}
var b Stringer

答案是【不一样】

我们用gdb打印下对应类型(gdb相关见Tips-如何优雅的使用GDB调试Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 空接口类型
>>> ptype a
type = struct runtime.eface {
runtime._type *_type;
void *data;
}
// 有函数定义的接口类型
>>> ptype b
type = struct runtime.iface {
runtime.itab *tab;
void *data;
}
// itable相关类型
>>> ptype b.tab
type = struct runtime.itab {
// 接口相关信息
runtime.interfacetype *inter;
// 构造类型
runtime._type *_type;
uint32 hash;
[4]uint8 _;
// 构造类型的函数列表
[1]uintptr fun;
} *
>>> ptype b.tab.inter
type = struct runtime.interfacetype {
// 接口的类型
runtime._type typ;
runtime.name pkgpath;
// 接口定义的函数列表
[]runtime.imethod mhdr;
} *

以此可见Go内部定义了两种interface(但都是两个机器字)

eface

空接口,指没有定义方法的接口

内部存储了构造类型(concrete typetypedata

eface

iface

有方法的接口

有了相比efacetype更丰富的itab字段,其中记录了构造类型及所实现的interface类型的类型和方法

iface

0x02 类型如何相互转换

如下代码,当我们做接口赋值时,Go又会怎样填充底层结构呢?

1
2
3
4
5
6
7
8
9
10
11
type Binary uint64
func (i Binary) String() string {
return strconv.Itoa(int(i))
}

func conversion() {
var b Stringer
var i Binary = 1
b = i // <= 这里发生了什么
println(b.String())
}

gdb 进到 b = i 这一步,会发现他调用了runtime/iface.go:convT64方法实现iface的赋值

查阅源码,会发现很多convXXX函数, 他们是干什么的?

convXXX的命名

convFrom2To 指代 To=From 的转换

From和To的类型有三种:
(参见cmd/compile/internal/types/type.go:Tie

  • E (eface)
  • I (iface)
  • T (Type)

这一堆函数看的人眼晕,但参照提交specialize convT2x, don’t alloc for zero vals深入分析,就会清晰许多

起初的convT2{I,E} 和 convI2I

最初只有 convT2{I,E} 和 convI2I

主要实现分配内存(newobject),然后拷贝赋值(typedmemmove

convI2I 还会有getitab, 具体是什么我们后边类型断言时说

然后也在调用他们前(walkexpr)做了优化

  • 减少值拷贝

ToType为类指针(pointer-shaped)或者一个机器字内(int)的话,可以直接存入interface的data字段(主要优化在这里)

pointer-shaped类型: ptr, chan, map, func, unsafe.Pointer

再辅以type的存储,就只是两个字(two-word)的拷贝

  • 减少内存分配

零值,bool/byte 可以不用分配内存,而用已存在值(zerobase,staticbytes

只读的全局变量(readonly global)直接可以用

1kb以内,不escape到堆上,非interface的变量可以使用栈上分配的临时变量(stack temporary initialized)

这类value最后以取地址形式转化为interface: {type/itab, &value}.

  • interface转空接口(eface)

可以丢弃除type以外的itab

1
2
3
4
5
tmp = i.itab
if tmp != nil {
tmp = tmp.type
}
e = iface{tmp, i.data}

针对类型优化后的convXXX

但这里会有一些可以优化的点,如:

  • 分配内存是否可以需要清零?

类指针的类型需要清零,不然内存可能有脏数据

但无指针类型(pointer-free)如拷贝时直接可以覆盖对应内存则不需要

int其拷贝在一个机器字内完成,不需要分配时清零
(32位系统上不调用convT64,就可以保证访问内存是安全的原子操作)

  • 是否可以简化值拷贝?

int,string,slice这些Type分配的x拷贝val时,可以简化为 *(*Type)(x) = val

  • 拷贝内存是否可以不增加gc调用(写屏障)?

按ToType类型是否含指针区分
类指针类型(pointer-shaped): convT2{E,I} 需要拷贝时gc调用(typedmemmove

无指针类型(pointer-free): convT2{E,I}noptr 不需要拷贝时gc调用(memmove

这样一看就明白这些函数的用意了,还是为了针对性的提高转化效率

最后结合其调用处convXXX列表如下:

1
2
3
4
// cmd/compile/internal/gc/walk.go:walkexpr
case OCONVIFACE:
...
fnname, needsaddr := convFuncName(fromType, toType)
函数(fnname)From类型值取地址存(needsaddr)
convI2Iiface
convT{16,32,64}底层为整型数据(不含指针,对齐不大于机器字)
convTstringstring
convTsliceslice
convT2EType
convT2Enoptr无指针Type
convT2IType
convT2Inoptr无指针Type

不会存在 convE2E 和 convE2I
needsaddr: 类型不含指针,大小大于64位字或未知大小时,使用值的地址来存

0x03 类型断言如何实现

interface支持类型断言,来动态判断其构造类型,

判定成功可返回对应构造类型,便于调用其方法

可构造类型实现interface不需要显示声明,

那如下代码是怎么确定interface b(构造类型是Binary)实现Stringer呢?

1
2
3
4
5
6
7
8
9
10
11
type Binary uint64

func (i Binary) String() string {
return fmt.Sprint(i)
}

func typeAssert() {
var b interface{} = Binary(1)
v, ok := b.(Stringer)
println(v, ok)
}

调试后会发现,其调用了assertE2I2

这里函数命名有两类,如下

assertE2I: v := eface1.(iface1)

assertE2I2: v,ok := eface1.(iface1)

这里有一点,类型断言非 v,ok 方式的,断言失败会panic)

原来其内部进行了itab表(itabTable)查询interface和构造类型的映射表,如果匹配则说明实现

下边代码分析如下

首先初始512个entry的表

1
2
3
4
5
6
7
8
const itabInitSize = 512
type itabTableType struct {
// 上限
size uintptr
// 当前用量
count uintptr
entries [itabInitSize]*itab
}

查表是否匹配

在类型断言中调用 getitab(inter, typ, canfail) 查表

  • 先不加锁atomic读取itabTable,找到返回
  • 未找到加锁再查一遍,找到返回
  • 还没有就创建一个itab添加到表中,添加完后解锁
  • 期间如果判定不匹配则按是否可以panic(canfail)返回

其中查表用到 itabTable.find(inter, typ)

插入用到 itabAdd(m)

尝试插入更新

  • 插入前需先用m.inter/m._type pair 初始化 m.fun 数组,不匹配则m.fun[0]==0

(m.fun 类型 [1]uintptr,实际指向是大小为接口定义方法数的方法数组。详见 func (m *itab) init())

  • 用量count超过上限的75%触发扩容,大小为2倍以上(要向上内存对齐),扩容后更新itabTable是原子操作

  • 以itab m的interface类型和构造类型的hash计算对应itabTable的起始偏移,然后插入到其后第一个不为空的entry。如果已存在则直接返回

这里用到了开放地址探测法,公式是:

h(i) = h0 + i*(i+1)/2 mod 2^k

具体插入用到 itabTable.add(m)

这里和其实map插入的逻辑很相似

动态判定效率优化

不过,这里有一个问题?

假定,interface定义了ni个方法,构造类型实现nt个方法,

常规匹配构造类型是否实现全部ni个方法需要两层遍历,复杂度为O(ni*nt)

这样在初始化itab.fun或类型断言匹配是效率会比较低。

Go设计时也考虑了这个问题,把复杂度降低为O(ni+nt)

这也是使用hashtable的原因之一:

  • 首先interface的函数定义列表itab.inter.mhdr和构造类型的函数列表itab.fun都是按函数名排好序的

  • 这样第一次itab初始化时,判定构造类型是否实现函数列表可以O(ni+nt)内遍历完成

  • 然后用开放地址探测法更新到itabtable中,查询时也可以用同样的方式定位到此itab是否存在。

两个(有序)列表的遍历匹配代码精简如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// runtime/iface.go:init()
j:=0
imethods:
// 遍历interface定义函数列表
for k := 0; k < ni; k++ {
// 遍历构造类型函数列表
for ; j < nt; j++ {
// 如果两者类型(type),包路径(pkgpath),函数名(name)匹配
if xxx {
// 将方法记录到 fun0 (最终全匹配则赋值给 m.fun)
continue imethods
}
}
// 未全匹配
m.fun[0] = 0
}
m.fun[0] = uintptr(fun0)

总结一下interface的底层设计:

  • interface 分为空接口(eface)和接口(iface)两类,但都是两机器字(two-word)存储结构
  • interface 转换中针对不同类型做了优化,主要集中于提升内存分配和值拷贝效率
  • interface 类型断言时动态判定,利用有序列表遍历+全局哈希表表缓存优化判定效率

See More: 官方解释 InterfaceSlice 为什么不能直接转化​


最后留个问题:

下边这段转换代码内部没有调convT64,为什么?

1
2
var b Stringer = Binary(1)
_ = b.String()

这个问题下一篇文章再来给出解答。

本文代码见 NewbMiao/Dig101-Go

如有疑问,请文末留言交流或邮件:newbvirgil@gmail.com 本文链接 : http://blog.newbmiao.com/2020/02/26/dig101-golang-interface.html