• 从零开始的 JSON 库教程(七):生成器解答篇
    • 1. 生成字符串
    • 2. 生成数组和对象
    • 3. 优化 lept_stringify_string()
    • 4. 总结

    从零开始的 JSON 库教程(七):生成器解答篇

    • Milo Yip
    • 2017/1/5

    本文是《从零开始的 JSON 库教程》的第七个单元解答篇。解答代码位于 json-tutorial/tutorial07_answer。

    1. 生成字符串

    我们需要对一些字符进行转义,最简单的实现如下:

    1. static void lept_stringify_string(lept_context* c, const char* s, size_t len) {
    2. size_t i;
    3. assert(s != NULL);
    4. PUTC(c, '"');
    5. for (i = 0; i < len; i++) {
    6. unsigned char ch = (unsigned char)s[i];
    7. switch (ch) {
    8. case '\"': PUTS(c, "\\\"", 2); break;
    9. case '\\': PUTS(c, "\\\\", 2); break;
    10. case '\b': PUTS(c, "\\b", 2); break;
    11. case '\f': PUTS(c, "\\f", 2); break;
    12. case '\n': PUTS(c, "\\n", 2); break;
    13. case '\r': PUTS(c, "\\r", 2); break;
    14. case '\t': PUTS(c, "\\t", 2); break;
    15. default:
    16. if (ch < 0x20) {
    17. char buffer[7];
    18. sprintf(buffer, "\\u%04X", ch);
    19. PUTS(c, buffer, 6);
    20. }
    21. else
    22. PUTC(c, s[i]);
    23. }
    24. }
    25. PUTC(c, '"');
    26. }
    27. static void lept_stringify_value(lept_context* c, const lept_value* v) {
    28. switch (v->type) {
    29. /* ... */
    30. case LEPT_STRING: lept_stringify_string(c, v->u.s.s, v->u.s.len); break;
    31. /* ... */
    32. }
    33. }

    注意到,十六进位输出的字母可以用大写或小写,我们这里选择了大写,所以 roundstrip 测试时也用大写。但这个并不是必然的,输出小写(用 "\\u%04x")也可以。

    2. 生成数组和对象

    生成数组也是非常简单,只要输出 [],中间对逐个子值递归调用 lept_stringify_value()。只要注意在第一个元素后才加入 ,。而对象也仅是多了一个键和 :

    1. static void lept_stringify_value(lept_context* c, const lept_value* v) {
    2. size_t i;
    3. switch (v->type) {
    4. /* ... */
    5. case LEPT_ARRAY:
    6. PUTC(c, '[');
    7. for (i = 0; i < v->u.a.size; i++) {
    8. if (i > 0)
    9. PUTC(c, ',');
    10. lept_stringify_value(c, &v->u.a.e[i]);
    11. }
    12. PUTC(c, ']');
    13. break;
    14. case LEPT_OBJECT:
    15. PUTC(c, '{');
    16. for (i = 0; i < v->u.o.size; i++) {
    17. if (i > 0)
    18. PUTC(c, ',');
    19. lept_stringify_string(c, v->u.o.m[i].k, v->u.o.m[i].klen);
    20. PUTC(c, ':');
    21. lept_stringify_value(c, &v->u.o.m[i].v);
    22. }
    23. PUTC(c, '}');
    24. break;
    25. /* ... */
    26. }
    27. }

    3. 优化 lept_stringify_string()

    最后,我们讨论一下优化。上面的 lept_stringify_string() 实现中,每次输出一个字符/字符串,都要调用 lept_context_push()。如果我们使用一些性能剖测工具,也可能会发现这个函数消耗较多 CPU。

    1. static void* lept_context_push(lept_context* c, size_t size) {
    2. void* ret;
    3. assert(size > 0);
    4. if (c->top + size >= c->size) { // (1)
    5. if (c->size == 0)
    6. c->size = LEPT_PARSE_STACK_INIT_SIZE;
    7. while (c->top + size >= c->size)
    8. c->size += c->size >> 1; /* c->size * 1.5 */
    9. c->stack = (char*)realloc(c->stack, c->size);
    10. }
    11. ret = c->stack + c->top; // (2)
    12. c->top += size; // (3)
    13. return ret; // (4)
    14. }

    中间最花费时间的,应该会是 (1),需要计算而且作分支检查。即使使用 C99 的 inline 关键字(或使用宏)去减少函数调用的开销,这个分支也无法避免。

    所以,一个优化的点子是,预先分配足够的内存,每次加入字符就不用做这个检查了。但多大的内存才足够呢?我们可以看到,每个字符可生成最长的形式是 \u00XX,占 6 个字符,再加上前后两个双引号,也就是共 len * 6 + 2 个输出字符。那么,使用 char* p = lept_context_push() 作一次分配后,便可以用 *p++ = c 去输出字符了。最后,再按实际输出量调整堆栈指针。

    另一个小优化点,是自行编写十六进位输出,避免了 printf() 内解析格式的开销。

    1. static void lept_stringify_string(lept_context* c, const char* s, size_t len) {
    2. static const char hex_digits[] = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F' };
    3. size_t i, size;
    4. char* head, *p;
    5. assert(s != NULL);
    6. p = head = lept_context_push(c, size = len * 6 + 2); /* "\u00xx..." */
    7. *p++ = '"';
    8. for (i = 0; i < len; i++) {
    9. unsigned char ch = (unsigned char)s[i];
    10. switch (ch) {
    11. case '\"': *p++ = '\\'; *p++ = '\"'; break;
    12. case '\\': *p++ = '\\'; *p++ = '\\'; break;
    13. case '\b': *p++ = '\\'; *p++ = 'b'; break;
    14. case '\f': *p++ = '\\'; *p++ = 'f'; break;
    15. case '\n': *p++ = '\\'; *p++ = 'n'; break;
    16. case '\r': *p++ = '\\'; *p++ = 'r'; break;
    17. case '\t': *p++ = '\\'; *p++ = 't'; break;
    18. default:
    19. if (ch < 0x20) {
    20. *p++ = '\\'; *p++ = 'u'; *p++ = '0'; *p++ = '0';
    21. *p++ = hex_digits[ch >> 4];
    22. *p++ = hex_digits[ch & 15];
    23. }
    24. else
    25. *p++ = s[i];
    26. }
    27. }
    28. *p++ = '"';
    29. c->top -= size - (p - head);
    30. }

    要注意的是,很多优化都是有代价的。第一个优化采取空间换时间的策略,对于只含一个字符串的JSON,很可能会分配多 6 倍内存;但对于正常含多个值的 JSON,多分配的内存可在之后的值所利用,不会造成太多浪费。

    而第二个优化的缺点,就是有稍增加了一点程序体积。也许有人会问,为什么 hex_digits 不用字符串字面量 "0123456789ABCDEF"?其实是可以的,但这会多浪费 1 个字节(实际因数据对齐可能会浪费 4 个或更多)。

    4. 总结

    我们用 80 行左右的代码就实现了 JSON 生成器,并尝试了做一些简单的优化。除了这种最简单的功能,有一些 JSON 库还会提供一些美化功能,即加入缩进及换行。另外,有一些应用可能需要大量输出数字,那么就可能需要优化数字的输出。这方面可考虑 C++ 开源库 double-conversion,以及参考本人另一篇文章《RapidJSON 代码剖析(四):优化 Grisu》。

    现时数组和对象类型只有最基本的访问、修改函数,我们会在下一篇补完。

    如果你遇到问题,有不理解的地方,或是有建议,都欢迎在评论或 issue 中提出,让所有人一起讨论。