钰儿的Blog

上一篇主要讲了 Lua代码 的运作过程，这一篇主讲 Lua Table 和 基于 MetaTable 实现的 MetaMethod。

其实我觉得，Lua之所以能大放异彩，其一是它非常精小，其二是其开源，其三则是因为它的MetaMethod 的设计。

Lua 类型

虽然本篇主要讲 table，不过在那之前，最好先来认识一下 Lua 其他类型在 Lua解释器中的实现。

UserData 暂且不谈，NUMBER细分为浮点数和整数，字符串则分长短字符串，函数又分Lua函数和C函数还有轻量的C函数，这一部分会分别留到字符串和闭包的时候再谈论。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#define LUA_TNIL		0
#define LUA_TBOOLEAN		1
#define LUA_TLIGHTUSERDATA	2
#define LUA_TNUMBER		3
#define LUA_TSTRING		4
#define LUA_TTABLE		5
#define LUA_TFUNCTION		6
#define LUA_TUSERDATA		7
#define LUA_TTHREAD		8

#define LUA_TNUMFLT	(LUA_TNUMBER | (0 << 4))  /* float numbers */
#define LUA_TNUMINT	(LUA_TNUMBER | (1 << 4))  /* integer numbers */

#define LUA_TSHRSTR	(LUA_TSTRING | (0 << 4))  /* short strings */
#define LUA_TLNGSTR	(LUA_TSTRING | (1 << 4))  /* long strings */

#define LUA_TLCL	(LUA_TFUNCTION | (0 << 4))  /* Lua closure */
#define LUA_TLCF	(LUA_TFUNCTION | (1 << 4))  /* light C function */
#define LUA_TCCL	(LUA_TFUNCTION | (2 << 4))  /* C closure */

其实在此之前已经写了一个 Lua 5.3 源码剖析系列，还有好几篇存档没有发。为什么突然又不发了呢？（甚至还删了），是因为我感觉之前那样学习的方式过于难受，折磨心智（人这一生最不该做的就是折磨自己），没有抓清主次，同时和网络上的博文同质化严重。因此就决定，再读一次 Lua 的源码，这次读的是 Lua 5.3.6 是 Lua 5.3 系列的最后一个版本。

本系列，不会谈论 Lua 语法，也默认读者已经有 Lua使用经验，我们将绕过 Lua 的编译器（大部分都是词法语法分析），直接进入到 Lua解释器中，来学习我们写好的 Lua 源码是怎么跑起来的。为了理解的方便，代码会有大量删减，只抽取其核心。

Lua 编译过程

虽然，我们在一开始就说好，不谈论 Lua 编译器，但是还是要先理解 Lua 的运行机制。这里简单提一下，你写好的 xxx.lua 文件 会经过 luac 工具将 Lua源代码编译成 二进制文件，Lua 作者在代码中称其为 Chunk，接着 Lua解释器会加载它并执行，所以 Lua执行起来，看起来是边执行边编译，但实际上是先编译成 Chunk，再加载 Chunk去执行。

加载 Chunk

假设我们现在有一段 lua代码，且已经过了 luac工具 编译出了 Chunk，那么 Lua解释器是怎么将其加载的呢？

我们可以大胆猜测，Lua会有个load函数，去load我们的 Chunk。

1
2
3
4
5
6
7
8
9
10

LUA_API int lua_load (lua_State *L, lua_Reader reader, void *data,
                      const char *chunkname, const char *mode) {
  ....
  status = luaD_protectedparser(L, &z, chunkname, mode);
  if (status == LUA_OK) {  /* no errors? */
    LClosure *f = clLvalue(L->top - 1);  /* get newly created function */
		....
  }
  return status;
}

近期工作的内容主要是设计一个通用的游戏排行榜服务器, 通用的含义指的是同时为多个项目组提供一套通用的解决方案, 经过不断的调研, 最终写下此文.

本文将会讲述 排行榜的多种实现方式, 不过最终我选择了 SkipList 作为底层的数据结构, 因此会着重讲SkipList.

先来讲一下排行榜的主要功能.

排行榜主要功能

• 更新/删除/获取 一个 Key 在某个 排行榜 上的 排名, 及展示信息
• 获取 一个排行榜 任意区间(例如排名区间) 的展示信息

排行榜排序方案

游戏中的排行榜的排序方案无非就两种

• 实时排序, 即玩家数值变化的瞬间, 就完成了对它的排序
• 非实时排序, 亦可称之为定时排序, 玩家数据变动不立即排序, 而是直到策划所配的时间点到的时候才进行排序

这两种排序方案没有好坏之分, 主要是看策划他想要什么? (或许他自己也不知道想要什么, 他都想试试看, 他只顾着他自己)

前言

本节主要是讲 网络编程中, 常用的I/O 多路复用. 全文大概分为以下几点.

1. 为什么需要I/O多路复用?
2. I/O多路复用的使用场景?
3. 为什么都是与非阻塞I/O进行搭配, 而不是与阻塞I/O进行搭配呢?
4. select 的 优缺点 及 内核实现
5. poll 的 优缺点 及 内核实现
6. epoll 的 优缺点 及 内核实现

这是 Linux 系统编程系列 中的第一篇, 在这个系列里面, 我想以这么个顺序来讲述每一篇的内容, 先是快速简单地了解一下 常见的使用方法, 即API如何使用, 接着再深入其中, 了解内核为API提供的帮助, 大致是 C标准库 → 系统调用 这么个学习路线.

时间的定义

首先要记住 计算机的起始时间 为 (格林威治时间)1970年1月1日0点, 被称作 GMT时间 是时区时间, 不过它是根据地球公转和自转来计算的, 不是特别准确. 在计算机世界中, 往往被称作 UTC时间, 它是以原子钟来计算时间, 简单来说就是 UTC时间 比 GMT时间要准确, 同时两个时间又恰好没有时差, 但是UTC时间又不是时区时间, 因此容易被人弄混.

Loki Allocator 有三个类 这玩意对比起 pool allocator 的优点就在于 它有把内存还给系统

但是它作为一个 内存分配器 却在里面使用了 vector 作为容器… 按道理来说 应该在其内部实现一个简易版的 vector 才不会那么奇怪 但也没所谓 只是 先用了一次标准库的分配器 后续使用容器的时候 就可以用 Loki 分配器了.

• Chunk
• FixedAllocator
• SmallObjAllocator

Chunk 解剖

Chunk 是整个分配器的最底层 里面主要是三个 成员变量

1
2
3
4
5
6

// 指向内存块
unsigned char * pData_;
// 目前可用区块的第一块的索引
unsigned char firstAvailableBlock_;
// 有多少块可用
unsigned char blocksAvailable_;

Chunk 的几个关键函数 已进行 剪裁 和 修改

Chunk 分配

分配流程很简单 就是 申请了内存以后 将每个小区块的第一个字节设置为索引 排好号

取的流程:

1. 从 当前可用区块的第一块索引中取 得当前可用区块
2. 当前可用区块会被返回
3. 被返回的可用区块中的索引 被设置到 当前可用区块索引去(这样下一次就会使用到它)
4. 可用区块数目 - 1

为什么要实现内存池?

一方面 是为了减少 调用 malloc() 的次数(尽管 malloc() 不慢) 但是调多了 会产生(外碎片)

另一方面 是因为 每次用 malloc() 分配到的内存 是要交税的 就是上一节中讲的 cookie 里面记录着 这一块内存的大小信息(内碎片) 特别是在频繁申请小内存的时候尤为明显

最终 pool_allocator 版本

具体代码可见 Memory_Pool

原理可见 C++ 内存管理 之 STL内存分配实现原理

本文主要讲讲 GNU-C++ 4.9 下的扩展内存分配器

首先 GNU-C++ 4.9 有 7 个扩展的内存分配器

• new_allocator
• malloc_allocator
• pool_allocator
• __mt_alloc
• array_allocator
• debug_allocator
• bitmap_allocator

主要看看 pool_allocator array_allocator bitmap_allocator

以下源码都可在 .../ext/*.h 下找到 我将其进行了适当的 删减和修改

__gnu_cxx::new_allocator

直接用 ::operator new 和 ::operator delete 实现出来的 好处是 可以被重载 没啥特色

1
2
3
4
5
6
7
8
9
10

template<typename _Tp>
class new_allocator {
public:
    pointer allocate(size_type __n, const void* = 0) {
        return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp)));
    }
    void deallocate(pointer __p, size_type) {
        ::operator delete(__p);
    }
};

本文主要讲的是 各个C++版本 中的STL标准库中的默认内存分配器 的 各种实现

VC6 标准分配器实现

VC6 它什么内存管理都没做 直接调用的 operator new 而 operator new 内部实际上 调用的就是 malloc

此外 VC6 下 是以元素为单位 比如 int 的话 他就会分配 512 ints 如果是 double 则会分配 512 doubles

而 GNU-C++ 2.9 以字节为单位 GNU-C++ 4.9 以元素为单位 在 G2.9 中的容器默认分配器 被移到了 pool_allocator 中

注意 G2.9 的标准分配器 和 容器默认分配器 不一样噢!

GNU-C++ 2.9 标准分配器实现

std::allocator 标准分配器 也是什么都没做

但是 G2.9 容器使用的分配器 不是上面的那个 std::allocator 而是 std::alloc

为什么要叫原生版本?

因为我觉得这一块是 C++ 自带的表达式 表达式里面 去调用 C语言的 CRT 库中的 malloc 和 free 但这篇 只讲自带的表达式 而不去深究 CRT 中的内存分配函数 所以只叫原生版本

常见的内存分配

使用示例

其中 ::operator new() 和 ::operator delete() 调用了 malloc() 和 free()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

    void *p1 = malloc(512);
    free(p1);
    
    complex<int> *p2 = new complex<int>;
    delete p2;
    
    void *p3 = ::operator new(512);
    ::operator delete(p3);

#ifdef _MSC_VER
    // 属于 non-static 要先实例化object再调用
    int *p4 = allocator<int>().allocate(3, (int*)0);
    allocator<int>().deallocate(p4, 3);
#endif

#ifdef __GUNC__
    // 早期 GNU-C++ 2.9 版本
    // void *p4 = alloc::allocate(512);
    // alloc::deallocate(p4, 512);
    // alloc 换名字了
    void *p5 = __gnu_cxx::__pool_alloc<int>().allocate(9);
    __gnu_cxx::__pool_alloc<int>().deallocate((int*)p5, 9);
    // 4.9 版本之后
    void *p4 = allocator<int>().allocate(7);
    allocator<int>().deallocate((int*)p4, 7);

#endif