优化 cJSON 库的 array 插入速度
和参考资料一样,我在我的项目中应用 cJSON 数组功能,发现在创建 array 的时候耗时很厉害(作为嵌入式 CPU,几十个 array 项的插入,居然花了 300ms)。搜了一下,网上已经有人遇到过了,就是参考资料的那篇。本文解释一下优化的思路和方法。
Reference
修改方法
下面左边是原版的 cJSON 代码,右边是修改后的,可以自己看看:
void cJSON_AddItemToArray (cJSON *array, cJSON *item) | void cJSON_AddItemToArray (cJSON *array, cJSON *item) { | { cJSON *c = array->child; | cJSON *c = array->child; if (!item) | if (!item) return; | return; | if (!c) { | if (!c) { array->child=item; | array->child=item; | array->child->prev = item; } | } else { | else { while (c && c->next) | item->prev = array->child->prev; c=c->next; | array->child->prev->next = item; /* MARK */ suffix_object(c,item); | array->child->prev = item; | item->next = NULL; } | } | } | }
如果只单纯改上面这个函数的话(参考资料就只改了这点),实际上是会有 bug 的,那就是如果对一个使用 cJSON_Parse()
得到的对象进行 addObject 操作的话,程序会崩溃,原因是上述标记的 “MARK” 的语句的prev
成员为空,因而出现内存越界。
我现在做的实际上的函数是这样的:
void cJSON_AddItemToArray(cJSON *array, cJSON *item) { cJSON *c = array->child; if (!item) { return; } if (!c) { /* list is empty, start new one */ array->child = item; array->child->prev = item; } else { /* append to the end */ if (array->child->prev) { item->prev = array->child->prev; array->child->prev->next = item; array->child->prev = item; item->next = NULL; } else { while (c->next) c = c->next; suffix_object(c, item); array->child->prev = item; } } }
修改思路
原文提到两种修改方法,其实本质上是一模一样的。
我们先看原来 cJSON 的代码思路:每次添加数组成员时,都会遍历链表以找到最后一个数组成员,然后在这个成员的next
上加上新数组成员。
那么修改思路自然是:每次插入新成员时,都把这个 “最后一个数组成员” 缓存下来就好了嘛。
这里我们注意到一个很重要的点:对于 cJSON 数组成员的第一项,它的 “prev” 成员永远是 NULL,也就是压根没用上!所以,原文的修改思路就是:复用没用到的第一个成员的 prev 变量,用来保存 last 值。实际上,原文这么做,也同时把 cJSON array 的单向链表变成了一个循环链表~~
THE END——实在是一个很不错的修改。我的操作时间从几百毫秒变成了30毫秒了。
WARNING:这个修改没有经过经过完整用例的测试,也没有与作者本人 Dave Gamble 确认过,所以请各位谨慎食用。