Re: [ovs-dev] [PATCH v2 1/1] json: Serialize strings using a lookup table

[Ben Pfaff]

On Wed, Oct 05, 2016 at 04:47:21PM +, Rodriguez Betancourt, Esteban wrote:
> 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.

Thanks, applied to master.
___
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev

[ovs-dev] [PATCH v2 1/1] json: Serialize strings using a lookup table

[Rodriguez Betancourt, Esteban]

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
NOVS Master  Lookup TableDifferenceDiff per op
1   233182200369   3281332813
10 2724931   1919168  80576380576.3
100   22802794  24406648-1603854   -16038.54
1000 253645888 2062597604738612847386.128
1   23522457031906839780   44540592344540.5923
10 23967770920   19012178655  495559226549555.92265

Serialize echo example
NOVS Master  Lookup TableDifferenceDiff per op
1385712565 -8708-8708
10  17403 7312 10091 1009.1
100 5785956613  1246   12.46
1000   592310   528110 64200   64.2
1 6096334  5576109520225   52.0225
10   60970439 58477626   2492813   24.92813

Serialize mutate example
NOVS Master  Lookup TableDifferenceDiff per op
17115  19051 -11936  -11936
10  34110  39561  -5451-545.1
100296613 298645  -2032-20.32
1000  35104992930588 579911579.911
133898710   302786313620079362.0079
10  305069356  280622992   24446364244.46364

Signed-off-by: Esteban Rodriguez Betancourt 
---
I can't believe that I didn't send the patch in the previous mail, sorry about 
that.
Regards,
Esteban

 lib/json.c | 76 +-
 1 file changed, 40 insertions(+), 36 deletions(-)

diff --git a/lib/json.c b/lib/json.c
index 995f3c2..080e881 100644
--- a/lib/json.c
+++ b/lib/json.c
@@ -1610,49 +1610,53 @@ json_serialize_array(const struct json_array *array, 
struct json_serializer *s)
 ds_put_char(ds, ']');
 }
 
+const char *chars_escaping[256] = {
+"\\u", "\\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':
-