一例误用unsafe包引起的内存问题

Go语言的指针真的很灵活,远非其他带GC的语言可以比拟的。

比如下面这段代码,并不会产生GC问题。

而在其他带GC的语言中,是不太可能写出类似这种代码的。

var b *int
{
    a := make([]int, 3)
    b = &a[1]
}
fmt.Println(*b)

在写Go代码时,常常会让人有种在写C语言的错觉,他的指针几乎实现了90%的功能,剩下没有实现的10%则是与GC有关。

而unsafe包则可以让我们做到剩下的10%, 但是内存安全性需要我们自己保证。

比如下面代码就是完全正确的,只要c还活着,a就不可能被回收。

var b unsafe.Pointer
{
    a := make([]int, 3)
    a[1] = 0x01020304
    b = unsafe.Pointer(&a[1])
}
c := (*byte)(b)
fmt.Printf("%04x\n", *c)

在一些性能敏感的地方,比如在一场回合制战斗或者一个复杂对象的反序列化中,内存分配可能会吃掉相当一部分算力。

这些场景都有一个共同的特别,有一大批小对象同生共死。如果能够将这些小对象分配进行批量化,就可以显著提高性能。

比如下面代码,性能会有将近300%的差别。

package main

import (
    "os"
    "unsafe"
)

type Foo struct {
    a uint64
}
var pool []uint64
//go:noinline
func Alloc(direct bool) *Foo {
    if direct {
        return &Foo{}
    } else {
        var f *Foo
        size := unsafe.Sizeof(*f)
        need := (size + 7) / 8
        if len(pool) < int(need) {
            pool = make([]uint64, 512)
        }
        p := unsafe.Pointer(&pool[0])
        pool = pool[need:]
        return (*Foo)(p)
    }
}

func main() {
    direct := len(os.Args) == 1
    for i := 0; i < 64*1024*1024; i++ {
        Alloc(direct)
    }
}
/*
$ time ./a
./a  0.77s user 0.01s system 110% cpu 0.710 total
$ time ./a x
./a x  0.26s user 0.06s system 129% cpu 0.250 total
*/

不用怀疑,上面的代码一定是对的。

因为所有使用Alloc分配出来的指针一定是8字节对齐的,而所有的Foo指针也必将引用pool对象的内存,使他不被回收。

然而,有朝一日,代码被迭代成了下面的样子,GC就会开始紊乱了。

package main

import (
    "os"
    "unsafe"
)

type Bar struct {
    b uint64
}

type Foo struct {
    a uint64
    b *Bar
}

var pool []uint64

//go:noinline
func Alloc(direct bool) *Foo {
    if direct {
        return &Foo{}
    } else {
        var f *Foo
        size := unsafe.Sizeof(*f)
        need := (size + 7) / 8
        if len(pool) < int(need) {
            pool = make([]uint64, 512)
        }
        p := unsafe.Pointer(&pool[0])
        pool = pool[need:]
        return (*Foo)(p)
    }
}

func main() {
    direct := len(os.Args) == 1
    for i := 0; i < 64*1024*1024; i++ {
        f := Alloc(direct)
        f.b = &Bar{}
        //do something with f
    }
}

让我们来写段代码测试一下:

package main

import (
    "fmt"
    "runtime"
    "time"
    "unsafe"
)

type Bar struct {
    b [64]int
}

type Foo struct {
    a uint64
    b *Bar
}

var pool []uint64

//go:noinline
func Alloc(direct bool) *Foo {
    if direct {
        return &Foo{}
    } else {
        var f *Foo
        size := unsafe.Sizeof(*f)
        need := (size + 7) / 8
        if len(pool) < int(need) {
            pool = make([]uint64, 512)
        }
        p := unsafe.Pointer(&pool[0])
        pool = pool[need:]
        return (*Foo)(p)
    }
}

func fin(r *Bar) {
    fmt.Printf("fin %p\n", r)
}

func main() {
    f := Alloc(false)
    f.b = &Bar{}
    runtime.SetFinalizer(f.b, fin)
    fmt.Printf("%p %d\n", f.b, unsafe.Sizeof(*f.b))
    time.Sleep(time.Second)
    runtime.GC()
    time.Sleep(time.Second)
    fmt.Printf("%p %d\n", f.b, f.b.b[0])
}

在第50行代码,我特意加上了fmt.Print来引用f对象,甚至引用了f.b对象。

但是我们可以从log看出,在48行GC时,f.b指向的内存已经被回收了。

之所以会出现这种情况,本质上和Go语言的GC机制有关系。

在上一篇文章中,我找到了一些资料来解释为什么Go语言的指针可以有这么大的自由度。

现在这篇文章同样能解释这次的Bug。

本质上在Go语言代码层面,所有的指针和unsafe.Pointer的功能并无两样,仅用于指明这个变量是指针,在进行GC Mark时,需要Mark这个变量所指向的内存块。

至于这块内存中指针变量的位置,是在new这块内存时,Go编译器会根据这块内存的类型来标记的。

我们上面的Alloc池,在分配内存时给GC的信息是,我们要分配一个512大小的uint64类型的slice。

编译器生成代码时就会标明,这块内存中没有指针成员,在GC Mark时不需要继续Mark子元素。

虽然我们将其中的某块内存使用unsafe包强转成Foo对象的指针,但这也仅能保证pool对象内存的安全,并不能保证Foo对象中指针变量指向内存的安全。

GC系统从Foo的指针最终是Mark的是pool对象,当然也就不能Mark到Foo.b所指向的内存。

在这段代码中,还有一个有意思的现象,即使第50行我们引用了f.b对象。但是依然不能阻止GC对他的回收。

但是我们在47行之后,如果插入一行b := f.b就可以阻止f.b对象被回收。

这是因为,虽然Go的最新版GC使用了混合写屏障,但是在一个GC循环中,每个goroutine的栈至少会被扫描一遍的。

GC不在运行中,代码44行的混合写屏障没能开启,所以f.b没能被mark。

GC运行时扫描栈对象时,又识别不出f.b变量是个指针,更不可能Mark内存块f.b。

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变量只在当前作用域使用,所以分配到栈上就足够了。

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

重新抽象图形API

这次抽象,我几乎全盘否定了之前的抽象

本来,RHI的抽象已经基本完成了,可以开心的写基础的光照阴影这些功能了。

但是,在QQ群里无意间看到大佬们聊起来bindless, 然后去查了查资料,发现bindless性能又好,抽象又好做,于是果断入bindless的坑。

在bindless抽象中,会把所有用到的材质参数,纹理全部放加载到显存,然后使用一个ID索引来引用相关的资源。

随着重构的进行,我发现之前的设计思路有很多问题,这都是因为我对GPU资源管理的不熟悉所致。

当我们向GPU上传纹理时或做更新资源时,由于GPU离CPU较远,所以Vulkan总是倾向于我们调用批量接口。

对!就像Nvidia说的那样,Batch! Batch! Batch!,但不仅仅局限于DrawCall, 转换内存布局,上传资源都需要Batch。

那么,此前做的所有抽象基本完全无用了。

在之前的抽象中,我都是基于同步的思路来做的,比如我new一个图片就需要等待他上传成功才能返回,不然结构体中的一些数据没有办法进行初始化。

经过仔细思考后,我认为此前提到的方案1其实是更好的选择。

数据冗余的问题也不难解决,只要我们把图形API层需要用到的数据下沉到图形API层的内部代码中,然后在RHI层的结构中做一个代理函数,通过gpu_handle来获取相关属性并返回即可。在实际应用中,由于width,height,format等属性属于低频访问,无论怎么封装,其实都不能成为性能瓶颈。

这样,新RHI层的数据结构只需要持有相应gpu_handle即可,这个结构有释放资源的责任。

比较微妙的是,由于bindless的存在,我们shader中的参数,如纹理,材质参数也都是通过id来索引的。

这样我们便直接把图形API层的资源管理透明掉了,RHI的数据结构可以直接和shader进行匹配,而不用关心图形API层是如何管理资源的。

透明掉图形API层之后,我们便拥有了更大的实现自由,比如在new rhi::texture2d时,图形API层只需要把上传到GPU时所需要的数据保存下来,然后分配一个gpu_handle, 函数就可以立即返回了。

在业务逻辑调用DrawCall之前,把需要用到的资源上传到GPU即可。

在实践中,由于DrawCall也是通过写入CommandBuffer中最终提交才异步执行的,因此我们只需要保证在CommandBuffer中,上传资源相关的GPU命令先于相关的DrawCall命令之前执行就可以了。

在Batch的指导思想下,其实使用gpu_handle的封装方式,能获得更好的Cache Friendly。因为所有图形API层的数据结构总是在渲染时,被批量访问。

而且,由于gpu_handle并不是指针,如果有需要还可以实现一些池的优化技术,如内存整理等(随着分配释放的进行,池中可能会有很多空位长时间用不到,这时出于内存和Cache Friendly的考虑,需要整理一个池中的元素的分布)。

最后,这次重构代码在此

ps. 由于一些原因,可能未来很长一段时间内,这个引擎的Thread都需要换出了,先在这里保存一下上下文,以便后面可以继续换入 😀

给Lua实现了一个数学库

我的玩具引擎计划以Lua语言为第一业务语言。

引擎可以加载出一个场景之后,我就需要一个相机控制器,来接收用户输入来移动和旋转相机,以实现场景漫游。

我打算使用Lua来编写这一逻辑。在计算相机的Transform时,需要进行一定的数学运算。这就需要一个Lua版的数学库

怎么给Lua写一个简洁高效的数学库,这并不是最近才开始思考的问题。

早些年在使用tolua框架时,就发现在Lua中进行数学计算时会产生大量的临时对象,极大的加重GC的负担。

虽然这两年时不时就会想起这个问题,也一直没有解决方案。

这次,在没有了Unity的包袱之后, 希望能找到一条全新的思路。

为什么在C#中写数学运算就不会产生GC呢。根本原因是,在C#中(vector3,quaternion,matrix)等对象都是struct类型,即值类型。这些对象都是在栈上分配,函数返回即销毁。就算当值返回,也是直接值拷贝出去的。

在Lua中,严格意义的值类型只有boolean,number两种类型。虽然string表现的像个值类型,但是临时string对象一样会产生内存垃圾。

所以我们一般实现vector3时,会使用Table或userdata来保存xyz。这是因为Lua中的值类型不足以装下xyz这么多数据。

一个很直觉的思路,我们能不能扩展Lua中的值类型,使他最多能包含xyzw四个字段。

答案是能,但是代价很大。内存的代价,性能的代价,以及维护的代价。

我仔细回忆了这几年有限的客户端经历,我发现数学运算都是扎堆的。

换句话说,我们的数学运算一般都是几个有限的输入和几处有限的输出。但是中间计算过程很复杂,只要解决了这些中间过程产生的临时变量,那也算基本符合预期了。

沿着这个思路,即然Lua中只有numbert和boolean是值类型,那我有没有可能用number来代表一个vector3或quaternion呢?

答案是肯定的。我们只需要用C实现一片额外的空间,然后用索引指向这个vector3或quaternion的值就大功告成了。

基于以上思路,我实现了一个数学栈。这个栈的范围只能在一个函数内使用。

如果你想将计算结果返回到另一个函数使用,你只能将栈中的值取出,然后显式返回给其他函数。

如果其他函数需要再次进行数学计算,就需要重新开辟一个数学栈空间。

大致用法如下:

local mathx = require "engine.math"
local camera_up = {x = 0, y = 0, z = 0}
local camera_forward = {x = 0, y = 0, z = 0}
local camera_right = {x = 0, y = 0, z = 0}

local stk<close> = mathx.begin()
print("rotation", component.get_quaternion(self))
local rot = stk:quaternion(component.get_quaternion(self))
local up = stk:mul(rot, stk:vector3f_up())
local forward = stk:mul(rot, stk:vector3f_forward())
local right = stk:mul(rot, stk:vector3f_right())
stk:save(up, camera_up)
stk:save(right, camera_right)
stk:save(forward, camera_forward)

首先使用math.begin()来创建一个数学栈,接着我们就可以在栈上进行各种数学计算。

当数学计算结束时,我们可以使用stk:save来取出数学栈中的xyzw的值。

stk:save有两种使用方式,当我们传入一个table时,stk会直接将xyzw的值置入table内。我们还可以不传入参数,这时stk:save就会根据值的类型返回xyz或xyzw的值。

这里使用了Lua的toclose特性, 当栈使用完之后,__close函数会自动将栈对象放入Cache中。

下次调用math.begin时,直接从Cache中分配,这样可以做到0内存分配。

在实现完这个库之后,我特意与xlua做了一个性能对比。

local stk<close> = math.begin()
local v1 = stk:vector3f(xx_v3_1)
local v2 = stk:vector3f(xx_v3_2)
v2 = stk:vector3f_cross(v1, v2)
v2 = stk:vector3f_cross(v1, v2)
v2 = stk:vector3f_cross(v1, v2)
v2 = stk:vector3f_cross(v1, v2)
stk:save(v2, xx_v3_2)

与同样逻辑的xlua写法对比,性能要高出300%左右。并且随着计算过程的增加,性能优势会越来越明显。

除此之外,在进行数学计算之前,我们往往需要获取到transform中的position,rotation,scale等属性。

这些属性要么是vector3, 要么是quaternion。如果我们用table或userdata来返回依然会加重GC负担。

仔细数一下其实这些数据类型最大也只有4个变量。因此,我让函数component.get_position直接返回xyz三个值,而component.get_rotation直接返回xyzw四个值。

至于是否需要存到table里,这个交由业务逻辑来控制。

谈谈跨平台图形API的抽象

本来按3月份的计划,是先把王者荣耀基本模式抄完 ,并以此为基础来抽象出一套基于Lua的通用客户端框架,然后根据需求再慢慢优化。

但是,3月底GAMES系列又出了一个新课GAMES104,《现代游戏引擎:从入门到实践》。

这门课一下子燃爆了我的兴趣,于是我决定暂停客户端框架的开发计划。学完GAMES104之后再回来继续开发客户端框架。

经过这几年的观察。我发现由于算力的缘故,很多高级的技术总是选应用于端游,然后再过很多年。才被用于手游开发(有时甚至还需要各种Trick才能跑得起来)。所以,要想学习和体验最新的引擎技术,最好还是通过端游引擎。

我打算趁着这次GAMES104的课程,写一个自己的引擎。

这个引擎应该使用最新的技术和最新的硬件特性。

这个引擎的业务逻辑语言为Lua。从表现力上讲,Lua要比C和C++强不少,虽然性能会慢一点,但是因为是实验性质的引擎,开发快反而会更重要。

这个引擎应该是跨平台的。虽然我的主要目标是端游,但是我也希望像在手机算力允许的情况下,可以在手机上玩耍。

我花了一周时间把vulkan教程上的例子抄了一遍(画一一个三角形,我竟然抄了3天半 ^_^!)。

然后就开始根据GAMES104的视频课程实现引擎了。

虽然第一版引擎以Vulkan图形API为基础,但是我还是希望能先抽象的个差不多的RHI(Render Hardware Interface), 为未来支持Direct3D和Metal打下基础。

这对我来讲很难,因为我没有任何Direct3D和Metal的基础,连Vulkan也只有一个星期的经验。

我还是想试一下。


一个最容易想到的方案是,为所有图形API设计相同的接口和相同的导出结构,然后使用宏来切换平台,这也正是RHI的表面含义.

伪码如下:

//-----rhi/texture.h------
namespace rhi {
    gpu_handle texture_create();
    texture_destroy(gpu_handle handle);
}
//-----rhi/texture.cpp-------
#ifdef RHI_VULKAN
#include "vulkan/texture.cpp"
#elseif RHI_DIRECT3D
#include "direct3d/texture.cpp"
#elseif RHI_METAL
#include "metal/texture.cpp"
#endif
//-----render/texture2d.h
namespace render {
    class texture2d {
    public:
        texture2d() {
            gpu_texture = texture_create();
        }
        ~texture2d() {
            texture_destroy(gpu_texture);
        }
    private:
        gpu_handle gpu_texture;
        int width;
        int height;
    }
}

但是这么做会有一些令人纠结的问题。

以texture2d为例,在Vulkan层面去使用texture时,部分情况是需要用到width和height,write_enable,filter_mode等属性,这时需要如何去获取这些属性。

这时有三种方案:

  • 第一种方案:在调用rhi::texture_create()时把所有需要用到的参数都传递过去,然后Vulkan层在内部保存供后面使用。这样做有两个坏处:数据冗余严重、需要额外的代码来将texture2d和gpu_texture之间的属性进行同步。

  • 第二种方案:在调用rhi::texture_create()时,直接把texture2d的this指针传递进去,Vulkan层在内部将gpu_texture和this进行绑定。Vulkan层在内部操作gpu_texture时可以通过这种绑定关系,查询到texture2d的指针,并读取相关设置信息。这么做同样也有坏处,首先是会产生循环引用,在render层textuer_2d引用了gpu_texture, 在vulkan层gpu_texture又引用了texture2d,然后是,因为rhi::texture_create的参数有了类型,那么就需要为每一种texture(textur2d, texture3d, cubemap)等添加一个texture_create/texture_destroy接口。

  • 第三种方案:在第二种方案的基础上,可以通过去掉gpu_handle的存在,来切断循环引用。

伪码如下:

//-----rhi/texture.h------
namespace rhi {
    bool texture_create(texture2d *tex);
    void texture_destroy(texture2d *tex);
}
//-----rhi/texture.cpp-------
#ifdef RHI_VULKAN
#include "vulkan/texture.cpp"
#elseif RHI_DIRECT3D
#include "direct3d/texture.cpp"
#elseif RHI_METAL
#include "metal/texture.cpp"
#endif
//-----render/texture2d.h
namespace render {
    class texture2d {
    public:
        texture2d() {
            rhi::texture_create(this);
        }
        ~texture2d() {
            rhi::texture_destroy(this);
        }
    private:
        int width;
        int height;
    }
}

当调用rhi::texture_create时,Vulkan层会创建一个texture的GPU资源,并这份GPU资源和texture2d指针进行绑定,但是这种绑定并不导出到外部接口使用。

后续操作某个GPU资源时,直接使用texture2d指针即可。

至于绑定方式,可以有多种多样,最简单直接方式就是使用unordered_map(显然性能并不会太高)。

第三种方案和第二种方案有一个通病,就是一个texture2d资源同时需要至少两个对象来表示,render层的texture2d和vulkan层的gpu_texture2d, 这会造成内存碎片问题。


花了2周时间反复重构了多次,都不太满意。

在重构过程中,我想到了一个全新的思路。

伪码如下:

//-----render/texture2d.h
namespace render {
    class texture2d {
    pubilc:
    static texture2d *create(int width, int height);
    static void destroy(texture2d *tex);
    protected:
        texture2d() {}
        ~texture2d() {}
    protected:
        gpu_handle gpu_texture;
        int width;
        int height;
    }
}

//-----vulkan/vk_texture2d.h
namespace vulkan {
    class vk_texture2d : public render::texture2d {
    public:
        vk_texture2d(int width, int height) : texture2d() {
            //todo some gpu create
        }
        ~vk_texture2d() {
            ~texture2d()
            //release some gpu resource
        }
    private:
        //some GPU-related resource
    }
}

//-----vulkan/vk_factory.h
namespace render {
    texture2d *texture2d::create(int width, int height) 
    {
        return new vk_texture2d(width, height);
    }
    void texture2d::destroy(texture2d *tex)
    {
        delete (vk_texture2d *)tex;
    }
}

在这次抽象中,我彻底去掉了RHI相关的所有中间层。而且几乎解决了上述方案中所有的缺点:内存碎片不存在了,循环引用没有了,GPU和CPU端数据的粘合逻辑消失了。

当然,这套抽象也有他自己的缺点:

但是,相比他能解决的问题,我觉得这两个问题都不算是大问题。

业务逻辑是使用Lua来做,所以本来也不会用到new来创建渲染对象。

少使用乃至不使用继承更是我一惯的坚持原则。

最后, 完整代码附上

寻路和Flocking算法的结合

最近本来在研究行为树, 然后无意间发现了一本名叫《Artificial Intelligence for Games, Second Edition》的书,就顺便看了起来。

书中第三章提到了一个Flocking算法,该算法一般用于模拟群体(羊群,鸟群,鱼群,人群)的移动行为。

这让我想起了大约一年前,他们QQ群里分享了一个蚁群行军的视频。当时为了研究他是如何时实现的,还特意去学习了VO,RVO算法(没有学会),最终也没有实现出来。

这次,我想用Flocking算法再试一次。


先简单介绍一下Flocking算法。

对于鸟群中的一只鸟而言,除了他本身要飞行的速度向量Velocity外,还有三个额外的分量来辅助校正最终的速度向量。

这三个额外分量分别如下:

Separation:每只鸟都会考虑到它们相对周围其他鸟的位置,如果过近,就会产生一个排斥速度分量。

Cohesion: 每只鸟都会检查自己半径R范围内鸟的位置,计算出这群鸟的质心,产生一个向质心靠拢的速度分量。

Alignment: 每只鸟都会检查自己半径R范围内的鸟的速度,计算出这群鸟的平均速度,然后产生一个向平均速度靠拢的速度分量。

最终每只鸟的速度为:Velocity + Separation + Cohesion + Alignment(在叠加过程中,可以根据情况给每个分量加上相应的权重)。

Flocking在没有障碍物的场景,比如天空,海底,平原等表现都很不错。但是一旦进入有障碍物的场景如蚁穴,就会很难工作。

这时就需要加入寻路系统来提供路径支持。


然而,事情并没有这么简单。

由于有SeparationCohesionAlignment速度分量的存在,即使我们给每只鸟单独寻出来一条路径,也不能保证这只鸟就一定会严格按照路径行走。

比如我们为某只鸟寻出来的路径为((0,0), (0,1),(0,2))(我们把地图切成很多小块格子,坐标为格子坐标,不是实际的世界坐标)。

在从(0,0)到(0,1)运行的过程中,由于鸟群的干扰,可能会把这只鸟挤到了(1,1)格子,这时可能(1,1)是到不了(0,2)的,需要重新寻路。

这就意味着,每只鸟每跨过一个格子,就需要重新寻路一次,这么大的开销足以使FPS降到5。


在网上搜到一种解决方案。

给整个鸟群指定一个Leader。为Leader计算一条路径,Leader严格按照路径行走。鸟群中的其他鸟使用Flocking算法来跟随Leader即可。

我尝试了这种方案后,发现这个方案在绕过大片障碍物时非常好用。但是在通过狭窄通道时,很容易发生跟随失败,导致一些鸟永远卡在那里不能行动。

比如下面这种情况:

                   xxxxxL
                  x
  ------------ x --------------
                  x
                   x
                      xB

Leader在位置L处,B位置处的鸟要跟随Leader,必然要产生一个从B位置向L位置的速度。

如果B鸟按这个跟随速度运动,就会被卡在墙的一侧,永远的脱离队伍。

我尝试优化这种方案,除了Leader之外,我加入了Target角色。

所有的鸟在运动时,会在自身周围一定范围内寻找一个Leader或Target作为跟随的目标。

找到跟随目标之后,自身也会变成Target角色,供其他鸟跟随。

如果找不到合适的跟随目标,自己就会变成临时Leader。然后重新计算一条路径,并严格按照路径运动。直到遇见一个合适的Target之后,这只鸟就会再次变回Target。

这种方案可以应对各种极端障碍物情况。但是这个方案几乎把Flocking所有的特性都抹掉了,鸟群在整个运动过程中会排成一字长蛇阵,看起来非常不自然。


我找到当时的QQ聊天记录,仔细读了几遍,然后换了个思路。

计划让鸟群运行到某个目标点那一刻,使用Dijkstra算法计算出地图上所有格子到目标点的最佳运动方向。

这里有个小技巧,我们使用目标点作起始点,然后运行Dijkstra算法。

当Open列表为空时,就已经完成了地图上所有格子到目标点的最佳方向计算。

每只鸟在移动前,根据当前位置计算出当前格子,然后直接查询出下一步的目标点。

理论上,根据目标点计算出鸟的Velocity速度向量,再叠加SeparationCohesionAlignment速度分量就是最终的速度值。

然而,现实是残酷的。

经过实验发现,由于鸟群的作用力,经常会有鸟被挤进障碍物中,尤其是在经过狭窄通道时。

因此我们还需要静态避障速度分量。

在《Artificial Intelligence for Games, Second Edition》中第“3.3.15 Obstacle and Wall Avoidance”节中,讲到可以使用射线检测来躲避静态障碍物。

测试发现,当角度比较奇葩时,射线检测不到障碍物的存在,从而导致最终被挤到墙里面去,3.3.15节也有提到过这种情况。

最终,我采用了AABB来检测周围是否存在障碍物,当有障碍物时,根据障碍物的质心和当前鸟的位置来产生一个远离障碍物的速度分量,这个分量的权重要显著大于其他4个速度分量。

如果障碍物形状态复杂时,可能需要重写AABB检测逻辑,根据相交的边计算出远离障碍物的速度分量。


到目前为止,最大的开销就剩下为地图上所有格子计算最佳方向了。

如果地图过大,这样计算是不现实的。

在写这篇文章时,我想到了一个优化算法,还没来得及测试。

通过观察Flocking算法,不难发现鸟群中的鸟几乎全是按照大致相同的路线行走的。

也就是说,只要我们想办法生成一个有宽度的路径,基本上就可以满足给鸟群寻路的需求了。

首先使用AStar算法,从整个鸟群的质心到目标点计算出一条路径。

然后,对第一步中路径的每个格子,都使用Dijkstra算法,计算出周边格子到这个格子的最短路径。计算时要限制Dijkstra算法遍历的深度。只要我们选取的深度合适,大部分鸟行走的格子都会被命中。

值得一提的是,在应用Dijkstra算法时,路径中相临格子的周围是相互覆盖的,需要根据权重进行刷新。

举个例子:

已经使用AStar算法计算出A到D的路径为(A,B,C,D)。

对格子B应用Dijkstra算法时,对邻居E生成了最佳运动方向为向B运动,E到D的权重为E(1)+B(2) = 3。

对格子C应用Dijkstra算法时,同样会处理到邻居E,这时不能简单的跳过E,而应该计算E到D的权重为E(1) + C(1) = 2。

这时应将E的最佳运动方向改为向C而不是B。

如果某只鸟被挤到了一个我们事先没有计算过的格子上,就使用AStar以此格子为原点向目标点寻路。

这里有一个可以优化的地方,我们已经有了一条很宽的路径,只要AStar寻到已有的路径格子就可以停止继续寻路了。

最后,Demo在此

行为树的一种高效实现

我的玩具项目中,需要有一定智能的NPC来辅助人类攻击防御塔。

通常实现智能会采用状态机,行为树,GOAP等技术。

GOAP技术我没有研究过,行为树在早些年大致了解过一些。因为觉得行为树性能太差,不可能取代状态机实现,之后就再也没有研究过了。

随着这些年我性能强迫症的好转,再加上听到行为树的次数逐年增加,我打算趁机仔细研究一下。

我找来《Behavior Trees in Robotics and AI》仔细读了一遍。这本书详细介绍了行为树,并且对比了行为树和状态机之间的优劣。

根据《Behavior Trees in Robotics and AI》描述,行为树一般有4种控制节点(Sequence, Fallback, Parallel, Decorator)和两种执行节点(Action和Condition)。只有执行节点才能成为叶子节点。

先来简单描述一下最重要的两种控制节点, Sequence和Fallback。

Sequence节点: 当执行Sequence节点时,从左往右顺序执行子节点,直到某一个子节点返回Failure或Running状态,伪码如下:

//Algorithm 1: Pseudocode of a Sequence node with N children
for i 1 to N do
    childStatus <- Tick(child(i))
    if childStatus = Running then
        return Running
    else if childStatus = Failure then
        return Failure
return Success

Fallback节点:当执行Fallback节点时,从左往右顺序执行子节点,直到某一个子节点返回Success or Running状态,伪码如下:

//Algorithm 2: Pseudocode of a Fallback node with N children
for i 1 to N do
    childStatus <- Tick(child(i))
    if childStatus = Running then
        return Running
    else if childStatus = Success then
        return Success
return Failure

Action和Condition节点,是我们具体的业务逻辑,不是本次优化的重点。


对比行为树和状态机可以发现,行为树比状态机额外多出的开销, 就是在执行执行节点之前,必须要先穿过控制节点

如果我们在运行时能避过控制节点,只执行执行节点,那行为树和状态机的开销差别就只是多了几次函数调用而已。

仔细思考过之后, 我认为这是可能的。

结合上面对Sequence和Fallback节点的定义。我们不难发现,在编程语言中,Sequence就是and(与)逻辑,而Fallback就是or(或)逻辑。

整棵行为树的控制节点就是用来描述if-else的逻辑,叶子节点是相应的业务逻辑。从这个角度来看,行为树和语法树有颇多相似之处。

不难发现,整棵树的执行路径,其实依赖于特定执行节点的特定返回值。

某一个执行节点(叶子节点)返回Failure或Success, 整棵行为树下一步要执行的执行节点是固定的。

某个执行节点返回Running, 整棵树就停止执行。在下一Tick之后从头执行,这种情况比较简单,暂时不需要考虑。

来看一棵简单的行为树:

如果 Action 1 Done 返回Success,下一步将要执行的执行节点(叶子节点)就是 Actino 2 Done
如果 Action 1 Done 返回Failure, 下一步将要执行的执行节点(叶子节点)就是 Action 1

这种逻辑可以递归到所有的执行节点

这样,我们只需要两张跳转表(Success跳转表,Failure跳转表),就可以在运行时,以状态机的开销来实现行为树的功能。

以上面的行为树为例,我们可以生成如下跳转表:

local tree = {
["Action 1 Done"] = {
    ["Success"] = "Action 2 Done",
    ["Failure"] = "Action 1"
},
["Action 1"] = {
    ["Success"] = "Action 2 Done",
    ["Failure"] = nil, --nil 代表整棵树执行结束
},
["Action 2 Done"] = {
    ["Success"] = nil,
    ["Failure"] = "Action 2"
},
["Action 2"] = {
    ["Success"] = nil,
    ["Failure"] = nil,
}
}

在运行时,我们首先执行整棵行为树的第一个节点"Action 1 Done"。

如果"Action 1 Done"返回Success, 根据表tree可知,下一步需要执行的是"Action 2 Done"。

如果"Action 2 Done"返回Failure, 根据表tree可知,下一步需要执行的是"Action 2"。

这样我们仅需要生成一个跳转表,就可以在运行时抹掉所有控制节点所带来的开销。

最终,我花了200行代码实现了根据行为树生成上述跳转表的逻辑。

PS.我把生成跳转表的行为称之为编译。如果控制节点是Parallel或Decorator类型,或者有记忆功能。在编译过程中,需要将其保留,不能将其编译掉。不然无法完成和行为树等价的逻辑。

PPS. 在示例代码,我使用了behavior3来编辑行为树。

内测过程中Shader出现的问题

兜兜转转一年多, 终于再次内测了。

这次在客户端开发中,我们的指导思想是能用GPU做的坚决不用CPU做,除非GPU出现了瓶颈。因此我们大量使用了自定义Shader。

由于我之前其实没有太多Shader的编写经验,这次上线之后暴露了不少实践性问题。


首先遇到的就是精度问题。

在地表渲染过程中, 如果碰到下雨天,我们会在地面湿滑到一定程度之后生成涟漪。

这个功能是直接做在地形Shader中的,与涟漪Bug相关的代码如下:

//ripple.a = 0.4117647
float f1 = frac(ripple.a + _Time.y);

上线之后,我们发现在小米系列手机上,当_Time.y的值大于300之后, f1的值会产生跳变。

经过抓帧之后发现。

_Time.y``300.033``f`等于`0.5019608`, 此时`f`的正确值应该是`0.4447647

_Time.y``300.066`时,`f`的值还是等于`0.5019608`, 此时`f`的正确值应该是`0.4777647

将代码改为如下:

//ripple.a = 0.4117647
float f1 = frac(ripple.a + frac(_Time.y));

_Time.y``300.033``300.066`时,f1的值分别为`0.4431373``0.4784314

与正确值相比,误差分别是0.0016274``0.0006667

这些数值是通过颜色调试法取得,而像素的颜色精度只有1/255(0.0039216), 因此可以认为误差是颜色调试法带来的,而整个计算是精准的。

这说明了高通系列的GPU,其float在计算过程中,要比IEEE 754标准的浮点型精度更低,可能远小于7位有效数字。

这也给我提了一个醒,当我们的Shader需要长时间运行时,一定要注意_Time.y过大之后,在运算过程中会精度丢失的问题。即使GPU完全按照IEEE 754标准来实现,只要运行的时间足够久,也会出现这个问题(比如我们的树,在所有客户端上,只要运行超过4个小时之后,就会静止不动)。

有些情况下,不是简单加一个frac函数就能解决问题的。这时,就需要将与_Time.y相关的数值移到C#中去计算,然后在每一帧的Update中,向Shader设置变量,这么做会有一个额外好处,可以将对_Time.y相关的计算减少到每帧一次。如果在shader中计算_Time.y相关的逻辑,则每一个顶点或像素都需要重新计算一次。


另外一个Bug还是与精度有关,不过是以另一种方式存在。

在世界地图中,如果玩家立国,需要将国家的颜色铺满整个行省,而行省的形状是异形的,如果使用Quad的方式去铺满整个地图,会带来大量的Overdraw。

因此在实现过程中,我们给整个大地图设计了一张IDMap, 每一个像素都会有一个整数ID来代表他所在的行省。

在FragmentShader中,我们采样IDMap之后,并不直接用于渲染,而是将他转换成整数ID,然后使用ID来当索引查询当前行省的颜色。将查询到的颜色用于渲染。

大概代码如下:

fixed4 frag (v2f i) : SV_Target
{
    fixed4 c = tex2D(_MainTex, i.uv);
    int n = clamp(c.a * 255, 0.0, 45.0);
    return _Colors[n];
}

上线之后,我们发现在华为系列手机,这个n会有偏差(安卓系统和鸿蒙系统表现还不太一样),但是在国内其他主流手机,如小米,Oppo上不会出现。

在问题排查过程中,我一度怀疑是精度问题。因此不停地在图片格式上做文章。直到最后我才发现我犯了一些常识性错误。

首先,RGBA32格式的图片是指RGBA的4个通道分别占用一个byte(8bit)来表示一个通道颜色值。

图片文件中,实际存储的颜色值是0~255的整型,而不是0~1的浮点型,也就是说单通道精度最高也只能到1/255。

而我们实际使用过程中n的值只是0~45,远低于1/255,不可能是图片精度问题。

其次,在计算过程中 1/255*255 `的结果实际上并不是`1`而是`0.99999999999975左右。

在Intel、AMD、高通系列芯片上,int a = (int)(1.0 / 255.0 * 255.0), a是会等于1的。

在麒麟系列芯片,a则会等于0,我不能说麒麟系列芯片的精度够或是不够,只能说我写的代码不规范。

这次的教训告诉我,浮点型在不同平台的实现过程中,会有平台相关性。

定位到了问题,修复自然就是一件很简单的事。

int n = clamp(round(c.a * 255), 0.0, 45.0);

或者

int n = clamp(c.a * 255 + 0.0000001, 0.0, 45.0);

都可以解决问题。

彻底解决多国语言

最近,我在抄王者荣耀玩。而多国语言自然是一个避不开的问题。

在这次的设计中,UI系统我采用了FairyGui

FairyGUI通过“字符串表”和“分支”功能提供了多国语言解决方案。

FairyGUI把用到的所有文字导出到一个xml文件中,然后为每个外国语言翻译一个相应的xml文件(字符串表),只要在运行时加载相应的xml文件,就可以将所有UI上的文字自动切换到相应的语言。

当然多国语言不止有文字,还有图片等资源。FairyGUI可以为每个外国语言设置一个分支(假设所有外国语言都需要使用不同的图片),每个分支上可以使用不同的图片、布局等,只要执行 UIPackage.branch = "en";,打开UI时就会显示对应分支的UI。这样就实现了非文字类多国语言的方案。

这案相当惊艳,对我有不小的启发。


虽然FairyGUI已经有了相当完美的多国语言方案,但是游戏不仅仅只有UI,一些非UI部分同样会有多国语言的需求,比如不同国家玩家看到的英雄的Tips, 一些3D素材等。

因此,业务逻辑还需要一个自己的多国语言模块,这部分我6年前就实现过

但是,FairyGUI的多国语言方案让我意识到一个事实,多国语言应该是一种和业务逻辑无关的需求。因此理论上,业务程序员不需要关心多国语言的存在,仅策划和美术关心就够了。

之前的设计中,所有多国语言的显示,都需要业务程序员干预,比如写一条local str = multi_lan.get(key)

如果显示多国语言的UI设计有变动,业务程序员就要相应的增加或删减multi_lan.get语句。

这违反了Open-Close原则,同时增加了业务程序的心智负担。

我希望这次可以更近一步,业务程序员完全不需要干预

我重新思考了一下整个游戏的运行流程后发现,屏幕上的所有显示内容其实都是来源于配置。游戏逻辑代码中不需要也不应该去写死每一个字符串(文字或资源路径)。

这样只要我们从配置入手,就可以在底层彻底解决多国语言的问题。

虽然,新的设计要比之前复杂很多。但是,大部分开销和复杂度都在离线(打表)逻辑,运行时代价不高。

按以往的经验,程序需要的配置表往往不是策划直接操作的第一格式。

策划大都是先用Excel来配置相关数据,之后再使用程序提供的配置生成工具,将Excel文件转换为程序使用的配置表格式。

这次多国语言的主角就是这个配置生成工具


由于Excel的特性, 一般在使用Excel文件作配置表时,都会使用关系型数据库的思路来操作。即先设计表结构,再填充表内容。

比如一个Hero表的Excel文件格式可能是下面这样:

HeroID HeroName HeroTips HeroSpeed
int(a) string(c) string(c) int(s)
1000 刘备 刘皇叔是大哥 100
1001 关羽 关云长是二哥 50
1002 张飞 张翼德是小弟 50

第一行用于标识每一列数据的字段名。

第二行用于标识每一个字段的类型(int, string), 以及是被客户端(c、a), 还是服务端(s、a)使用。

第三行开始(包括)就是真正的配置数据。

按照之前的多国语言思路,整个流程大致是这样的。

先将上述Hero表拆分为Hero表和Language表。 Hero表用来配置Hero相关信息的,Language表用于配置多国语言信息。

Hero表:

HeroID HeroName HeroTips HeroSpeed
int(a) string(c) string(c) int(s)
1000 HeroName_1000 HeroTips_1000 100
1001 HeroName_1001 HeroTips_1001 50
1002 HeroName_1002 HeroTips_1002 50

Language表:

Key Value
string(c) string(c)
HeroName_1000 刘备
HeroName_1001 关羽
HeroName_1002 张飞
HeroTips_1000 刘皇叔是大哥
HeroTips_1001 关云长是二哥
HeroTips_1002 张翼德是小弟

然后在需要显示HeroName和HeroTips的地方(即使HeroTips是资源路径同样适用)使用如下代码:

local id = 1000
local name = Language[Hero[id].HeroName]
local tips = Language[Hero[id].HeroTips]

上述工作流有不少弊端:

  1. 程序不满足Open-Close原则,业务程序员需要关心哪些字段是需要做多国语言处理的,一旦UI改了表现设计,可能需要程序修改代码。相比之下,改了UI表现的FairyGUI却不需要修改业务逻辑代码。

  2. 对策划不友好,策划需要手工维护Hero表和Language表之间的同步,人类极不擅长这类工作。这使用两表之间同步极易出错,而且不易发现(只有在运行时用到配错的那一行数据时,才能发现错误)。就算是使用自动化测试都不太可能覆盖表中100%的数据。

  3. 由于人类极不擅长Hero和Language表之间的同步,导致策划在修改Language表时,往往只增加不删除,这会导致Language越来越大。以我的经验来讲,这种情况是存在的,尤其是对于半路接手的策划。

  4. 由于所有跟文字相关的内容都被移到Language表中,这导致Hero表的可读性下降,往往打开一个Hero.xls之后,你找不到“刘备”是哪个。策划们的通常做法是再加一个字段, 这个字段即不用于客户端也不用于服务端, 仅用增加可读性。但是,增加了一个字段的同时,又增加了维护数据之间同步的工作量,出错的概率更大了。


新的多国语言设计中,我为Excel文件引入了lan类型。

lan类型不仅表明这个字段是一个字符串类型,还表明这个字段对于每个外国语言都有一个不同的值。

我们的Hero表最终配置如下:

HeroID HeroName HeroTips HeroSpeed
int(a) lan(c) lan(c) int(s)
1000 刘备 刘皇叔是大哥 100
1001 关羽 关云长是二哥 50
1002 张飞 张翼德是小弟 50

是的,策划的工作仅仅是把需要进行多国语言处理的字段由string改成lan即可(当然根据需要可以扩展为lan[](c)等列表类型)。

配置生成工具会有一个选项叫做导出多国语言文件,用于导出所有表中类型为lan的字段。

配置生成工具总是会在输出文件的末尾追加新添加的文字。而已经翻译过的文字保持不变。

导出的语言文件Lan.xlsx如下:

CN
刘备
关羽
张飞
刘皇叔是大哥
关云长是二哥
张翼德是小弟

在Lan.xlsx中添加要支持的语言及翻译内容,例如添加英语支持:(注:配置生成工具不会也不应该修改已经翻译过的文字, 如果某一列已经删除,可以将这一列移动第二个Sheet中去,以做备份)

CN EN
刘备 Liu Bei
关羽 Guan Yu
张飞 Zhang Fei
刘皇叔是大哥 Uncle Liu is the eldest brother
关云长是二哥 Guan Yunchang is the second brother
张翼德是小弟 Zhang Yide is the younger brother

再使用配置生成工具中的导出配置文件功能, 生成客户端和服务端需要使用的配置即可(这里可以使用增量导出功能, 参考Makefile的做法)。

至于配置生成工具到底如何工作,采用不同的配置文件格式有不同的做法。

以Lua为例,我们导出的配置文件如下:

--hero.lua
local lan = require LAN .. ".hero"
local M =  {
[1000] = {
    HeroID = 1000,
    HeroName = lan.HeroName_1000,
    HeroTips = lan.HeroTips_1000,
    HeroSpeed = 100,
},
[1001] = {
    HeroID = 1001,
    HeroName = lan.HeroName_1001,
    HeroTips = lan.HeroTips_1001,
    HeroSpeed = 50,
},
[1002] = {
    HeroID = 1002,
    HeroName = lan.HeroName_1002,
    HeroTips = lan.HeroTips_1002,
    HeroSpeed = 50,
},
}
return M
--cn/hero.lua
local M = {
HeroName_1000 = '刘备',
HeroName_1001 = '关羽',
HeroName_1002 = '张飞',
HeroTips_1000 = '刘皇叔是大哥',
HeroTips_1001 = '关云长是二哥',
HeroTips_1002 = '张翼德是小弟',
}
return M
--en/hero.lua
local M = {
HeroName_1000 = 'Liu Bei',
HeroName_1001 = 'Guan Yu',
HeroName_1002 = 'Zhang Fei',
HeroTips_1000 = 'Uncle Liu is the eldest brother',
HeroTips_1001 = 'Guan Yunchang is the second brother',
HeroTips_1002 = 'Zhang Yide is the younger brother',
}
return M

有同学说,你这个和策划配出来的XML格式并没有什么不同啊,优势在哪里。

以写代码而论,本质上你写的高级语言和汇编并没有什么不同。为什么你要写高级语言呢,因为写的效率高,出错概率小。

有了这个思路,再次对比上面新旧两种多国语言方案的优劣:

新的多国语言方案,策划只需要做两件事就能保证一定正确:1. 配置正确的lan类型。 2. 给出正确的翻译文本

旧的多国语言方案, 同步Language和Hero表有负担,一旦同步错误不容易发现,没有特殊手段清理Language表中废弃的行,Hero.xls表失去可读性等各种缺点。