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 *