Sucha's Blog ~ Archive for August, 2020

20年8月17日 周一 23:32

LuaJIT 下的双链表及 AVL 树

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

先说优点,上面两个都是使用 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.luaffi_avl.lua

一些问题

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

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

后记

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

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

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

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 画出来的框架图: