3

一个Lua的json解析器

 3 years ago
source link: https://zhuanlan.zhihu.com/p/383848133
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

一个Lua的json解析器

我为我的Lua扩展库增加了一个json解析器。之前在项目中一直使用cjson，它的速度很快，接口也简单，是一个很优秀的模块。但是后面我发现它有一些不大符合标准的地方，还有一些功能的缺失(比如格式化，比如支持注释)。我终于还是决定自己撸一个。

像json这样的简单parser，其现实模式是很固定的，按着套路来很容易就能写一个像模像样的东西。我的确花了一两个晚上就把parser给写好了，可是写完之后和cjson一比较，性能还是差了那么一点点。接下来的几天就开始各种折腾，对里面的每个点进行反复的研究和思考，最终代码不过800来行，但推翻和修改过的行数恐怖不止1000行。这个过程非常有意思，它使我领悟到的东西远比看代码来得多。

一开始我实现了一套统一的流接口，parser从流中取字符来解析，流的数据从哪里来的parser并不用关心。流本身持有一个reader回调函数，当没有数据时则调用reader函数去取数据；这个reader函数由外部指定，因此数据来源对流本身也是透明的，它可以实现为从内存buffer取，也可以实现为从磁盘文件取，甚至于从网络上下载也是可以的，这看起来真是太“美好”了。

流本身持有一个数据指针(ptr)和一个数据剩余大小(size)，每次从流取一个字节时，就判断size，如果大于0，就减1并返回ptr里的字节，然后ptr++；如果size已为0就调用reader函数再去取数据。也就是这个设计使得取字符多了对size的操作。但其实json parser的需求是很简单的，它面对的是一个json文本，也就是一个字符串；可以限定字符串以\0结尾，这样就不用去判断size是否为0。最后我的解析器弃用了这个流接口，改为直接从字符串取字符出来解析，至于字符串是从文件加载还是从网络加载就交上更上一层好了。

解析器的下一步工作是生成token，根据字符判断它可能是哪种token，比如遇到'{'就应该是对象，遇到'['就应该是数组，遇到'"'就应该是字符串等等。有两种方法进行判断，一种是对字符进行switch case；另一种是使用一个映射表根据字符直接返回token类型。我选择了switch case，原因是映射表需要占用256个额外的元素空间，并且有些字符是不能立即确定token类型的，比如遇到't'，还得判断后面是rue才能确定是true。switch case看起来是没有映射表快，但我相信编译器能提供足够的优化，最后的性能测试也确实能佐证这一点。

对数字的解析是一个性能热点，一开始我用最保守的做法：先准备好数字的字符串，再调用strtoll或strtod将字符串转换成整型或浮点数。后来发现直接调用strtoll可能不符合json标准，因为strtoll可容纳的格式更广一些，像0300这个数字没问题，但在json里是不合法的。为了严格遵守json的标准，我在取字符时一边对格式进行了一次验证，发现合格才交给strtoll或strtod去转换。这样处理后的确符合标准了，但速度也有明显的下降。最快的方式应该是一边取字符一边转换，等字符取好了，转换也同时完成；先假设是整型，转换过程中发现不是整型再切成浮点数；显然这样的需求很难有一个库函数能满足，于是我只能自己来实现，在查询各种资料后，终于实现了数字的转换。最后的测试表明，浮点数的解析速度几乎是cjson的一倍快。

字符串的解析也是一个重点，没办法对""里的内容作无脑扫描，因为它可能存在控制字符的转义和Unicode的转义；需要把常规字符存进一个临时Buffer，遇到\时去作转义处理，再把转义结果存进Buffer；在解析开始前我就创建了一个Buffer，后面的解析工作一直重用它，Buffer一开始引用的是栈上的内存，这块内存有512个字节，等到不够了才真正去申请堆上的内存。可以说80%的json文本都是短字符串，这个设计能够大大减少创建动态内存的机会。

parser部分是通用的，中间的解析结果通过“回调函数”触发，像Lua只需实现下面这些“回调函数”：

//-------------------------------------
// 与Lua相关的代码
static inline void l_add_object(lua_State *L) {
    luaL_checkstack(L, 6, NULL);
    lua_newtable(L);
}
static inline void l_begin_pair(lua_State *L, const char *k, size_t sz) {
    lua_pushlstring(L, k, sz);
}
static inline void l_end_pair(lua_State *L) {
    lua_rawset(L, -3);
}
static inline void l_add_array(lua_State *L) {
    luaL_checkstack(L, 6, NULL);
    lua_newtable(L);
}
static inline void l_add_index(lua_State *L, int i) {
    lua_rawseti(L, -2, i+1);
}
static inline void l_add_string(lua_State *L, const char *s, size_t sz) {
    lua_pushlstring(L, s, sz);
}
static inline void l_add_float(lua_State *L, double f) {
    lua_pushnumber(L, (lua_Number)f);
}
static inline void l_add_integer(lua_State *L, int64_t i) {
    lua_pushinteger(L, (lua_Integer)i);
}
static inline void l_add_boolean(lua_State *L, int b) {
    lua_pushboolean(L, b);
}
static inline void l_add_null(lua_State *L) {
    lua_pushlightuserdata(L, NULL);
}
static inline void l_error(lua_State *L, const char *msg) {
    luaL_error(L, msg);
}

// 解析事件
#define ON_ADD_OBJECT(ud) l_add_object((lua_State*)(ud))
#define ON_BEGIN_PAIR(ud, k, sz) l_begin_pair((lua_State*)(ud), k, sz)
#define ON_END_PAIR(ud) l_end_pair((lua_State*)(ud))
#define ON_ADD_ARRAY(ud) l_add_array((lua_State*)(ud))
#define ON_ADD_INDEX(ud, i) l_add_index((lua_State*)(ud), i)
#define ON_ADD_STRING(ud, s, sz) l_add_string((lua_State*)(ud), s, sz)
#define ON_ADD_FLOAT(ud, f) l_add_float((lua_State*)(ud), f)
#define ON_ADD_INTEGER(ud, i) l_add_integer((lua_State*)(ud), i)
#define ON_ADD_BOOLEAN(ud, b) l_add_boolean((lua_State*)(ud), b)
#define ON_ADD_NULL(ud) l_add_null((lua_State*)(ud))
#define ON_ERROR(ud, msg) l_error((lua_State*)(ud), msg)

参考这个做法应该当很容易将parser移植给其他脚本使用，虽然我没有试过。

最后是一些测试数据，分别对比了cjson和python的json模块：

load
=====================================================================
                    cojson              cjson               python3
---------------------------------------------------------------------
test_float.json     1.083171            2.0871              1.560977
test_int.json       1.014711            1.173078            0.933070
test_string.json    0.186342            0.191351            0.224133
test_string2.json   0.103958            0.09565             0.297270
twitter.json        0.283848            0.275911            0.331106
citm_catalog.json   0.435639            0.43991             0.408701
player.json         0.170948            0.180764            0.174330


dump
=====================================================================
                    cojson              cjson               python3
---------------------------------------------------------------------
test_float.json     0.899501            1.029               2.852951
test_int.json       0.551159            0.61152             0.826302
test_string.json    0.107919            0.106341            0.231275
test_string2.json   0.071458            0.080719            0.114707
twitter.json        0.091735            0.097119            0.298636
citm_catalog.json   0.114465            0.118821            0.308602
player.json         0.084445            0.084446            0.183507

由于这是一个为Lua写的解析器，解析过程还要考虑Lua的操作成本，因此没有办法和其他json解析器作性能对比，这里只比较了python的。

性能指标权当一个参考就好了，都是用C写的，只要不出意外都不会差到哪儿去。

代码在这里：

https://github.com/colinsusie/colib/blob/main/src/ljson.c​github.com


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK