Go语言之闭包篇

在有GC和闭包实现的语言中,我最熟悉的是Lua语言。所以在使用Go语言时,碰到不熟悉的细节,总是会以Lua的机制来对比。

然而由于动态语言和静态语言的区别(静态语言总是有更多优化的机制), 以至于很多时候会得出错误的结论。

比如下面代码:

package main
import "os"
func exist(list []int, f func(n int)bool) bool {
    for _, n := range list {
        if f(n) == true {
            return true
        }
    }
    return false
}
func main() {
    count := len(os.Args)
    a := make([]int, 0)
    for i := 0; i < count; i++ {
        a = append(a, i)
    }
    exist(a, func(n int) bool {
        return n == (count - 1)
    })
}

这段代码定义了一个闭包,然后作为参数传给exist函数。

按照Lua的经验,定义闭包肯定是需要malloc内存。然而Go语言反手就教我做人。

使用go run -gcflags="-m -l" a.go可以发现,这个闭包并没有被分配在堆上。

再使用go tool compile -N -l -S a.go来看一下与闭包相关的Plan9汇编代码。

"".exist STEXT size=234 args=0x28 locals=0x58
    ................
    0x0085 00133 (a.go:5)   MOVQ    "".f+120(SP), DX
    0x008a 00138 (a.go:5)   MOVQ    AX, (SP)
    0x008e 00142 (a.go:5)   MOVQ    (DX), AX
    0x0091 00145 (a.go:5)   PCDATA  $1, $1
    0x0091 00145 (a.go:5)   CALL    AX
    0x0093 00147 (a.go:5)   MOVBLZX 8(SP), AX
    0x0098 00152 (a.go:5)   MOVB    AL, ""..autotmp_5+23(SP)
    0x009c 00156 (a.go:5)   NOP
    0x00a0 00160 (a.go:5)   TESTB   AL, AL
    0x00a2 00162 (a.go:5)   JNE     166
    0x00a4 00164 (a.go:5)   JMP     184
    0x00a6 00166 (a.go:6)   MOVB    $1, "".~r2+128(SP)
    0x00ae 00174 (a.go:6)   MOVQ    80(SP), BP
    0x00b3 00179 (a.go:6)   ADDQ    $88, SP
    0x00b7 00183 (a.go:6)   RET
    0x00b8 00184 (a.go:5)   PCDATA  $1, $-1
    0x00b8 00184 (a.go:5)   JMP     186
    0x00ba 00186 (a.go:5)   JMP     188

"".main STEXT size=372 args=0x0 locals=0x90
    ................
    0x00ff 00255 (a.go:17)  XORPS   X0, X0
    0x0102 00258 (a.go:17)  MOVUPS  X0, ""..autotmp_4+88(SP)
    0x0107 00263 (a.go:17)  LEAQ    ""..autotmp_4+88(SP), AX
    0x010c 00268 (a.go:17)  MOVQ    AX, ""..autotmp_6+104(SP)
    0x0111 00273 (a.go:17)  TESTB   AL, (AX)
    0x0113 00275 (a.go:17)  LEAQ    "".main.func1(SB), CX
    0x011a 00282 (a.go:17)  MOVQ    CX, ""..autotmp_4+88(SP)
    0x011f 00287 (a.go:17)  TESTB   AL, (AX)
    0x0121 00289 (a.go:17)  MOVQ    "".count+72(SP), AX
    0x0126 00294 (a.go:17)  MOVQ    AX, ""..autotmp_4+96(SP)
    0x012b 00299 (a.go:17)  MOVQ    "".a+112(SP), AX
    0x0130 00304 (a.go:17)  MOVQ    "".a+120(SP), CX
    0x0135 00309 (a.go:17)  MOVQ    "".a+128(SP), DX
    0x013d 00317 (a.go:17)  MOVQ    AX, (SP)
    0x0141 00321 (a.go:17)  MOVQ    CX, 8(SP)
    0x0146 00326 (a.go:17)  MOVQ    DX, 16(SP)
    0x014b 00331 (a.go:17)  MOVQ    ""..autotmp_6+104(SP), AX
    0x0150 00336 (a.go:17)  MOVQ    AX, 24(SP)
    0x0155 00341 (a.go:17)  CALL    "".exist(SB)

"".main.func1 STEXT nosplit size=54 args=0x10 locals=0x10
    0x0000 00000 (a.go:17)  TEXT    "".main.func1(SB), NOSPLIT|NEEDCTXT|ABIInternal, $16-16
    0x0000 00000 (a.go:17)  SUBQ    $16, SP
    0x0004 00004 (a.go:17)  MOVQ    BP, 8(SP)
    0x0009 00009 (a.go:17)  LEAQ    8(SP), BP
    0x000e 00014 (a.go:17)  FUNCDATA        $0, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
    0x000e 00014 (a.go:17)  FUNCDATA        $1, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
    0x000e 00014 (a.go:17)  MOVQ    8(DX), AX
    0x0012 00018 (a.go:17)  MOVQ    AX, "".count(SP)
    0x0016 00022 (a.go:17)  MOVB    $0, "".~r1+32(SP)
    0x001b 00027 (a.go:18)  MOVQ    "".count(SP), AX
    0x001f 00031 (a.go:18)  DECQ    AX
    0x0022 00034 (a.go:18)  CMPQ    "".n+24(SP), AX
    0x0027 00039 (a.go:18)  SETEQ   "".~r1+32(SP)
    0x002c 00044 (a.go:18)  MOVQ    8(SP), BP
    0x0031 00049 (a.go:18)  ADDQ    $16, SP
    0x0035 00053 (a.go:18)  RET

上面的代码并不算太复杂,我们大致可以翻译出他的等价Go语言(翻译出来的代码是可以被编译运行的)。

package main
import "os"
type Closure1 struct {
    F func(int) bool
    n int
}

var DX *Closure1

func func1(n int) bool {
    x := DX.n - 1
    return x == n
}
func exist(list []int, f *Closure1) bool {
    for _, n := range list {
        DX = f
        if f.F(n) == true {
            return true
        }
    }
    return false
}
func main() {
    count := len(os.Args)
    a := make([]int, 0)
    for i := 0; i < count; i++ {
        a = append(a, i)
    }
    c := &Closure1{
        F: func1,
        n: count,
    }
    exist(a, c)
}

从上面的Go代码可以很清楚的看到,其实一个闭包到底分配不分配内存,关键就在于Closure1在栈上还是在堆上。

当Closure1结构暴露出来之后,一切都是那么的显然。

即然闭包是一个struct对象,那么Go当然可以和一般的自定义struct一样进行逃逸分析,而根据逃逸规则,这里的c对象显然不需要逃逸。

一切都很完美,只是还有一个问题没有解决。

exist在调用f函数时,是如何区分调用的是闭包还是非闭包,比如下面代码:

package main
import "os"
func exist(list []int, f func(n int)bool) bool {
        for _, n := range list {
                if f(n) == true {
                        return true
                }
        }
        return false
}
func foo(n int) bool {
        return n == 3
}
func main() {
        count := len(os.Args)
        a := make([]int, 0)
        for i := 0; i < count; i++ {
                a = append(a, i)
        }
        exist(a, foo)
}

再来看一下对应的汇编代码:

"".exist STEXT size=234 args=0x28 locals=0x58
    .......
    0x0085 00133 (a.go:5)   MOVQ    "".f+120(SP), DX
    0x008a 00138 (a.go:5)   MOVQ    AX, (SP)
    0x008e 00142 (a.go:5)   MOVQ    (DX), AX
    0x0091 00145 (a.go:5)   PCDATA  $1, $1
    0x0091 00145 (a.go:5)   CALL    AX
    0x0093 00147 (a.go:5)   MOVBLZX 8(SP), AX
    0x0098 00152 (a.go:5)   MOVB    AL, ""..autotmp_5+23(SP)
    0x009c 00156 (a.go:5)   NOP
    0x00a0 00160 (a.go:5)   TESTB   AL, AL
    0x00a2 00162 (a.go:5)   JNE     166
    0x00a4 00164 (a.go:5)   JMP     184
    .......

"".main STEXT size=300 args=0x0 locals=0x78
    0x00ea 00234 (a.go:20)  MOVQ    "".a+88(SP), AX
    0x00ef 00239 (a.go:20)  MOVQ    "".a+96(SP), CX
    0x00f4 00244 (a.go:20)  MOVQ    "".a+104(SP), DX
    0x00f9 00249 (a.go:20)  MOVQ    AX, (SP)
    0x00fd 00253 (a.go:20)  MOVQ    CX, 8(SP)
    0x0102 00258 (a.go:20)  MOVQ    DX, 16(SP)
    0x0107 00263 (a.go:20)  LEAQ    "".foo·f(SB), AX
    0x010e 00270 (a.go:20)  MOVQ    AX, 24(SP)
    0x0113 00275 (a.go:20)  CALL    "".exist(SB)

通过对比可以发现,其实exist函数的代码并没有任何变化,有变化的代码是a.go第20行。

再来将汇编翻译成Go语言:

package main
import "os"
type Closure1 struct {
    F func(int) bool
}
var DX *Closure1
func foo(n int) bool {
    return n == 3
}
func exist(list []int, f *Closure1) bool {
    for _, n := range list {
        DX = f
        if f.F(n) == true {
            return true
        }
    }
    return false
}
func main() {
    count := len(os.Args)
    a := make([]int, 0)
    for i := 0; i < count; i++ {
        a = append(a, i)
    }
    c := &Closure1{
        F: foo,
    }
    exist(a, c)
}

通过对比两次翻译后的Go语言,可以发现一件很有意思的事。

Go语言其实把所有函数都抽象成闭包,这一点倒是与Lua有颇多相似之处。

只是没有任何值捕获的闭包,在逃逸分析时可以做更多的优化。

Go语言之内存篇

TL;DR:本文不讨论三色垃圾回收,不讨论读写屏障,不讨论内存分配策略。仅仅从内存视角抽象出一个简单的屏障。以便可以在写Go语言时,知道语言的边界,可以把之前C/C++的经验复用。

上一篇文章中,我提到了一个疑问,就是两个Slice分别引用一个Array的不同部分,GC是如何保证在Mark时,可以Mark到那个被引用的Array。

在这里,我陷入了一个很大的误区。

根据Lua和C#的经验,GC在Mark一个对象时,实际上是Mark一块内存,当这个内存被Mark之后,他就不会被释放。从malloc这个函数也很容易知道,释放一个内存块同样需要内存块的首地址。

这也是为什么很多带GC的语言都不允许做指针运算的原因。

我当时看过的Go语言书籍都说,Go语言虽然有指针,但是不允许做指针运算。

经验主义让我认为,GC系统的主流设计思想都差不多,无非就是算法的不同。

然后,我就有了一种Go语言的指针和C#的引用其实是一个东西的错觉

然而,这种错觉无法解释上一篇文章中有关Slice的GC问题。

事实上,由于潜意识的限制,我甚至忽略了一种更为普遍的情况。

来看一段代码(只是为了演示问题,因为这么做毫无道理):

func foo() *int {
    a := make([]int, 3)
    return &a[1]
}

是的,我甚至弄错了,Go语言的指针是真的指针这一事实。

Go不能做指针运算,指的是我们不能将一个指针加上或减去任意一个偏移量。

Go的指针可以是指向任意一块合法内存的地址。

以上面的代码为例。

当一个函数bar调用foo之后并持有这个int指针,即使Slice变量a被销毁,a所指向的Array也不会被回收。

那么我之前对Go的GC理解必然是错的。

几经辗转,终于在《Go语言设计与实现》中的7.1节“内存分配器的实现原理”找到线索。

Go的内存分配器在1.11版本前后实现是不一样的,《Go语言设计与实现》花了大量笔墨来介绍1.11版本之后的实现细节。

两个版本对上层的抽象是一致的,但是1.11之后的版本稍嫌复杂了,1.11版之前的“线性分配器”版本,更能帮助我建立简单直观的印象。

于是,我找到另一篇文章,这篇文章详细介绍了"线性分配器"的设计思路。

这篇文章中,我们可以得到几个很重要的提示:

  • 内存分配的最小单位是Page
  • 分配出去的内存块是一个称之为mspan的结构,每一个mpan结构一定持整数个Page
  • 任意一个Page都会有与之对应mspan结构的指针,当一个mspan持有多个Page时,多个Page会有相同的mspan结构。

上面提示,已经足够解释前面所有的问题了。

由于每个Page都是同样大小,可以根据内存地址以O(1)的时间复杂度得到Page的索引。

再根据Page的索引,以O(1)的时间复杂度得到mspan的指针。

一个mspan内存块中,所有对象都占用同样大小的内存,使用spanClass来表示对象的大小(spanClass==0例外)。

这样,再根据从mspan得到的对象大小信息,算出指针指向对象的首地址在何处。

当我搞明白这种思路之后,简直都惊呆了。

Go语言通过将内存分配器和GC系统融合之后,提供了几乎90%的指针功能,此时我有点明白“云时代的C语言”这种说法了。


上一篇文章中我炫技似的留下了一段关于接口相关的代码,如下:

package main
import "fmt"
type FooBar interface {
    foo()
    bar()
}
type st1 struct {
    FooBar
    n int
}
type st2 struct {
    FooBar
    m int
}

func (s *st1) foo() {
    fmt.Println("st1.foo", s.n)
}
func (s *st1) bar() {
    fmt.Println("st1.bar", s.n)
}
func (s *st2) foo() {
    fmt.Println("st2.foo", s.m)
}
func test(fb FooBar) {
    fb.foo()
    fb.bar()
}
func main() {
    v1 := &st1{n: 1}
    v3 := &st2{
        m:      3,
        FooBar: v1,
    }
    test(v1)
    test(v3)
}

当时,由于Plan9汇编的阻碍,我对于底层的实现和机制没太明白,更没有明白这种用法的边界是什么。

最近终于有一个自洽的推测了。

是的,因为我目前为止依然看不太懂Plan9汇编,以下全是推测,只有部分佐证。

我先尝试使用C语言写出上面代码的等价代码。

//a.c
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef void (*foo_t)(void *);
typedef void (*bar_t)(void *);
struct FooBarFn {
    foo_t foo;
    bar_t bar;
};
struct FooBar {
    void *data;
    struct FooBarFn *itab;
};
struct st1 {
    struct FooBar _foobar;
    int n;
};
struct st2 {
    struct FooBar _foobar;
    int m;
};
void st1_foo(struct st1 *s) {
    printf("st1.foo:%d\n", s->n);
}
void st1_bar(struct st1 *s) {
    printf("st1.bar:%d\n", s->n);
}
void st2_foo(struct st2 *s) {
    printf("st2.foo:%d\n", s->m);
}
void st2_bar(struct st2 *s) {
    s->_foobar.itab->bar(s->_foobar.data);
}

struct FooBar st1_interface(struct st1 *s) {
    struct FooBar i;
    i.data = (void *)s;
    i.itab = malloc(sizeof(struct FooBarFn));
    i.itab->foo = (foo_t)st1_foo;
    i.itab->bar = (bar_t)st1_bar;
    return i;
}

struct FooBar st2_interface(struct st2 *s) {
    struct FooBar i;
    i.data = (void *)s;
    i.itab = malloc(sizeof(struct FooBarFn));
    i.itab->foo = (foo_t)st2_foo;
    i.itab->bar = (bar_t)st2_bar;
    return i;
}

void test(struct FooBar bar) {
    bar.itab->foo(bar.data);
    bar.itab->bar(bar.data);
}
int main() {
    struct FooBar i1, i2;
    struct st1 *v1 = malloc(sizeof(*v1));
    struct st2 *v3 = malloc(sizeof(*v3));
    memset(v1, 0, sizeof(*v1));
    memset(v3, 0, sizeof(*v3));
    v1->n = 1;
    v3->m = 3;
    v3->_foobar = st1_interface(v1);
    i1 = st1_interface(v1);
    i2 = st2_interface(v3);
        test(i1);
    test(i2);
    return 0;
}
//gcc -o a a.c

上面这段代码是可以被编译通过的,而且和各种Go语言书中披露的interface实现,非常接近,我几乎可以认定Go语言就是这么实现的。

这段代码主要想解释“结构/接口内嵌”,编译器到底做了什么,他的规则是什么,以便我可以更好的利用这种规则。

Go的整个嵌入结构其实非常酷炫,但是也难以理解。

但是如果按上面的C代码去分析,其实整个规则非常简单,只是两个语法糖而已。

先来单纯看struct的内存布局。

在C语言时代我们所有人都写过下面这种代码:

struct A {
    int f1;
    int f2;
};
struct B {
    struct A a;
    int f3;
};
void foo() {
    struct B b;
    b.a.f1 = 3;
    b.a.f2 = 4;
    b.f3 = 5;
}

对应的Go语言如下:

type A struct {
    f1 int
    f2 int
}
type B struct {
    A
    f3 int
}
type D struct {
    A a
    f3 int
}
func foo() {
    b := new(B)
    b.f1 = 3
    b.f2 = 4
    b.f3 = 5
    d := new(D)
    d.a.f1 = 3
    d.a.f2 = 4
    d.f3 = 5
}

可以看到,内嵌结构体的字段访问,其实就是个语法糖。

Go编译器在编译阶段, 会将结构B转换为结构D,再进行编译(注:这里是指源码级,由于是值嵌入,在编译时,可以直接算出地址偏移量,在汇编层面优化不优化都没有任何区别,如果是指针嵌入效果又不一样)。

下面让我们来证明一下这个结论:

package main
import (
    "fmt"
    "unsafe"
)
type A struct {
    f1 int8
    f2 int8
}
type B struct {
    A
    f3 int8
}
func (*A) foo() {}
func main() {
    var a A
    var b B
    fmt.Println(unsafe.Sizeof(a))
    fmt.Println(unsafe.Sizeof(b))
}

上面的代码可以证明,关于struct结构布局并没有什么魔法,B结构的大小就是A结构的大小+int8的大小。

同理,type B struct {*A}type B struct {a *A}也并没有任何区别。

再来看函数,当一个B嵌入A时,他就有了A的所有函数, 如foo函数。

其实,这也是一个很甜的语法糖,甜到都像是魔法了。

当B嵌入了A之后,他会帮B生成一套A的所有函数,这样B就有了自己的foo函数。

而B.foo函数的函数体,其实只干一件事,就是再调用A.foo函数。

之所以会这样,是因为调用A.foo时,需要传入A对象的内存地址。

这一切都是优化前的思路。

如果你直接去反汇编,可能会得到不同的结论。

为了少生成一条call指令,编译器通常会在调用B.foo时,直接生成B.A.foo代码。

但是我们可以通过println来找到蛛丝马迹。

func main() {
    fA := (*A).foo
    fB := (*B).foo
    println(fA)
    println(fB)
}

至此,Go语言的所有内存布局相关的细节,我们基本上都和C语言对上了。

ps. 有人说研究这些没有用。但是不搞清语言的边界,怎么才能发挥出一个语言的最大威力呢 ^_^!

初识Go语言

其实严格来讲也不算初识,大概在15年时,就学过一次Go语言的语法。

由于当时Go语言GC的名声不太好,也就没太认真研究,只是大致把语法学习了一下。

对Go的印象除了语法有点怪,也就没有其他特别的印象了。

这一次,我仔细学习了一下Go语言(到目前为止已经学习了4周了)。

有了一些不太一样的感受,还发现了一些令人耳目一新的点。


首先就是GC。

我仔细回忆了一下,Go竟然是我知道的第一门编译型带GC的语言(IL2CPP不算),这里的编译不是将代码编译成字节码然后解释的那种,是真正编译成能在CPU上执行的native code。

编译成native代码运行肯定会更快,但同时也会有一些潜在的问题。

Go编译器在编译代码时,会在代码的各处插入GC相关的代码。

在进行源码级调试时,一般不会有太大的问题,调试器会智能跳过编译器插入的代码。

但是,当想看某一行代码在汇编级是怎么执行时(这是从C语言时代就养成的习惯,一般写一行C语法,基本上都能预测出生成的非优化汇编代码), 我发现代码中到处充斥着Go插入的代码,让代码的可读性差很多。

而一些使用虚拟机的语言如Lua,Java等。OpCode和逻辑代码是一一对应的,GC相关的细节被封装在虚拟机内部。

这种分层会让底层的OpCode非常清晰,对底层调优很有帮助。

当然,这也许正是Go想要的也说不定,可能他不希望你做这么底层的优化:D


然后就是汇编。

是的,当我知道Go反汇编出来的是Plan9汇编时,我震惊了。

这就意味着,即使我能突破编译器插入代码这个障碍,我依然看不到最终执行的X86指令,我依然不知道代码最终在CPU上是如何执行的。

举个最简单的例子,所有人都说goroutine的切换开销比线程小,其实我一直对这个观点保持怀疑态度。

按照我X86汇编的经验,在编译器的优化阶段,总是尽可能的将栈上变量,优化到寄存器上去,甚至前几个参数都是通过寄存器来传递的。

来随便看段简单的C代码和相应的汇编。

int foo(int a, int b)  {
    int e = a / b;
    return a * b * e;
}
foo:
.LFB0:
    .cfi_startproc
    mov eax, edi
    cdq
    idiv    esi
    imul    edi, esi
    imul    eax, edi
    ret
    .cfi_endproc

可以看到foo函数中的e变量并没有在栈上,而是直接分配了一个寄存器。

这就导致一个问题,当一个线程被抢占时,他当前的整个callstack的上下文中,被使用的寄存器是不确定的。

因此在linux中的,Thread被换出时,需要保存全套的寄存器(EAX,EBX….)。

但是所有的Go文章都说goroutine切换代价很小,他需要保存更少的寄存器,有些人甚至说他只需要保存3个寄存器。

我对这个说法最开始是相信的,如果goroutine的切换点总是在函数调用时进行,他完全可以做到把ABI的"callee saved registers"的个数减少到3个。

但是,后来我看到了goroutine是可以在任意时机被抢占的。

这我就不太能理解了,不管是不是Plan9汇编,最终只要跑在x86指令集的机器上,他们的优化思路都应该是尽可能多的使用寄存器,而不是栈。

那么,只要我整个函数使用的寄存器超过3个,想要在for {}语句中抢占一个goroutine,就势必要保存整套寄存器,那所谓的轻量切换也就不存在了,最多就是栈的空间消耗会少一些。

当我想进一步寻找答案时,Plan9成了阻碍。

我很难确定,是不是在Plan9的ABI中,每个函数只有三个寄存器可用。

在从Plan9生成X86汇编时,会把栈上的变量尽可能多地转移到x86寄存器上。

除非我将最终的二进制文件反汇编成x86, 显然我还没有对go熟悉到这种程度,这个问题就只能暂时搁置了。

而且我不得不说,相关的资料真的很少,不管是中文的还是英文的。


Go的slice是一个很有意思的数据结构。

多个slice,有时会共享内存,有时不会。会不会共享取决于当时的代码执行情况,但结果可以预测。

我理解下来,这基本上是对性能妥协的结果。

总的来讲我认为这个妥协是正向的,因为共享不共享是有明确规则的,只要留心一点,一般问题不大。

我比较好奇的是,slice和GC交互的部分。

先看一小段代码:

type slice struct {
    array unsafe.Pointer
    len   int
    cap   int
}
func foo() []int {
    a := make([]int, 5)
    b := a[3:4]
    return b
}

在这段代码中,我把slice的数据结构和示例代码放在一起了。

可以从go的任意一本参考书上可知,上面代码约等于下面这段C代码:

struct slice {
    int *array;
    int len;
    int cap;
}

func foo() slice {
    struct slice a, b;
    a.array = malloc(5 * sizeof(int));
    a.cap = 5;
    a.len = 5;
    b.array = &a.array[3];
    b.cap = a.cap - 3;
    b.len = 4 - 3;
    return b;
}

所有的资料都提到,Go语言的GC是并发三色垃圾回收。

现在问题来了,由于b.array做了指针计算(所有带垃圾回收功能的语言,都会避免支持指针运算,因为这会让GC变得很难)。

当GC模块去Mark变量b时,它该如何找到这块内存的首地址呢,这一点我一直没有想通。

相关的文档没有找到,而且似乎大家也不是很关心这个事情 ^_^!


上面都是一些实现细节,下面谈谈语言层面上的设计。

Go语言的接口机制和CSP同步机制,着实让人耳目一新。

Go语言作为一门静态语言,竟然实现了DuckType, 这一点我挺意外的。

更意外的是,他的接口机制还有一种很奇特的机制。

下面展示一段代码看看效果:

package main

import "fmt"

type FooBar interface {
    foo()
    bar()
}

type st1 struct {
    FooBar
    n int
}

type st2 struct {
    FooBar
    m int
}

func (s *st1) foo() {
    fmt.Println("st1.foo", s.n)
}

func (s *st1) bar() {
    fmt.Println("st1.bar", s.n)
}

func (s *st2) foo() {
    fmt.Println("st2.foo", s.m)
}

func test(fb FooBar) {
    fb.foo()
    fb.bar()
}

func main() {
    v1 := &st1{n: 1}
    v3 := &st2{
        m:      3,
        FooBar: v1,
    }
    test(v1)
    test(v3)
}
/*输出结果:
st1.foo 1
st1.bar 1
st2.foo 3
st1.bar 1
*/

对于前两行的输入,其实在我知道了Go支持DuckType时,就已经可以预见了。

但是后两行的输出,真的是让人惊艳。

这种组合方式,不仅粘合了两个struct, 还粘合了两个变量。

如果用得好,也许会有出其不意的威力

当然,天下没有白吃的午餐。

整个interface机制是有运行时开销的,这个开销会发生在由具体的struct到相应的interface对象转换时。

具体的开销,可能要等我熟悉了Plan9汇编和runtime库之后,才能破解谜题了。


再来看看Go的CSP编程,Go是通过channel来实现CSP编程的。

同样,先来看一小段代码:

package main

import (
    "fmt"
    "time"
)

func main() {
    ch1 := make(chan int)
    ch2 := make(chan int)
    go func() {
        n := <-ch1
        fmt.Println(n)
        ch2 <- (n + 1)
    }()
    go func() {
        fmt.Println("0")
        ch1 <- 1
        n := <-ch2
        fmt.Println(n)
    }()
    time.Sleep(1 * time.Second)
}

无论执行多少次,这段代码都会严格按照“0,1,2”的顺序打印。

如果在C语言中,用线程和一般的消息队列来写类似的代码,并不会有此效果。

每次程序运行都有可能会输出不一样的结果。

我认为这就是CSP(Communicating Sequential Process)的本质。

channel不仅仅是用来通信的,它还是一种同步手段。

channel会协调两端的goroutine在某一个点进行对接,然后再各自并发。

在这个对接点上,channel两端的goroutine是同步的。

用Go语言文档上的话说,在channel的一端没有取走数据之前,发送端的goroutine是不会被唤醒的。

当然Go语言还提供一种有缓冲的channel, 这种就更像是一个消息队列。

我理解下来,有缓冲的channel更适合于一些非常规场合,CSP则推荐使用无缓冲channel。

几乎所有的Go的参考书都会给我们强调说:并发属于代码;井行属于一个运行中的程序

这句话结合CSP的概念,让我有了一种不一样的感觉。

仍以上面的代码为例,当13行的fmt.Println被换成更具体而繁重的任务时,两个goroutine不可能有机会并行执行。

并发属于代码;井行属于一个运行中的程序这句话似乎在隐隐告诉我:不要害怕CSP导致并行度下降,只要你开足够多的goroutine,并行度在运行时很快就上去了,这也是为什么Go语言一直不停的鼓励我们写并发结构程序的原因。

想象一下,我们有64个CPU核心,有1W个goroutine。

就算每156个goroutine被channel粘合到一起,不得不串行执行,64个CPU核心依然会被跑满。

在CSP的模式下,整个系统的负载会更加均衡,不会出现生产者撑爆内存,或者消费者饿死的情况。

同时,理论上,由于隐式同步的存在,并发的Bug也会更少。


最后提一下Go的逃逸分析。

Go在堆上分配内存的机制,和一般的带GC的面向对象语言稍有不同。

以C#为例,他把对象分为值类型和引用类型。struct对象就是值类型,class就是引用类型。

因此,C#在new struct时会直接在栈上分配,在new class时会直接在堆上分配。

在Go语言中,对象是否分配在栈上,规则稍有不同。他取决于你是否向接口转换,或者这个变量的作用域是否超出的定义他域。

下面看一段很有意思的代码:

package main

func main() {
    m := make(map[int]int, 5)
    m[3] = 5
}

如果按照C#的经验,这个m变量肯定要分配到堆上的,因为map/dictionary是一个引用类型。

但是Go可以通过逃逸分析发现,这个m变量只在当前作用域使用,所以分配到栈上就足够了。

这不得不说是一个很大的优化。

初窥Rust

在2021年4月14号LKML 邮件组在讨论是不是要接纳Rust语言进行开发,而Linus本人似乎对Rust也没有那么反感。种种迹象表明Rust是一门值得一学的语言。但是拖延症让我一直拖到2周以前才开始学习Rust.

现代编程语言一般都围绕三个方面进行设计:范式内存并发(这是我自己的理解,也许并不正确,毕竟我没有设计过编程语言:D)。

就“范式”而言,Rust是一门多范式编程语言,而编程范式这几十年来没有什么太大变化,Rust同样在这方面也没有太大的创新。因此这一块没什么好说的。

刚接触Rust我就被它的“内存”管理震惊了,它号称在没有GC机制的情况下,可以做到内存安全。

我深知其中的艰难。

大约在5年前,我就尝试过通过编译器推导,来自动调用内存释放函数。

比如下面这段代码,在编译时可以推导出buf指针最长的生命周期在bar函数内,所以在bar函数的结束处可以自动生成free(buf)代码。

void foo(void *buf) {
//do_somthing of buf
}
void bar() {
char *buf = malloc(64);
foo(buf);
buf[64] = 0;
}

再复杂一点,我们依然可以推导出,这个指针该在bar函数的结束处释放。

char *foo(const char *s) {
    return strdup(s);
}
void bar() {
    char *s = foo("hello");
    s[0] = 'x';
}

但是,对于一些更为复杂情况(结构体中包含指针、运行时执行路径的多变,比如下面代码、等),靠编译器是无法正确推导的。这个想法也就以失败而告终。

void bar(int a) {
    char *s;
    if (a == 1) {
        s = foo("hello");
    } else {
        s = "world";
    }
    printf("%s", s);
}

也因此,Rust的内存管理方式对我格外有吸引力。

Rust首先提出了“所有权”的概念,某个变量拥有一个的所有权,在离开作用域时,它就有责任清理这个。“所有权”可以转移,不可以共享、复制。

在上面三段代码中不难看出,要推导一个函数内的所有的生命周期并不困难。困难的是当一个贯穿多于一个函数之后,生命周期就变得非常复杂。

Rust基于“所有权”,在函数原型上约束了参数的生命周期。函数原型会指明,每一个参数是“借用(没有清理责任)”还是“转移(连清理责任一起传递过来了)”。这样编译器就可以检查调用期间,"所有权"是否正确转移。

可以说,这是一种极为睿智的取舍。只添加了少许限制,就可以完成所有的生命周期的推导。简直是发明了,除引用计数标记清除之外的第三种内存管理方式。

这种限制似乎在实现复杂数据结构上颇为掣肘。

于是,又不得不在标准库中引入智能指针(引用计数)来辅助实现一些复杂的数据结构,这着实让人觉得有点美中不足。

不过,Rust的智能指针并不像OC等语言一样,在语言层面实现,而是以标准库的形式提供。总算是能弥补一点遗憾。


Rust下的并发同样值得一提,在“所有权”的内存管理机制下,编译器可以提前避免各种竞争问题。

在大家都吹爆GO语言的goroutine时, 我也跟风学习了一下。

然而学完之后,我对GO语言一直热情不太高。

其根本原因就是,他们吹爆的goroutine,根本没有解决并发问题。goroutine解决的只是线程切换成本过高的问题。

我不清楚是不是吹爆GO的都是做Web的选手。因为Web具有天然的并行性,他们最终的逻辑都只在数据库交织。而数据库已经为他们实现了各种各样的锁。

考虑下面的go代码,大概率在你的计算机上最终a的值是小于1000的。

package main
import (
    "fmt"
    "time"
)
func main() {
    var a = 0
    for i := 0; i < 1000; i++ {
        go func(idx int) {
            a += 1
        }(i)
    }
    time.Sleep(time.Second)
    fmt.Println(a)
}

在C语言时代,这是一个常见的并发问题:没有加锁。

那为什么在GO语言上也会出现这种现象呢,因为goroutine是跑在线程池上的。

也许你会说:“加个锁不就好了么?”,“GO推荐使用channel进行通信,你用了不就解决问题了”。

在C++领域,我们造不出锁么,我们造不出channel么,为什么后来单线程大行其道。

其根本原因是,加锁这种行为,是极易犯错的。就算你使用了channel等同步机制,语言本身还是允许你自由的访问共享内存,不经意间就会产生竞争问题。

而Rust在这方面就做的非常好,他的“所有权”机制。可以在编译时就能提醒你潜在的并发问题。

如果你要在线程中访问一个变量,这个线程就必须拥有这个变量所代表值的“所有权”。如果别的线程访问同一个变量就会产生编译错误。这就从编译时解决了并发问题。

同样, Rust的多线程也允许两种同步方式:加锁和channel。

使用channel进行同步时,多线程不可以同时访问同一个变量,因为在发送某一个值时,连它的“所有权”也一起发送出去了。

在使用锁进行同步时,Rust的“所有权”机制同样会保证,你不获取锁就不能访问某个变量。

我认为只有在这样安全的环境下, 才可以真正编写并发程序。

ps. 我想Rust是继C,Lua之后我喜欢的第三门语言。

给silly增加热更新

最新抽了点时间给silly增加了一个silly.patch模块,用于对热更新提供一些有限的支持。

热更新最麻烦之处莫过于“数据迁移”, 即怎么使新函数(要更新的函数)以“运行时数据”的状态运行。

其实http这类无状态协议是最为简单的,因为他们不需要“数据迁移”的过程。http的这种架构,使得所有的函数都是无副作用的,所有的数据在请求结束给出Response的同时, 数据就已经存入了数据库。当需要热更新函数时,根本就不需要考虑数据的问题,直接替换就可以完美解决。

与此相对的是,通常的服务器或应用程序都会有“非局部变量”的存在(所有生命周期不是在函数被call时建立,ret时销毁的变量都可以认为是非局部变量,比如lua中的全局变量或上值)。

对于这类程序,在热更新时,就必须要小心处理这类数据,使热更新之后的函数安全的以“运行时数据”所代表的状态运行。当涉及数据结构或功能变化较大时,这种“数据迁移”的安全性很难面面俱道,也很难提出一个通用的解决方案。

再考虑一下解bug的场景,大多数情况下,bug可能只会出现在某几行代码或某几个函数之中,一般会延续之前的设计而不太会有大量数据结构或大量代码的改变。

在这种情况下,热更新实现的复杂度就可以降低不止一个数量级。在实现上也可以有更好的保证。

因此,这次新增的silly.patch模块也仅仅对热更新bugfix做了一些支持。


silly.patch模块只提供一个功能,即将a函数中的所有“非局部变量” patch 到b函数中去,以便b函数以a当前的运行时状态继续运行。

借助luaVM提供了一组调试函数,使得我们可以方便的对a,b两个函数进行“数据迁移”。

比如,使用debug.getinfo来遍历出a,b两个函数的所有上值,然后使用debug.getuservalue和debug.upvaluejoin将b函数的所有上值均引用至a函数的上值。这样就可以使逻辑以b函数的代码以a函数的数据去运行。

但是这里面有些问题需要处理.

a,b两个函数必然不会相同(不然也不会去更新了),那也就不能保证a函数的第一个上值意义与b函数的第一个上值意义完全相同。比如下面代码:

local foo = "hello"
local bar = "world"
local function f1()
	print(foo)
	print(bar)
end
local function f2()
	print(bar)
	print(foo)
end

如果a函数是f1, b函数是f2。f1的第二个上值是foo(因为使用了print,所以第一个上值是_ENV),而f2的第二个上值是bar。如果按上值的id去patch,上述代码就会出现很诡异的bug。

因此silly.patch模块做了一个简单的约定,如果要拿b函数去修复a函数,就必须保证a函数中使用的所有上值在b函数中必须不得改变其意义。

有了这个约定,silly.patch就可以根据“非局部变量”的名字去进行“数据迁移”。 比如f1使用了上值foo, f2中只要foo的意义不变,不管他属于f2的第几个上值,都可以保证“数据迁移”的正确性。

还需要注意的是,如果a和b函数的上值变量是函数时,需要递归对其上值函数进行“数据迁移”。


silly.patch仅仅是对热更新做了支持,他并不是一个完整的热更新模块。还需要对silly.patch进行一定的封装才可以使用。

在进行封装时一般的步骤为,生成新函数b,找到等修复函数a, 执行silly.patch, 将a的数据迁移到b函数上, 然后使用b函数替换为a函数。

生成新函数b,一般是通过load/loadfile来生成一个chunk, 然后调用chunk来生成.

为了避免在调用chunk函数时有副作用,一般在调用load/loadfile时,会传入一个新的_ENV表作来将chunk置于沙盒之中,如果有顾虑新的函数b会使用新的全局变量(即函数a从没使用过的全局变量),可以在整个热更新的最后, 将load/loadfile时传入的_ENV表有选择性的合并运行时环境中(只合并运行时环境不存在的变量)。

比较麻烦的是怎么找到要修复的函数并进行替换,lua中提供的debug接口中并不能获取一个chunk中的所有函数。

当然就算提供了这样一个接口也很难使用。在lua中,function是first class, 这就意味着当你定义两个变量指向同一个函数时,这个函数就拥有了两个名字。

因此在我们约定不给可能会热更新的函数起别名的情况下,有两种实现方式。

一种不太通用的实现是,在每个chunk中实现两个函数,一个函数提供通过名字对chunk中的任意函数进行定位,一个函数提供通过名字对chunk中任意函数进行替换。这种方法比较麻烦,而且容易出错。

另一种方式依赖于一个事实,一般每一个lua模块都会导出一些接口函数供其他函数使用,那么就从这些接口上做文章。

比如我们想要将module模块中a函数热更新为b函数,我们可以直接require “module”得到module模块的接口函数表,然后再根据名字定位到相应的函数,如果替换则直接将module模块函数表中的相应字段重新赋值就可以了。

如果想要热更module中某个local函数,就比较很麻烦,但是也可以办到。在上文silly.patch的实现中可以得知,如果一个函数有上值,而且上值是一个函数的情况下,silly.patch同样会对上值函数进行“数据迁移”,这也意味着,上值函数同时也会被热更新到最新。所以,在需要热更新某个local函数时,可以通过热更调用他的模块接口函数来实现。

但是需要注意的是,这里有一个坑。如果函数module.a1和函数module.a2同时引用了module中的一个名为foo的局部函数。如果只热更module.a1的话,module.a2将依然会使用旧的foo函数。

基于通用考虑,在silly的console模块提供了一个patch命令, 这个命令正是基于方式2来实现的。

为什么要有头文件

我在写C文件时,一般会首先确定这个模块需要哪些功能,然后在头文件中定义相应的接口函数。之后才是在C文件中实现,在实现过程中除非有遗漏的接口,不然是不会再切回头文件的,一般辅助函数我都是直接以static的方式定义在C文件中。

在写C++代码时,这些代码辅助类的函数,都必需要以private的方式在头文件中声明。这会导致在写代码时,需要频繁在h/cpp之间切换,极度令人不舒服。

因此每次在写C++代码时,都免不了在心里抱怨几句为什么不把private函数直接定义在cpp文件中,或者干脆像java一样不要头文件算了。

前两天把这事跟朋友抱怨了一下,结果竟然得到了一个反问为什么需要头文件,头文件的作用到底是什么?

有人说头文件是为了展现接口,以头文件和.a或.so发布时,别人只要看头文件就可以知道提供了什么接口,然而对于java这类没有头文件的语言来讲只要一个工具同样可以提取出来class文件中的public接口信息。因此我觉得还是需要从编译器角度来分析一下头文件的用途。

那么C语言的头文件到底起到什么作用呢?且看下面一段代码(ps.为了使这段代码在任何平台上效果都一样,使用了stdint.h中的可移植类型):

////////////compile: gcc -o a a.c b.c
////////////b.h
#ifndef _B_H
#define _B_H
#include <stdint.h>
struct test {
        uint8_t a1;
        uint8_t a2;
        uint8_t b1;
        uint8_t b2;
};
#endif
////////////b1.h
#ifndef	_B1_H
#define	_B1_H
#include <stdint.h>
struct test {
        uint16_t a;
        uint16_t b;
};
extern struct test T;
#endif
////////////b.c
#include "b.h"
struct test T = {.a1 = 1, .a2 = 2, .b1 = 3, .b2 = 4};
////////////a.c
#include &lt;stdio.h&gt;
#include "b1.h"
int main()
{
        printf("a:0x%x b:0x%x\n", T.a, T.b);
        return 0;
}

这段代码的运行结果很有意思,是’a:0x201 b:0x403’。

这段代码编译器不会报任何错误,甚至连警告也不会报。为什么会这样呢?这要从几个.c文件变成elf(linux)/exe(win)文件过程说起。

从c文件到可执行文件至少要经过两个阶段,即‘编译’和‘链接’。
‘编译’会将相应的C代码转换成相应的汇编,但保留符号名(如上述代码中的T)然后生成.o文件.
而‘链接’会收集所有的.o文件然后为每个符号分配地址,并将.o文件中的相应的符号换成相关地址并生成相应格式的可执行文件(ps.上面的流程并不严谨).

以a.c中的代码为例,在编译时T.a语句其实就已经转换为了与*((uint16_t*)((uint8_t *)&T+0))等效的汇编代码,相应的T.b的语句等效*((uint16_t*)((uint8_t *)&T+sizeof(uint16_t))).这一点其实可以通过gcc -S来反汇编证明。

那么头文件的功能就呼之欲出了,在‘编译期间’为了保证能生成正确的汇编代码,必须要头文件指明struct的字段分布,及此c文件中引用的符号在外部有提供(这就是声明的意义)。

当然头文件所带来的问题也正像上述代码中描述的一样,当给出一个错误的头文件时编译器并不会察觉,在没有源码的情况下,这种错误极难发现。

那么java是如何实现的呢?我尝试着写了两个类编译了一下。猜测,他应该是在编译时自动提取出本类的声明信息,然后放在.class文件中,当javac编译时用到某个类时就去找当前目录下打开‘类.class’文件,从其中提出取类的声明信息,从而达到与有头文件有相同的效果。

ps. 我怀疑.class的声明信息与其反射机制有密切关系,但是jvm的代码量有20多万行,找到其反射部分的实现还是比较麻烦的,天气这么冷还是先放一下:)

pps. 如果C语言也这么搞的话,似乎是行不通的,java中的类的概念,可以约定使用哪个类就从‘类名.class’文件中寻找,如果是C呢,找一个struct test的布局去test.o中找?那找一个函数helloworld应该去哪个文件中找呢?


在与Qwerty交流后发现,查找helloworld函数时可以根据此c文件import的模块来实现,那么似乎为C引用import机制也并不是不太可能。

简单思考了一下,在不改变现有编译流程的情况下,似乎可以为c文件引入一个轻量级import机制来代替头文件。

我们可以在编译器(如:gcc)之上包个壳,假设叫xcc,然后为.o为文件也加上一个壳叫.m。

.m文件其实包含了其源文件中的public的函数接口定义和一个完整的gcc编译出来的.o文件内容。

xcc的执行流程大概如下:

1. 使用xcc编译A.c文件时,xcc首先分析出A.c文件中的声明信息’T’及import的模块’M’。
2. 从M.m文件中提取出M.c文件中的声明信息T,并生成M.h文件,之后将a.c中的import ‘M’替换为#include “M.h”,并另存为到/tmp/A.c.tmp。
3. 调用相应的编译器如’gcc’编译/tmp/A.c.tmp生成A.o
4. 将A.c的声明信息T追加到A.o的最后(之所以追加到最后,是因为A.m可以被当作A.o直接传给ld, 这样我们就不用为ld再包一个壳了)

有一个特例,一个struct是否要导出,必须要等分析完所有的导出接口之后才能决定,如果在导出接口参数中有用到,那么我们就可以将其导出到头文件中。

如此,我们就有了一个兼容import的C语言。

实现了一个lualint

在使用动态语言的过程中,由于其运行时检查特性,很多手误并不能在刚运行时暴露出来。虽然并不会导致程序个程序crash掉,但总归是很麻烦的。

网上找了一个lualint试了试,效果还不错。这个工具的原理就是基于在写lua代码时并不会使用全局变量。在检测到全局变量时直接报警即可。

仔细研究了一下这个lualint的原理。

lua自带的工具luac是可以把编译后的OPCODE打印出来的,更关键的是自带注释。

利用OPCODE和注释就可以分析出在哪一行哪些变量是使用了什么全局变量。只要我们在代码中不使用全局变量这一事实成立,那么所有使用了全局变量的地方都可能是手误打错了。

但对于我来说这个lualint有2个缺陷。

1. 但这这个lualint是并不支持lua5.3版本。因此在使用如’//’这类lua5.3新支持的特性时,这个lualint工具就不能很好的工作了。
2. 如果我require了一个表,并且使用了这个表中不存在的字段,那么他并不会报警,这对我来说很不习惯。因为大部分模块调用都是使用通过使用module.member的方式来调用的,如果member的名字打错(如A.l1打成了A.ll), 这个工具并不会报警出来。

基于以上原因,我基于lua53重新实现了一个lua分析工具修复了上述缺陷。虽然依然叫lualint, 但为了简化实现复杂度,这个lua检查工具在部分地方使用了动态分析。

在lua53中,对全局变量的作法做了些改动。

所有全局变量都是放在_ENV表中存放的,而一个代码块的所有代码是共享一个upvalue的。而访问全局变量是通过类似 ‘GETTABUP 0 0 -1 ; _ENV “print”‘的OPCODE来完成的。因此检测访问全局变量的OPCODE要改为监测使用GETTABUP/SETTABUP 对于_ENV表中的字段进行操作的代码。

考虑如下代码:

local b = require "testb"
--code1
print(b.CONST_A)

function hello()
        --code2
        print(b.CONST_A)
end

对于b.CONAT_A中的访问检测则稍微有些麻烦。

在code1处对模块testb的成员CONST_A的访问OPCODE和在code2处的OPCODE并不相同,因为code1属于main chunk而code2属于function chunk, 变量b与code1是平级的,即相当于code1的局部变量,而对于code2来说b变量为函数hello的upvalue, 因此在main chunk中访问模块testb的成员CONST_A使用的是GETTABLE而在function chunk使用的是GETTABUP. 顺便插一句,lua之所以能够实现的如此简洁,应该与其这种设计的统一性不无关系。

如果通过分析OPCODE来检测模块B是否有CONST_A变量虽然也可以做到,但是会很麻烦。因此这里取了个巧,采用了动态加载的方式。模拟require的行为,然后将模块testb的返回值接收下来并保存,当访问testb的成员时直接查看testb返回的表中是否有这个成员即可。

当然事情不可能这么简单,在函数中访问testb中CONST_A时会生成的OPCODE如’GETTABUP 1 1 -3 ; b “CONST_B”‘。 这里存在两个麻烦:一个是如果b是某个模块的别名,那么怎么确认他是哪个模块的别名,,因为生成require的OPCODE并不会有别名b的信息。一个是怎么找到这个b到底是模块testb的别名还是此函数的另外一个上值。

对于第一个问题,其实在分析require的过程中,我会重新再解析一遍当前代码文本,require中的那一行找到相关模块’testb’的别名即为b,做一个反向映射,如果GETTABUP指令访问b就把b当做别名找出真正的模块名’testb’,从而找出模块’testb’的表引用。由于需要分析require,因此顺带着就把整个project的依赖关系给解析了,在使用时也就不需要使用如find . -name ‘*.lua’ | xargs grep ./lualint 之类的命令来使用了。设置完ENTRY之后,直接使用./lua lualint.lua就可以自动分析完整个project是否警告信息。

对于第二个问题出于对实现的简化,采用了鸵鸟政策,碰到此类情况均当做是对模块’xxx’的变量的访问。当然做了一点小小的优化,如果从别名找不到真正的模块名,就认为访问的不是模块的成员变量,直接忽略。

ps.由于急用,实现的有些丑陋,因此附一篇文章大致说一下思路:D

使用lua过程中需要注意事项

最近一段时间写了不少lua代码,由于这一次的代码量比以往都多,因此也就遇到了以前没有遇到问题, 需要说明的是,这就是一篇lua问题大集合, 并不涉及其他。

先说说遇到的问题及解决方案。

在lua中没有多余的数据结构,全靠一张表,这也是他简洁的根本所在。

当索引为全为数字时即可当数组使用,然而需要注意的是lua假设数组的索引一定是连续的,在此基础上lua尽可能快的优化了取数据长度的算法,因此lua对‘#’操作符的描述是“当table[i]不为nil, 而table[i+1]为nil时,则数组的长度为i”.

因此如果table = {1, nil, 2, 3}, 那么使用#table得到的结果会是1.因为table[1]不为nil, 而table[1+1]为nil。其实这一点在”Programming in Lua”是有明确说明的,只不过在写代码时我忘记了。

如果想删除数组中的元素而又保证#table的正确性,可以使用table.remove函数来删除指定位置的值,table.remove所做的事情其实就是把所有元素向前移动一位,因此在使用table.remove时一定要估算好移动元素带来的开销是否超出了预期。如果超出了预期就要考虑其他方案,而其他方案也与‘#’引起的问题没有关系了。

‘#’的语义带来的麻烦还不仅仅于此。考虑下面一段代码:

        function test1(...)
                local param = {...}
                local p1, p2, p3, p4 = table.unpack(param)
        end

当调用test(1, nil, 2, 3)之后,得到的结果是p1 = 1, p2 = nil, p3 = nil, p4 = nil。

之所以这样是因为table.unpack(param) 等价于table.unpack(param, 1, #param), 而’#’的语义导致了#param得到的结果是1,所以table.unpack其实只unpack出了第一个值而已。

即然存在此类问题,显然也存在着解决方案。lua的table库中提供了一个函数table.pack。table.pack(…)与{…}惟一不一样的地方就是,table.pack会自动识别…中有几个参数,并把这个值赋给返回的表中的”n”字段。

所以上述代码要想支持传递nil就必须改成如下:

        function test1(...)
                local param = table.pack(...)
                local p1, p2, p3, p4 = table.unpack(param, 1, param.n)
        end

再说说优化问题。

3R在很多文章上都有提到,就不再多说什么了,但是对于Reuse需要注意的是,并不是所有的值都值得Reuse,需要考虑这个表的Reuse的代价有多大。

考虑一个表从产生到销毁的过程(不包含对元表的__gc函数的调用过程)。

local xx = {} 就代表着要构造一个新表,这就代表要调用malloc, 当这个表不再被使用时,就会被gc回收free掉。

如果我们可能重用xx表,那么就可以省去malloc/free的开销,要知道malloc的开销是相当大的。

但是这里需要注意的一个问题是,xx已经有了预分配槽位,假设之前xx表中被设置过xx[1]~xx[100]个数据,那么就意味着重用xx表后,向xx[1]~xx[100]的位置赋值是是不会触发malloc进行扩容的。

之所以说这是一个问题而不是一个优点,是因为在不同的情况下,这种重用有时有利有时有害。这取决于被重用的xx表的用途,如果xx几乎是固定大小,那么显然这种不需要扩容就是有利的,反之如果xx大部分情况下都很小,就会浪费很多空间。

当重用的表是一个模块的upvalue时,还需要考虑的是当你为这个表的每一个槽位都赋为nil的代价与构造一个表的代价哪个更高,如果无法评估则应该选取语言更简单的模式“直接构造一个表”。

next函数常用来进行无序遍历整张表,同样你必须知道他的底层实现,才能够很好的使用它。从lua源码中可以找到next函数具体实现,当传递给next的key为nil时,事实上next函数会从table的第一个空槽位开始遍历,直接找到第一个值为非nil的key并返回。因此在使用next进行遍历时,必须对整个table中的布局做到心中有数。

考虑一种极端情况,有一个table有1M个数组空间,只有在索引接近1M时,值才不为nil,其他值都为nil,如果这时候需要频繁的调用next来遍历整个表,势必会造成程序性能急剧下降。这种情况下就需要在表的基础上构造出相应的数据结构来提高程序性能,比如记录第一个非nil的起始索引。

在lua中有很多基本库和函数是存在于_ENV表中,比如table库,math库等,如果调用这些函数很频繁,可以考虑将函数局部化,能显著提高程序性能。

下面对比一下两段代码,和编译后的OPCODE

--使用全局函数
local tbl = {}
for i = 1, 100 do
        table.insert(tbl, i)
end
--OPCODE
main <a.lua:0,0> (12 instructions at 0x7fc748c043f0)
0+ params, 8 slots, 1 upvalue, 5 locals, 4 constants, 0 functions
	1	[1]	NEWTABLE 	0 0 0
	2	[3]	LOADK    	1 -1	; 1
	3	[3]	LOADK    	2 -2	; 100
	4	[3]	LOADK    	3 -1	; 1
        --for i = 1, 100 do
	5	[3]	FORPREP  	1 5	; to 11
	6	[4]	GETTABUP 	5 0 -3	; _ENV "table"
	7	[4]	GETTABLE 	5 5 -4	; "insert"
	8	[4]	MOVE     	6 0
	9	[4]	MOVE     	7 4
	10	[4]	CALL     	5 3 1
	11	[3]	FORLOOP  	1 -6	; to 6
        -- end
	12	[5]	RETURN   	0 1

--全局函数局部化

local tinsert = table.insert
local tbl = {}
for i = 1, 100 do
        tinsert(tbl, i)
end
--OPCODE
main <b.lua:0,0> (13 instructions at 0x7fb5a94043f0)
0+ params, 9 slots, 1 upvalue, 6 locals, 4 constants, 0 functions
	1	[1]	GETTABUP 	0 0 -1	; _ENV "table"
	2	[1]	GETTABLE 	0 0 -2	; "insert"
	3	[2]	NEWTABLE 	1 0 0
	4	[3]	LOADK    	2 -3	; 1
	5	[3]	LOADK    	3 -4	; 100
	6	[3]	LOADK    	4 -3	; 1
        -- for i = 1, 100 do
	7	[3]	FORPREP  	2 4	; to 12
	8	[4]	MOVE     	6 0
	9	[4]	MOVE     	7 1
	10	[4]	MOVE     	8 5
	11	[4]	CALL     	6 3 1
	12	[3]	FORLOOP  	2 -5	; to 8
        -- end
	13	[5]	RETURN   	0 1

对比可以看出使用局部变量tinsert代替table.insert之后在for循环内少了两条对table的操作(GETTABUP, GETTABLE) 效率大概提高了10%

当语言内置操作和标准库一样时,应该优先选择语言内置操作。其实这很好理解语言内置操作执行一起一般比调用标准库要生成更少的OPCODE,在功能一样的情况下一般OPCODE数目越少,应该就越高效才对。
在循环100W次的情况下table[#table+1]=i要比table.insert(table, i)快30%左右。

btw, 在看lvm.c的过程中,越来越觉得脚本语言是比C/C++更高层次的抽象,不过也只有这样才能达到简少代码的目的。然而高层次抽象就意味着我们失去了很多优化的能力。

C++默认构造函数

在C++中,如果不为某个struct/class实现一个构造函数,那么编译器就会自动为这个类添加一个默认构造函数,而这个默认构造函数什么也不干。

但是我却从来不知道,默认构造函数在不同的情况下,会出现不一样的效果(当然这是C++03之后的标准).

先看一段代码:

struct test {
int a;
int b;
};


void *operator new(size_t sz)
{
void *p = malloc(sz);
for (size_t i = 0; i < sz; i++)
((char *)p)[i] = 0x01;
return p;
}
int main()
{
struct test *t1 = new test;
struct test *t2 = new test();
printf("t1:%x-%x\n", t1->a, t1->b);
printf("t2:%x-%x\n", t2->a, t2->b);
return 0;
}

重载new操作符是为了把分配出来的内存弄脏。然后观察new test和new test()的区别。

结果出人意料,t1的值就是内存中被污染的值,然后t2的值却全部被清0,而造成这种现象的惟一的区别就是new之后类型是否带有括号。

这就是C++03版本的新增内容,当没有实现构造函数时,编译器为你自动生成的构造函数是有两种用途的。当你在使用new T()构造对象时,默认的构造函数会对各变量执行清0操作,其实应该就是memset为0. 而在使用new T来构造对象时,其默认构造函数是任何事也不做的。

总觉得这么做违背了语言的一致性的设计, 但是不管怎么说有了这个,在写struct定义时在一定的情况下就可以省掉默认构造函数了。

迭代器模式

在写C++代码时,首先接触的就是迭代器。甚至于设计模式都有一种模式叫迭代器模式。虽说网上到处都说迭代器用于隐藏数据结构的细节,但我却一直没有真正搞明白为什么需要迭代器去隐藏数据结构细节。

在写C++代码时,一般我每用一个数据结构都会去查一下,他大致是如何实现的(不然用起来不太放心:D)。

因此一般情况下我在c++下都是使用类似类似for(size_t i = 0; i < vector.size(); i++)的方式去遍历vector的每个元素。

直到最近的一次重构我才大概明白什么时候去使用迭代器模式。


首先大致说一下zproto的作用。

zproto是一个序列化/反序列化的工具,类似google protobuf,但是实现更简单,更轻量级。

在实现之初,我是希望zproto.c可以实现syntax和serialize/unserialize的核心功能,然后再为每种不同的语言写一组操作本语言数据结构的函数,即可通过zproto.c来实现bind功能。但我又不想做成callback接口。

由于zproto所有字段都是可选的,因此某一字段可能是不存在的,在encode和decode时,zproto.c必须知道上一次有效的字段是哪一个。

因此接口就变成了这个样子:

void zproto_encode_tag(struct zproto_buffer *zb, struct zproto_field *last,
struct zproto_field *field, int32_t count);
void zproto_encode(struct zproto_buffer *zb, struct zproto_field *last,
struct zproto_field *field, const char *data, int32_t sz);
struct zproto_field *zproto_decode_tag(struct zproto_buffer *zb, struct zproto_field *last,
struct zproto_record *proto, int32_t *sz);

从接口就可以看出,在写bind代码时,每次都需要维护上一个有效有字段,这其实从一定程度上暴漏了zproto.c作为core的实现细节而且加重了写bind代码的负担,这一度让我觉得很恶心。

几次想把last放入zproto_buffer字段中,但这样就需要在zproto_buffer中维护一个栈的结构,因为record(结构体)中有field(字段),field又可能是record类型。 这样一来就增加了实现复杂度,与我的初衷不符。因此也就迟迟没有动手。

直到最近在一次写C++的代码时,再一次用到迭代器(遍历map中的所值)时,突然觉得这个问题可以用迭代器来解决。

使用迭代器实现后的接口如下:

void zproto_encode_array(struct zproto_buffer *zb, struct zproto_field_iter *iter,
int32_t count);
void zproto_encode(struct zproto_buffer *zb, struct zproto_field_iter *iter,
const char *data, int32_t sz);
int zproto_decode_field(struct zproto_buffer *zb, struct zproto_record *proto,
struct zproto_field_iter *iter, int32_t *sz);
int zproto_decode(struct zproto_buffer *zb, struct zproto_field_iter *iter,
uint8_t **data, int32_t *sz);

明显可以看出,接口和内聚性都提高了很多。在写bind代码时再也不需要维护上一次有效的字段了,因为在encode时已经被记入iter了。

当然代价肯定了也是有的,就是多实现了一组迭代器的函数,不过我认为这代代价是值得的。

由于zproto已经完全屏蔽了细节,因此在写bind代码时可以只关心本语言的数据结构的存取,而不会由于不懂zproto的实现细节导致传入错误的last_field造成zproto.c工作异常,大大降低了心理的包袱。


可以结总出迭代器一般用于提供给其他模块遍历时才使用(其实从标准库就可以看出,只是我自己没领会到^_^!),迭代器数据结构也不一定只存储用于遍历的数据,只要方便达到目的也可以存一些冗余数据,比如zproto.c中的迭代器会存储上一次有效的字段。

现在再反思为什么以前写代码都不会用到迭代器模式其实都很清楚了。

在写C语言时,模块一般都是提供某种属性或某种行为的而不会提供遍历的特性,这种情况下也就没有必要去为此模块提供一个迭代器。

而在模块内部的数据结构, 其实也没有必要去实现一个迭代器,有时候直接操作成员去访问可以更直观更高效。

同样在C++开发时也并非说,实现了一个容器类数据结构就需要去为他实现一个迭代法器,如果此数据结构仅仅为优化特定模块而生。那么直接去访问有时后反而代码更少更简洁,也并不会造成什么坏的影响。

还是那句话,没有银弹,什么时候合适什么时候不合适还是要靠自己判断。