cJSON 链表的缺陷

cJSON 使用双向链表来表示 JSON 的 array 或 object,但在父节点中只保存链表的头指针。于是需要插入到链表尾端的操作,如 cJSON_AddItemToArray 和 cJSON_AddItemToObject 函数调用,所需的时间复杂度和 array 或 object 的当前长度成正比。其结果就是使用 cJSON 在一个 array 中插入 n 个元素的时间复杂度是 O(n2)。而如果对其做一个简单的修改,在 cJSON 的数据结构中加入链表的尾指针,就能得到常数的函数调用时间复杂度。这点实在是让我不得不认为是个设计缺陷。

起因是这样的,在一个嵌入式设备上,cJSON 生成 1MB 的 JSON 花了 10 秒。调查后发现的罪魁祸首就是 cJSON 里的这个链表。同时由于嵌入式设备 CPU 的 L1/L2 缓存普遍较小,cJSON 遍历链表时的 cache miss 使得其效率在这一场景下低到不可忍受。

对于简单的 JSON 解析和生成,yajl(Yet Another JSON Library)会是更好的选择。它的功能简单,不具备操作 JSON 树的功能。但相对的,它对 JSON 的解析和生成都是流式的,不需要记录太多的中间状态和已解析完成的内容,所以内存占用非常小,速度也相当快。

Advertisements
This entry was posted in Computer and Internet and tagged . Bookmark the permalink.

One Response to cJSON 链表的缺陷

  1. Pingback: 缓存友好的数据结构 | Xu Weidong 的空间

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s