为silly增加了互斥锁

silly是基于Lua语言的Coroutine机制而实现的一个高并发网络框架。

其coroutine调度机制很简单,所有的函数都被包裹在coroutine中被执行,当代码调用socket.read/core.sleep等指定API时,当前coroutine会挂起,直到socket.read/core.sleep返回结果为止。在此coroutine被挂起期间,会将CPU调度给其他coroutine来运行。

大部分情况下,基于coroutine编程和基于多线程编程的思路是一致的。

例外就是,由于是调用指定API时才会挂起当前coroutine,相比多线程而言,基于coroutine的调度机制会引入一个缺点和一个优点。

缺点就是,如果不慎编写死循环代码,当前coroutine永远也不会挂起,其他coroutine永远也得不到执行的机会。

优点刚好就是缺点的另一面,由于只在调用指定API才会挂起当前coroutine, 我们可以在coroutine中安心的修改所有数据而不必担心由于调度的不确定性而产生数据竞争问题。同样由于我们在需要挂起时才挂起,所有不必要的上下文切换都可以避免,可以极大地减少上下文切换的开销。


一直以来,我都认为mutex是为了解决抢占式调度的不确定性才被发明的。由于silly不存在抢占式调度,所以没有必要实现一个mutex锁。

但是就我这几年的经验来看,不管是不是抢占式调度,并发问题始终都存在。

只不过非抢占式调度所造成的影响范围更少,以致为我认为那不是并发的问题,是异步的问题(现在回头看看这两个概念也没有分得这么清楚)。

对于这种异步问题,我通常的做法,要么是做惰性队列,要么是做失败补偿。都是针对特定业务逻辑case by case的去实现。并没有一套成熟通用的方案。

下面来看两个例子(一个基于失败补偿,一个基于惰性队列):

---失败被偿
local user = {
    money = 100
}

func Foo() {
    if user.money < 50 then
        return false
    end
    user.money = user.money - 50
    ok = rpc:call("FooOtherService")
    if !ok {
        user.money = user.money + 50
    }
    return ok
}

func Bar() {
    if user.money < 60 then
        return false 
    end
    user.money = user.money - 60
    ok = rpc:call("BarOtherService")
    if !ok {
        user.money = user.money + 60
    }
    return ok
}
---惰性队列
local user = {
    money = 100,
    q = nil,
}

func enter() {
    if user.q then
        table.insert(user.q, core.running())
        core.wait()
    } else {
        user.q = {}
    }
}

func leave() {
    if user.q then
        co := table.remove(user.q, 1)
        if not co then
            user.q = nil
        else
            core.wakeup(co)
        end
    end
}

func Foo() {
    enter()
    if user.money < 50 then
        return false 
    end
    ok = rpc:call("FooOtherService")
    if ok {
        user.money = user.money - 50
    }
    leave()
    return ok
}

func Bar() {
    enter()
    if user.money < 60 then
        return false 
    end
    ok = rpc:call("BarOtherService")
    if ok {
        user.money = user.money - 60
    }
    leave()
    return ok
}

对比上面两段代码,可以发现,失败补偿逻辑基本没有任何被抽象的可能。

惰性队列虽然可以借助于Lua语言的动态性来抽象成库,但他只能解决单层异步问题,再复杂的异步问题惰性队列就无法完美抽象了。

还是上面的代码,假如Bar函数改为如下需求, 就需要新增一个惰性队列来处理。不然就会产生死锁。

local user = {
    money = 100,
    money2 = 100,
    q = nil,
    q2 = nil,
}

func enter(obj, name) {
    if obj[name] then
        table.insert(obj[name], core.running())
        core.wait()
    } else {
        obj[name] = {}
    }
}

func leave(obj, name) {
    if obj[name] then
        co := table.remove(obj[name], 1)
        if not co then
            obj[name] = nil
        else
            core.wakeup(co)
        end
    end
}

func Foo() {
    enter(user, "q")
    if user.money < 50 then
        return false 
    end
    ok = rpc:call("FooOtherService")
    if ok {
        user.money = user.money - 50
    }
    leave(user, "q")
    return ok
}

func Bar() {
    enter(user, "q2")
    if user.money2 < 60 then
        return false 
    end
    --do something
    ok := Foo()
    if ok {
        user.money2 = user.money2 - 60
    }
    leave(user, "q2")
}

最近突然觉得把这类问题归结于并发问题, 一把可重入锁就可以完美解决上面所有问题。

比如下面代码:

local user = {
    money = 100,
    money2 = 100,
    lock = lock:new()
}

func Foo() {
    local guad<close> = user.lock()
    if user.money < 50 then
        return fales
    end
    ok = rpc:call("FooOtherService")
    if ok {
        user.money = user.money - 50
    }
    return ok
}

func Bar() {
    local guad<close> = user.lock()
    if user.money2 < 60 then
        return false 
    end
    --do something
    ok := Foo()
    if ok {
        user.money2 = user.money2 - 60
    }
}

由于锁是可重入的,所以同一个coroutine内的函数者都可以加锁成功,这样不管后期这个模块怎么修改,模块内都不会产生死锁效果。

按照传统方式,一个锁在使用之前是需要new出来并初始化的,在一些极端场景(比如我之前的经历,有400W个格子)可能会需要new出来很多锁。

由于我们的非抢占式调度的机制,大部分情况下,锁冲突的概率很小,所有需要锁的地方都new一个锁,在这种场合下稍嫌浪费。

换句话说,虽然我们需要实现一把互斥锁,但是他是乐观的。

基于以上思路,我换了一种锁的实现方式,它的使用方式大概如下:

local mutex = require "sys.sync.mutex"
local user = {
    money = 100,
    money2 = 100,
}

func Foo() {
    local guad<close> = mutex.lock(user)
    if user.money < 50 then
        return fales
    end
    ok = rpc:call("FooOtherService")
    if ok {
        user.money = user.money - 50
    }
    return ok
}

func Bar() {
    local guad<close> = mutex.lock(user)
    if user.money2 < 60 then
        return false 
    end
    --do something
    ok := Foo()
    if ok {
        user.money2 = user.money2 - 60
    }
}

基于乐观锁的前提,这个锁被分配出来之后几乎不会发生碰撞,很快就会被释放掉。

我们在mutex内部可以做一些内存优化,比如我们做一个mutex cache, 当一把锁释放后就放入mutex cache中,当我们需要一个锁时先尝试从cache中分配等。

这样我们就有了一种通用的抽象方案。

ps. 写这篇文章时,我特意去查了wiki, 互斥锁原本就是为了解决并发问题而存在的,这种并发并不局限于抢占式并发还是非抢占式并发。

2022(完)

2022年终于过完了,细细数来,有用时间真的比往年都短。

我翻了翻Blog, 几乎没有什么转折性的收获。

因为服务器一直找不到突破方向,打算在客户端方向努努力。

年初的打算是,先打磨出一个可用的,基于Lua的客户端框架,以便能更深刻理解客户端的全部开发流程(虽然我改过客户端框架,写过还算可用的热更新框架,也写了一些Shader。 但是对于从0实现一个客户端框架,我确实没有经验)。

框架由具体需求驱动。因为我不是专业搞客户端的,所以边抄一个游戏,边实现框架是目前来讲最好的方式。

刚好这时我在网上找到了类似《王者荣耀》的全套资源,那就先抄个王者荣耀试试吧。

UI方面,我接入了FairyGUI

在接入时,我灵光一现,设计了一套多国语言机制。即使一年后今天,我重新审视这套机制,也并不能发现任何缺点。

这套机制几乎可以实现在任何语言和任何表结构下。

王者荣耀,地图中会有很多小兵参与战斗。

因此在做完登录流程之后,小兵的AI就是下一步要做的事。

游戏AI,行为树几乎是必不可少的标配。它对策划同学太友好了,实现起来复杂度又不高。

在看完《Behavior Trees in Robotics and AI》书中描述的行为树后。

我观察到一个现象,行为树表达出的逻辑,其实是状态机的一个子集。

在经过不复杂的“编译”过程后。我们可以做到在运行时以状态机的开销,来达成行为树描述的逻辑。

这样可以大大提升行为树的运行效率(对于策划而言,使用上还是行为树,只是在运行前才会将整棵树编译成一张跳转表)。

在研究行为树的过程中,发现了一本叫《Artificial Intelligence for Games, Second Edition》的书。

这本书中提到了一种叫做Flocking的算法,以前就对此类算法很有兴趣,就趁机研究了一下

后面两个月,其实就只干了一件事,抢菜。

复工之后,由于公开课《现代游戏引擎:从入门到实践》的出现,我暂停了实现客户端框架的计划。

相比实现一个客户端框架,从0实现一个客户端引擎,更能引起我的兴趣。

虽然此时的我,还没有写过一行Vulkan代码,没有看过如UE之类的开源引擎代码。

但依然想试着,根据课程内容和Unity的使用经验,来实现一个玩具引擎

在能基本渲染出一个场景后,我就迫不及待想要使用键盘来控制相机的移动。

在实现相关逻辑时,我重新思考了如何使用Lua,高效地编写3D数学相关代码

由于之前基于Vulkan抽象出来的RHI不够好(使用起来很别扭),再加上了解到了Bindless这一黑魔法。

打算将引擎直接重构成基于Bindless的RHI抽象。

比较惨的是,刚抽象完,公司就倒闭了,被迫中止客户端相关知识的学习。

根据市场需要,从零开始学习Go语言。

Go语言的优劣,我不想评判。但是他有很多不错的闪光点。

比如:这个这个还有这个

然后这个年就过完了。

再简单总结一下。

2022年技术上一共就干了三件事,结果还都没有一个完成的。

  1. 客户端框架,只做完UI相关部分
  2. 客户端引擎,只做到基于Bindless RHI的抽象,shader接口,资源格式等都还没有设计
  3. Go语言,只熟悉了,工作用最常用的底层机制,对调度及编译优化等相关的知识并不深入

2023年学习的时间不可能像以前那么多了,那么就少安排任务吧:

  1. 继续熟悉Go语言
  2. 熟悉K8S, etcd, kafka,ELK等这些在Go圈常用的基础设施
  3. 放弃之前基于静态容量的分布式架构设计,基于K8S来重新设计一套可以动态伸缩的服务器架构
  4. 研究ECS在服务端的应用

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有颇多相似之处。

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

一例误用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在此