云风的 BLOG: 读了一点 go 的源码

首先是 runtime 里的 hashmap ，想看看 go 的 hashmap 和 lua 的有什么区别。

结论就是 go 的比 lua 的实现复杂的多（lua 的 ltable.c 不到 600 行代码，go 的 hashmap.c 有超过 1500 行）。go 的 hashmap 更注重于空间效率。go 的 map 是有类型的，key value 类型都固定，存在类型描述结构里。key value 的大小在编译期都不固定，但在构造时就可以确定了。

hash 值是一个 uintptr ，在 64 位系统下是 8 字节。key 的 hash 值是不完整保存在 hashmap 的结构中，那样太浪费。Lua 同样也不会把 hash 值保存在表中，但 Lua 的类型很少且固定，所以比较好处理。

go 的 map key 类型可以用户自定义，每次重新调用类型的对应方法计算 hash 值恐怕有性能问题。go 的折中方法是，在 hash 表里只保存 hash 值中的一个字节。

key/value 对以 8 个一组保存在一个叫 Bucket 的结构中，这组 key 的 hash 值和表的大小（2 的整数次幂）取 and 后有相同的值，然后再用高位字节做进一步区分以加快检索效率。如果一个 Bucket 不只 8 对值，就用链表扩展。

注意：0 作为特殊 hash 值对待，表示 Bucket 中这一项为空。如果 hash 值的高字节的确是 0, 就改为 1 。

当表中存放的总量相对表的 slot 数超过一定量后，就扩展 hash 表的 slot 位之前的两倍。这个类似于 lua 的策略。但 lua 是闭散列的，go 是开散列的。扩展阈值 LOAD = 6.5 倍是一个经验数值。

个人判断采用开散列有利于多线程的实现（空间不够时不是必须做扩展）。

目测 go 的 map 是不可以并发写的，但可以并发读。另需解决的问题是迭代过程中的插入。go 有专门的 map 迭代器，这会比 lua 的迭代方法效率更高（Lua 的迭代是无状态的，每次都需要做一次 hash ）。但如果在迭代过程中如果表增长了，迭代器就有可能迭代旧数组。

go 的解决方法是同时保存新数组和老数组，直到迭代器销毁才释放旧数组。

是否在迭代中用 hash 表结构中的 flags 控制，为了支持并发读，用了 CAS 指令做无锁设计。

我没读 go 的源码之前有一个疑问，就是 go 支持海量 goroutine 如何解决 stack 空间占用问题的。lua 的 coroutine 没有这个问题是因为 lua 是在虚拟机内运行，自己在 heap 上开辟空间保存 VM 中的 stack ，lua 5.2 中的 coroutine 的基本内存开销仅有 208 字节（64 位系统下）。

但 go 是要编译成本地代码的，并且需要和传统的 C 代码做交互。它需要使用传统的 stack 模型。这样就必须让 stack 大小可以动态增长且不必连续。

事实上 go 的确是这样的，如果你写一个无限递归的 go 函数，它不会像 C 函数那样很快就 stackoverflow ，而仅仅是一点点吃掉内存而已。

解决这个问题的方法是采用一种叫作 Split Stacks 或是 segmented stacks 的技术。我们只需要在函数调用的时候检查当前堆栈的容量，如果快用净就新申请一块内存，并把栈指针指过去。当函数返回后，再把栈指针修改回来即可。

透明的作到这点需要增强编译器，更准确的说，我们增强链接器即可。因为与其在编译时给函数调用前后插入代码，不如在链接过程给链入的函数加一个壳。并且可以通过 #pragma 给链接器提供建议。

具体分析可以见这篇文章。我顺着读到 gcc 对 splitstack 的扩展支持，如果能让 gcc 对这个支持良好，那么就可以实现一个不错的 coroutine 库了。

不过我对里面提到的向前兼容的方案有点意见。当调用原来没有经过 splitstack 编译链接过的 C 库时，文章里提到分配一块足够大（64K）的栈空间供其使用。10 年前，我为梦幻西游的客户端实现过一个简单的 coroutine 库，由于需要开辟上千条 coroutine (当时物理内存只保证有 128M ），我只给每条 coroutine 预留了 4k 空间。那么在 coroutine 里像调用传统函数，只需要把 stack 指针切回到当前系统线程的 stack 上即可。

这样做可行是因为，之所以我们需要为 coroutine 保留独立 stack ，是因为 coroutine 中可以通过 yield 保存延续点，以后需要跳回。但传统函数里绝对不可能调用 yield ，我们就可以断言这些函数运行时，当前线程不会有任何其它 coroutine 的执行序混于其间。一个线程的所有 coroutine 都可以共享一个栈空间来执行这些传统函数。

读 go 的源代码时发现一个有趣的东西，那就是 go 自己实现了一个 C 编译器来编译 C 代码。这样可以更好的和 go 的目标代码链接在一起。go 是有一整套包系统的，所以编译器为 C 扩展了带 namespace 的api 语法。

不像 C++ 用 :: 来切分 namespace ，go 的 C 编译器采用了一个非 ascii 的符号 · ，粗看像 . 但却是我们用来分割人名用的小圆点。

我很好奇洋人们怎么输入这个符号。当然对中国人来说方便的很，只需要在中文符号输入状态下按 @ 就够了。