diff mbox series

[ovs-dev,4/4] json: Store short arrays in-place.

Message ID 20250606112253.3314013-5-i.maximets@ovn.org
State Changes Requested
Headers show
Series json: Store short strings and arrays in-place. | expand

Checks

Context Check Description
ovsrobot/apply-robot success apply and check: success
ovsrobot/cirrus-robot success cirrus build: passed
ovsrobot/github-robot-_Build_and_Test success github build: passed
ovsrobot/github-robot-_Build_and_Test success github build: passed

Commit Message

Ilya Maximets June 6, 2025, 11:22 a.m. UTC 
Similarly to strings, 24 bytes that we have in 'struct json' can fit
up to 3 JSON_ARRAY elements.  And we can use separate storage types
to count them.

There are many small arrays in typical databases, for example, every
UUID is a 2-element array.  So, the change does have a noticeable
performance impact.

With 350MB OVN Northbound database with 12M atoms:

                         Before        After       Improvement
 ovsdb-client dump      16.6 sec      14.9 sec       10.2 %
 Compaction             13.4 sec      11.0 sec       17.9 %
 Memory usage (RSS)     2.05 GB       1.90 GB         7.3 %

With 615MB OVN Southbound database with 23M atoms:

                         Before        After       Improvement
 ovsdb-client dump      43.7 sec      40.5 sec        7.3 %
 Compaction             32.5 sec      29.4 sec        9.5 %
 Memory usage (RSS)     4.80 GB       4.46 GB         7.1 %

In the results above, 'ovsdb-client dump' is measuring how log it
takes for the server to prepare and send a reply, 'Memory usage (RSS)'
reflects the RSS of the ovsdb-server after loading the full database.
ovn-heater tests report similar reduction in CPU and memory usage
on heavy operations like compaction.

Signed-off-by: Ilya Maximets <i.maximets@ovn.org>
---
 include/openvswitch/json.h |  20 ++++++-
 lib/json.c                 | 119 +++++++++++++++++++++++++++++++------
 2 files changed, 119 insertions(+), 20 deletions(-)
diff mbox series

Patch

diff --git a/include/openvswitch/json.h b/include/openvswitch/json.h
index e556ceadd..134890553 100644
--- a/include/openvswitch/json.h
+++ b/include/openvswitch/json.h
@@ -32,6 +32,7 @@ 
 
 #include <stdio.h>
 #include "openvswitch/shash.h"
+#include "openvswitch/util.h"
 
 #ifdef  __cplusplus
 extern "C" {
@@ -66,9 +67,19 @@  struct json_array {
 /* Maximum string length that can be stored inline ('\0' is not included). */
 #define JSON_STRING_INLINE_LEN (sizeof(struct json_array) - 1)
 
+#define JSON_ARRAY_INLINE_LEN 3
+BUILD_ASSERT_DECL(sizeof(struct json_array) / sizeof(struct json *)
+                    >= JSON_ARRAY_INLINE_LEN);
+
 enum json_storage_type {
-    JSON_STRING_DYNAMIC = 0, /* JSON_STRING is stored via 'str_ptr'. */
-    JSON_STRING_INLINE,      /* JSON_STRING is stored in 'str' array. */
+    /* JSON_STRING storage types. */
+    JSON_STRING_DYNAMIC = 0, /* Stored via 'str_ptr'. */
+    JSON_STRING_INLINE,      /* Stored in 'str' array. */
+    /* JSON_ARRAY storage types.*/
+    JSON_ARRAY_DYNAMIC,      /* 'elements' is a dynamically allocated array. */
+    JSON_ARRAY_INLINE_1,     /* Static 'elements' with exactly 1 element. */
+    JSON_ARRAY_INLINE_2,     /* Static 'elements' with exactly 2 elements. */
+    JSON_ARRAY_INLINE_3,     /* Static 'elements' with exactly 3 elements. */
 };
 
 /* A JSON value. */
@@ -78,7 +89,10 @@  struct json {
     size_t count;
     union {
         struct shash *object;   /* Contains "struct json *"s. */
-        struct json_array array;
+        union {
+            struct json *elements[JSON_ARRAY_INLINE_LEN];
+            struct json_array array;
+        }; /* JSON_ARRAY. */
         long long int integer;
         double real;
         union {
diff --git a/lib/json.c b/lib/json.c
index 1214268b1..1d2990edb 100644
--- a/lib/json.c
+++ b/lib/json.c
@@ -226,6 +226,7 @@  struct json *
 json_array_create_empty(void)
 {
     struct json *json = json_create(JSON_ARRAY);
+    json->storage_type = JSON_ARRAY_DYNAMIC;
     json->array.elements = NULL;
     json->array.size = 0;
     json->array.allocated = 0;
@@ -235,6 +236,39 @@  json_array_create_empty(void)
 void
 json_array_add(struct json *array_, struct json *element)
 {
+    switch (array_->storage_type) {
+    case JSON_ARRAY_DYNAMIC:
+        if (!array_->array.size) {
+            array_->storage_type = JSON_ARRAY_INLINE_1;
+            array_->elements[0] = element;
+            return;
+        }
+        break;
+
+    case JSON_ARRAY_INLINE_1:
+    case JSON_ARRAY_INLINE_2:
+        array_->elements[array_->storage_type - JSON_ARRAY_DYNAMIC] = element;
+        array_->storage_type++;
+        return;
+
+    case JSON_ARRAY_INLINE_3: {
+        struct json **elements = xmalloc(4 * sizeof *elements);
+
+        memcpy(elements, array_->elements, 3 * sizeof array_->elements[0]);
+        array_->array.elements = elements;
+        array_->array.elements[3] = element;
+        array_->array.size = 4;
+        array_->array.allocated = 4;
+        array_->storage_type = JSON_ARRAY_DYNAMIC;
+        return;
+    }
+
+    case JSON_STRING_DYNAMIC:
+    case JSON_STRING_INLINE:
+    default:
+        OVS_NOT_REACHED();
+    }
+
     struct json_array *array = &array_->array;
     if (array->size >= array->allocated) {
         array->elements = x2nrealloc(array->elements, &array->allocated,
@@ -247,18 +281,43 @@  void
 json_array_set(struct json *json, size_t index, struct json *element)
 {
     ovs_assert(json_array_size(json) > index);
-    json->array.elements[index] = element;
+    if (json->storage_type == JSON_ARRAY_DYNAMIC) {
+        json->array.elements[index] = element;
+    } else {
+        json->elements[index] = element;
+    }
 }
 
 struct json *
 json_array_pop(struct json *json)
 {
-    return json->array.size ? json->array.elements[--json->array.size] : NULL;
+    if (!json_array_size(json)) {
+        return NULL;
+    }
+    if (json->storage_type == JSON_ARRAY_DYNAMIC) {
+        return json->array.elements[--json->array.size];
+    }
+    if (json->storage_type > JSON_ARRAY_INLINE_1) {
+        return json->elements[--json->storage_type - JSON_ARRAY_DYNAMIC];
+    }
+
+    /* Need to fall back to an empty array in case it's the last
+     * inline element. */
+    struct json *element = json->elements[0];
+    json->storage_type = JSON_ARRAY_DYNAMIC;
+    json->array.elements = NULL;
+    json->array.size = 0;
+    json->array.allocated = 0;
+    return element;
 }
 
 void
 json_array_trim(struct json *array_)
 {
+    if (array_->storage_type != JSON_ARRAY_DYNAMIC) {
+        return;
+    }
+
     struct json_array *array = &array_->array;
     if (array->size < array->allocated) {
         array->allocated = array->size;
@@ -271,6 +330,7 @@  struct json *
 json_array_create(struct json **elements, size_t n)
 {
     struct json *json = json_create(JSON_ARRAY);
+    json->storage_type = JSON_ARRAY_DYNAMIC;
     json->array.elements = elements;
     json->array.size = n;
     json->array.allocated = n;
@@ -280,28 +340,37 @@  json_array_create(struct json **elements, size_t n)
 struct json *
 json_array_create_1(struct json *elem0)
 {
-    struct json **elements = xmalloc(sizeof *elements);
-    elements[0] = elem0;
-    return json_array_create(elements, 1);
+    struct json *json = json_create(JSON_ARRAY);
+
+    json->storage_type = JSON_ARRAY_INLINE_1;
+    json->elements[0] = elem0;
+
+    return json;
 }
 
 struct json *
 json_array_create_2(struct json *elem0, struct json *elem1)
 {
-    struct json **elements = xmalloc(2 * sizeof *elements);
-    elements[0] = elem0;
-    elements[1] = elem1;
-    return json_array_create(elements, 2);
+    struct json *json = json_create(JSON_ARRAY);
+
+    json->storage_type = JSON_ARRAY_INLINE_2;
+    json->elements[0] = elem0;
+    json->elements[1] = elem1;
+
+    return json;
 }
 
 struct json *
 json_array_create_3(struct json *elem0, struct json *elem1, struct json *elem2)
 {
-    struct json **elements = xmalloc(3 * sizeof *elements);
-    elements[0] = elem0;
-    elements[1] = elem1;
-    elements[2] = elem2;
-    return json_array_create(elements, 3);
+    struct json *json = json_create(JSON_ARRAY);
+
+    json->storage_type = JSON_ARRAY_INLINE_3;
+    json->elements[0] = elem0;
+    json->elements[1] = elem1;
+    json->elements[2] = elem2;
+
+    return json;
 }
 
 bool
@@ -399,14 +468,28 @@  size_t
 json_array_size(const struct json *json)
 {
     ovs_assert(json->type == JSON_ARRAY);
-    return json->array.size;
+    if (json->storage_type == JSON_ARRAY_DYNAMIC) {
+        return json->array.size;
+    }
+    return json->storage_type - JSON_ARRAY_DYNAMIC;
 }
 
 const struct json *
 json_array_at(const struct json *json, size_t index)
 {
     ovs_assert(json->type == JSON_ARRAY);
-    return (json->array.size > index) ? json->array.elements[index] : NULL;
+
+    if (json->storage_type == JSON_ARRAY_DYNAMIC) {
+        if (json->array.size <= index) {
+            return NULL;
+        }
+        return json->array.elements[index];
+    }
+
+    if (json->storage_type - JSON_ARRAY_DYNAMIC <= index) {
+        return NULL;
+    }
+    return json->elements[index];
 }
 
 struct shash *
@@ -516,7 +599,9 @@  json_destroy_array(struct json *json, bool yield)
             json_destroy(CONST_CAST(struct json *, json_array_at(json, i)));
         }
     }
-    free(json->array.elements);
+    if (json->storage_type == JSON_ARRAY_DYNAMIC) {
+        free(json->array.elements);
+    }
 }
 
 static struct json *json_deep_clone_object(const struct shash *object);