get:
Show a patch.

patch:
Update a patch.

put:
Update a patch.

GET /api/patches/1529530/
HTTP 200 OK
Allow: GET, PUT, PATCH, HEAD, OPTIONS
Content-Type: application/json
Vary: Accept

{
    "id": 1529530,
    "url": "http://patchwork.ozlabs.org/api/patches/1529530/",
    "web_url": "http://patchwork.ozlabs.org/project/openvswitch/patch/20210917171739.1060303-3-i.maximets@ovn.org/",
    "project": {
        "id": 47,
        "url": "http://patchwork.ozlabs.org/api/projects/47/",
        "name": "Open vSwitch",
        "link_name": "openvswitch",
        "list_id": "ovs-dev.openvswitch.org",
        "list_email": "ovs-dev@openvswitch.org",
        "web_url": "http://openvswitch.org/",
        "scm_url": "git@github.com:openvswitch/ovs.git",
        "webscm_url": "https://github.com/openvswitch/ovs",
        "list_archive_url": "",
        "list_archive_url_format": "",
        "commit_url_format": ""
    },
    "msgid": "<20210917171739.1060303-3-i.maximets@ovn.org>",
    "list_archive_url": null,
    "date": "2021-09-17T17:17:39",
    "name": "[ovs-dev,v2,2/2] ovsdb-data: Optimize subtraction of sets.",
    "commit_ref": null,
    "pull_url": null,
    "state": "changes-requested",
    "archived": false,
    "hash": "3b572a3bb33f3ae37541a2da6a07101a2a3f755b",
    "submitter": {
        "id": 76798,
        "url": "http://patchwork.ozlabs.org/api/people/76798/",
        "name": "Ilya Maximets",
        "email": "i.maximets@ovn.org"
    },
    "delegate": null,
    "mbox": "http://patchwork.ozlabs.org/project/openvswitch/patch/20210917171739.1060303-3-i.maximets@ovn.org/mbox/",
    "series": [
        {
            "id": 262864,
            "url": "http://patchwork.ozlabs.org/api/series/262864/",
            "web_url": "http://patchwork.ozlabs.org/project/openvswitch/list/?series=262864",
            "date": "2021-09-17T17:17:37",
            "name": "ovsdb: Optimize set operations.",
            "version": 2,
            "mbox": "http://patchwork.ozlabs.org/series/262864/mbox/"
        }
    ],
    "comments": "http://patchwork.ozlabs.org/api/patches/1529530/comments/",
    "check": "success",
    "checks": "http://patchwork.ozlabs.org/api/patches/1529530/checks/",
    "tags": {},
    "related": [],
    "headers": {
        "Return-Path": "<ovs-dev-bounces@openvswitch.org>",
        "X-Original-To": [
            "incoming@patchwork.ozlabs.org",
            "ovs-dev@openvswitch.org"
        ],
        "Delivered-To": [
            "patchwork-incoming@ozlabs.org",
            "ovs-dev@lists.linuxfoundation.org"
        ],
        "Authentication-Results": "ozlabs.org;\n spf=pass (sender SPF authorized) smtp.mailfrom=openvswitch.org\n (client-ip=140.211.166.133; helo=smtp2.osuosl.org;\n envelope-from=ovs-dev-bounces@openvswitch.org; receiver=<UNKNOWN>)",
        "Received": [
            "from smtp2.osuosl.org (smtp2.osuosl.org [140.211.166.133])\n\t(using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)\n\t key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest\n SHA256)\n\t(No client certificate requested)\n\tby ozlabs.org (Postfix) with ESMTPS id 4HB0yb1XMxz9sSn\n\tfor <incoming@patchwork.ozlabs.org>; Sat, 18 Sep 2021 03:17:59 +1000 (AEST)",
            "from localhost (localhost [127.0.0.1])\n\tby smtp2.osuosl.org (Postfix) with ESMTP id 1DDEE4079C;\n\tFri, 17 Sep 2021 17:17:56 +0000 (UTC)",
            "from smtp2.osuosl.org ([127.0.0.1])\n\tby localhost (smtp2.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)\n\twith ESMTP id GMBSOf_6LGmn; Fri, 17 Sep 2021 17:17:54 +0000 (UTC)",
            "from lists.linuxfoundation.org (lf-lists.osuosl.org\n [IPv6:2605:bc80:3010:104::8cd3:938])\n\tby smtp2.osuosl.org (Postfix) with ESMTPS id 73E1440796;\n\tFri, 17 Sep 2021 17:17:53 +0000 (UTC)",
            "from lf-lists.osuosl.org (localhost [127.0.0.1])\n\tby lists.linuxfoundation.org (Postfix) with ESMTP id 354B0C0026;\n\tFri, 17 Sep 2021 17:17:53 +0000 (UTC)",
            "from smtp3.osuosl.org (smtp3.osuosl.org [140.211.166.136])\n by lists.linuxfoundation.org (Postfix) with ESMTP id 2D50CC0029\n for <ovs-dev@openvswitch.org>; Fri, 17 Sep 2021 17:17:52 +0000 (UTC)",
            "from localhost (localhost [127.0.0.1])\n by smtp3.osuosl.org (Postfix) with ESMTP id A4EE061BCF\n for <ovs-dev@openvswitch.org>; Fri, 17 Sep 2021 17:17:51 +0000 (UTC)",
            "from smtp3.osuosl.org ([127.0.0.1])\n by localhost (smtp3.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)\n with ESMTP id nVdPtmyfvzHt for <ovs-dev@openvswitch.org>;\n Fri, 17 Sep 2021 17:17:51 +0000 (UTC)",
            "from relay3-d.mail.gandi.net (relay3-d.mail.gandi.net\n [217.70.183.195])\n by smtp3.osuosl.org (Postfix) with ESMTPS id 8072C61BA7\n for <ovs-dev@openvswitch.org>; Fri, 17 Sep 2021 17:17:50 +0000 (UTC)",
            "(Authenticated sender: i.maximets@ovn.org)\n by relay3-d.mail.gandi.net (Postfix) with ESMTPSA id F000560002;\n Fri, 17 Sep 2021 17:17:47 +0000 (UTC)"
        ],
        "X-Virus-Scanned": [
            "amavisd-new at osuosl.org",
            "amavisd-new at osuosl.org"
        ],
        "X-Greylist": "domain auto-whitelisted by SQLgrey-1.8.0",
        "From": "Ilya Maximets <i.maximets@ovn.org>",
        "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 <i.maximets@ovn.org>, Dumitru Ceara <dceara@redhat.com>",
        "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": "<ovs-dev.openvswitch.org>",
        "List-Unsubscribe": "<https://mail.openvswitch.org/mailman/options/ovs-dev>,\n <mailto:ovs-dev-request@openvswitch.org?subject=unsubscribe>",
        "List-Archive": "<http://mail.openvswitch.org/pipermail/ovs-dev/>",
        "List-Post": "<mailto:ovs-dev@openvswitch.org>",
        "List-Help": "<mailto:ovs-dev-request@openvswitch.org?subject=help>",
        "List-Subscribe": "<https://mail.openvswitch.org/mailman/listinfo/ovs-dev>,\n <mailto:ovs-dev-request@openvswitch.org?subject=subscribe>",
        "Content-Type": "text/plain; charset=\"us-ascii\"",
        "Content-Transfer-Encoding": "7bit",
        "Errors-To": "ovs-dev-bounces@openvswitch.org",
        "Sender": "\"dev\" <ovs-dev-bounces@openvswitch.org>"
    },
    "content": "Current algorithm for ovsdb_datum_subtract looks like this:\n\n  for-each atom in a:\n      if atom in b:\n          swap(atom, <last atom in 'a'>)\n          destroy(atom)\n  quicksort(a)\n\nComplexity:\n\n  Na * log2(Nb)  +  (Na - Nb) * log2(Na - Nb)\n    Search          Comparisons for quicksort\n\nIt's not optimal, especially because Nb << Na in a vast majority of\ncases.\n\nReversing the search phase to look up atoms from 'b' in 'a', and\nclosing gaps from deleted elements in 'a' by plain memory copy to\navoid quicksort.\n\nResulted complexity:\n\n  Nb * log2(Na)  +    (Na - Nb)\n    Search          Memory copies\n\nSubtraction is heavily used while executing database transactions.\nFor example, to remove one port from a logical switch in OVN.\nComplexity of such operation if original logical switch had 100 ports\ngoes down from\n\n 100 * log2(1)   = 100 comparisons for search and\n  99 * log2(99)  = 656 comparisons for quicksort\n                   ------------------------------\n                   756 comparisons in total\nto only\n\n   1 * log2(100) = 7 comparisons for search\n   + memory copy of 99 * sizeof (union ovsdb_atom) bytes.\n\nWe could use memmove to close the gaps after removing atoms, but\nit will lead to 2 memory copies inside the call, while we can perform\nonly one to the temporary 'result' and swap pointers.\n\nPerformance in cases, where sizes of 'a' and 'b' are comparable,\nshould not change.  Cases with Nb >> Na should not happen in practice.\n\nAll in all, this change allows ovsdb-server to perform several times\nmore transactions, that removes elements from sets, per second.\n\nSigned-off-by: Ilya Maximets <i.maximets@ovn.org>\n---\n lib/ovsdb-data.c | 52 +++++++++++++++++++++++++++++++++++++-----------\n 1 file changed, 40 insertions(+), 12 deletions(-)",
    "diff": "diff --git a/lib/ovsdb-data.c b/lib/ovsdb-data.c\nindex 11bf95fed..b6129d6ba 100644\n--- a/lib/ovsdb-data.c\n+++ b/lib/ovsdb-data.c\n@@ -2019,26 +2019,54 @@ ovsdb_datum_subtract(struct ovsdb_datum *a, const struct ovsdb_type *a_type,\n                      const struct ovsdb_datum *b,\n                      const struct ovsdb_type *b_type)\n {\n-    bool changed = false;\n-    size_t i;\n+    size_t i, ai, bi, n_idx;\n+    size_t *idx;\n \n     ovs_assert(a_type->key.type == b_type->key.type);\n     ovs_assert(a_type->value.type == b_type->value.type\n                || b_type->value.type == OVSDB_TYPE_VOID);\n \n-    /* XXX The big-O of this could easily be improved. */\n-    for (i = 0; i < a->n; ) {\n-        unsigned int idx = ovsdb_datum_find(a, i, b, b_type);\n-        if (idx != UINT_MAX) {\n-            changed = true;\n-            ovsdb_datum_remove_unsafe(a, i, a_type);\n-        } else {\n-            i++;\n+    idx = xmalloc(b->n * sizeof *idx);\n+    n_idx = 0;\n+    for (bi = 0; bi < b->n; bi++) {\n+        ai = ovsdb_datum_find(b, bi, a, b_type);\n+        if (ai == UINT_MAX || (n_idx && ai <= idx[n_idx - 1])) {\n+            /* No such atom in 'a' or it's already marked for removal. */\n+            continue;\n         }\n+        idx[n_idx++] = ai;\n     }\n-    if (changed) {\n-        ovsdb_datum_sort_assert(a, a_type->key.type);\n+    if (!n_idx) {\n+        free(idx);\n+        return;\n     }\n+\n+    struct ovsdb_datum result;\n+\n+    ovsdb_datum_init_empty(&result);\n+    ovsdb_datum_reallocate(&result, a_type, a->n - n_idx);\n+\n+    for (i = 0; i < n_idx; i++) {\n+        ai = idx[i];\n+\n+        /* Destroying atom. */\n+        ovsdb_atom_destroy(&a->keys[ai], a_type->key.type);\n+        if (a_type->value.type != OVSDB_TYPE_VOID) {\n+            ovsdb_atom_destroy(&a->values[ai], a_type->value.type);\n+        }\n+\n+        /* Copy non-removed atoms from 'a' to result. */\n+        unsigned int start_idx = (i > 0) ? idx[i - 1] + 1 : 0;\n+        ovsdb_datum_push_unsafe(&result, a, start_idx, ai - start_idx, a_type);\n+    }\n+    /* Copying remaining atoms. */\n+    ovsdb_datum_push_unsafe(&result, a, idx[n_idx - 1] + 1,\n+                            a->n - (idx[n_idx - 1] + 1), a_type);\n+    a->n = 0;\n+\n+    ovsdb_datum_swap(&result, a);\n+    ovsdb_datum_destroy(&result, a_type);\n+    free(idx);\n }\n \f\n struct ovsdb_symbol_table *\n",
    "prefixes": [
        "ovs-dev",
        "v2",
        "2/2"
    ]
}