From patchwork Wed Sep 22 23:47:22 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ilya Maximets X-Patchwork-Id: 1531474 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=openvswitch.org (client-ip=2605:bc80:3010::138; helo=smtp1.osuosl.org; envelope-from=ovs-dev-bounces@openvswitch.org; receiver=) Received: from smtp1.osuosl.org (smtp1.osuosl.org [IPv6:2605:bc80:3010::138]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4HFFMy4Sy3z9sW5 for ; Thu, 23 Sep 2021 09:47:42 +1000 (AEST) Received: from localhost (localhost [127.0.0.1]) by smtp1.osuosl.org (Postfix) with ESMTP id 6023384226; Wed, 22 Sep 2021 23:47:39 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from smtp1.osuosl.org ([127.0.0.1]) by localhost (smtp1.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id MzuVIV7E59Cv; Wed, 22 Sep 2021 23:47:38 +0000 (UTC) Received: from lists.linuxfoundation.org (lf-lists.osuosl.org [140.211.9.56]) by smtp1.osuosl.org (Postfix) with ESMTPS id 1A5D08420F; Wed, 22 Sep 2021 23:47:37 +0000 (UTC) Received: from lf-lists.osuosl.org (localhost [127.0.0.1]) by lists.linuxfoundation.org (Postfix) with ESMTP id 0510DC0024; Wed, 22 Sep 2021 23:47:35 +0000 (UTC) X-Original-To: ovs-dev@openvswitch.org Delivered-To: ovs-dev@lists.linuxfoundation.org Received: from smtp3.osuosl.org (smtp3.osuosl.org [140.211.166.136]) by lists.linuxfoundation.org (Postfix) with ESMTP id B5C18C000D for ; Wed, 22 Sep 2021 23:47:33 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp3.osuosl.org (Postfix) with ESMTP id A46D060B85 for ; Wed, 22 Sep 2021 23:47:33 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from smtp3.osuosl.org ([127.0.0.1]) by localhost (smtp3.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 7RSVXmp5eT2P for ; Wed, 22 Sep 2021 23:47:32 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.8.0 Received: from relay4-d.mail.gandi.net (relay4-d.mail.gandi.net [217.70.183.196]) by smtp3.osuosl.org (Postfix) with ESMTPS id 27160605BE for ; Wed, 22 Sep 2021 23:47:31 +0000 (UTC) Received: (Authenticated sender: i.maximets@ovn.org) by relay4-d.mail.gandi.net (Postfix) with ESMTPSA id 3D22AE0004; Wed, 22 Sep 2021 23:47:29 +0000 (UTC) From: Ilya Maximets To: ovs-dev@openvswitch.org Date: Thu, 23 Sep 2021 01:47:22 +0200 Message-Id: <20210922234724.3697532-2-i.maximets@ovn.org> X-Mailer: git-send-email 2.31.1 In-Reply-To: <20210922234724.3697532-1-i.maximets@ovn.org> References: <20210922234724.3697532-1-i.maximets@ovn.org> MIME-Version: 1.0 Cc: Ilya Maximets , Dumitru Ceara Subject: [ovs-dev] [PATCH v3 1/3] ovsdb-data: Optimize union of sets. X-BeenThere: ovs-dev@openvswitch.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: ovs-dev-bounces@openvswitch.org Sender: "dev" Current algorithm of ovsdb_datum_union looks like this: for-each atom in b: if not bin_search(a, atom): push(a, clone(atom)) quicksort(a) So, the complexity looks like this: Nb * log2(Na) + Nb + (Na + Nb) * log2(Na + Nb) Comparisons clones Comparisons for quicksort for search ovsdb_datum_union() is heavily used in database transactions while new element is added to a set. For example, if new logical switch port is added to a logical switch in OVN. This is a very common use case where CMS adds one new port to an existing switch that already has, let's say, 100 ports. For this case ovsdb-server will have to perform: 1 * log2(100) + 1 clone + 101 * log2(101) Comparisons Comparisons for for search quicksort. ~7 1 ~707 Roughly 714 comparisons of atoms and 1 clone. Since binary search can give us position, where new atom should go (it's the 'low' index after the search completion) for free, the logic can be re-worked like this: copied = 0 for-each atom in b: desired_position = bin_search(a, atom) push(result, a[ copied : desired_position - 1 ]) copied = desired_position push(result, clone(atom)) push(result, a[ copied : Na ]) swap(a, result) Complexity of this schema: Nb * log2(Na) + Nb + Na Comparisons clones memory copy on push for search 'swap' is just a swap of a few pointers. 'push' is not a 'clone', but a simple memory copy of 'union ovsdb_atom'. In general, this schema substitutes complexity of a quicksort with complexity of a memory copy of Na atom structures, where we're not even copying strings that these atoms are pointing to. Complexity in the example above goes down from 714 comparisons to 7 comparisons and memcpy of 100 * sizeof (union ovsdb_atom) bytes. General complexity of a memory copy should always be lower than complexity of a quicksort, especially because these copies usually performed in bulk, so this new schema should work faster for any input. All in all, this change allows to execute several times more transactions per second for transactions that adds new entries to sets. Alternatively, union can be implemented as a linear merge of two sorted arrays, but this will result in O(Na) comparisons, which is more than Nb * log2(Na) in common case, since Na is usually far bigger than Nb. Linear merge will also mean per-atom memory copies instead of copying in bulk. 'replace' functionality of ovsdb_datum_union() had no users, so it just removed. But it can easily be added back if needed in the future. Signed-off-by: Ilya Maximets Acked-by: Han Zhou Acked-by: Mark D. Gray --- lib/db-ctl-base.c | 28 +++++++------ lib/ovsdb-data.c | 103 ++++++++++++++++++++++++++++++---------------- lib/ovsdb-data.h | 10 ++--- lib/ovsdb-idl.c | 29 ++++++------- ovsdb/mutation.c | 2 +- vswitchd/bridge.c | 6 +-- 6 files changed, 105 insertions(+), 73 deletions(-) diff --git a/lib/db-ctl-base.c b/lib/db-ctl-base.c index 77cc76a9f..3923683fd 100644 --- a/lib/db-ctl-base.c +++ b/lib/db-ctl-base.c @@ -314,15 +314,18 @@ get_row_by_id(struct ctl_context *ctx, row, id->name_column, key, value); /* Extract the name from the column. */ - const union ovsdb_atom *name; + const union ovsdb_atom *name = NULL; if (!id->key) { name = datum->n == 1 ? &datum->keys[0] : NULL; } else { const union ovsdb_atom key_atom = { .string = CONST_CAST(char *, id->key) }; - unsigned int i = ovsdb_datum_find_key(datum, &key_atom, - OVSDB_TYPE_STRING); - name = i == UINT_MAX ? NULL : &datum->values[i]; + unsigned int i; + + if (ovsdb_datum_find_key(datum, &key_atom, + OVSDB_TYPE_STRING, &i)) { + name = &datum->values[i]; + } } if (!name) { continue; @@ -819,14 +822,14 @@ check_condition(const struct ovsdb_idl_table_class *table, goto out; } - idx = ovsdb_datum_find_key(have_datum, - &want_key, column->type.key.type); - if (idx == UINT_MAX && !is_set_operator(operator)) { + bool found = ovsdb_datum_find_key(have_datum, &want_key, + column->type.key.type, &idx); + if (!found && !is_set_operator(operator)) { retval = false; } else { struct ovsdb_datum a; - if (idx != UINT_MAX) { + if (found) { a.n = 1; a.keys = &have_datum->values[idx]; a.values = NULL; @@ -992,9 +995,8 @@ cmd_get(struct ctl_context *ctx) return; } - idx = ovsdb_datum_find_key(datum, &key, - column->type.key.type); - if (idx == UINT_MAX) { + if (!ovsdb_datum_find_key(datum, &key, + column->type.key.type, &idx)) { if (must_exist) { ctl_error( ctx, "no key \"%s\" in %s record \"%s\" column %s", @@ -1375,7 +1377,7 @@ set_column(const struct ovsdb_idl_table_class *table, ovsdb_atom_destroy(&value, column->type.value.type); ovsdb_datum_union(&datum, ovsdb_idl_read(row, column), - &column->type, false); + &column->type); ovsdb_idl_txn_verify(row, column); ovsdb_idl_txn_write(row, column, &datum); } else { @@ -1514,7 +1516,7 @@ cmd_add(struct ctl_context *ctx) ovsdb_datum_destroy(&old, &column->type); return; } - ovsdb_datum_union(&old, &add, type, false); + ovsdb_datum_union(&old, &add, type); ovsdb_datum_destroy(&add, type); } if (old.n > type->n_max) { diff --git a/lib/ovsdb-data.c b/lib/ovsdb-data.c index 1f491a98b..7f9ff83f4 100644 --- a/lib/ovsdb-data.c +++ b/lib/ovsdb-data.c @@ -799,7 +799,7 @@ ovsdb_atom_check_constraints(const union ovsdb_atom *atom, const struct ovsdb_base_type *base) { if (base->enum_ - && ovsdb_datum_find_key(base->enum_, atom, base->type) == UINT_MAX) { + && !ovsdb_datum_find_key(base->enum_, atom, base->type, NULL)) { struct ovsdb_error *error; struct ds actual = DS_EMPTY_INITIALIZER; struct ds valid = DS_EMPTY_INITIALIZER; @@ -1784,14 +1784,16 @@ ovsdb_datum_compare_3way(const struct ovsdb_datum *a, a->n)); } -/* If 'key' is one of the keys in 'datum', returns its index within 'datum', - * otherwise UINT_MAX. 'key.type' must be the type of the atoms stored in the - * 'keys' array in 'datum'. +/* If 'key' is one of the keys in 'datum', returns 'true' and sets '*pos' to + * its index within 'datum', otherwise returns 'false' and sets '*pos' to the + * index where 'key' should have been. 'key.type' must be the type of the + * atoms stored in the 'keys' array in 'datum'. */ -unsigned int +bool ovsdb_datum_find_key(const struct ovsdb_datum *datum, const union ovsdb_atom *key, - enum ovsdb_atomic_type key_type) + enum ovsdb_atomic_type key_type, + unsigned int *pos) { unsigned int low = 0; unsigned int high = datum->n; @@ -1803,10 +1805,16 @@ ovsdb_datum_find_key(const struct ovsdb_datum *datum, } else if (cmp > 0) { low = idx + 1; } else { - return idx; + if (pos) { + *pos = idx; + } + return true; } } - return UINT_MAX; + if (pos) { + *pos = low; + } + return false; } /* If 'key' and 'value' is one of the key-value pairs in 'datum', returns its @@ -1821,10 +1829,11 @@ ovsdb_datum_find_key_value(const struct ovsdb_datum *datum, const union ovsdb_atom *value, enum ovsdb_atomic_type value_type) { - unsigned int idx = ovsdb_datum_find_key(datum, key, key_type); - if (idx != UINT_MAX - && value_type != OVSDB_TYPE_VOID - && !ovsdb_atom_equals(&datum->values[idx], value, value_type)) { + unsigned int idx; + + if (!ovsdb_datum_find_key(datum, key, key_type, &idx) + || (value_type != OVSDB_TYPE_VOID + && !ovsdb_atom_equals(&datum->values[idx], value, value_type))) { idx = UINT_MAX; } return idx; @@ -1948,38 +1957,62 @@ ovsdb_datum_add_unsafe(struct ovsdb_datum *datum, } } +/* Adds 'n' atoms starting from index 'start_idx' from 'src' to the end of + * 'dst'. 'dst' should have enough memory allocated to hold the additional + * 'n' atoms. Atoms are not cloned, i.e. 'dst' will reference the same data. + * Caller also should take care of the result being sorted. */ +static void +ovsdb_datum_push_unsafe(struct ovsdb_datum *dst, + const struct ovsdb_datum *src, + unsigned int start_idx, unsigned int n, + const struct ovsdb_type *type) +{ + memcpy(&dst->keys[dst->n], &src->keys[start_idx], n * sizeof src->keys[0]); + if (type->value.type != OVSDB_TYPE_VOID) { + memcpy(&dst->values[dst->n], &src->values[start_idx], + n * sizeof src->values[0]); + } + dst->n += n; +} + void ovsdb_datum_union(struct ovsdb_datum *a, const struct ovsdb_datum *b, - const struct ovsdb_type *type, bool replace) + const struct ovsdb_type *type) { - unsigned int n; - size_t bi; + struct ovsdb_datum result; + unsigned int copied, pos; - n = a->n; - for (bi = 0; bi < b->n; bi++) { - unsigned int ai; + ovsdb_datum_init_empty(&result); + ovsdb_datum_reallocate(&result, type, a->n + b->n); - ai = ovsdb_datum_find_key(a, &b->keys[bi], type->key.type); - if (ai == UINT_MAX) { - if (n == a->n) { - ovsdb_datum_reallocate(a, type, a->n + (b->n - bi)); - } - ovsdb_atom_clone(&a->keys[n], &b->keys[bi], type->key.type); - if (type->value.type != OVSDB_TYPE_VOID) { - ovsdb_atom_clone(&a->values[n], &b->values[bi], - type->value.type); - } - n++; - } else if (replace && type->value.type != OVSDB_TYPE_VOID) { - ovsdb_atom_destroy(&a->values[ai], type->value.type); - ovsdb_atom_clone(&a->values[ai], &b->values[bi], + copied = 0; + for (size_t bi = 0; bi < b->n; bi++) { + if (ovsdb_datum_find_key(a, &b->keys[bi], type->key.type, &pos)) { + /* Atom with the same key already exists. */ + continue; + } + if (pos > copied) { + /* Need to copy some atoms from 'a' first. */ + ovsdb_datum_push_unsafe(&result, a, copied, pos - copied, type); + copied = pos; + } + /* Inserting new atom from 'b'. */ + ovsdb_atom_clone(&result.keys[result.n], &b->keys[bi], type->key.type); + if (type->value.type != OVSDB_TYPE_VOID) { + ovsdb_atom_clone(&result.values[result.n], &b->values[bi], type->value.type); } + result.n++; } - if (n != a->n) { - a->n = n; - ovs_assert(!ovsdb_datum_sort(a, type->key.type)); + if (a->n > copied) { + /* Copying remaining atoms. */ + ovsdb_datum_push_unsafe(&result, a, copied, a->n - copied, type); } + /* All atoms are copied now. */ + a->n = 0; + + ovsdb_datum_swap(&result, a); + ovsdb_datum_destroy(&result, type); } void diff --git a/lib/ovsdb-data.h b/lib/ovsdb-data.h index aa035ebad..4581e792f 100644 --- a/lib/ovsdb-data.h +++ b/lib/ovsdb-data.h @@ -209,9 +209,10 @@ bool ovsdb_datum_equals(const struct ovsdb_datum *, const struct ovsdb_type *); /* Search. */ -unsigned int ovsdb_datum_find_key(const struct ovsdb_datum *, - const union ovsdb_atom *key, - enum ovsdb_atomic_type key_type); +bool ovsdb_datum_find_key(const struct ovsdb_datum *, + const union ovsdb_atom *key, + enum ovsdb_atomic_type key_type, + unsigned int *pos); unsigned int ovsdb_datum_find_key_value(const struct ovsdb_datum *, const union ovsdb_atom *key, enum ovsdb_atomic_type key_type, @@ -227,8 +228,7 @@ bool ovsdb_datum_excludes_all(const struct ovsdb_datum *, const struct ovsdb_type *); void ovsdb_datum_union(struct ovsdb_datum *, const struct ovsdb_datum *, - const struct ovsdb_type *, - bool replace); + const struct ovsdb_type *); void ovsdb_datum_subtract(struct ovsdb_datum *a, const struct ovsdb_type *a_type, const struct ovsdb_datum *b, diff --git a/lib/ovsdb-idl.c b/lib/ovsdb-idl.c index d3caccec8..c9c567e2c 100644 --- a/lib/ovsdb-idl.c +++ b/lib/ovsdb-idl.c @@ -2840,9 +2840,8 @@ ovsdb_idl_txn_extract_mutations(struct ovsdb_idl_row *row, struct ovsdb_datum *new_datum; unsigned int pos; new_datum = map_op_datum(map_op); - pos = ovsdb_datum_find_key(old_datum, - &new_datum->keys[0], - key_type); + ovsdb_datum_find_key(old_datum, &new_datum->keys[0], + key_type, &pos); if (ovsdb_atom_equals(&new_datum->values[0], &old_datum->values[pos], value_type)) { @@ -2851,11 +2850,9 @@ ovsdb_idl_txn_extract_mutations(struct ovsdb_idl_row *row, } } else if (map_op_type(map_op) == MAP_OP_DELETE){ /* Verify that there is a key to delete. */ - unsigned int pos; - pos = ovsdb_datum_find_key(old_datum, - &map_op_datum(map_op)->keys[0], - key_type); - if (pos == UINT_MAX) { + if (!ovsdb_datum_find_key(old_datum, + &map_op_datum(map_op)->keys[0], + key_type, NULL)) { /* No key to delete. Move on to next update. */ VLOG_WARN("Trying to delete a key that doesn't " "exist in the map."); @@ -2950,11 +2947,9 @@ ovsdb_idl_txn_extract_mutations(struct ovsdb_idl_row *row, any_ins = true; } else { /* SETP_OP_DELETE */ /* Verify that there is a key to delete. */ - unsigned int pos; - pos = ovsdb_datum_find_key(old_datum, - &set_op_datum(set_op)->keys[0], - key_type); - if (pos == UINT_MAX) { + if (!ovsdb_datum_find_key(old_datum, + &set_op_datum(set_op)->keys[0], + key_type, NULL)) { /* No key to delete. Move on to next update. */ VLOG_WARN("Trying to delete a key that doesn't " "exist in the set."); @@ -4119,7 +4114,6 @@ ovsdb_idl_txn_write_partial_map(const struct ovsdb_idl_row *row_, struct ovsdb_idl_row *row = CONST_CAST(struct ovsdb_idl_row *, row_); enum ovsdb_atomic_type key_type; enum map_op_type op_type; - unsigned int pos; const struct ovsdb_datum *old_datum; if (!is_valid_partial_update(row, column, datum)) { @@ -4131,8 +4125,11 @@ ovsdb_idl_txn_write_partial_map(const struct ovsdb_idl_row *row_, /* Find out if this is an insert or an update. */ key_type = column->type.key.type; old_datum = ovsdb_idl_read(row, column); - pos = ovsdb_datum_find_key(old_datum, &datum->keys[0], key_type); - op_type = pos == UINT_MAX ? MAP_OP_INSERT : MAP_OP_UPDATE; + if (ovsdb_datum_find_key(old_datum, &datum->keys[0], key_type, NULL)) { + op_type = MAP_OP_UPDATE; + } else { + op_type = MAP_OP_INSERT; + } ovsdb_idl_txn_add_map_op(row, column, datum, op_type); } diff --git a/ovsdb/mutation.c b/ovsdb/mutation.c index 56edc5f00..03d1c3499 100644 --- a/ovsdb/mutation.c +++ b/ovsdb/mutation.c @@ -383,7 +383,7 @@ ovsdb_mutation_set_execute(struct ovsdb_row *row, break; case OVSDB_M_INSERT: - ovsdb_datum_union(dst, arg, dst_type, false); + ovsdb_datum_union(dst, arg, dst_type); error = ovsdb_mutation_check_count(dst, dst_type); break; diff --git a/vswitchd/bridge.c b/vswitchd/bridge.c index cb7c5cb76..c790a56ad 100644 --- a/vswitchd/bridge.c +++ b/vswitchd/bridge.c @@ -4229,7 +4229,7 @@ bridge_configure_aa(struct bridge *br) union ovsdb_atom atom; atom.integer = m->isid; - if (ovsdb_datum_find_key(mc, &atom, OVSDB_TYPE_INTEGER) == UINT_MAX) { + if (!ovsdb_datum_find_key(mc, &atom, OVSDB_TYPE_INTEGER, NULL)) { VLOG_INFO("Deleting isid=%"PRIu32", vlan=%"PRIu16, m->isid, m->vlan); bridge_aa_mapping_destroy(m); @@ -4826,7 +4826,7 @@ queue_ids_include(const struct ovsdb_datum *queues, int64_t target) union ovsdb_atom atom; atom.integer = target; - return ovsdb_datum_find_key(queues, &atom, OVSDB_TYPE_INTEGER) != UINT_MAX; + return ovsdb_datum_find_key(queues, &atom, OVSDB_TYPE_INTEGER, NULL); } static void @@ -5020,7 +5020,7 @@ bridge_configure_mirrors(struct bridge *br) union ovsdb_atom atom; atom.uuid = m->uuid; - if (ovsdb_datum_find_key(mc, &atom, OVSDB_TYPE_UUID) == UINT_MAX) { + if (!ovsdb_datum_find_key(mc, &atom, OVSDB_TYPE_UUID, NULL)) { mirror_destroy(m); } } From patchwork Wed Sep 22 23:47:23 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ilya Maximets X-Patchwork-Id: 1531475 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=openvswitch.org (client-ip=140.211.166.138; helo=smtp1.osuosl.org; envelope-from=ovs-dev-bounces@openvswitch.org; receiver=) Received: from smtp1.osuosl.org (smtp1.osuosl.org [140.211.166.138]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4HFFN14nL6z9sW5 for ; Thu, 23 Sep 2021 09:47:45 +1000 (AEST) Received: from localhost (localhost [127.0.0.1]) by smtp1.osuosl.org (Postfix) with ESMTP id CD45C8420C; Wed, 22 Sep 2021 23:47:41 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from smtp1.osuosl.org ([127.0.0.1]) by localhost (smtp1.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 9RALsB1Ik7aH; Wed, 22 Sep 2021 23:47:40 +0000 (UTC) Received: from lists.linuxfoundation.org (lf-lists.osuosl.org [IPv6:2605:bc80:3010:104::8cd3:938]) by smtp1.osuosl.org (Postfix) with ESMTPS id 8B15B8422A; Wed, 22 Sep 2021 23:47:39 +0000 (UTC) Received: from lf-lists.osuosl.org (localhost [127.0.0.1]) by lists.linuxfoundation.org (Postfix) with ESMTP id 5E324C000D; Wed, 22 Sep 2021 23:47:39 +0000 (UTC) X-Original-To: ovs-dev@openvswitch.org Delivered-To: ovs-dev@lists.linuxfoundation.org Received: from smtp1.osuosl.org (smtp1.osuosl.org [140.211.166.138]) by lists.linuxfoundation.org (Postfix) with ESMTP id 93827C000F for ; Wed, 22 Sep 2021 23:47:35 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp1.osuosl.org (Postfix) with ESMTP id 51FF3841E9 for ; Wed, 22 Sep 2021 23:47:35 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from smtp1.osuosl.org ([127.0.0.1]) by localhost (smtp1.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id D0r52xCbZpIm for ; Wed, 22 Sep 2021 23:47:34 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.8.0 Received: from relay4-d.mail.gandi.net (relay4-d.mail.gandi.net [217.70.183.196]) by smtp1.osuosl.org (Postfix) with ESMTPS id 38E90840BC for ; Wed, 22 Sep 2021 23:47:33 +0000 (UTC) Received: (Authenticated sender: i.maximets@ovn.org) by relay4-d.mail.gandi.net (Postfix) with ESMTPSA id 96346E0005; Wed, 22 Sep 2021 23:47:31 +0000 (UTC) From: Ilya Maximets To: ovs-dev@openvswitch.org Date: Thu, 23 Sep 2021 01:47:23 +0200 Message-Id: <20210922234724.3697532-3-i.maximets@ovn.org> X-Mailer: git-send-email 2.31.1 In-Reply-To: <20210922234724.3697532-1-i.maximets@ovn.org> References: <20210922234724.3697532-1-i.maximets@ovn.org> MIME-Version: 1.0 Cc: Ilya Maximets , Dumitru Ceara Subject: [ovs-dev] [PATCH v3 2/3] ovsdb-data: Optimize subtraction of sets. X-BeenThere: ovs-dev@openvswitch.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: ovs-dev-bounces@openvswitch.org Sender: "dev" Current algorithm for ovsdb_datum_subtract looks like this: for-each atom in a: if atom in b: swap(atom, ) destroy(atom) quicksort(a) Complexity: Na * log2(Nb) + (Na - Nb) * log2(Na - Nb) Search Comparisons for quicksort It's not optimal, especially because Nb << Na in a vast majority of cases. Reversing the search phase to look up atoms from 'b' in 'a', and closing gaps from deleted elements in 'a' by plain memory copy to avoid quicksort. Resulted complexity: Nb * log2(Na) + (Na - Nb) Search Memory copies Subtraction is heavily used while executing database transactions. For example, to remove one port from a logical switch in OVN. Complexity of such operation if original logical switch had 100 ports goes down from 100 * log2(1) = 100 comparisons for search and 99 * log2(99) = 656 comparisons for quicksort ------------------------------ 756 comparisons in total to only 1 * log2(100) = 7 comparisons for search + memory copy of 99 * sizeof (union ovsdb_atom) bytes. We could use memmove to close the gaps after removing atoms, but it will lead to 2 memory copies inside the call, while we can perform only one to the temporary 'result' and swap pointers. Performance in cases, where sizes of 'a' and 'b' are comparable, should not change. Cases with Nb >> Na should not happen in practice. All in all, this change allows ovsdb-server to perform several times more transactions, that removes elements from sets, per second. Signed-off-by: Ilya Maximets Acked-by: Han Zhou Acked-by: Mark D. Gray --- lib/ovsdb-data.c | 53 +++++++++++++++++++++++++++++++++++++----------- 1 file changed, 41 insertions(+), 12 deletions(-) diff --git a/lib/ovsdb-data.c b/lib/ovsdb-data.c index 7f9ff83f4..5297f91ed 100644 --- a/lib/ovsdb-data.c +++ b/lib/ovsdb-data.c @@ -2020,26 +2020,55 @@ ovsdb_datum_subtract(struct ovsdb_datum *a, const struct ovsdb_type *a_type, const struct ovsdb_datum *b, const struct ovsdb_type *b_type) { - bool changed = false; - size_t i; + unsigned int *idx, ai; + size_t n_idx; ovs_assert(a_type->key.type == b_type->key.type); ovs_assert(a_type->value.type == b_type->value.type || b_type->value.type == OVSDB_TYPE_VOID); - /* XXX The big-O of this could easily be improved. */ - for (i = 0; i < a->n; ) { - unsigned int idx = ovsdb_datum_find(a, i, b, b_type); - if (idx != UINT_MAX) { - changed = true; - ovsdb_datum_remove_unsafe(a, i, a_type); - } else { - i++; + idx = xmalloc(b->n * sizeof *idx); + n_idx = 0; + for (size_t bi = 0; bi < b->n; bi++) { + ai = ovsdb_datum_find(b, bi, a, b_type); + if (ai == UINT_MAX) { + /* No such atom in 'a'. */ + continue; } + /* Not destroying right away since ovsdb_datum_find() will use them. */ + idx[n_idx++] = ai; } - if (changed) { - ovsdb_datum_sort_assert(a, a_type->key.type); + if (!n_idx) { + free(idx); + return; } + + struct ovsdb_datum result; + + ovsdb_datum_init_empty(&result); + ovsdb_datum_reallocate(&result, a_type, a->n - n_idx); + + unsigned int start_idx = 0; + for (size_t i = 0; i < n_idx; i++) { + ai = idx[i]; + + /* Destroying atom. */ + ovsdb_atom_destroy(&a->keys[ai], a_type->key.type); + if (a_type->value.type != OVSDB_TYPE_VOID) { + ovsdb_atom_destroy(&a->values[ai], a_type->value.type); + } + + /* Copy non-removed atoms from 'a' to result. */ + ovsdb_datum_push_unsafe(&result, a, start_idx, ai - start_idx, a_type); + start_idx = idx[i] + 1; + } + /* Copying remaining atoms. */ + ovsdb_datum_push_unsafe(&result, a, start_idx, a->n - start_idx, a_type); + a->n = 0; + + ovsdb_datum_swap(&result, a); + ovsdb_datum_destroy(&result, a_type); + free(idx); } struct ovsdb_symbol_table * From patchwork Wed Sep 22 23:47:24 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ilya Maximets X-Patchwork-Id: 1531476 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=openvswitch.org (client-ip=2605:bc80:3010::137; helo=smtp4.osuosl.org; envelope-from=ovs-dev-bounces@openvswitch.org; receiver=) Received: from smtp4.osuosl.org (smtp4.osuosl.org [IPv6:2605:bc80:3010::137]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4HFFN523q9z9sW5 for ; Thu, 23 Sep 2021 09:47:49 +1000 (AEST) Received: from localhost (localhost [127.0.0.1]) by smtp4.osuosl.org (Postfix) with ESMTP id 14D03415F2; Wed, 22 Sep 2021 23:47:46 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from smtp4.osuosl.org ([127.0.0.1]) by localhost (smtp4.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id wNlrQ-OWVDVt; Wed, 22 Sep 2021 23:47:43 +0000 (UTC) Received: from lists.linuxfoundation.org (lf-lists.osuosl.org [140.211.9.56]) by smtp4.osuosl.org (Postfix) with ESMTPS id 45C094159F; Wed, 22 Sep 2021 23:47:41 +0000 (UTC) Received: from lf-lists.osuosl.org (localhost [127.0.0.1]) by lists.linuxfoundation.org (Postfix) with ESMTP id 3F021C0025; Wed, 22 Sep 2021 23:47:40 +0000 (UTC) X-Original-To: ovs-dev@openvswitch.org Delivered-To: ovs-dev@lists.linuxfoundation.org Received: from smtp1.osuosl.org (smtp1.osuosl.org [140.211.166.138]) by lists.linuxfoundation.org (Postfix) with ESMTP id CEF70C001D for ; Wed, 22 Sep 2021 23:47:37 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp1.osuosl.org (Postfix) with ESMTP id 86860841E9 for ; Wed, 22 Sep 2021 23:47:37 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from smtp1.osuosl.org ([127.0.0.1]) by localhost (smtp1.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id B1_cHW_dwcCl for ; Wed, 22 Sep 2021 23:47:36 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.8.0 Received: from relay4-d.mail.gandi.net (relay4-d.mail.gandi.net [217.70.183.196]) by smtp1.osuosl.org (Postfix) with ESMTPS id 511A2841F6 for ; Wed, 22 Sep 2021 23:47:36 +0000 (UTC) Received: (Authenticated sender: i.maximets@ovn.org) by relay4-d.mail.gandi.net (Postfix) with ESMTPSA id C6FAFE0004; Wed, 22 Sep 2021 23:47:33 +0000 (UTC) From: Ilya Maximets To: ovs-dev@openvswitch.org Date: Thu, 23 Sep 2021 01:47:24 +0200 Message-Id: <20210922234724.3697532-4-i.maximets@ovn.org> X-Mailer: git-send-email 2.31.1 In-Reply-To: <20210922234724.3697532-1-i.maximets@ovn.org> References: <20210922234724.3697532-1-i.maximets@ovn.org> MIME-Version: 1.0 Cc: Ilya Maximets , Dumitru Ceara Subject: [ovs-dev] [PATCH v3 3/3] ovsdb-datum: Add function to apply diff in-place. X-BeenThere: ovs-dev@openvswitch.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: ovs-dev-bounces@openvswitch.org Sender: "dev" ovsdb_datum_apply_diff() is heavily used in ovsdb transactions, but it's linear in terms of number of comparisons. And it also clones all the atoms along the way. In most cases size of a diff is much smaller than the size of the original datum, this allows to perform the same operation in-place with only O(diff->n * log2(old->n)) comparisons and O(old->n + diff->n) memory copies with memcpy. Using this function while applying diffs read from the storage gives a significant performance boost and allows to execute much more transactions per second. Signed-off-by: Ilya Maximets Acked-by: Mark D. Gray --- At the first glance this function seems very similar to 'union' and 'subtract' and even more general version of them, but I'm not sure if we can actually combine them somehow without sacrificing code clarity while trying to handle all the corner cases. lib/ovsdb-data.c | 100 ++++++++++++++++++++++++++++++++++++++++++++ lib/ovsdb-data.h | 6 +++ ovsdb/file.c | 10 ++--- tests/ovsdb-data.at | 12 ++++++ tests/test-ovsdb.c | 17 ++++++++ 5 files changed, 139 insertions(+), 6 deletions(-) diff --git a/lib/ovsdb-data.c b/lib/ovsdb-data.c index 5297f91ed..90f3b4a53 100644 --- a/lib/ovsdb-data.c +++ b/lib/ovsdb-data.c @@ -2247,6 +2247,106 @@ ovsdb_datum_diff(struct ovsdb_datum *diff, } } +/* Apply 'diff' to 'a'. + * + * Return NULL if the 'a' is successfully updated, otherwise, return + * ovsdb_error. */ +struct ovsdb_error * +ovsdb_datum_apply_diff_in_place(struct ovsdb_datum *a, + const struct ovsdb_datum *diff, + const struct ovsdb_type *type) +{ + struct ovsdb_error *error = NULL; + struct ovsdb_datum result; + size_t i, new_size; + unsigned int *idx, pos; + enum { + DIFF_OP_ADD, + DIFF_OP_REMOVE, + DIFF_OP_UPDATE, + } *operation; + + if (!ovsdb_type_is_composite(type)) { + ovsdb_datum_destroy(a, type); + ovsdb_datum_clone(a, diff, type); + return NULL; + } + + operation = xmalloc(diff->n * sizeof *operation); + idx = xmalloc(diff->n * sizeof *idx); + new_size = a->n; + for (i = 0; i < diff->n; i++) { + if (!ovsdb_datum_find_key(a, &diff->keys[i], type->key.type, &pos)) { + operation[i] = DIFF_OP_ADD; + new_size++; + } else if (type->value.type != OVSDB_TYPE_VOID + && !ovsdb_atom_equals(&diff->values[i], &a->values[pos], + type->value.type)) { + operation[i] = DIFF_OP_UPDATE; + } else { + operation[i] = DIFF_OP_REMOVE; + new_size--; + } + idx[i] = pos; + } + + /* Make sure member size of 'new' conforms to type. */ + if (new_size < type->n_min || new_size > type->n_max) { + error = ovsdb_error(NULL, "Datum crated by diff has size error"); + goto exit; + } + + ovsdb_datum_init_empty(&result); + ovsdb_datum_reallocate(&result, type, new_size); + + unsigned int copied = 0; + for (i = 0; i < diff->n; i++) { + pos = idx[i]; + + if (copied < pos) { + /* Copying all atoms that should go before the current one. */ + ovsdb_datum_push_unsafe(&result, a, copied, pos - copied, type); + copied = pos; + } + + switch (operation[i]) { + case DIFF_OP_UPDATE: + case DIFF_OP_ADD: + /* Inserting new atom from 'diff'. */ + ovsdb_atom_clone(&result.keys[result.n], + &diff->keys[i], type->key.type); + if (type->value.type != OVSDB_TYPE_VOID) { + ovsdb_atom_clone(&result.values[result.n], + &diff->values[i], type->value.type); + } + result.n++; + if (operation[i] != DIFF_OP_UPDATE) { + break; + } + /* fall through */ + + case DIFF_OP_REMOVE: + /* Destroying atom. */ + ovsdb_atom_destroy(&a->keys[pos], type->key.type); + if (type->value.type != OVSDB_TYPE_VOID) { + ovsdb_atom_destroy(&a->values[pos], type->value.type); + } + copied++; /* Skipping removed atom. */ + break; + } + } + /* Copying remaining atoms. */ + ovsdb_datum_push_unsafe(&result, a, copied, a->n - copied, type); + a->n = 0; + + ovsdb_datum_swap(&result, a); + ovsdb_datum_destroy(&result, type); +exit: + free(operation); + free(idx); + return error; +} + /* Apply 'diff' to 'old' to regenerate 'new'. * * Return NULL if the 'new' is successfully generated, otherwise, return diff --git a/lib/ovsdb-data.h b/lib/ovsdb-data.h index 4581e792f..b634e97ff 100644 --- a/lib/ovsdb-data.h +++ b/lib/ovsdb-data.h @@ -252,6 +252,12 @@ struct ovsdb_error *ovsdb_datum_apply_diff(struct ovsdb_datum *new_datum, const struct ovsdb_type *type) OVS_WARN_UNUSED_RESULT; +struct ovsdb_error * ovsdb_datum_apply_diff_in_place( + struct ovsdb_datum *a, + const struct ovsdb_datum *diff, + const struct ovsdb_type *type) +OVS_WARN_UNUSED_RESULT; + /* Raw operations that may not maintain the invariants. */ void ovsdb_datum_remove_unsafe(struct ovsdb_datum *, size_t idx, const struct ovsdb_type *); diff --git a/ovsdb/file.c b/ovsdb/file.c index 59220824f..9f44007d9 100644 --- a/ovsdb/file.c +++ b/ovsdb/file.c @@ -113,19 +113,17 @@ ovsdb_file_update_row_from_json(struct ovsdb_row *row, bool converting, if (row_contains_diff && !ovsdb_datum_is_default(&row->fields[column->index], &column->type)) { - struct ovsdb_datum new_datum; - - error = ovsdb_datum_apply_diff(&new_datum, + error = ovsdb_datum_apply_diff_in_place( &row->fields[column->index], &datum, &column->type); ovsdb_datum_destroy(&datum, &column->type); if (error) { return error; } - ovsdb_datum_swap(&datum, &new_datum); + } else { + ovsdb_datum_swap(&row->fields[column->index], &datum); + ovsdb_datum_destroy(&datum, &column->type); } - ovsdb_datum_swap(&row->fields[column->index], &datum); - ovsdb_datum_destroy(&datum, &column->type); } return NULL; diff --git a/tests/ovsdb-data.at b/tests/ovsdb-data.at index 8cd2a26cb..25c6acdac 100644 --- a/tests/ovsdb-data.at +++ b/tests/ovsdb-data.at @@ -846,18 +846,21 @@ OVSDB_CHECK_POSITIVE([generate and apply diff -- integer], [[diff-data '["integer"]' '[0]' '[2]']], [[diff: 2 apply diff: 2 +apply diff in place: 2 OK]]) OVSDB_CHECK_POSITIVE([generate and apply diff -- boolean], [[diff-data '["boolean"]' '[true]' '[false]']], [[diff: false apply diff: false +apply diff in place: false OK]]) OVSDB_CHECK_POSITIVE([generate and apply diff -- string], [[diff-data '["string"]' '["AAA"]' '["BBB"]']], [[diff: "BBB" apply diff: "BBB" +apply diff in place: "BBB" OK]]) dnl Test set modifications. @@ -870,15 +873,19 @@ OVSDB_CHECK_POSITIVE([generate and apply diff -- set], ]], [[diff: ["set",[0,2]] apply diff: ["set",[1,2]] +apply diff in place: ["set",[1,2]] OK diff: 0 apply diff: 1 +apply diff in place: 1 OK diff: ["set",[0,1]] apply diff: ["set",[0,1]] +apply diff in place: ["set",[0,1]] OK diff: ["set",[0,1]] apply diff: ["set",[]] +apply diff in place: ["set",[]] OK]]) dnl Test set modifications causes data to violate set size constrain. @@ -898,18 +905,23 @@ OVSDB_CHECK_POSITIVE([generate and apply diff -- map], ]], [[diff: ["map",[["2 gills","1 chopin"],["2 pints","1 quart"]]] apply diff: ["map",[["2 pints","1 quart"]]] +apply diff in place: ["map",[["2 pints","1 quart"]]] OK diff: ["map",[]] apply diff: ["map",[["2 gills","1 chopin"]]] +apply diff in place: ["map",[["2 gills","1 chopin"]]] OK diff: ["map",[["2 gills","1 chopin"]]] apply diff: ["map",[]] +apply diff in place: ["map",[]] OK diff: ["map",[["2 pints","1 quart"]]] apply diff: ["map",[["2 pints","1 quart"]]] +apply diff in place: ["map",[["2 pints","1 quart"]]] OK diff: ["map",[["2 gills","1 gallon"]]] apply diff: ["map",[["2 gills","1 gallon"]]] +apply diff in place: ["map",[["2 gills","1 gallon"]]] OK]]) OVSDB_CHECK_NEGATIVE([generate and apply diff with map -- size error], diff --git a/tests/test-ovsdb.c b/tests/test-ovsdb.c index 02485b136..86d75dfd9 100644 --- a/tests/test-ovsdb.c +++ b/tests/test-ovsdb.c @@ -512,6 +512,18 @@ do_diff_data(struct ovs_cmdl_context *ctx) ovs_fatal(0, "failed to apply diff"); } + /* Apply diff to 'old' in place. */ + error = ovsdb_datum_apply_diff_in_place(&old, &diff, &type); + if (error) { + char *string = ovsdb_error_to_string_free(error); + ovs_fatal(0, "%s", string); + } + + /* Test to make sure 'old' equals 'new' now. */ + if (!ovsdb_datum_equals(&new, &old, &type)) { + ovs_fatal(0, "failed to apply diff in place"); + } + /* Print diff */ json = ovsdb_datum_to_json(&diff, &type); printf ("diff: "); @@ -522,6 +534,11 @@ do_diff_data(struct ovs_cmdl_context *ctx) printf ("apply diff: "); print_and_free_json(json); + /* Print updated 'old' */ + json = ovsdb_datum_to_json(&old, &type); + printf ("apply diff in place: "); + print_and_free_json(json); + ovsdb_datum_destroy(&new, &type); ovsdb_datum_destroy(&old, &type); ovsdb_datum_destroy(&diff, &type);