Sucha's Blog ~ Archive for August, 2020

20年8月17日周一 23:32

LuaJIT 下的双链表及 AVL 树

Lua 描述结构数据方面，只有一种内建结构，就是 table，table 既是 array，又是 hashmap，算是简洁高效的实现，但我们需要一种动态表示元素先后、大小关系的数据结构时，内建的 table 就不合适了，比如常见的 fifo 及 binaryheap。

先说优点，上面两个都是使用 table 来描述先后顺序、大小关系的，缺点是，当有插入、删除发生时，时间效率太慢了。其中 fifo 是使用 table 的 array 实现的，需要在删除元素后，对其他的元素做拷贝迁移，避免空位；而 bianryheap，也是使用使用 table 的 array，当元素位置变动时，采用了冒泡算法，对元素重新排位。

空间效率是保住了，但就时间效率来说，太不专业了，O(N^2) 的实现，数据量稍微多一点点，时间不能看。

其实 fifo 算是一种双链表，只是插入是在头尾，算是双链表的特例。双链表下，非头尾的删除发生，时间效率是 O(1) 级别的。其实可以用 table 来描述链表关系，缺点是空间消耗大，为了描述两个相邻元素间的先后顺序，就得用一个 table 实例来做。

我用 Lua 内建的 table 实做了一把，时间效率是很高效的，空间的话，插入 number，10,000,000 级别的插入，内存大概 6G。

-- performance
push 1000,000, cost 0.393088
pop  1000,000, cost 0.092984

在 C 的双链表实现中，需要将链表节点跟数据结构绑定起来，要么是以链表节点为主，链表节点指向数据结构，或者像 Linux Kernel 里面规范化的双链表实现，链表节点实例，放在数据结构中，通过偏移定位数据起点。

但是在 Lua 里面做不到这样，不得不使用 value（值）到 node（节点），以及 node 到 value 的两个 table 来做关系映射，再加上相邻两个 value 的顺序关系使用一个 node（table）来实现，也是空间消耗大的原因。

LuaJIT 下 cdata 的妙用

LuaJIT 因为有 FFI，可以创建结构化的 cdata 来描述相邻 node 之间的关系，而不需要使用内建的 table，使得可以花费更少的空间代价，比如下面这样来描述双链表的节点关系：

ffi.cdef [[
struct _cnode {
    struct _cnode *prev;
    struct _cnode *next;
    float key;
};
struct _chead {
    struct _cnode *head;
    struct _cnode *tail;
};
void* calloc(size_t count, size_t size);
void free(void *ptr);
]]

特别注明 cdata 是 calloc 出来的，不在 gc 管理范围，因为 C 下面的指针，需要保证指向固定的内存地址。其他跟纯 table 实现的双链表一样，需要两个 table 来维护 value 跟 node之间的映射关系，如上面 struct _cnode 下的 key，其实是用于 node 到 value 的 table 的映射 key，原因下面再说。

同样的 AVL 树也可以使用 cdata 来维护节点间的大小关系：

ffi.cdef [[
struct _avl_node {
    struct _avl_node *left;
    struct _avl_node *right;
    struct _avl_node *parent;
    int height;
    float key;
};
struct _avl_root {
    struct _avl_node *node;
};
void* calloc(size_t count, size_t size);
void free(void *ptr);
]]

以上使用 cdata 描述元素关系时间效率跟纯 table 时间效率一样，空间效率的话，第一个例子下，内存占用不到 4G，地址 ffi_list.lua 及 ffi_avl.lua。

一些问题

LuaJIT 下使用 cdata 描述节点关系，遇到了一些问题：

cdata 做 key 不稳定，string.format("%p") 打印出来看 cdata 的值，经过变量传递后，有变化，做 key 的话，导致 node 到 value 的 mapping 找不到 value，所以 cdata 单独带了一个 float 类型的 key
我设想使用 math.random() 来产生 0 ~ 1 之间的小数做 key，但是在 ffi_list.lua 中，会导致其他的问题，不得不使用了固定小数增长的做法来实现，原因还不清楚，不过我这边自测用的数据范围是 10,000,000 及以上才会出现

上面的问题，估计还是要设计一些测试用例来定位一下才好，现在先这样吧。

后记

19 号解决了上面遇到的 2 个问题，原因在于 ffi.cdef 使用的 key 宽度是 float，但是 LuaJIT number 的宽度是 double 导致的，我修改 ffi.cdef node 里面的 key 为 double 类型，问题不再出现。

不过我也有疑问，为何 AVL 这边同样的实现，没有暴露出来问题呢。

反正现在修改为多轮循环 test 验证了，验证了几千遍，每次是 1000x1000 次的 push、pop，都是正常的了。

CategoryProgramming / Permalink / Discussion

20年8月02日周日 20:50

做了一个 web 框架：cincau

离职后在家呆了一个月，前面两周在休息，后面两周开始忙起来，想着将手头的数据搭一个可视化的网站出来，可以学习一下 web 前端的库之类的，但是呢，想找一个能 sqlite 和 nginx 的 web framework，找到一个感觉还可以的 Lor，但是呢，不支持 sqlite，感觉不算是一个 minimalist 的 web framework，就想着不如自己搭建一个吧。

可是如果搭建，顺便带上自己的 mnet 是肯定的了，当然 nginx 也是要支持的。于是参考了 lor 的不少东西，但更多的其实是自己摸索的，因为时间也比较充足，是先考虑了架构，才开始动手的。

没有浪费之前买的 goodnote 5，用来构思框架了，画了大概 5 个页面，大的模块上，跟 lor 一样，分为基础库，以及具体的项目代码。基础库在 /usr/local/cincau，用来生成基本的 demo 项目，本身包含了所有 proj 用到的的基础库。对上面的简单业务逻辑，封装 engine 层，不区分为 mnet 或者是 nginx，但实际上这两者一定是要区分开的，除非是静态的文件。

基础库里面，细分为 engine 层、router、MVC 逻辑、database、POST 的解析、HTTP Request 这几个部分，其中 MVC 中 view 的 rendering 用了 leafo 的 etlua，这其实是基于 openresty 的 lapis 的一个模版库。database 不出意外，我只考虑了 sqlite3，就是 minimalist 的 web framework，等有需要，在考虑 mysql、postgresql 之类的，毕竟这两者，没有基于 mnet 的接口，只有基于 nginx 的。

在 goodnotes 5 上面花了 3、4 天这样，其实上面这么多细节，都是在完成整个项目后，回头才细化出来的。在草图出来以后，框架搭建花了大概一周，mnet 是基于 ffi_mnet.lua 以及 hyperparser 的回调，拿到 http 数据结构层。而 nginx 是 content_by_lua_file 来驱动的。

然后还继续花了 3、4 天来完善框架细节，比如 POST 以及 HTTP request 的那一套，以及基于这个框架，写了一个 demo project，支持 ment、nginx，包含静态页面、mock 的 model，以及 post x-www-urlencoded 和 multipart/form-data 这几个部分。

该放地址了：cincau，话说之前也断断续续做过半个 web framework，现在终于点连成了线，水到渠成了。

goodnote 5 画出来的框架图：

CategoryProgramming / Permalink / Discussion