From patchwork Fri Sep 17 17:17:39 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ilya Maximets X-Patchwork-Id: 1529530 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.133; helo=smtp2.osuosl.org; envelope-from=ovs-dev-bounces@openvswitch.org; receiver=) Received: from smtp2.osuosl.org (smtp2.osuosl.org [140.211.166.133]) (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 4HB0yb1XMxz9sSn for ; Sat, 18 Sep 2021 03:17:59 +1000 (AEST) Received: from localhost (localhost [127.0.0.1]) by smtp2.osuosl.org (Postfix) with ESMTP id 1DDEE4079C; Fri, 17 Sep 2021 17:17:56 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from smtp2.osuosl.org ([127.0.0.1]) by localhost (smtp2.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id GMBSOf_6LGmn; Fri, 17 Sep 2021 17:17:54 +0000 (UTC) Received: from lists.linuxfoundation.org (lf-lists.osuosl.org [IPv6:2605:bc80:3010:104::8cd3:938]) by smtp2.osuosl.org (Postfix) with ESMTPS id 73E1440796; Fri, 17 Sep 2021 17:17:53 +0000 (UTC) Received: from lf-lists.osuosl.org (localhost [127.0.0.1]) by lists.linuxfoundation.org (Postfix) with ESMTP id 354B0C0026; Fri, 17 Sep 2021 17:17:53 +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 2D50CC0029 for ; Fri, 17 Sep 2021 17:17:52 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp3.osuosl.org (Postfix) with ESMTP id A4EE061BCF for ; Fri, 17 Sep 2021 17:17:51 +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 nVdPtmyfvzHt for ; Fri, 17 Sep 2021 17:17:51 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.8.0 Received: from relay3-d.mail.gandi.net (relay3-d.mail.gandi.net [217.70.183.195]) by smtp3.osuosl.org (Postfix) with ESMTPS id 8072C61BA7 for ; Fri, 17 Sep 2021 17:17:50 +0000 (UTC) Received: (Authenticated sender: i.maximets@ovn.org) by relay3-d.mail.gandi.net (Postfix) with ESMTPSA id F000560002; Fri, 17 Sep 2021 17:17:47 +0000 (UTC) From: Ilya Maximets To: ovs-dev@openvswitch.org Date: Fri, 17 Sep 2021 19:17:39 +0200 Message-Id: <20210917171739.1060303-3-i.maximets@ovn.org> X-Mailer: git-send-email 2.31.1 In-Reply-To: <20210917171739.1060303-1-i.maximets@ovn.org> References: <20210917171739.1060303-1-i.maximets@ovn.org> MIME-Version: 1.0 Cc: Ilya Maximets , Dumitru Ceara Subject: [ovs-dev] [PATCH v2 2/2] 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 --- lib/ovsdb-data.c | 52 +++++++++++++++++++++++++++++++++++++----------- 1 file changed, 40 insertions(+), 12 deletions(-) diff --git a/lib/ovsdb-data.c b/lib/ovsdb-data.c index 11bf95fed..b6129d6ba 100644 --- a/lib/ovsdb-data.c +++ b/lib/ovsdb-data.c @@ -2019,26 +2019,54 @@ 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; + size_t i, ai, bi, n_idx; + size_t *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 (bi = 0; bi < b->n; bi++) { + ai = ovsdb_datum_find(b, bi, a, b_type); + if (ai == UINT_MAX || (n_idx && ai <= idx[n_idx - 1])) { + /* No such atom in 'a' or it's already marked for removal. */ + continue; } + 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); + + for (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. */ + unsigned int start_idx = (i > 0) ? idx[i - 1] + 1 : 0; + ovsdb_datum_push_unsafe(&result, a, start_idx, ai - start_idx, a_type); + } + /* Copying remaining atoms. */ + ovsdb_datum_push_unsafe(&result, a, idx[n_idx - 1] + 1, + a->n - (idx[n_idx - 1] + 1), a_type); + a->n = 0; + + ovsdb_datum_swap(&result, a); + ovsdb_datum_destroy(&result, a_type); + free(idx); } struct ovsdb_symbol_table *