json: Serialize strings using a lookup table

The existing implementation uses a switch with
many conditions, that when compiled is translated
to a not optimal series of conditional jumps.

With a lookup table the generated code has less conditional jumps,
that should translate in improving the CPU ability to predict the
jumps.

Performance Comparison:
All the timings are in nanoseconds, "OVS Master" corresponds to 13a1d36.
N is the number of repetitions

Serialize vswitch.ovsschema
N        OVS Master  Lookup Table    Difference    Diff per op
1           233182        200369       32813        32813
10         2724931       1919168      805763        80576.3
100       22802794      24406648    -1603854       -16038.54
1000     253645888     206259760    47386128        47386.128
10000   2352245703    1906839780   445405923        44540.5923
100000 23967770920   19012178655  4955592265        49555.92265

Serialize echo example
N        OVS Master  Lookup Table    Difference    Diff per op
1            3857        12565         -8708        -8708
10          17403         7312         10091         1009.1
100         57859        56613          1246           12.46
1000       592310       528110         64200           64.2
10000     6096334      5576109        520225           52.0225
100000   60970439     58477626       2492813           24.92813

Serialize mutate example
N        OVS Master  Lookup Table    Difference    Diff per op
1            7115          19051         -11936      -11936
10          34110          39561          -5451        -545.1
100        296613         298645          -2032        -20.32
1000      3510499        2930588         579911        579.911
10000    33898710       30278631        3620079        362.0079
100000  305069356      280622992       24446364        244.46364

Signed-off-by: Esteban Rodriguez Betancourt <estebarb@hpe.com>
Signed-off-by: Ben Pfaff <blp@ovn.org>

1 files changed, 40 insertions, 36 deletions

diff --git a/lib/json.c b/lib/json.c
index 7b0398a7d..e052a6a0a 100644
--- a/lib/json.c
+++ b/lib/json.c
@@ -1624,49 +1624,53 @@ json_serialize_array(const struct json_array *array, struct json_serializer *s)
     ds_put_char(ds, ']');
 }
 
+const char *chars_escaping[256] = {
+        "\\u0000", "\\u0001", "\\u0002", "\\u0003", "\\u0004", "\\u0005", "\\u0006", "\\u0007",
+        "\\b", "\\t", "\\n", "\\u000b", "\\f", "\\r", "\\u000e", "\\u000f",
+        "\\u0010", "\\u0011", "\\u0012", "\\u0013", "\\u0014", "\\u0015", "\\u0016", "\\u0017",
+        "\\u0018", "\\u0019", "\\u001a", "\\u001b", "\\u001c", "\\u001d", "\\u001e", "\\u001f",
+        " ", "!", "\\\"", "#", "$", "%", "&", "'",
+        "(", ")", "*", "+", ",", "-", ".", "/",
+        "0", "1", "2", "3", "4", "5", "6", "7",
+        "8", "9", ":", ";", "<", "=", ">", "?",
+        "@", "A", "B", "C", "D", "E", "F", "G",
+        "H", "I", "J", "K", "L", "M", "N", "O",
+        "P", "Q", "R", "S", "T", "U", "V", "W",
+        "X", "Y", "Z", "[", "\\\\", "]", "^", "_",
+        "`", "a", "b", "c", "d", "e", "f", "g",
+        "h", "i", "j", "k", "l", "m", "n", "o",
+        "p", "q", "r", "s", "t", "u", "v", "w",
+        "x", "y", "z", "{", "|", "}", "~", "\x7f",
+        "\x80", "\x81", "\x82", "\x83", "\x84", "\x85", "\x86", "\x87",
+        "\x88", "\x89", "\x8a", "\x8b", "\x8c", "\x8d", "\x8e", "\x8f",
+        "\x90", "\x91", "\x92", "\x93", "\x94", "\x95", "\x96", "\x97",
+        "\x98", "\x99", "\x9a", "\x9b", "\x9c", "\x9d", "\x9e", "\x9f",
+        "\xa0", "\xa1", "\xa2", "\xa3", "\xa4", "\xa5", "\xa6", "\xa7",
+        "\xa8", "\xa9", "\xaa", "\xab", "\xac", "\xad", "\xae", "\xaf",
+        "\xb0", "\xb1", "\xb2", "\xb3", "\xb4", "\xb5", "\xb6", "\xb7",
+        "\xb8", "\xb9", "\xba", "\xbb", "\xbc", "\xbd", "\xbe", "\xbf",
+        "\xc0", "\xc1", "\xc2", "\xc3", "\xc4", "\xc5", "\xc6", "\xc7",
+        "\xc8", "\xc9", "\xca", "\xcb", "\xcc", "\xcd", "\xce", "\xcf",
+        "\xd0", "\xd1", "\xd2", "\xd3", "\xd4", "\xd5", "\xd6", "\xd7",
+        "\xd8", "\xd9", "\xda", "\xdb", "\xdc", "\xdd", "\xde", "\xdf",
+        "\xe0", "\xe1", "\xe2", "\xe3", "\xe4", "\xe5", "\xe6", "\xe7",
+        "\xe8", "\xe9", "\xea", "\xeb", "\xec", "\xed", "\xee", "\xef",
+        "\xf0", "\xf1", "\xf2", "\xf3", "\xf4", "\xf5", "\xf6", "\xf7",
+        "\xf8", "\xf9", "\xfa", "\xfb", "\xfc", "\xfd", "\xfe", "\xff"
+};
+
 static void
 json_serialize_string(const char *string, struct ds *ds)
 {
     uint8_t c;
+    uint8_t c2;
+    const char *escape;
 
     ds_put_char(ds, '"');
     while ((c = *string++) != '\0') {
-        switch (c) {
-        case '"':
-            ds_put_cstr(ds, "\\\"");
-            break;
-
-        case '\\':
-            ds_put_cstr(ds, "\\\\");
-            break;
-
-        case '\b':
-            ds_put_cstr(ds, "\\b");
-            break;
-
-        case '\f':
-            ds_put_cstr(ds, "\\f");
-            break;
-
-        case '\n':
-            ds_put_cstr(ds, "\\n");
-            break;
-
-        case '\r':
-            ds_put_cstr(ds, "\\r");
-            break;
-
-        case '\t':
-            ds_put_cstr(ds, "\\t");
-            break;
-
-        default:
-            if (c >= 32) {
-                ds_put_char(ds, c);
-            } else {
-                ds_put_format(ds, "\\u%04x", c);
-            }
-            break;
+        escape = chars_escaping[c];
+        while ((c2 = *escape++) != '\0') {
+            ds_put_char(ds, c2);
         }
     }
     ds_put_char(ds, '"');