优化cJSON_AddItemToArray函数，提高插入速率

最近在我的写了一个API程序，要求返回响应的数据是JSON，格式类似下面这种：

[{
  "columns":[
    {"text":"Time","type":"time"},
    {"text":"Country","type":"string"},
    {"text":"Number","type":"number"}
  ],
  "rows":[
    [1234567,"SE",123],
    [1234567,"DE",231],
    [1234567,"US",321]
  ],
  "type":"table"
}]
1
2
3
4
5
6
7
8
9
10
11
12
13

API是用C语言开发的，所以在构建json上，为了方便，使用了CJson库。代码如下：

static char *grafana_build_reponse_query_history(MYSQL *mysql, const char *request_body, grafana_query_request_s *rst, snetflow_job_s *job)
{
    cJSON *root, *response_json, *columns, *column, *rows, *row, *json_flow, *json_bytes;
...
	/* 根据target拼接json */
	response_json = cJSON_CreateArray();
	root = cJSON_CreateObject();
	cJSON_AddItemToArray(response_json, root);
	rows = cJSON_AddArrayToObject(root, "rows");
	columns = cJSON_AddArrayToObject(root, "columns");
	cJSON_AddStringToObject(root, "type", "table");
	/* rows */
	for(i = 0, it = history_vec.begin(); it != history_vec.end(); it++)  
	{
		json_flow = cJSON_CreateString((*it).flow);
		json_bytes = cJSON_CreateNumber((*it).bytes);
		row = cJSON_CreateArray();
	    cJSON_AddItemToArray(row, json_flow);
	    cJSON_AddItemToArray(row, json_bytes);
		/* 优化cJSON_AddItemToArray(rows, row)提高速度*/ 
		cJSON_AddItemToArray(rows, row);
	}
	/* columns */
	column = cJSON_CreateObject();
	cJSON_AddStringToObject(column, "text", cfg->name);
    cJSON_AddStringToObject(column, "type", "string");
	cJSON_AddItemToArray(columns, column);
    column = cJSON_CreateObject();
	cJSON_AddStringToObject(column, "text", "bytes");
    cJSON_AddStringToObject(column, "type", "number");
	cJSON_AddItemToArray(columns, column);
	/* 释放空间 */
	out = cJSON_Print(response_json);
	cJSON_Delete(response_json);

	return out;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

对于row，思路就是遍历一个map，然后组装一个数组，然后添加到大数组中。当map容量在几千的时候，还可有跑出结果，但是当map容量大到几十万的时候，跑了一个多小时还没有结果，而且几乎耗尽了CPU。我用gdb调试了一下，发现大部分时间是浪费在cJSON_AddItemToArray这个函数。

优化cJSON_AddItemToArray函数

我们可以看一下cJSON结构体的定义：

typedef struct cJSON
{
    struct cJSON *next;
    struct cJSON *prev;
    struct cJSON *child;
    int type;
    char *valuestring;
    int valueint;
    double valuedouble;
    char *string;
} cJSON;
1
2
3
4
5
6
7
8
9
10
11

这里面有三个指针。以这个json格式举例:

[{
  "columns":[
    {"text":"Time","type":"time"},
    {"text":"Country","type":"string"},
    {"text":"Number","type":"number"}
  ],
  "rows":[
    [1234567,"SE",123],
    [1234567,"DE",231],
    [1234567,"US",321]
  ],
  "type":"table"
}]
1
2
3
4
5
6
7
8
9
10
11
12
13

其中columns、rows、type称作同级，{“text”:“Time”,“type”:“time”},是columns的一个子级，[1234567,“DE”,231],是rows的一个子级。

在这个结构体中，next指向同级的下一个，prev指向同级的上一个，也就是说，同级之前构成了一个双向链表。child指向子级的第一个节点。

那么问题来了，cJSON_AddItemToArray内部是如何实现的呢？很显然，无非就是修改这几个指针的指向，虽然这是一个双向链表，但是却没有记录头和尾。所以，每次调用cJSON_AddItemToArray的时候，只能从头部向后遍历，使用尾插法，时间复杂度是n^2。当数据量很大的时候，有多么耗时就可想而知了。
（如果用头插法，会导致json串同级数据的顺序颠倒！所以，cJSON_AddItemToArray肯定采用的尾插法）

既然是我们已经了解了cJSON_AddItemToArray实现思路，所以我们就可以使用单链表的尾插法，来自己对这个函数进行改进，把时间复杂度降到n。

可以参考一下如下代码

	for(i = 0, it = history_vec.begin(); it != history_vec.end(); it++)  
	{
		json_flow = cJSON_CreateString((*it).flow);
		json_bytes = cJSON_CreateNumber((*it).bytes);
		row = cJSON_CreateArray();
	    cJSON_AddItemToArray(row, json_flow);
	    cJSON_AddItemToArray(row, json_bytes);
		/* 优化cJSON_AddItemToArray(rows, row)提高速度*/ 
		if(i == 0)
		{
			i = 1;
			cJSON_AddItemToArray(rows, row);
			prev = row;
		}
		else
		{
			row->prev = prev;
			prev->next = row;
			prev = row;
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

同理，其他的一些Add函数，如cJSON_AddItemToObject、cJSON_AddItemReferenceToObject等也可以使用这个思路优化。